На головну

Задачі про призначення і про комівояжера як окремі випадки цілочисельних ЗЛП.

  1. Cегментація ринку. Основні завдання. Критерії сегментації на В2С ринку.
  2. I-d діаграма вологого повітря, її структура. Характерні випадки зміни стану повітря і їх зображення на I-d діаграмі.
  3. I. ЗАВДАННЯ МЕДИЧНИХ ПРАЦІВНИКІВ В ЗАБЕЗПЕЧЕННІ МАРША
  4. I.1.2. Цілі, завдання та види інженерних вишукувань.
  5. III. Цілі, завдання та результати розвитку фінансового ринку на період до 2020 року
  6. III.3.7. ПРЕДМЕТ І ЗАВДАННЯ Логопсихологія
  7. Автоматизація офісу. Основні завдання та використовуються інформаційні системи управління.

При вирішенні багатьох завдань нецелочисленное рішення не має сенсу. Розділ математичного програмування, в якому на екстремальні завдання накладається умова дискретності змінних при кінцевій області допустимих рішень, називається дискретним програмуванням. При наявності умови целочисленности мається на увазі підрозділ дискретного програмування - целочисленное програмування.

В економіці багато завдань з фізичної неделимостью об'єктів, предметів і чинників розрахунку. Наприклад, не можна побудувати 1,7 будівлі, 6,1 заводу, 1,07 автомобіля, зробити 1,7 виміру, здійснити 3,4 подорожі, купити 4,5 туристичних путівок.

Завдання про призначення: має n виконавців, які можуть виконувати n різних робіт. відома корисність  , Пов'язана з виконанням i-м виконавцем j-й роботи ,  . Необхідно призначити виконавців на роботи так, щоб домогтися максимальної корисності, за умови, що кожен виконавець може бути призначений тільки на одну роботу і за кожною роботою должнен бути закріплений лише один виконавець.

Математична модель задачі матиме вигляд:

 (42.1)

Кожен виконавець призначається тільки на одну роботу:

 (42.2)

На кожну роботу призначається тільки один виконавець:

 (42.3)

Умови невід'ємності і целочисленности:

, , ,  . (42.4)

Завдання комівояжера: комівояжер повинен відвідати один, і тільки один, раз кожен з n міст і повернутися в початковий пункт. Його маршрут повинен мінімізувати сумарну довжину пройденого шляху.

Математична модель задачі:

 (42.5)

 (42.6)

 (42.7)

Умови невід'ємності і целочисленности

, , ,  . (42.8)

Додається умова проходження маршруту через все міста, тобто так зване умова циклічності. Інакше, маршрут повинен являти собою замкнуту ламану, без перетинів в містах-точках.

визначення: екстремальна задача лінійного програмування, в якій на рішення накладається цілочисельність компонент, є завданням цілочисельного програмування і називається целочисленной завданням.

визначення: екстремальна задача лінійного програмування, в якій на рішення накладається цілочисельність кількох компонент, є завданням цілочисельного програмування і називається частково целочисленной завданням.

 



Цілочисельні ЗЛП, графічний метод рішення в разі двох змінних. | Метод гілок і меж.

Моделі законів розподілу ймовірностей, що найбільш вживаються в соціально-економічних додатках. | Ланцюги Маркова та їх використання в моделюванні соціально-економічних процесів. | Види ЗЛП і способи переходу від одного виду до іншого. | Основні теореми лінійного програмування. | Симплекс-метод. | Порядок роботи з симплекс таблицею | Метод штучного базису. | Теореми подвійності. | Критерії оптимальності. | Теорема про існування оптимального рішення. |

© um.co.ua - учбові матеріали та реферати