3.3. ВЕНГЕРСКИЙ МЕТОД

Венгерский метод является одним из интереснейших и наиболее распространенных методов решения транспортных задач.

Рассмотрим сначала основные идеи венгерского метода на примере решения задачи выбора (задачи о назначениях), которая является частным случаем Т-задачи, а затем обобщим этот метод для произвольной Т-задачи.

Венгерский метод для задачи о назначениях

Постановка задачи. Предположим, что имеется  различных работ  и  механизмов , каждый из которых может выполнять любую работу, но с неодинаковой эффективностью. Производительность механизма  при выполнении работы  обозначим , и = 1,...,n; j = 1,...,n. Требуется так распределить механизмы по работам, чтобы суммарный эффект от их использования был максимален. Такая задача называется задачей выбора или задачей о назначениях.

Формально она записывается так. Необходимо выбрать такую последовательность элементов  из матрицы

чтобы сумма  была максимальна и при этом из каждой строки и столбца С был выбран только один элемент.

Введем следующие понятия.

Нулевые элементы  матрицы С  называются независимыми нулями, если для любого   строка и столбец, на пересечении которых расположен элемент , не содержат другие такие элементы .

Две прямоугольные матрицы С и D называются эквивалентными (C ~ D), если  для всех i,j . Задачи о назначениях, определяемые эквивалентными матрицами, являются эквивалентными (т.е. оптимальные решения одной из них будут оптимальными и для второй, и наоборот).

Описание алгоритма венгерского метода

Алгоритм состоит из предварительного этапа и не более чем (n-2) последовательно проводимых итераций. Каждая итерация связана с эквивалентными преобразованиями матрицы, полученной в результате проведения предыдущей итерации, и с выбором максимального числа независимых нулей. Окончательным результатом итерации является увеличение числа независимых нулей на единицу. Как только количество независимых нулей станет равным n, проблему выбора оказывается решенной, а оптимальный вариант назначений определяется позициями независимых нулей в последней матрице.

Предварительный этап. Разыскивают максимальный элемент в j – м столбце и все элементы этого столбца последовательно вычитают из максимального. Эту операцию проделывают над всеми столбцами матрицы С. В результате образуется матрица с неотрицательными элементами, в каждом столбце которой имеется, по крайней мере, один нуль.

Далее рассматривают i – ю строку полученной матрицы, разыскивают ее минимальный элемент a_i и из каждого элемента этой строки вычитают минимальный. Эту процедуру повторяют со всеми строками. В результате получим матрицу С₀ (С₀ ~ C), в каждой строке и столбце которой имеется, по крайней мере, один нуль. Описанный процесс преобразования С в С₀ называется приведением матрицы.

Находим произвольный нуль в первом столбце и отмечаем его звездочкой. Затем просматриваем второй столбец, и если в нем есть нуль, расположенный в строке, где нет нуля со звездочкой, то отмечаем его звездочкой. Аналогично просматриваем один за другим все столбцы матрицы С₀ и отмечаем, если возможно, следующие нули знаком “*”. Очевидно, что нули матрицы С₀, отмеченные звездочкой, являются независимыми. На этом предварительный этап заканчивается.

