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

Содержание

 

Введение

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

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

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

Примеры

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

Венгерский алгоритм — алгоритм оптимизации, решающий задачу о назначениях за полиномиальное время. Он был разработан и опубликован Харолдом Куном в 1955 году. Автор дал ему имя «венгерский метод» в связи с тем, что алгоритм в значительной степени основан на более ранних работах двух венгерских математиков Кёнига и Эгервари.

Джеймс Манкрес в 1957 году заметил, что алгоритм является (строго) полиномиальным. С этого времени алгоритм известен также как алгоритм Куна — Манкреса или алгоритм Манкреса решения задачи о назначениях. Временная сложность оригинального алгоритма была  , однако Эдмондс  и Карп (а также Томидзава независимо от них) показали, что его можно модифицировать так, чтобы достичь времени выполнения  . Форд и Фалкерсон распространили метод на общие транспортные задачи. В 2006 году было обнаружено, что Якоби нашёл решение задачи о назначениях в XIX веке и опубликовал его в 1890 году на латыни.

Задача о назначениях является частным случаем классической транс-портной задачи и, как следствие, является задачей транспортного типа.  
Транспортная задача – задача о наиболее экономном плане перевозок од-нородного или взаимозаменяемого продукта из пункта производства (станций отправления), в пункты потребления (станции назначения) – является важней-шей частной задачей линейного программирования, имеющей обширные прак-тические приложения не только к проблемам транспорта. 
 Применительно к задаче о назначениях симплексный метод не эффекти-вен, так как любое ее допустимое базисное решение является вырожденным. Специфические особенности задачи о назначениях позволили разработать эф-фективный метод ее решения, известный как венгерский метод.

 

 

 

 

 

 

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

Алгоритм состоит из предварительного этапа и не более чем (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, расположенный в выделенном столбце. Отмечаем его звездочкой и уничтожаем знак выделения второго столбца.