Двохетапна транспортна задача.

На практиці досить часто зустрічається випадок, коли певна частина продукції спочатку перевозиться до посередницьких фірм (сховищ), а потім споживачам. У такому разі розв’язання задачі поділяють на два етапи: спочатку знаходять оптимальний план перевезень від постачальників до посередників, а потім — від посередників до споживачів. Така задача має назву двохетапної транспортної задачі. Нехай в m пунктах постачання Неможливо розібрати вираз (невідома помилка): А_1, А_2, …, А_m

є відповідно Неможливо розібрати вираз (невідома помилка): a_1, a_2, ... a_m
одиниць продукції, яку необхідно перевезти до l посередницьких фірм  Неможливо розібрати вираз (невідома помилка): D_1, D_2, …, D_l

, місткості сховищ яких становлять Неможливо розібрати вираз (невідома помилка): D_1, D_2, …, D_l

, а потім доставити її споживачам Неможливо розібрати вираз (невідома помилка): B_1, B_2, …, B_m
, потреби яких становлять Неможливо розібрати вираз (невідома помилка): b_1, b_2, …, b_n
. Відомі також витрати на перевезення одиниці продукції від кожного постачальника до посередницьких фірм —  Неможливо розібрати вираз (невідома помилка): c_ik
та від посередників до споживачів — Неможливо розібрати вираз (невідома помилка): c_kj
. Потрібно визначити оптимальну схему перевезень продукції з мінімальни-ми сумарними витратами. Якщо обсяг продукції, що перевозить-ся від i-го постачальника до k-ої фірми, позначити через Неможливо розібрати вираз (невідома помилка): x_ik
, а об-сяг вантажу, що перевозиться від k-ої фірми j-му споживачеві — через Неможливо розібрати вираз (невідома помилка): x_kj
, то математична модель задачі матиме вигляд:  <\ br>

за умов: <\ br> Неможливо розібрати вираз (невідома помилка): \sum_{k=1}^l x_ik = a

; <\ br>

Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n c_jx_j \to \max

; <\ br>

Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n c_jx_j \to \max

; <\ br>

Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n c_jx_j \to \max

;.  <\ br>

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

Метод розв’язування двохетапної транспортної задачі, ро-зроб¬лений Орденом-Маршем, полягає у врахуванні місткос-тей посередників двічі — як постачальників і як споживачів. Умови задачі подаються у вигляді таблиці, в рядках якої запи-сують дані про постачальників, а також про посередницькі фір-ми, а в стовпцях — знову дані про посередників та споживачів. У клітинах, які розміщені на перетині рядків-постачальників та стовпців-споживачів, фіксують реальні затрати на перевезення одиниці продукції. В діагональних клітинах на перетині рядків і стовпців, які відповідають посередницьким фірмам, ставлять ну-льові величини затрат. Решту клітин таблиці блокують, тобто ва-ртості перевезень прирівнюють до деякого досить великого чис-ла М. У процесі розв’язування задачі в цих клітинах не будуть передбачатися перевезення продукції, що відповідає умовам дво-хетапної транспортної задачі.