Постановка и основные свойства транспортной задачи (стр. 6 из 7)
В результате построения Х1 в базис вводим 
. План Х1 является вырожденным (в цепочке есть два минимальных элемента). Поэтому один из этих элементов, например 
, в плане Х1 заменяем на .
Вторая итерация. Первый этап
 |  | | | |||||||
 |  | 0 | 2 | 2 | 0 | 0 | -1 | 2 | ||
 С1 = | 2 | 0 | | -3 |  +3 | С2 = | 5 | 3 | 0 | 0 |
| 0 | 1 | 2 | 0 | 0 | 1 | -1 | 0 | |||
| -3 |
Второй этап.
 |  |  |  |  | ||||||
 | 6 | 0 | 0 | | 6 | 0 | 0 | |||
| X1 = |  | 0 | 0 | 8* | * | X2 = | 0 | 0 | 2 | 6 |
| 4 | 0 | 0+ | 6* | 3 =min {8, 6}= 6 | 4 | 0 | 6 | 0 | ||
 |
Третья итерация. Первый этап.
 |  | | |  | ||||||
 | | | -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)
Величина 
называется суммарной невязкой для матрицы 
. Она характеризует близость к искомому плану Т-задачи. Итерации проводятся до тех пор, пока величина не станет равна нулю.
Описание алгоритма Венгерского метода
Предварительный этап. В каждом из столбцов матрицы транспортных издержек 
отыскивают минимальный элемент, который вычитают из всех элементов этого столбца. Получают матрицу С'. Далее в каждой строке матрицы С' выбирают минимальный элемент и вычитают его из всех элементов рассматриваемой строки. Приходят к матрице С0 (С0 ~ C), все элементы которой неотрицательны, причем в каждой строке и столбце С0 имеем по крайней мере, один нуль. Строят матрицу Х0 так, чтобы ее ненулевые элементы были расположены в позициях нулей матрицы С0.
Пусть 
- номер строки, в которой расположен k-й нуль j-го столбца матрицы С0. Тогда элементы первого столбца матрицы Х0 определяют по рекуррентной формуле
(3.3.4)
Т.е. все элементы первого столбца 
, которым соответствуют ненулевые элементы в матрицы С0, заполняют нулями, а остальные элементы этого столбца заполняют по методу северо-западного угла.
Допустим, что столбцы Х0 от первого до (j-1) – го включительно уже заполнены. Тогда элементы j-го столбца определяют в соответствии с формулой
(3.3.5)
Если 
, то Х0 – оптимальный план Т-задачи. Если 
, то переходим к первой итерации.
(k+1) – я итерация. Каждая итерация состоит из двух или трех этапов. Итерация начинается первым этапом, а заканчивается вторым. Между первым и вторым этапами в общем случае несколько раз могут быть проведены третий и первый этапы.
Допустим, что уже проведено k итераций, причем 
. В этом случае необходимо, используя матрицы Сk и Хk, провести следующую (k+1) – ю итерацию. Перед началом итерации выделяют знаком '+' те столбцы матрицы Сk, для которых невязки по столбцам равны
.
Первый этап. Если все ненулевые элементы матрицы Сk окажутся в выделенных столбцах, то переходят к третьему этапу. В противном случае пусть некоторый невыделенный нуль находится в 
-й строке и в 
-м столбце. Тогда вычисляют значения невязки -й строки: