Постановка задачі.

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

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

Найпростіше формулювання транспортної задачі за критерієм вартості звучить у такий спосіб.

У m пунктах відправлення знаходяться, відповідно, а ₁, а ₂,..., а _m одиниць однорідного вантажу (ресурси), що повинний бути доставлений у n заданих пунктів призначення (споживання), відповідно, у кількостях b ₁, b ₂,…, b_n одиниць (потреби). Нехай вартість перевезення одиниці вантажу з i -го пункту відправлення в j-й пункт призначення дорівнює G _ij, а відповідна кількість одиниць перевезеного вантажу дорівнює X_ij (i =l,... m; j =l,... n).

Потрібно скласти такий план перевезень, при якому загальна вартість виявиться мінімальною, тобто потрібно вказати, скільки одиниць вантажу повинне бути відправлене з довільного i -го пункту відправлення в будь-який j-й пункт призначення — так, щоб максимально задовольнити потреби і щоб сумарні витрати на перевезення були мінімальними.

Матриці, утворені значеннями змінних х_ij і коефіцієнтами G_ij, називаються, відповідно, планом перевезень і матрицею транспортних витрат.

Розрізняють закриті і відкриті математичні моделі транспортної задачі. У моделях першого типу зберігається баланс між сумарними ресурсами і сумарними потребами:

(1)

а в моделях другого типу порушений баланс між сумарними ресурсами і потребами:

(2)

(3)

Закрита модель для транспортної задачі є, у своєму роді, канонічною, і всі методи рішення розроблені саме для неї. Відкриту ж модель спочатку зводять до закритої і лише після цього приступають до рішення транспортної задачі.

З курсу лінійного програмування відомо, що для закритої моделі справедливі наступні твердження:

рівність (1) є необхідною і достатньою умовою спільності транспортної задачі;

будь-яка транспортна задача має оптимальний план;

якщо величини а_i і b_j є цілими числами, то і всі значення змінних x_ij в оптимальному плані будуть цілими величинами.