(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^*. Затем просматриваем второй столбец – в нем нет невыделенных элементов. Переходим к последнему невыделенному столбцу (пятому), ищем в нем невыделенные нули. Поскольку невыделенных нулей нет, то переходим к третьему этапу.

Третий этап. Находим минимальный элемент в невыделенной части матрицы С₀ (т.е. элементы, которые лежат в столбцах и строках, не отмеченных знаком “+”). Он равен h = 1.

Вычтем h = 1 из всех элементов невыделенных строк (т.е. всех, кроме второго) и прибавим ко всем элементам выделенных столбцов (первого и четвертого). Получим матрицу С^'₁ и перейдем к первому этапу.

Первый этап. Перед его началом вновь выделяем знаком “+” первый, второй и четвертый столбцы. Просматриваем невыделенный третий столбец, находим в нем невыделенный нуль С₂₃ = 0, отмечаем его знаком штрих. Поскольку во второй строке есть 0^* (элемент С₂₂), то выделяем знаком “+” вторую строку, далее уничтожаем знак выделения второго столбца, где лежит 0^*. Потом просмотрим второй столбец, находим в нем невыделенный нуль С₁₂ = 0, отмечаем его знаком штрих. Поскольку в первой строке есть нуль со звездочкой С₁₄ = 0^*, то выделяем его знаком “+”, и уничтожаем знак выделения четвертого столбца, где находился этот знак 0^*. Затем пересматриваем четвертый столбец и находим в нем невыделенный нуль С₅₄ = 0. Так как в строке, где он находится, нет нуля со звездочкой, то отметив этот 0 штрихом, переходим ко второму этапу.

Второй этап. Начиная с элемента с₅₄ = 0^’, строим цепочку, двигаясь от него по столбцу. Находим нуль со звездочкой с₁₄ = 0^*, далее от него движемся вдоль первой строки и находим 0^’(с₁₂), от этого элемента движемся вдоль первого столбца к с₂₂ = 0^*, в конечном итоге, двигаясь от с₂₂ = 0^* вдоль второй строки приходим к исходному с₂₃ = 0^’. Таким образом, цепочка построена: 0’₅₄-0^*_14-0’_12-0^*_22-0’₂₃. Заменяем штрих на звездочку и уничтожаем звездочки над четными элементами цепочки, а также все знаки выделения столбцов и строк. На этом первая итерация заканчивается. В результате число независимых нулей увеличилось на единицу. Поскольку следующие итерации выполняются аналогично, то приведем результаты их выполнения без дополнительных пояснений. После второй итерации количество независимых нулей (0^*) стало равно 5 (размерности матрицы С) и поэтому алгоритм заканчивает работу. Искомые элементы назначения соответствуют позициям независимых нулей матрицы С₃ (т.е.  0^*).

Соответствующее значение целевой функции

Первая итерация. Первый этап                               Третий этап

                                 h=1

Первая итерация. Первый этап.              Второй этап.  

                                                

        Вторая итерация.

Первый этап                                                                   Второй этап

                     

Венгерский метод для транспортной задачи

Рассмотренная выше задача о назначениях представляет собой частный случай Т-задачи, когда . Поэтому венгерский метод, применимый для решения транспортной задачи специального вида, можно распространить на общий случай Т-задачи. [18; 59].

Пусть требуется решить Т-задачу следующего вида

минимизировать

при условиях

Алгоритм решения Т-задачи, основанный на венгерском методе, состоит из предварительного этапа и конечного числа однотипных итераций.

В результате предварительного этапа вычисляют матрицу , элементы которой удовлетворяют следующим условиям:

,                                   (3.3.1)

.                                    (3.3.2)

Если в условиях (3.3.1), (3.3.2) строгие равенства, то матрица Х₀ является решением Т-задачи.

Матрицу, построенную в результате k-й итерации, обозначим . Обозначим также

 .                           (3.3.3)

Величина  называется суммарной невязкой для матрицы . Она характеризует близость  к искомому плану Т-задачи. Итерации проводятся до тех пор, пока величина  не станет равна нулю.

Описание алгоритма Венгерского метода

Предварительный этап. В каждом из столбцов матрицы транспортных издержек  отыскивают минимальный элемент, который вычитают из всех элементов этого столбца. Получают матрицу С'. Далее в каждой строке матрицы С' выбирают минимальный элемент и вычитают его из всех элементов рассматриваемой строки. Приходят к матрице С₀ (С₀ ~ C), все элементы которой неотрицательны, причем в каждой строке и столбце С₀ имеем по крайней мере, один нуль. Строят матрицу Х₀ так, чтобы ее ненулевые элементы были расположены в позициях нулей матрицы С₀.

Пусть — номер строки, в которой расположен k-й нуль j-го столбца матрицы С₀. Тогда элементы первого столбца матрицы Х₀ определяют по рекуррентной формуле

                   (3.3.4)

Т.е. все элементы первого столбца , которым соответствуют ненулевые элементы в матрицы С₀, заполняют нулями, а остальные элементы этого столбца заполняют по методу северо-западного угла.

Допустим, что столбцы Х₀ от первого до (j–1) – го включительно уже заполнены. Тогда элементы j-го столбца определяют в соответствии с формулой

                       (3.3.5)

Если , то Х₀ – оптимальный план Т-задачи. Если , то переходим к первой итерации.

(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: двигаясь по столбцу , выбирают нуль со звездочкой , далее двигаясь от него по строке , находят нуль со штрихом . Потом движутся от него по столбцу m₂ к следующему нулю со звездочкой и т.д.. Такой последовательный переход от 0’ к 0^* по столбцу и от 0^* к 0' по строке осуществляют до тех пор, пока это возможно.

Можно доказать, что процесс построения цепочки однозначный и законченный, цепочка не имеет циклов, начинается и заканчивается нулем со штрихом.

После того как цепочка вида

построена, осуществляют переход к матрице  от матрицы Х_k по формулам

        (3.3.7)

где                     (3.3.8)

Таким образом, -минимальный элемент среди совокупности четных элементов цепочки, невязки строки, где начинается цепочка, и столбца, где она заканчивается.

Вычисляем невязку для

На этом (k+1)-я итерация заканчивается.

Третий этап. Итак, допустим, что все нули выделены. Третий этап заключается в переходе от матрицы С_k к эквивалентной матрице С′_k, в которой появляется новый невыделенный нуль (или нули). Пусть , где минимум выбирают из всех невыделенных элементов матрицы С_k. Тогда из всех элементов невыделенных строк матрицы С_k вычитают h, а ко всем элементам выделенных столбцов прибавляют h. В результате получают матрицу С'_k(С'_k ~ C_k), в которой все существенные нули матрицы С_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) выполняются как строгие равенства, то план Х₀ – оптимален, согласно только что доказанному.

