Якщо таблиця велика, то реалізація попереднього методу ускладнюється. В цьому випадку використовують метод подвійної переваги. В кожному стовпці ставлять мітку в клітинку з найменшою вартістю. Те ж саме роблять і по рядкам. В клітинки з двома мітками розміщують по можливості більші перевозки, кожного разу виключаючи із розгляду відповідні рядки і стовпці. Потім розподіляють перевозки по клітинкам з одною міткою. В решту клітинок розміщують перевозки по найменшій вартості.
.
10.6.5. Метод потенціалів оптимізації опорного плану.
Якщо план транспортної задачі оптимальний, то йому відповідає система із чисел та , що задовольняють умовам:
1) , для ;
2) , для [10.8]
Числа та називаються потенціалами відповідно постачальників і споживачів.
Якщо хоч би одна не занята клітинка не задовольняє [10.8], то опорний план не оптимальний і його можна покращити, введенням в цю клітинку перевозку.
За первісний приймемо план одержаний методом найменшої вартості:
Так як маємо лише 7 заповнених комірок таблиці (), то план являється виродженим – рівнянь на одне менше, ніж невідомих. Тому придамо перевозці нульове значення.
|
|
Приймемо і по заштрихованим коміркам проведемо розрахунок значень потенціалів:
Після перевірки умови у вільних комірках опинилися з порушенням умови клітинки Тому включимо в базис комірку , в якій таке порушення найбільше, тобто в цю клітинку потрібно зробити занятою перевозкою. Для цього будуємо цикл (позначено пунктирною лінією). Із комірок, де стоять знаки «мінус» вибираємо найменше .
В комірку внесемо нульову перевозку. Подальші перетворення таблиць подаються без коментарів.
.
.
Одержали оптимальний базис .
Одержання розв’язку транспортної задачі в ЕТ Excel здійснюється по тій же технології, що і для симплекс-методу.
ПРИКЛАД