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

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

10.6.5. Метод потенціалів оптимізації опорного плану.

Якщо план транспортної задачі оптимальний, то йому відповідає система із чисел та , що задовольняють умовам:

1) , для ;

2) , для [10.8]

Числа та називаються потенціалами відповідно постачальників і споживачів.

Якщо хоч би одна не занята клітинка не задовольняє [10.8], то опорний план не оптимальний і його можна покращити, введенням в цю клітинку перевозку.

За первісний приймемо план одержаний методом найменшої вартості:

Так як маємо лише 7 заповнених комірок таблиці (), то план являється виродженим – рівнянь на одне менше, ніж невідомих. Тому придамо перевозці нульове значення.

Приймемо і по заштрихованим коміркам проведемо розрахунок значень потенціалів:

Після перевірки умови у вільних комірках опинилися з порушенням умови клітинки Тому включимо в базис комірку , в якій таке порушення найбільше, тобто в цю клітинку потрібно зробити занятою перевозкою. Для цього будуємо цикл (позначено пунктирною лінією). Із комірок, де стоять знаки «мінус» вибираємо найменше .