Первый этап. Цель первого этапа состоит в отыскании такого невыделенного нуля , для которого . Предположим, что такой нуль найден, и мы перешли ко второму этапу.

Второй этап. Он состоит в построении цепочки из нулей со штрихами и звездочками и переходе к Х_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. Приходим к матрице С₁. Далее, вычитая минимальный элемент из элементов каждой строки, получаем матрицу С₀:

                               

Строим начальную матрицу перевозок

Невязки для столбцов d_j = 0, 1, 9, 0, для строк d_j = 4; 6; 0. Суммарная невязка

Первая итерация. Первый этап. Отмечаем знаком “+” сверху первый и четвертый столбцы, которым соответствуют нулевые невязки, а знаком “х” слева первую и вторую строки, которым отвечают ненулевые невязки, черточкой сверху – существенные нули.

Просматриваем невыделенный второй столбец матрицы С₀, находим в нем невыделенный нуль С₃₂ = 0 и отмечаем его штрихом. Так как d₃ = 0, то выделяем третью строку знаком “+”. Просматриваем третью строку относительно выделенных столбцов. Там существенных нулей нет. Поскольку в С₀ больше не осталось невыделенных нулей (все нули расположены в выделенных строках или столбцах), то переходим к третьему этапу.

Третий этап. Среди элементов невыделенных строк и столбцов матрицы С₀ находим минимальный элемент h = 1, прибавляем его ко всем элементам выделенных столбцов и вычитаем из всех элементов невыделенных строк. Получим матрицу С₁.

                

Переходим к первому этапу.

Первый этап. Среди невыделенных столбцов находим нулевой элемент С_22,   который расположен в строке с ненулевой невязкой, а потому переходим ко второму этапу.

Второй этап. Цепочка состоит из одного элемента С₂₂ = 0. Находим  и прибавим q₁ = 1 к элементу х₁. Получим матрицу Х₁.

Вторая итерация. Первый этап. В матрице С₁ отмечаем знаком “+” первый, второй и четвертый столбцы, которым отвечают нулевые невязки. Находим в третьем столбце нуль С₃₃ = 0 и отмечаем его штрихом.

Так как невязка в  третьей строке равна нулю, то выделяем ее знаком “+”. Просматриваем эту строку, находим в ней существенный нуль С₃₂, расположенный в выделенном столбце. Отмечаем его звездочкой и уничтожаем знак выделения второго столбца.

Далее просматриваем второй столбец и отыскиваем в нем невыделенный нуль С₂₂. Так как невязка по строке d₂ > 0, то отметив этот нуль штрихом, переходим ко второму этапу.

Второй этап. Строим цепочку в матрице С₁ вида , а затем аналогичную цепочку в матрице Х₁.

В результате получаем матрицу Х₂: q₂ = min {5, 8, 9} = 5

  

