В
Третя ітерація. Перший етап. /Span> В В
В
В
В В
В В
-1
2
+1
0
0
0
3
З 2 =
5
3
В В
В
З 2 =
4
2
0
0
В
В
1
-1
0
+1
0
1
0
1
-1
-1
Так як в матриці З 3 немає негативних елементів, план Х 2 - оптимальний.
Угорська метод для транспортної задачі
Розглянута вище задача про призначення являє собою окремий випадок Т-задачі, коли. Тому угорський метод, який можна застосовувати для вирішення транспортної задачі спеціального виду, можна поширити на загальний випадок Т-завдання.
Нехай потрібно вирішити Т-задачу такого вигляду
мінімізувати
за умов
В
Алгоритм рішення Т-задачі, заснований на угорському методі, складається з попереднього етапу і кінцевого числа однотипних ітерацій.
У результаті попереднього етапу обчислюють матрицю, елементи якої задовольняють таким умовам:
, (1.3.1)
. (1.3.2)
Якщо в умовах (1.3.1), (1.3.2) строгі рівності, то матриця Х 0 є рішенням Т-завдання.
Матрицю, побудовану в результаті k-й ітерації, позначимо. Позначимо також
. (1.3.3)
Величина називається сумарної нев'язкої для матриці. Вона характеризує близькість до шуканого планом Т-завдання. Ітерації проводяться до тих пір, поки величина не стане дорівнює нулю. h4> Опис алгоритму Угорського методу
Попередній етап. У кожному зі стовпців матриці транспортних витрат відшукують мінімальний елемент, який віднімають з усіх елементів цього стовпця. Отримують матрицю З '. Далі в кожному рядку матриці З 'вибирають мінімальний елемент і віднімають його з усіх елементів розглянутої рядка. Приходять до матриці З 0 ( З 0 ~ C ), всі елементи якої невід'ємні, причому в кожному рядку і стовпці З 0 маємо принаймні, один нуль. Будують матрицю Х 0 так, щоб її ненульові елементи були розташовані в позиціях нулів матриці З 0 .
Нехай - номер рядка, в якій розташований k-й нуль j-го стовпця матриці З 0 . Тоді елементи першого стовпця матриці Х 0 визначають за рекуррентной формулою
(3.3.4)
Тобто всі елементи першого стовпчика, яким відповідають ненульові елементи в матриці З 0 , заповнюють нулями, а інші елементи цього шпальти заповнюють за методом північно-західного кута.
Припустимо, що стовпці Х 0 від першого до (j-1) - Го включно...
