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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Далее рассматривают i - ю строку полученной матрицы, разыскивают ее минимальный элемент ai и из каждого элемента этой строки вычитают минимальный. Эту процедуру повторяют со всеми строками. В результате получим матрицу С00 ~ 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. Решить задачу о назначениях с матрицей

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

При решении задачи используем следующие обозначения:

Знак выделения '+', подлежащий уничтожению, обводим кружком; цепочку, как и ранее, указываем стрелками.

Предварительный этап. Отыскиваем максимальный элемент первого столбца - 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*).

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

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

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

Описание алгоритма венгерского метода - student2.ru Описание алгоритма венгерского метода - student2.ru h=1

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


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

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

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

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


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

Наши рекомендации