Транспортна задача

Деякий однорідний вантаж у пунктах А1, А2, …, Аm зосереджено в кількостях а1, а2, …, аm одиниць вантажу відповідно. Цей вантаж необхідно перевезти в пункти В1, В2, …,Вn в кількостях b1, b2, …, bn одиниць вантажу відповідно. Відомо, що вартість перевезення одиниць вантажу із пункту А_i в пункт Bj(тобто тариф) складає cij грошових одиниць ().

Будемо вважати, що

.

Треба скласти такий план перевезень, щоб сумарна вартість усіх перевезень була найменшою, весь вантаж із пунктів Аi, () було вивезено, а потреби всіх пунктів Вj () задоволені. Сформульована вище задача називається транспортною задачею (або Т-задачею). Якщо умова виконана, то транспортна задача називається закритою, а якщо не виконана – відкритою. Побудуємо математичну модель транспортної задачі. Нехай заплановано перевезти із пункту Аi в Вj хij (, ) одиниць вантажу. Довільний план перевезень будемо позначати через X і записувати у вигляді матриці

.

Позначимо через Z сумарну вартість усіх перевезень за планом X. Тоді

.

На невідомі xij накладемо такі обмеження

.

(тобто весь вантаж із пункту Аi () повинен бути вивезений) і

.

(тобто потреби всіх пунктів B_j () повинні бути задоволені).

Отже, математична модель транспортної задачі є такою:

,

,

.

Присутність у системі обмежень двох однакових рівнянь говорить про лінійну залежність. Якщо одне із цих рівнянь відкинути, то в загальному випадку система обмежень повинна включати m + n – 1 лінійно незалежних рівнянь, отже, невироджений опорний план транспортної задачі містить m + n –– 1 додатних компонент або перевезень. Таким чином, якщо яким-небудь методом отримаємо невироджений опорний план транспортної задачі, то в матриці значення його компонентів додатними є тільки m + n – 1, а решта рівні нулю. Можна показати, що довільна закрита транспортна задача має розв’язок. Задача є задачею лінійного програмування. Тому її можна було б розв’язати симплекс-методом, але швидше і простіше це можна зробити за методом потенціалів, кроки розв’язування за яким є по суті кроками симплекс-алгоритму. Закрита Т-задача розв’язується за таким планом.

1. Знаходимо перший опорний план цієї задачі.

2. Перевіряємо план на оптимальність. Якщо план оптимальний, то маємо розв’язок задачі, якщо ні, то переходимо до п. 3.

3. Знаходимо інший опорний план, сумарна вартість перевезень за яким буде не більшою, ніж за попереднім, і знову переходимо до п. 2.

Перший опорний план можна знайти різними способами. Розглянемо два.

Якщо умова транспортної задачі та її опорний план записані у вигляді таблиці 1, то комірки, в яких знаходяться відмінні від нуля перевезення, називають зайнятими, а решта – незайнятими. Зайняті комірки відповідають базисним змінним, та для невиродженого опорного плану їх кількість дорівнює m + n – 1. Опірність плану при запису умови транспортної задачі у вигляді (табл. 6.1) міститься в його ациклічності, тобто в таблиці неможливо побудувати замкнутий цикл, усі вершини його лежать у зайнятих комірках.

Таблиця 6.1