Вихідна тт

	B1	B2	B3	B4	ui	Запасиai
A1	4	7 30	2 70	5 +	0	100
A2	3 80	6	1 40	8	-1	120
A3	9	3 70 +	6	2  70	-4	140
vj	4	7	2	6
Заявки bj	80	100	110	70		360

Опорний план не є оптимальним, тому що для клітинки . Це означає, що ця клітинка, як кажуть, є потенційною і має бути завантажена.

Для цього шукаємо контур, що містить у решті кутів зайняті клітинки. Це контур: (див. табл.54). Оскільки ми завантажуємо , присвоюємо їй знак “+”, потім, пересуваючись по контуру, послідовно міняємо знаки. Мінімальне абсолютне значення від'ємного обсягу знаходиться в клітинціі дорівнюєx_п = 30 в.о. Пересуваємо цей обсяг по контуру з урахуванням знаків і отримуємо новий план перевезень (див. табл. 55), при цьому вартість його реалізації буде дорівнювати:

L₂ = 70×2 + 30×5 + 80×3 + 40×1 + 100×3 + 40×2 = 950 у.г.о.

Порахуємо для нового плану перевезень нові значення потенціалів і, для цього знову приймаємо, тоді;. Використовуючи вже отримані потенціали, визначаємо решту потенціалів:;;

.

Перевіряємо побудований план на оптимальність, використовуючи отримані потенціали, а саме:

; ;;

; ;.

Таблиця 55

Тт після розподілу вантажу у клітинку а1в4

	B1	B2	B3	B4	ui	Запасиai
A1	4	7	2 70	5 30	0	100
A2	3 80	6	1 40	8	-1	120
A3	9	3 100	6	2 40	-3	140
vj	4	6	2	5
Заявки bj	80	100	110	70		360

План оптимальний, тому що для всіх незайнятих кліток виконується умова . (У додатку 6 наведений розрахунок цього ж самого прикладу у матричному процесорі Excel).

5. Угорський метод розв’язання транспортної задачі про призначення

Угорський метод є одним з найцікавіших і найпоширеніших методів рішення транспортних завдань. Основна ідея цього методу була вперше висловлена угорським математиком Е. Егерварі (звідси й назва методу) задовго до виникнення теорії лінійного програмування.

Розглянемо спочатку основні ідеї угорського методу на прикладі рішення завдання вибору (завдання про призначення), що є окремим випадком транспортної задачі, а потім узагальнимо цей метод для довільної транспортної задачі.