Третья итерация. Первый этап. В матрице С₂ отмечаем знаком “+” первый, второй и четвертый столбцы, которым соответствуют нулевые невязки. Находим нулевой элемент С₃₃ в третьем столбце. Так как ему соответствует нулевая невязка в третьей строке, то отмечаем этот нуль штрихом. Далее, просматриваем третью строку, отыскиваем в ней существенный нуль С₃₂ = 0, расположенный в выделенном втором столбце, отмечаем звездочкой этот нуль и уничтожаем знак выделения над вторым столбцом. Просматриваем второй столбец, находим в нем нулевой элемент С₂₂ = 0 и отмечаем его штрихом, а вторую строку, где он лежит, знаком “+” (так как d₂ = 0).

Далее, просмотрев вторую строку, находим в ней существенный нуль С₂₁ = 0 в выделенном первом столбце. Поэтому выделяем этот нуль звездочкой и уничтожаем знак “+” над первым столбцом.

h = min {4, 3, 2} = 2

             

На этом процесс выделения нулей заканчиваем. Так как больше выделенных нулей не имеется, то переходим к третьему этапу.

Третий этап. Находим минимальный невыделенный элемент в матрице С₂ h = 2, вычитаем h из всех элементов невыделенных строк и прибавляем ко всем элементам выделенных столбцов (т.е. прибавляем к четвертому столбцу и вычитаем из первой строки). В результате получим матрицу С₃, в которой появился новый невыделенный нуль (С­ ₁₃). Переходим к первому этапу.

Первый этап. В матрице С₃ находим невыделенный нуль С₁₃. Так как d₁ > 0, то переходим ко второму этапу.

Второй этап. Вся цепочка состоит из одного элемента . Поэтому q₃ = min {d₁ = 4, d₂ = 4} = 4. Прибавим q₃ к , получим матрицу X₃.

          

Так как D₃ = 0, то Х₃ – оптимальный план. Соответствующее значение целевой функции L_орт =  (сравните с результатами решения этой задачи методом потенциалов, см. пример 3.3).

Транспортная задача с ограниченными пропускными способностями

Рассмотрим Т_d - задачу:

Минимизировать

при условиях

Введем следующие определения.

1. Элемент с_ij = 0 матрицы С называется Х – неполным нулем, если в плане Х Т_d-задачи элемент х_ij < d_ij. Если же х_ij = d_ij, то элемент с_ij называется Х – полным нулем.

2. Х – существенным нулем матрицы С называется такой ее элемент с_ij = 0, для которого х_ij > 0, в противном случае этот элемент называется несущественным нулем.

Описание алгоритма венгерского метода. Алгоритм решения Т_d-задачи, основанный на венгерском методе, состоит из предварительного этапа и ряда однотипных итераций [18; 59].

Предварительный этап. Его цель – приведение матрицы С и построение начального приближения к решению Х₀.

В каждом столбце матрицы С разыскивают минимальный элемент и вычитают из всех элементов данного столбца. В результате получают матрицу С'. Далее, из всех элементов каждой строки С' вычитают минимальный элемент этой строки и получают в результате матрицу С₀(С₀@С), в каждой строке и столбце которой имеется хотя бы один нуль.

После этого формируют матрицу Х₀=|| x_ij⁰ ||, процесс построения которой ведут по столбцам. Пусть уже заполнены первые (j–1) столбцы матрицы Х₀. Перенумеруем нули j-го столбца матрицы С₀ сверху вниз и через i_kj (k=1,2,…,r) обозначим номер строки, содержащей k-й нуль j-го столбца. Тогда элементы j-го столбца определяются в соответствии с формулой

 если  k=1,2.. (3.3.21)

Если для матрицы Х₀ суммарная невязка

то Х₀ – оптимальной план Т_d-задачи.

Если же D₀>0, то переходят к первой итерации.

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

(k+1)-я итерация. Предположим, что уже осуществлено k итераций алгоритма, в результате которых получены матрицы Х_k и С_k.

Пусть  и еще не установлена неразрешимость Т_a-задачи.

Целью (k+1)-й итерации является построение матрицы Х_k+1 и проверка ее на оптимальность или на установление неразрешимости Т_d-задачи. Перед началом итерации знаком “+” выделяют те столбцы матрицы С_k, для которых невязка

 .

Первый этап. Выбирают произвольный невыделенный Х_k- неполный нуль матрицы С_k, если это элемент С_ij^k , то вычисляют невязку строки i, его содержащей:

 .

Тогда возможен один из двух случаев:

Во втором случае, отметив этот невыделенный нуль c_ij^k =0 знаком штрих, сразу переходим ко второму этапу.

В первом случае знаком “+” выделяют i -ю строку матрицы С_k , а элемент с_ij^k отмечают штрихом. Если на пересечении μ-го выделенного столбца i-й строки матрицы С_k расположен Х_k-существенный нуль матрицы С_k , то знак выделения этого столбца уничтожают, а сам элемент c_iμ^k =0 отмечают звездочкой. Далее просматривают столбец m, отыскивают в нем невыделенный неполный нуль (нули). Если такой нуль имеется, то отмечают его штрихом и анализируют строку, содержащую его. За конечное число шагов процесс выделения Х_k-неполных нулей  матрицы С_k заканчивается одним из трех исходов:

1) найден Х_k-неполный нуль в строке і, где > 0, тогда переходим ко второму этапу, отметив этот нуль штрихом;

2) все Х_k-неполные нули выделены, для каждого из них , а среди невыделенных элементов матрицы С_k имеются либо положительные, либо среди дважды выделенных элементов С_k (т.е. элементов, расположенных на пересечении выделенных строк и столбцов), отрицательные элементы. В этом случае переходим к третьему этапу;

3) все Х_k-неполные нули выделены (для кажого из них d_и^(k) = 0), все невыделенные элементы С_k – отрицательны, а дважды выделенные –положительны. Это означает неразрешимость Т_d - задачи.

Второй этап. Он состоит в построении цепочки из нулей матрицы С_k, отмеченных штрихами и звездочками. С помощью этой цепочки осуществляют переход от Х_k к Х_k+1. Итак, пусть первый этап завершился таким образом, что для некоторого невыделенного неполного нуля, расположенного, например, на пересечении строки l₁ и столбца m₁, невязка . Этот элемент принимают за начало цепочки из отмеченных нулей матрицы С_k. Цепочку строят так.

Движутся по столбцу m₁ матрицы С₀ и находят в нем нуль со звездочкой , далее движутся от него по строке l₁ и находят  и т.д. Процесс построения цепочки, складывающийся из последовательных переходов от нуля со штрихом к нулю со звездочкой по столбцу и от нуля со звездочкой к нулю со штрихом по строке, всегда начинается и заканчивается на нуле со штрихом.

Пусть в результате построения образована цепочка вида

 .      (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-задачу со следующими условиями

 

                                    — матрица пропускных способностей коммуникаций.

Предварительный этап. Составляем матрицу С:

 .

Затем строим матрицу Х₀ с учетом матрицы D:

 .

Будем отмечать одной точкой сверху неполные нули матрицы С_k , а двумя точками Х_k -полные нули этих матриц. Строки матрицы С_k , которым отвечают ненулевые невязки, будем отмечать знаком “´”.

Первая итерация             Третий этап

                         

Первый этап              Второй этап

 

Первая итерация. Первый этап. Знаком “+” выделяем четвертый столбец. Так как матрица С₀ не содержит ни одного Х₀ – неполного нуля, то сразу переходим к третьему состоянию, отыскиваем неполный невыделенный нуль, c₂₃ и, отметив его штрихом, переходим ко второму этапу. Цепочка, построенная на втором этапе, состоит из одного элемента x₃₂⁰ . Поэтому

Вторая итерация

+

                    

Третья итерация     Первый этап                                   Третий этап                                

;

                               

Второй этап

              

D₃ = 2

Третья итерация состоит из первого и третьего этапов при h = 1, а также из первого и второго этапов, причем цепочка второго этапов, причем цепочка второго этапа содержит лишь один элемент x₃₁².

Четвертая итерация

Первый и третий этапы

         

Третий этап                                                                                                      Первый этап

 

 Второй этап       

Поскольку суммарная невязка D₄=0, то Х_4-оптимальный план. Соответствующее значение целевой функции L_min=3·I + 1·4 + 2·2 + 1·4 + 2·1 + 1·3 + 1·2 + 1·1 = 23.