ify"> n і назвемо її матрицею тарифів.
Для наочності умови ТЗ можна уявити таблицею (табл. 2.1), яку будемо називати розподільної. Розподільну таблицю називають іноді табличній або матричної моделлю ТЗ. br/>
Таблиця 2.1
В
Економіко-математична модель ТЗ повинна відображати всі умови і мета завдання в математичній формі. Так, змінні повинні задовольняти обмеженням по запасах, потреб і умов невід'ємності.
У математичній формі ці умови можна записати так.
цілочисельний відсікання транспортний Гомори
(2.1)
(2.2)
Мета ТЗ - мінімізувати загальні витрати на реалізацію плану перевезень, які можна представити функцією
(2.3)
Отже, математично ТЗ ставиться так. Дано система обмежень (2.1) за умови (2.2) і лінійна функція (2.3). Потрібен серед безлічі рішень системи (2.1) знайти таке невід'ємне рішення, при якому лінійна функція (2.3) приймає мінімальне значення (мінімізується). p align="justify"> Будемо називати план перевезень Х = [хij] т Г— п допустимим, якщо він задовольняє обмеженням (2.1) та (2.2).
Допустимий план перевезень, який доставляє мінімум цільової функції (2.3), називається оптимальним.
. Завдання про призначення (проблема вибору, завдання про наречених і наречених)
Вона є історично першим завданням дискретного програмування (опублікована угорським математиком Е. Егерварі в 1932 р. як завдання транспортного типу).
Мається n виконавців, які можуть виконувати n різних робіт. p align="justify"> Відома корисність cij пов'язана з виконанням i-м виконавцем j-й роботи.
В
Необхідно так призначити виконавців на роботи, щоб домогтися максимальної корисності за умови, що кожен виконавець може бути призначений тільки на одну роботу і за кожною роботою повинен бути закріплений тільки один виконавець.
Для складання математичної моделі задачі позначимо через xij факт призначення або непризначення i-го виконавця на j-ту роботу. Так як кількість виконавців дорівнює кількості робіт і кожен з них може бути призначений тільки на одну роботу, то xij повинні приймати тільки два значення: 1 або 0. Такі змінні називають булевими. Отже,
В
Приходимо до задачі: знайти план призначення xij, який максимізує сумарну корисність призначень:
В
при наступних обмеженнях. Кожен виконавець призначається тільки на одну роботу:
