Двохетапна транспортна задача.
На практиці досить часто зустрічається випадок, коли певна частина продукції спочатку перевозиться до посередницьких фірм (сховищ), а потім споживачам. У такому разі розв’язання задачі поділяють на два етапи: спочатку знаходять оптимальний план перевезень від постачальників до посередників, а потім — від посередників до споживачів. Така задача має назву двохетапної транспортної задачі. Нехай в m пунктах постачання Неможливо розібрати вираз (невідома помилка): A_1, A_2, …, A_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 , то математична модель задачі матиме вигляд:
Неможливо розібрати вираз (невідома помилка): min Z = \sum_{i=1}^m \sum_{k=1}^l c_ik x_ik + \sum_{k=1}^l \sum_{j=1}^n c_kj x_kj
за умов:
Неможливо розібрати вираз (невідома помилка): \sum_{k=1}^l x_ik = a
;
Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n c_jx_j \to \max
;
Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n c_jx_j \to \max
;
Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n c_jx_j \to \max
;.
Неможливо розібрати вираз (невідома помилка): x_ik >=0 , Неможливо розібрати вираз (невідома помилка): x_kj >=0 , Неможливо розібрати вираз (невідома помилка): i=1..m
- Неможливо розібрати вираз (невідома помилка): i=j..n
- Неможливо розібрати вираз (невідома помилка): k=1..l
.
Зазначимо, що коли загальний обсяг вантажу Неможливо розібрати вираз (невідома помилка): \sum_{i=1}^m a_i
дорівнює місткості всіх складів і баз Неможливо розібрати вираз (невідома помилка): \sum_{k=1}^l d_k
, а також сумарній потребі всіх споживачів Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n b_j
, тобто Неможливо розібрати вираз (невідома помилка): \sum_{i=1}^m a_i = \sum_{k=1}^l d_k = \sum_{i=1}^m a_i
, то така двохетапна транспортна задача може бути розв’язана як дві одноетапні. В іншому разі окремі оптимальні плани двох задач не збігатимуться з оптимальним планом загальної задачі.
Метод розв’язування двохетапної транспортної задачі, розроблений Орденом-Маршем, полягає у врахуванні місткостей посередників двічі — як постачальників і як споживачів. Умови задачі подаються у вигляді таблиці, в рядках якої записують дані про постачальників, а також про посередницькі фірми, а в стовпцях — знову дані про посередників та споживачів. У клітинах, які розміщені на перетині рядків-постачальників та стовпців-споживачів, фіксують реальні затрати на перевезення одиниці продукції. В діагональних клітинах на перетині рядків і стовпців, які відповідають посередницьким фірмам, ставлять ну-льові величини затрат. Решту клітин таблиці блокують, тобто ва-ртості перевезень прирівнюють до деякого досить великого числа М. У процесі розв’язування задачі в цих клітинах не будуть передбачатися перевезення продукції, що відповідає умовам дво-хетапної транспортної задачі.
