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

Предварительный этап. На этом этапе формируется рабочая матрица из матрицы эффективностей. В каждом столбце матрицы эффективностей С(N,N) находится максимальный элемент, из которого вычитаются все элементы этого столбца. Далее в каждой строке получаемой матрицы выбирается минимальный элемент, который вычитается из всех элементов соответствующей строки. В первом столбце полученной матрицы выделяется произвольный нуль и отмечается (*). Затем просматриваются нули второго столбца и если среди них есть такие, которые не находятся в одной строке с нулем первого столбца, уже отмеченном звездочкой, то один из них отмечается звездочкой. Аналогично рассматриваются нули всех других столбцов. Отмеченные звездочками нули независимые, т.к. в каждой строке и каждом столбце может быть не более одного нуля со звездочкой.

Общий этап. Целью каждой последующей итерации является увеличение числа независимых нулей. Перед началом итерации выделяются знаком (+) столбцы матрицы, содержащие нули со звездочкой. Элементы, расположенные в выделенных столбцах (строках), называются выделенными, а остальные невыделенными. Итерация включает в себя три шага и устанавливает, имеются ли среди невыделенных элементов матрицы хотя бы один невыделенный нуль. Возможны два случая:

а) среди невыделенных элементов нет нулей.

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

б) среди невыделенных элементов имеется хотя бы один нуль. Тогда невыделенный нуль помечается штрихом (׳)и проверяется, содержит ли строка с невыделенным нулем также нуль со звездочкой. Если да, то строка, содержащая отмеченный штрихом нуль, помечается справа знаком (+) и снимается знак выделения (+) над столбцом, в котором расположен нуль со звездочкой. Если в строке с невыделенным элементом нуля со звездочкой нет, то строится цепочка элементов по правилу: движение начинается от последнего нуля со штрихом (׳) по столбцу к нулю со звездочкой (*), от нуля со (*) по строке к нулю со (׳), вновь от 0’ к 0^* по столбцу и т.д. начало и конец цепочки – нули со штрихами. После построения цепочки звездочки над нулями цепочки уничтожаются, а штрихи над нулями цепочки заменяются звездочками. Уничтожаются также все знаки выделения в матрице (штрихи, плюсы) кроме звездочек. Т.к. в цепочке нулей со штрихами на один больше, то в результате общее число нулей со звездочками увеличивается на единицу. Затем подсчитывается число нулей со (*). Если их число равно N, то найден оптимальный план назначения. В противном случае повторяется общий этап.

Заключительный этап. Определяется оптимальный план назначений по положению независимых нулей на последней итерации.

Имеется исходная матрица эффективностей. Таблица 1

В каждом столбце данной матрицы эффективностей находится максимальный элемент, из которого вычитаются все элементы этого столбца.

Таблица 2

Далее в каждой строке получаемой матрицы выбирается минимальный элемент, который вычитается из всех элементов соответствующей строки. В первом столбце полученной матрицы выделяется произвольный нуль и отмечается (*). Затем просматриваются нули второго столбца и если среди них есть такие, которые не находятся в одной строке с нулем первого столбца, уже отмеченном звездочкой, то один из них отмечается звездочкой. Аналогично рассматриваются нули всех других столбцов. Выделяются знаком (+) столбцы матрицы, содержащие 0^* .

Таблица 3

+ + + + +

	0^*
			0^*
								0^*
							0^*
				0^*

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

Таблица 4

+ + +

	0^*	0^’
			0^*
								0^*
	0^’						0^*
							0^’
				0^*

Так как в седьмой строке с невыделенным нулем нет нуля со (*), то строится цепочка элементов, после чего (*) над нулями цепочки уничтожаются, а штрихи над нулями цепочки заменяются звездочками. Уничтожаются также все (’) и (+).

Таблица 5

+ + + + + +

	0	0^*
			0^*
								0^*
	0^*						0^*
							0^*
				0^*

В первой строке имеется еще один невыделенный нуль, он помечается (’), а во втором столбце снимается знак (+). Затем находится минимальный элемент и производится пересчет таблицы.

Таблица 6

+ + + + + +

	1	0^*			0^’
			0^*
								0^*
	0^*
							0^*
				0^*

Невыделенные нули опять помечаются (’), строки, где они находятся (+), а со столбцов, соответствующих нулям со (*), находящихся в данной строке, снимается знак (+). И т.к. в пятой строке нет нуля со (*), поэтому строим цепочку элементов.

Таблица 7

+ + +

	1	0^*	1		0^’
			0^*		0^’
								0^*
	0^*	0^’
			0^’
							0^*
				0^*

Результирующая матрица примет следующий вид:

Таблица 8

+ + + + + + + +

	1	0			1	0^*
					0^*
								0^*
		0^*
	0^*
							0^*
				0^*
			0^*

Число (*) равно 8-ми, следовательно, решение найдено. Решение равно сумме элементов исходной матрицы, соответствующих нулям со (*) в конечной матрице, т.е. 6+6+8+6+9+12+8+8=63.

Дата добавления: 2015-08-21