Відкрита транспортна задача
Будемо вважати, що ми вже знаємо, що таке транспортна задача, як вирішити закриту транспортну задачу, як скласти початковий опорний план і як боротися з виродженням плану. Якщо що - то з цього Вам незнайоме, то при бажанні можна вивчити тут:
Транспортна задача називається відкритою, якщо не дотримується баланс між обсягом попиту і обсягом пропозиції. Наприклад, якщо запаси на всіх складах менше або більше потреб всіх магазинів - споживачів, то маємо справу з відкритою транспортної моделлю.
Для того, щоб застосувати до задачі метод потенціалів, необхідно привести відкриту транспортну задачу до закритої моделі. Тобто необхідно виконати перетворення, при яких. "Те, що є, стане рівним, тому, що треба".
Все дуже просто. Якщо не вистачає товару, щоб задовольнити потреби магазинів, потрібно додати мнимого (фіктивного) постачальника. Якщо пропозиція перевищує над попитом, додамо мнимого (фіктивного) споживача.
У відкритій транспортній задачі це реалізується додаванням рядка або стовпця, в залежності від того, чого не вистачає. Так як в реальності фіктивний постачальник (споживач) не існує, то вартість доставки до нього від будь-якого пункту дорівнює нулю.
Щоб привести відкриту транспортну задачу до закритого (замкнутому) виду, додаємо стовпець (рядок) з нульовими вартостями.
Якщо перевищують запаси - додаємо фіктивного споживача (стовпець)
Якщо перевищує попит - додаємо фіктивного постачальника (рядок)
Розглянемо докладно на прикладі.
Відкрита транспортна задача - приклад 1:
Вирішити транспортну задачу з вихідними даними:
Загальні потреби (попит) = 40 + 180 + 80 + 60 = 360
Загальні запаси (пропозиція) = 120 + 100 = 220
Бачимо, що попит перевищує над пропозицією.
Отже додаємо фіктивного постачальника А3 з обсяг запасів 360 - 220 = 140.
Отримали закриту транспортну задачу: попит = пропозиції.
Дивитися повне рішення транспортної задачі / Клацнути мишкою
Перевіримо початковий план на оптимальність:
Детально про те, як були заповнені таблиці можна подивитися тут: Як вирішити транспортну задачу?
Серед оціночних значень правої таблиці є негативні, отже план не оптимальний.
Побудували замкнутий ланцюжок знаків "+" і "-".
Серед осередків, помічених "-" виберемо осередок з мінімальним значенням:
Це значення 80 перенесемо в порожню клітинку, позначену "+", далі, до значень в осередках з "+" додамо К, з значень в осередках з "-" віднімемо К.
Визначимо вартість перевезення на першому кроці:
S1 = 40 · 4 + 80 · 9 + 100 · 11 + 0 · 0 + 80 · 0 + 60 · 0 = 1980
Серед оціночних значень правої таблиці є негативні, отже план не оптимальний.
В осередках з "+" додамо дане значення, в осередках з "-" віднімемо.
Загальна вартість перевезення на даному етапі:
S2 = 40 · 4 + 80 · 9 + 20 · 11 + 80 · 3 + 80 · 0 + 60 · 0 = 1340 Бачимо, що вартість перевезення на поточному кроці менше ніж на попередньому. Серед оціночних значень правої таблиці є негативні, отже план не оптимальний. Загальна вартість перевезення на даному етапі: S3 = 40 · 4 + 80 · 9 + 80 · 3 + 20 · 4 + 100 · 0 + 40 · 0 = 1200 Бачимо, що вартість перевезення на поточному кроці менше ніж на попередньому. Серед оціночних значень немає негативних, отже рішення оптимально. S4 = 40 · 4 + 40 · 9 + 40 · 2 + 40 · 3 + 60 · 4 + 140 · 0 = 960 Завдання вирішена, отриманий оптимальний план перевезень. Вирішити відкриту транспортну задачу з вихідними даними: Загальні потреби (попит) = 40 + 40 + 20 = 100 Загальні запаси (пропозиція) = 20 + 30 + 40 + 20 = 110 Бачимо, що пропозиція перевищує над попитом. Отже додаємо фіктивного споживача В4 до потреб 110 - 100 = 10. Отримали закриту транспортну задачу: попит = пропозиції.Відкрита транспортна задача - приклад 2: