Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

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б).