Метод північно-західного кута

Не звертаючи уваги на вартість перевозок, починають задовольнять потреби за рахунок . Клітинку заповнюють величиною . Остачу переносять в клітинку , якщо або в , якщо . Процес продовжуємо допоки всі рядки і стовпці не будуть заповненими. Покажемо метод на прикладі такої задачі:

В таблиці заповнено 8 клітинок. Значить план не вироджений.

Так як в процесі вартості перевозок не враховувались, то зрозуміло, що план далекий від оптимального:

Метод найменшої вартості

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

Із частини таблиці, що залишилась знову вибирають найменшу вартість і так продовжують до повного заповнення таблиці:

.

Як бачимо, план ближчий до оптимального.

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

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

.

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

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

1) , для ;

2) , для [10.8]

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

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

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

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

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

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

В комірку внесемо нульову перевозку. Подальші перетворення таблиць подаються без коментарів.

.

.

Одержали оптимальний базис .

Одержання розв’язку транспортної задачі в ЕТ Excel здійснюється по тій же технології, що і для симплекс-методу.

ПРИКЛАД