Побудова опорного плану транспортної задачі методом подвійної переваги

Метод подвійної переваги при знаходженні опорного плану транспортної задачі зазвичай використовується в тому випадку коли таблиця вартостей ТЗ достатньо велика і перебір всіх її елементів є досить трудоємкою процедурою. Також слід відмітити, що у багатьох випадках рішення транспортної задачі методом потенціалів з використання методу подвійної переваги виявляється більш простим, зручним і швидким, в порівнянні з іншими методами. Далі, розглянемо алгоритм даного методу більш детально, після чого спробуємо застосувати його для конкретного прикладу:

  1. На першому кроці, у кожному стовпці транспортної таблиці відзначають знаком “V” комірку з найменшою вартістю.
  2. Потім те ж проробляють в кожному рядку. В результаті виконання другого кроку, деякі комірки транспортнї таблиці будуть містити відмітку “VV”.
  3. На останньму кроці, у комірки з подвійними відмітками (подвійна перевага) поміщають максимально можливі обсяги перевезень, щоразу виключаючи з розгляду відповідні стовпці або рядки. Потім розподіляють перевезення по комірках з одиничною відміткою. Решта перевезення розподіляють згідно  алгоритму методу мінімального елемента.

Побудова опорного плану транспортної задачі методом подвійної переваги – приклад:

На три бази поступив товар в кількості 160, 140 і 170 одиниць відповідно. Цей груз потрібно перевезти в чотири пункти призначення , потреби яких становлять 120, 50, 190, 110. Тарифи на перевезення одиниці продукції записані в наступній таблиці:

Таблиця тарифів на перевезення

Для побудови опорного плану транспортної задачі методом подвійної переваги, спочатку, відзначаємо знаком V комірку з найменшою вартістю в кожному стовпці, потім – в кожному рядку. В результаті транспортна таблиця даної задачі набуде наступного вигляду:

комірку з Знаходження комірки знайменшою вартістю в кожному стовпці та рядку

Після цього, на першомк кроці, заповнюємо комірки (мають відмітку “VV”). Зауважимо, що запонювати комірку з відміткою “V” не будемо, тому що рядок в якому вона знаходиться вже виключно з розгляду. Далі, комірки що  залишились, заповнюємо за мінімальною вартістю, тобто у наступній послідовності: .

Побудова опорного плану транспортоної задачі методом подвійної переаги

Обчисливши загальну суму витрат на перевезення вантажу за цим планом та порівнюючи її з результатаи, отриманим за допомогою інших методів (метод мінімального елемента1530; метод північно-західного кута1740; метод Фогеля1330) бачимо, що отримана сума не являється мінімальною, що трапляється доволі рідко. Таким чином, для даної задачі, найменшу вартість має опорний план, отриманий за методом Фогеля, а отже, він найбільш близький до оптимального.

Блок-схема алгоритму побудови опорного плану транспортної задачі методом подвійної переваги

Метод подвійної переваги алгоритм

Залишити коментар

Your email address will not be published. Required fields are marked *

*