- Цветы и растения
- Аквариум и рыбы
- Для работы
- Для сайта
- Для обучения
- Почтовые индексы Украины
- Всяко-разно
- Электронные библиотеки
- Реестры Украины
- Старинные книги о пивоварении
- Словарь старославянских слов
- Все романы Пелевина
- 50 книг для детей
- Стругацкие, сочинения в 33 томах
- Записи Леонардо да Винчи
- Биология поведения человека
Главная ![]() ![]() ![]() |
Математичне програмування - Наконечний С.І.
5.7. Двохетапна транспортна задача
У класичній постановці транспортної задачі допускається, що вантаж перевозиться безпосередньо від постачальників до споживачів. Але на практиці досить часто зустрічається випадок, коли певна частина продукції спочатку перевозиться до посередницьких фірм (сховищ), а потім споживачам. У такому разі розв’язання задачі поділяють на два етапи: спочатку знаходять оптимальний план перевезень від постачальників до посередників, а потім — від посередників до споживачів. Така задача має назву двохетапної транспортної задачі.
Нехай в m пунктах постачання А1, А2, …, Аm є відповідно одиниць продукції, яку необхідно перевезти до l посередницьких фірм
, місткості сховищ яких становлять
, а потім доставити її споживачам
, потреби яких становлять
. Відомі також витрати на перевезення одиниці продукції від кожного постачальника до посередницьких фірм —
та від посередників до споживачів —
. Потрібно визначити оптимальну схему перевезень продукції з мінімальними сумарними витратами. Якщо обсяг продукції, що перевозиться від i-го постачальника до k-ої фірми, позначити через
, а обсяг вантажу, що перевозиться від k-ої фірми j-му споживачеві — через
, то математична модель задачі матиме вигляд:
за умов:
;
;
;
;
.
Зазначимо, що коли загальний обсяг вантажу дорівнює місткості всіх складів і баз
, а також сумарній потребі всіх споживачів
, тобто
=
=
, то така двохетапна транспортна задача може бути розв’язана як дві одноетапні. В іншому разі окремі оптимальні плани двох задач не збігатимуться з оптимальним планом загальної задачі.
Метод розв’язування двохетапної транспортної задачі, розроблений Орденом-Маршем, полягає у врахуванні місткостей посередників двічі — як постачальників і як споживачів. Умови задачі подаються у вигляді таблиці, в рядках якої записують дані про постачальників, а також про посередницькі фірми, а в стовпцях — знову дані про посередників та споживачів. У клітинах, які розміщені на перетині рядків-постачальників та стовпців-споживачів, фіксують реальні затрати на перевезення одиниці продукції. В діагональних клітинах на перетині рядків і стовпців, які відповідають посередницьким фірмам, ставлять нульові величини затрат. Решту клітин таблиці блокують, тобто вартості перевезень прирівнюють до деякого досить великого числа М. У процесі розв’язування задачі в цих клітинах не будуть передбачатися перевезення продукції, що відповідає умовам двохетапної транспортної задачі.
Виробниче об’єднання складається з трьох філіалів: А1, А2, А3, які виготовляють однорідну продукцію в обсягах відповідно 1000, 1500 та 1200 одиниць на місяць. Ця продукція відправляється на два склади D1 і D2 місткістю відповідно 2500 та 1200 од., а потім — до п’яти споживачів B1, B2, …, B5, попит яких становить відповідно 900, 700, 1000, 500 і 600 од. Вартості перевезень одиниці продукції (в умовних одиницях) від виробників на склади, а потім — зі складів до споживачів наведені в табл. 5.23 і табл. 5.24.
Таблиця 5.23
Виробник |
Вартість перевезення 1000 т бензину від виробника на склад, ум. од. |
|
D1 |
D2 |
|
А1 |
2 |
8 |
А2 |
3 |
5 |
А3 |
1 |
4 |
Таблиця 5.24
Склад |
Вартість перевезення 1000 т бензину до споживачів, ум. од. |
||||
В1 |
В2 |
В3 |
В4 |
В5 |
|
D1 |
1 |
3 |
8 |
5 |
4 |
D2 |
2 |
4 |
5 |
3 |
1 |
Крім того, за індивідуальними контрактами можливі також безпосередні поставки продукції з першого філіалу до другого споживача, а також з третього філіалу — до четвертого споживача. Вартість транспортування одиниці продукції та транзитним маршрутом А1B2 дорівнює 3 ум. од., а за маршрутом А3B4 — 4 ум. од. Перевезення продукції зі складу на склад недопустимі.
Сформулювати поставлену задачу як транспортну з проміжними пунктами (двохетапну) та визначити її оптимальний план.
Розв’язання. У поставленій задачі кожний склад можна подати як вихідний пункт відправлення продукції і як пункт призначення. Тому в транспортній таблиці вони гратимуть роль і постачальника продукції, і її споживача.
Перевезення продукції безпосередньо від філіалів до споживачів (крім випадків, визначених в умові задачі), а також зі складу на склад блокується введенням у відповідні клітини досить великих вартостей перевезення одиниці продукції — М.
Побудовану з урахуванням цього транспортну таблицю двохетапної задачі наведено нижче (табл. 5.25).
Таблиця 5.25
Зауважимо, що в клітинках D1D1 і D2D2 розміщується нульова вартість перевезення продукції. Це допускає неповне використання ємностей сховищ у зв’язку з можливим транзитним транспортуванням продукції.
Ця транспортна задача є збалансованою, бо:
од.,
а також од.,
тому немає потреби вводити в транспорту таблицю фіктивного постачальника або споживача.
Перший опорний план транспортної задачі побудовано методом мінімальної вартості. Розрахуємо загальну вартість перевезень, що відповідає цьому плану:
Z1 = 2 х 1000 + 3 х 300 + 5 х 1200 + 1 х 1200 + 1 х 900 + 3 х 700 +
+ 8 х 900+ 5 х 100 + 3 х 500 + 1 х 600 = 22 900 (ум. од.).
Цей опорний план задачі неоптимальний. Перехід від нього до другого плану виконуємо, заповнюючи порожню клітинку D1D1 згідно з побудованим циклом (табл. 5.26).
Таблиця 5.26
Визначимо вартість перевезень згідно з другим опорним планом:
Z2 = 2 х 300 + 3 х 700 + 3 х 300 + 5 х 1200 + 1 х 1200 +
+ 1 х 900 + 8 х 900 + 5 х 100 + 3 х 500 + 1 х 600 = 21 500 (ум. од.).
Таблиця, що відповідає третьому опорному плану задачі, має такий вигляд:
Таблиця 5.27
Aі, Dk |
Dk, Bj |
ui |
||||||
d1 = 2500 |
d2 = 1200 |
b1 = 900 |
b2 = 700 |
b3 = 1000 |
b4 = 500 |
b5 = 600 |
||
a1 = 1000 |
2 300 |
8 |
M |
3 700 |
M |
M |
M |
u1 = 0 |
a2 = 1500 |
3 300 |
5 1200 |
M |
M |
M |
M |
M |
u2 = 1 |
a3 = 1200 |
1 700 |
4 |
M |
M |
M |
4 500 |
M |
u3 = –1 |
d1 = 2500 |
0 1200 |
M |
1 900 |
3 |
8 400 |
5 |
4 |
u4 = 0 |
d2 = 1200 |
M |
0 |
2 |
4 |
5 600 |
3 |
1 600 |
u5 = –3 |
vj |
v1 = 2 |
v2 = 4 |
v3 = 1 |
v4 = 3 |
v5 = 8 |
v6 = 6 |
v7 = 4 |
|
В табл. 5.27 маємо оптимальний план транспортної задачі:
Zmin = 2 х 300 + 3 х 700 + 3 х 300 + 5 х 1200 + 1 х 700 + 4 х 500 + + 1 х 900 + 8 х 400 + 5 х 600 + 1 х 600 = 20 000 (ум. од.).
Для більшої наочності оптимальний план перевезень продукції двохетапної транспортної задачі подамо у вигляді схеми (риc. 5.1):
Рис. 5.1. Оптимальний план перевезень продукції
На схемі показано, що на перший склад надходить лише 300 + 300 + 700 = 1300 од. продукції, тобто його місткість використовується не повністю (D1D1 = 1200 од.). Це зумовлено прямими поставками продукції за маршрутами А1В2 у обсязі 700 од. і А3В4 — у обсязі 500 од.
Розглянута транспортна задача має ще один альтернативний оптимальний план, який відрізняється від першого лише перевезеннями продукції зі складів до третього та п’ятого споживачів.
Крім розглянутої у транспортних задачах із проміжними пунктами можуть зустрічатися і такі ситуації:
1. Незбалансованість транспортної задачі (). У цьому разі необхідно ввести або фіктивного постачальника, або фіктивного споживача, звівши у такий спосіб задачу до закритого типу.
2. Місткість проміжних пунктів не дорівнює загальному обсягу продукції постачальників: а) коли (у цьому разі потрібно або ввести фіктивний проміжний пункт, і обсяг продукції, що «перевозитиметься» до нього, має дорівнювати невивезеній частині продукції відповідного постачальника, або дозволити транзитні перевезення за обсягом не менш як
(од.)); б) коли
(у цьому разі немає потреби вводити фіктивного постачальника і, зрозуміло, що місткість проміжних пунктів повністю не використовуватиметься).
3. Місткість проміжних пунктів не відповідає загальній потребі споживачів: а) (у цьому разі потрібно або ввести фіктивний проміжний пункт, і обсяг продукції, що «перевозитиметься» від нього до споживача Вj, має означати незадоволений попит відповідного споживача, або дозволити пряме перевезення продукції від постачальників до споживачів за обсягом не менш як
(од.)); б)
(аналогічно п. 2б).
Created/Updated: 25.05.2018