3.3. ВЕНГЕРСКИЙ МЕТОД
Венгерский метод является одним из интереснейших и наиболее распространенных методов решения транспортных задач.
Рассмотрим сначала основные идеи венгерского метода на примере решения задачи выбора (задачи о назначениях), которая является частным случаем Т-задачи, а затем обобщим этот метод для произвольной Т-задачи.
Венгерский метод для задачи о назначениях
Постановка задачи. Предположим, что имеется 
различных работ 
и механизмов 
, каждый из которых может выполнять любую работу, но с неодинаковой эффективностью. Производительность механизма 
при выполнении работы 
обозначим 
, и = 1,...,n; j = 1,...,n. Требуется так распределить механизмы по работам, чтобы суммарный эффект от их использования был максимален. Такая задача называется задачей выбора или задачей о назначениях.
Формально она записывается так. Необходимо выбрать такую последовательность элементов 
из матрицы
чтобы сумма 
была максимальна и при этом из каждой строки и столбца С был выбран только один элемент.
Введем следующие понятия.
Нулевые элементы 
матрицы С называются независимыми нулями, если для любого 
строка и столбец, на пересечении которых расположен элемент 
, не содержат другие такие элементы 
.
Две прямоугольные матрицы С и D называются эквивалентными (C ~ D), если 
для всех i,j . Задачи о назначениях, определяемые эквивалентными матрицами, являются эквивалентными (т.е. оптимальные решения одной из них будут оптимальными и для второй, и наоборот).
Описание алгоритма венгерского метода
Алгоритм состоит из предварительного этапа и не более чем (n-2) последовательно проводимых итераций. Каждая итерация связана с эквивалентными преобразованиями матрицы, полученной в результате проведения предыдущей итерации, и с выбором максимального числа независимых нулей. Окончательным результатом итерации является увеличение числа независимых нулей на единицу. Как только количество независимых нулей станет равным n, проблему выбора оказывается решенной, а оптимальный вариант назначений определяется позициями независимых нулей в последней матрице.
Предварительный этап. Разыскивают максимальный элемент в j - м столбце и все элементы этого столбца последовательно вычитают из максимального. Эту операцию проделывают над всеми столбцами матрицы С. В результате образуется матрица с неотрицательными элементами, в каждом столбце которой имеется, по крайней мере, один нуль.
Далее рассматривают i - ю строку полученной матрицы, разыскивают ее минимальный элемент ai и из каждого элемента этой строки вычитают минимальный. Эту процедуру повторяют со всеми строками. В результате получим матрицу С0 (С0 ~ C), в каждой строке и столбце которой имеется, по крайней мере, один нуль. Описанный процесс преобразования С в С0 называется приведением матрицы.
Находим произвольный нуль в первом столбце и отмечаем его звездочкой. Затем просматриваем второй столбец, и если в нем есть нуль, расположенный в строке, где нет нуля со звездочкой, то отмечаем его звездочкой. Аналогично просматриваем один за другим все столбцы матрицы С0 и отмечаем, если возможно, следующие нули знаком '*'. Очевидно, что нули матрицы С0, отмеченные звездочкой, являются независимыми. На этом предварительный этап заканчивается.
(k+1)-ая итерация. Допустим, что k-я итерация уже проведена и в результате получена матрица Сk. Если в ней имеется ровно n нулей со звездочкой, то процесс решения заканчивается. В противном случае переходим к (k+1) - й итерации.
Каждая итерация начинается первым и заканчивается вторым этапом. Между ними может несколько раз проводиться пара этапов: третий - первый. Перед началом итерации знаком '+' выделяют столбцы матрицы Сk, которые содержат нули со звездочками.
Первый этап. Просматривают невыделенные столбцы Сk. Если среди них не окажется нулевых элементов, то переходят к третьему этапу. Если же невыделенный нуль матрицы Сk обнаружен, то возможен один из двух случаев: 1) строка, содержащая невыделенный нуль, содержит также и нуль со звездочкой; 2) эта строка не содержит нуля со звездочкой.
Во втором случае переходим сразу ко второму этапу, отметив этот нуль штрихом.
В первом случае этот невыделенный нуль отмечают штрихом и выделяют строку, в которой он содержится (знаком '+' справа от строки). Просматривают эту строку, находят нуль со звездочкой и уничтожают знак '+' выделения столбца, в котором содержится данный нуль.
Далее просматривают этот столбец (который уже стал невыделенным) и отыскивают в нем невыделенный нуль (или нули), в котором он находится. Этот нуль отмечают штрихом и выделяют строку, содержащую такой нуль (или нули). Затем просматривают эту строку, отыскивая в ней нуль со звездочкой.
Этот процесс за конечное число шагов заканчивается одним из следующих исходов:
1) все нули матрицы Сk выделены, т.е. находятся в выделенных строках или столбцах. При этом переходят к третьему этапу;
2) имеется такой невыделенный нуль в строке, где нет нуля со звездочкой. Тогда переходят ко второму этапу, отметив этот нуль штрихом.
Второй этап. На этом этапе строят следующую цепочку из нулей матрицы Сk: исходный нуль со штрихом, нуль со звездочкой, расположенный в одном столбце с первым нулем со штрихом в одной строке с предшествующим нулем со звездочкой и т.д. Итак, цепочка образуется передвижением от 0' к 0* по столбцу, от 0* к 0' по строке и т.д.
Можно доказать, что описанный алгоритм построения цепочки однозначен и конечен, при этом цепочка всегда начинается и заканчивается нулем со штрихом.
Далее над элементами цепочки, стоящими на нечетных местах ( 0' ) -, ставим звездочки, уничтожая их над четными элементами ( 0* ). Затем уничтожаем все штрихи над элементами Сk и знаки выделения '+'. Количество независимых нулей будет увеличено на единицу. На этом (k+1) -я итерация закончена.
Третий этап. К этому этапу переходят после первого, если все нули матрицы Сk выделены. В таком случае среди невыделенных элементов Сk выбирают минимальный и обозначают его h (h>0). Далее вычитают h из всех элементов матрицы Сk, расположенных в невыделенных строках и прибавляют ко всем элементам, расположенным в выделенных столбцах. В результате получают новую матрицу С'k, эквивалентную Сk. Заметим, что при таком
преобразовании, все нули со звездочкой матрицы Сk остаются нулями и в С'k, кроме того, в ней появляются новые невыделенные нули. Поэтому переходят вновь к первому этапу. Завершив первый этап, в зависимости от его результата либо переходят ко второму этапу, либо вновь возвращаются к третьему этапу.
После конечного числа повторений очередной первый этап обязательно закончится переходом на второй этап. После его выполнения количество независимых нулей увеличится на единицу и (k+1) - я итерация будет закончена.
Пример 3.4. Решить задачу о назначениях с матрицей
При решении задачи используем следующие обозначения:
Знак выделения '+', подлежащий уничтожению, обводим кружком; цепочку, как и ранее, указываем стрелками.
Предварительный этап. Отыскиваем максимальный элемент первого столбца - 4. Вычитаем из него все элементы этого столбца. Аналогично для получения второго, третьего, четвертого и пятого столбцов новой матрицы вычитаем все элементы этих столбцов от п'яти, трех, двух и трех соответственно. Получим матрицу С'(C'~C). Так как в каждой строке С' есть нуль, то С' = С0 и процесс приведения матрицы заканчивается. Далее ищем и отмечаем знаком '*' независимые нули в С0, начиная с первой строки.
Первая итерация. Первый этап. Выделяем знаком '+' первый, второй, и четвертый столбцы матрицы С0, которые содержат 0*.
Просматриваем невыделенный третий столбец, находим в нем невыделенный нуль С23 = 0, отмечаем его штрихом и выделяем знаком '+' вторую строку. Просматриваем эту строку, находим в ней элемент С22 = 0* и уничтожаем знак выделения второго столбца, содержащего 0*. Затем просматриваем второй столбец - в нем нет невыделенных элементов. Переходим к последнему невыделенному столбцу (пятому), ищем в нем невыделенные нули. Поскольку невыделенных нулей нет, то переходим к третьему этапу.
Третий этап. Находим минимальный элемент в невыделенной части матрицы С0 (т.е. элементы, которые лежат в столбцах и строках, не отмеченных знаком '+'). Он равен h = 1.
Вычтем h = 1 из всех элементов невыделенных строк (т.е. всех, кроме второго) и прибавим ко всем элементам выделенных столбцов (первого и четвертого). Получим матрицу С'1 и перейдем к первому этапу.
Первый этап. Перед его началом вновь выделяем знаком '+' первый, второй и четвертый столбцы. Просматриваем невыделенный третий столбец, находим в нем невыделенный нуль С23 = 0, отмечаем его знаком штрих. Поскольку во второй строке есть 0* (элемент С22), то выделяем знаком '+' вторую строку, далее уничтожаем знак выделения второго столбца, где лежит 0*. Потом просмотрим второй столбец, находим в нем невыделенный нуль С12 = 0, отмечаем его знаком штрих. Поскольку в первой строке есть нуль со звездочкой С14 = 0*, то выделяем его знаком '+', и уничтожаем знак выделения четвертого столбца, где находился этот знак 0*. Затем пересматриваем четвертый столбец и находим в нем невыделенный нуль С54 = 0. Так как в строке, где он находится, нет нуля со звездочкой, то отметив этот 0 штрихом, переходим ко второму этапу.
Второй этап. Начиная с элемента с54 = 0', строим цепочку, двигаясь от него по столбцу. Находим нуль со звездочкой с14 = 0*, далее от него движемся вдоль первой строки и находим 0'(с12), от этого элемента движемся вдоль первого столбца к с22 = 0*, в конечном итоге, двигаясь от с22 = 0* вдоль второй строки приходим к исходному с23 = 0'. Таким образом, цепочка построена: 0'54-0*14-0'12-0*22-0'23. Заменяем штрих на звездочку и уничтожаем звездочки над четными элементами цепочки, а также все знаки выделения столбцов и строк. На этом первая итерация заканчивается. В результате число независимых нулей увеличилось на единицу. Поскольку следующие итерации выполняются аналогично, то приведем результаты их выполнения без дополнительных пояснений. После второй итерации количество независимых нулей (0*) стало равно 5 (размерности матрицы С) и поэтому алгоритм заканчивает работу. Искомые элементы назначения соответствуют позициям независимых нулей матрицы С3 (т.е. 0*).
Соответствующее значение целевой функции
Первая итерация. Первый этап Третий этап
h=1
Первая итерация. Первый этап. Второй этап.
 |
Вторая итерация.
Первый этап Второй этап
 |
Венгерский метод для транспортной задачи
Рассмотренная выше задача о назначениях представляет собой частный случай Т-задачи, когда 
. Поэтому венгерский метод, применимый для решения транспортной задачи специального вида, можно распространить на общий случай Т-задачи. [18; 59].
Пусть требуется решить Т-задачу следующего вида
минимизировать 
при условиях
Алгоритм решения Т-задачи, основанный на венгерском методе, состоит из предварительного этапа и конечного числа однотипных итераций.
В результате предварительного этапа вычисляют матрицу 
, элементы которой удовлетворяют следующим условиям:
, (3.3.1)
. (3.3.2)
Если в условиях (3.3.1), (3.3.2) строгие равенства, то матрица Х0 является решением Т-задачи.
Матрицу, построенную в результате k-й итерации, обозначим 
. Обозначим также
. (3.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 окажутся в выделенных столбцах, то переходят к третьему этапу. В противном случае пусть некоторый невыделенный нуль находится в -й строке и в 
-м столбце. Тогда вычисляют значения невязки -й строки:
.
Возможен один из двух случаев: 1)
, 2)
. В первом случае -ю строку Сk отмечают знаком '+' справа от нее, а сам невыделенный нуль отмечают штрихом. Далее просматривают элементы -й строки, которые лежат в выделенных столбцах и ищут среди них существенные нули (напомним, что существенным нулем Сk называется такой элемент 
, для которого 
). Если таким существенным нулем оказался элемент 
, а сам столбец m - выделен, то знак выделения '+' над столбцом m уничтожают, а сам этот нуль отмечают звездочкой.
Затем просматривают m-й столбец и отыскивают в нем нуль (нули), расположенные в отличных от 
-й строках. Если такой нуль имеется, то отмечают его штрихом и анализируют невязку его строки.
Далее процесс поиска нулей и выделение их (штрихами или звездочками) продолжается аналогично, и за несколько шагов он заканчивается одним из следующих исходов:
1) найдем очередной невыделенный нуль матрицы Сk, для которого невязкая в строке 
. Тогда отметив его штрихом, переходим ко второму этапу;
2) все нули матрицы Сk оказались выделенными, причем для каждого из нулей, выделяемых штрихом, невязка 
. Тогда переходим к третьему этапу.
Во втором случае, отметив этот нуль штрихом, сразу переходим к третьему этапу.
Второй этап. Состоит в построении цепочки из нулей матрицы Сk, отмеченных штрихами и звездочками, и в последующем переходе к новой матрице Хk+1
Пусть для некоторого нуля со штрихом матрицы Сk, расположенного, например, в позиции (
), невязка строки 
. Начиная с этого элемента 
, строят цепочку из отмеченных нулей матрицы Сk: двигаясь по столбцу 
, выбирают нуль со звездочкой 
, далее двигаясь от него по строке 
, находят нуль со штрихом 
. Потом движутся от него по столбцу m2 к следующему нулю со звездочкой и т.д.. Такой последовательный переход от 0' к 0* по столбцу и от 0* к 0' по строке осуществляют до тех пор, пока это возможно.
Можно доказать, что процесс построения цепочки однозначный и законченный, цепочка не имеет циклов, начинается и заканчивается нулем со штрихом.
После того как цепочка вида
построена, осуществляют переход к матрице 
от матрицы Хk по формулам
(3.3.7)
где 
(3.3.8)
Таким образом, 
-минимальный элемент среди совокупности четных элементов цепочки, невязки строки, где начинается цепочка, и столбца, где она заканчивается.
Вычисляем невязку для 
На этом (k+1)-я итерация заканчивается.
Третий этап. Итак, допустим, что все нули выделены. Третий этап заключается в переходе от матрицы Сk к эквивалентной матрице С′k, в которой появляется новый невыделенный нуль (или нули). Пусть 
, где минимум выбирают из всех невыделенных элементов матрицы Сk. Тогда из всех элементов невыделенных строк матрицы Сk вычитают h, а ко всем элементам выделенных столбцов прибавляют h. В результате получают матрицу С'k(С'k ~ Ck), в которой все существенные нули матрицы Сk остаются нулями, и кроме того, появляются новые невыделенные нули.
Далее переходят к первому этапу, и в зависимости от его результата либо переходят ко второму этапу, либо снова возвращаются к третьему этапу. За конечное число повторов пары этапов третий - первый обязательно перейдем ко второму этапу.
Если после выполнения второго этапа 
то Хk+1 - оптимальный план. В противном случае переходим к (k+2) итерации.
Отметим некоторые важные особенности венгерского метода.
Поскольку данный метод в отличие от метода потенциалов не использует опорных планов, то явление вырожденности плана для него отсутствует. Это устраняет возможность зацикливания, связанного с вырожденностью планов Т-задачи, которая облегчает программирование метода и его реализацию на ЭВМ.
Метод позволяет на каждой итерации по величине невязки оценить близость Хk к оптимальному плану, а также верхнюю границу необходимого числа оставшихся итераций Nост:
. (3.3.9)
Эта формула справедлива для целочисленных значений всех переменных 
и 
.
Обоснование венгерского метода
Прежде всего введем справедливость признака оптимальности, т.е. если 
, то план Хk - оптимален.
Действительно, в силу построения Хk, если , то (эти нули называют существенными). Поэтому план Хk оказывается оптимальным для задачи с матрицей Сk, так как
. (3.3.10)
Но матрица Сk получена эквивалентными преобразованиями из исходной матрицы С. Докажем, что Хk - оптимален и для задачи с матрицей С. Матрицы С и Сk как эквивалентные связаны соотношениями
для всех (i,j) (3.3.11)
Тогда значение целевой функции для плана Хk при матрице С будет равно
(3.3.12)
Но так как 
, то
і. 
(3.3.13)
Подставляя (3.3.13) в (3.3.12), получим с учетом (3.3.10)
. (3.3.14)
Но 
и не зависит от плана Хk, поэтому план Хk оптимален и для исходной задачи с матрицей С.
Перейдем теперь к обоснованию алгоритма.
Предварительный этап. На предварительном этапе строят матрицу Хk элементы которой удовлетворяют условиям
, (3.3.15)
. (3.3.16)
Если все условия (3.3.15), (3.3.16) выполняются как строгие равенства, то план Х0 - оптимален, согласно только что доказанному.
Первый этап. Цель первого этапа состоит в отыскании такого невыделенного нуля 
, для которого 
. Предположим, что такой нуль найден, и мы перешли ко второму этапу.
Второй этап. Он состоит в построении цепочки из нулей со штрихами и звездочками и переходе к Хk+1. Пусть цепочка имеет вид:
. (3.3.17)
Элементы матрицы Хk+1 вычисляют по рекуррентным формулами
|
|
|
|
|
|
|
|
|
|
|
|
(3.3.18)
Так как в каждой строке и столбце имеется как 0', так и 0*, либо они оба отсутствуют, за исключением строки 
и столбца 
, где имеется лишь 0', то
(3.3.19)
(3.3.20)
Поэтому, если матрица Хk удовлетворяла ограничениям (3.3.15), (3.3.16), то и матрица Хk+1 будет им также удовлетворять.
Наконец, на основании соотношений (3.3.19), (3.3.20) получим
.
Третий этап. В соответствии с правилами перехода от Сk к С'k при выборе элемента h > 0 элементы невыделенных строк Сk уменьшаются на величину h, появляются новые нули, и можно снова перейти к первому этапу. При этом по правилу выделения строк и столбцов все существенные нули Сk останутся нулями и в матрице C'k.
Пример 3.5. Найти решение транспортной задачи со следующими условиями:
Проверим условие баланса 
Предварительный этап. Вычитаем из элементов первого столбца 2, из второго - 3, из третьего -1, из четвертого -2. Приходим к матрице С1. Далее, вычитая минимальный элемент из элементов каждой строки, получаем матрицу С0:
Строим начальную матрицу перевозок
Невязки для столбцов dj = 0, 1, 9, 0, для строк dj = 4; 6; 0. Суммарная невязка
Первая итерация. Первый этап. Отмечаем знаком '+' сверху первый и четвертый столбцы, которым соответствуют нулевые невязки, а знаком 'х' слева первую и вторую строки, которым отвечают ненулевые невязки, черточкой сверху - существенные нули.
Просматриваем невыделенный второй столбец матрицы С0, находим в нем невыделенный нуль С32 = 0 и отмечаем его штрихом. Так как d3 = 0, то выделяем третью строку знаком '+'. Просматриваем третью строку относительно выделенных столбцов. Там существенных нулей нет. Поскольку в С0 больше не осталось невыделенных нулей (все нули расположены в выделенных строках или столбцах), то переходим к третьему этапу.
Третий этап. Среди элементов невыделенных строк и столбцов матрицы С0 находим минимальный элемент h = 1, прибавляем его ко всем элементам выделенных столбцов и вычитаем из всех элементов невыделенных строк. Получим матрицу С1.
Переходим к первому этапу.
Первый этап. Среди невыделенных столбцов находим нулевой элемент С22, который расположен в строке с ненулевой невязкой, а потому переходим ко второму этапу.
Второй этап. Цепочка состоит из одного элемента С22 = 0. Находим 
и прибавим q1 = 1 к элементу х1. Получим матрицу Х1.
Вторая итерация. Первый этап. В матрице С1 отмечаем знаком '+' первый, второй и четвертый столбцы, которым отвечают нулевые невязки. Находим в третьем столбце нуль С33 = 0 и отмечаем его штрихом.
Так как невязка в третьей строке равна нулю, то выделяем ее знаком '+'. Просматриваем эту строку, находим в ней существенный нуль С32, расположенный в выделенном столбце. Отмечаем его звездочкой и уничтожаем знак выделения второго столбца.
Далее просматриваем второй столбец и отыскиваем в нем невыделенный нуль С22. Так как невязка по строке d2 > 0, то отметив этот нуль штрихом, переходим ко второму этапу.
Второй этап. Строим цепочку в матрице С1 вида 
, а затем аналогичную цепочку в матрице Х1.
В результате получаем матрицу Х2: q2 = min {5, 8, 9} = 5
Третья итерация. Первый этап. В матрице С2 отмечаем знаком '+' первый, второй и четвертый столбцы, которым соответствуют нулевые невязки. Находим нулевой элемент С33 в третьем столбце. Так как ему соответствует нулевая невязка в третьей строке, то отмечаем этот нуль штрихом. Далее, просматриваем третью строку, отыскиваем в ней существенный нуль С32 = 0, расположенный в выделенном втором столбце, отмечаем звездочкой этот нуль и уничтожаем знак выделения над вторым столбцом. Просматриваем второй столбец, находим в нем нулевой элемент С22 = 0 и отмечаем его штрихом, а вторую строку, где он лежит, знаком '+' (так как d2 = 0).
Далее, просмотрев вторую строку, находим в ней существенный нуль С21 = 0 в выделенном первом столбце. Поэтому выделяем этот нуль звездочкой и уничтожаем знак '+' над первым столбцом.
h = min {4, 3, 2} = 2
На этом процесс выделения нулей заканчиваем. Так как больше выделенных нулей не имеется, то переходим к третьему этапу.
Третий этап. Находим минимальный невыделенный элемент в матрице С2 h = 2, вычитаем h из всех элементов невыделенных строк и прибавляем ко всем элементам выделенных столбцов (т.е. прибавляем к четвертому столбцу и вычитаем из первой строки). В результате получим матрицу С3, в которой появился новый невыделенный нуль (С 13). Переходим к первому этапу.
Первый этап. В матрице С3 находим невыделенный нуль С13. Так как d1 > 0, то переходим ко второму этапу.
Второй этап. Вся цепочка состоит из одного элемента 
. Поэтому q3 = min {d1 = 4, d2 = 4} = 4. Прибавим q3 к , получим матрицу X3.
Так как D3 = 0, то Х3 - оптимальный план. Соответствующее значение целевой функции Lорт = 
(сравните с результатами решения этой задачи методом потенциалов, см. пример 3.3).
Транспортная задача с ограниченными пропускными способностями
Рассмотрим Тd - задачу:
Минимизировать
при условиях
Введем следующие определения.
1. Элемент сij = 0 матрицы С называется Х - неполным нулем, если в плане Х Тd-задачи элемент хij < dij. Если же хij = dij, то элемент сij называется Х - полным нулем.
2. Х - существенным нулем матрицы С называется такой ее элемент сij = 0, для которого хij > 0, в противном случае этот элемент называется несущественным нулем.
Описание алгоритма венгерского метода. Алгоритм решения Тd-задачи, основанный на венгерском методе, состоит из предварительного этапа и ряда однотипных итераций [18; 59].
Предварительный этап. Его цель - приведение матрицы С и построение начального приближения к решению Х0.
В каждом столбце матрицы С разыскивают минимальный элемент и вычитают из всех элементов данного столбца. В результате получают матрицу С'. Далее, из всех элементов каждой строки С' вычитают минимальный элемент этой строки и получают в результате матрицу С0(С0@С), в каждой строке и столбце которой имеется хотя бы один нуль.
После этого формируют матрицу Х0=|| xij0 ||, процесс построения которой ведут по столбцам. Пусть уже заполнены первые (j-1) столбцы матрицы Х0. Перенумеруем нули j-го столбца матрицы С0 сверху вниз и через ikj (k=1,2,.,r) обозначим номер строки, содержащей k-й нуль j-го столбца. Тогда элементы j-го столбца определяются в соответствии с формулой
если 
k=1,2.. (3.3.21)
Если для матрицы Х0 суммарная невязка
то Х0 - оптимальной план Тd-задачи.
Если же D0>0, то переходят к первой итерации.
Каждая итерация алгоритма в общем случае включает 3 этапа: начинается первым этапом, затем несколько раз могут повторяться первый и третий этапы, а заканчивается итерация вторым этапом либо установлением неразрешимости данной задачи.
(k+1)-я итерация. Предположим, что уже осуществлено k итераций алгоритма, в результате которых получены матрицы Хk и Сk.
Пусть 
и еще не установлена неразрешимость Тa-задачи.
Целью (k+1)-й итерации является построение матрицы Хk+1 и проверка ее на оптимальность или на установление неразрешимости Тd-задачи. Перед началом итерации знаком '+' выделяют те столбцы матрицы Сk, для которых невязка
.
Первый этап. Выбирают произвольный невыделенный Хk- неполный нуль матрицы Сk, если это элемент Сijk , то вычисляют невязку строки i, его содержащей:
.
Тогда возможен один из двух случаев:
Во втором случае, отметив этот невыделенный нуль cijk =0 знаком штрих, сразу переходим ко второму этапу.
В первом случае знаком '+' выделяют i -ю строку матрицы Сk , а элемент сijk отмечают штрихом. Если на пересечении μ-го выделенного столбца i-й строки матрицы Сk расположен Хk-существенный нуль матрицы Сk , то знак выделения этого столбца уничтожают, а сам элемент ciμk =0 отмечают звездочкой. Далее просматривают столбец m, отыскивают в нем невыделенный неполный нуль (нули). Если такой нуль имеется, то отмечают его штрихом и анализируют строку, содержащую его. За конечное число шагов процесс выделения Хk-неполных нулей матрицы Сk заканчивается одним из трех исходов:
1) найден Хk-неполный нуль в строке і, где 
> 0, тогда переходим ко второму этапу, отметив этот нуль штрихом;
2) все Хk-неполные нули выделены, для каждого из них , а среди невыделенных элементов матрицы Сk имеются либо положительные, либо среди дважды выделенных элементов Сk (т.е. элементов, расположенных на пересечении выделенных строк и столбцов), отрицательные элементы. В этом случае переходим к третьему этапу;
3) все Хk-неполные нули выделены (для кажого из них dи(k) = 0), все невыделенные элементы Сk - отрицательны, а дважды выделенные -положительны. Это означает неразрешимость Тd - задачи.
Второй этап. Он состоит в построении цепочки из нулей матрицы Сk, отмеченных штрихами и звездочками. С помощью этой цепочки осуществляют переход от Хk к Хk+1. Итак, пусть первый этап завершился таким образом, что для некоторого невыделенного неполного нуля, расположенного, например, на пересечении строки l1 и столбца m1, невязка 
. Этот элемент принимают за начало цепочки из отмеченных нулей матрицы Сk. Цепочку строят так.
Движутся по столбцу m1 матрицы С0 и находят в нем нуль со звездочкой 
, далее движутся от него по строке l1 и находят 
и т.д. Процесс построения цепочки, складывающийся из последовательных переходов от нуля со штрихом к нулю со звездочкой по столбцу и от нуля со звездочкой к нулю со штрихом по строке, всегда начинается и заканчивается на нуле со штрихом.
Пусть в результате построения образована цепочка вида
. (3.3.22)
Элементы хij(k+1) матрицы Хk+1 вычисляют по рекуррентной формуле
|
- не входят в цепочку;
(3.3.23)
Параметр 
определяют из соотношения
, (3.3.24)
где 
- минимальный четный по порядку следования элемент цепочки; 
- минимальный резерв до насыщения для нечетных (по порядку следования) элементов цепочки;
- невязкая строки, откуда начинается цепочка,
- невязкая столбца, где цепочка заканчивается.
Если суммарная невязка
то матрица Хk+1 является решением Тd-задачі, в противном случае переходят к следующей итерации.
Третий этап. На этом этапе производят преобразование матрицы Сk в эквивалентную матрицу Сk'.
Пусть первый этап закончился вторым исходом. Обозначим минимальный элемент
,
где h' - минимальный среди невыделенных положительных элементов матрицы Сk ; h'' - минимальный среди дважды выделенных отрицательных элементов матрицы Сk , взятых с обратным знаком. Вычитаем h из элементов матрицы Сk , расположенных в невыделенных строках, и прибавляем h к элементам Сk , расположенным в выделенных столбцах. Получим матрицу Сk' . Если дважды выделенный отрицательный элемент Сk становится нулем в Сk' , то знак выделения над столбцом уничтожают, а сам элемент отмечают звездочкой. Остальные знаки выделения, а также все отметки нулей переносят из матрицы Сk в матрицу Сk'.
Далее, снова переходят к первому этапу, заменив Сk на Сk'. Если первый этап снова завершится вторым исходом, то опять возвращаются к третьему этапу. Циклы, состоящие из первого и третьего этапов, проводят до тех пор, пока последний из них не закончится первым или третьим исходом. При первом исходе переходят ко второму этапу, а при третьем - делают вывод о неразрешимости Тd-задачи из-за несовместимости ее условий.
Пример 3.6. Решить венгерским методом Тd-задачу со следующими условиями
- матрица пропускных способностей коммуникаций.
Предварительный этап. Составляем матрицу С:
.
Затем строим матрицу Х0 с учетом матрицы D:
.
Будем отмечать одной точкой сверху неполные нули матрицы Сk , а двумя точками Хk -полные нули этих матриц. Строки матрицы Сk , которым отвечают ненулевые невязки, будем отмечать знаком '´'.
Первая итерация Третий этап
Первый этап Второй этап
Первая итерация. Первый этап. Знаком '+' выделяем четвертый столбец. Так как матрица С0 не содержит ни одного Х0 - неполного нуля, то сразу переходим к третьему состоянию, отыскиваем неполный невыделенный нуль, c23 и, отметив его штрихом, переходим ко второму этапу. Цепочка, построенная на втором этапе, состоит из одного элемента x320 . Поэтому
Вторая итерация
|
Третья итерация Первый этап Третий этап
|
Второй этап
D3 = 2
Третья итерация состоит из первого и третьего этапов при h = 1, а также из первого и второго этапов, причем цепочка второго этапов, причем цепочка второго этапа содержит лишь один элемент x312.
Четвертая итерация
Первый и третий этапы
Третий этап Первый этап
Второй этап 
Поскольку суммарная невязка D4=0, то Х4-оптимальный план. Соответствующее значение целевой функции Lmin=3.I + 1.4 + 2.2 + 1.4 + 2.1 + 1.3 + 1.2 + 1.1 = 23.
