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

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

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

Читати повністю