Содержание
Введение
Описание алгоритма венгерского
метода
Венгерский метод для транспортной
задачи
Обоснование венгерского метода
Примеры
Введение
Венгерский алгоритм — алгоритм оптимизации, решающий задачу о назначениях за полиномиальное время.
Он был разработан и опубликован Харолдом Куном в 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)
Величина
называется суммарной невязкой для
матрицы
. Она характеризует близость
к искомому плану Т-задачи. Итерации
проводятся до тех пор, пока величина
не станет равна нулю.
Описание алгоритма
Венгерского метода