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

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

Перебрали столбцы и выявили систему из 4-х нулей 0*. Пометили столбцы +.

Метки	+	+		+		+
	-			0*
		-
			-			0*
	0*			-
					-
		0*				-

Просматриваем невыделенную часть. Нашли 0, находящийся в одной строке с 0*.

Метки	+	+		+		+
	-			0*
		-
			-			0*
	0*			-
					-
		0*				-

Пометили найденный 0 штрихом. Сняли выделение со 2-ого столбца и пометили 6-ю строку.

Метки	+			+		+
	-			0*
		-
			-			0*
	0*			-
					-
+		0*	0’			-

Просматриваем невыделенную часть. Нашли 0, находящийся в одной строке с 0*.

Метки	+			+		+
	-			0*
		-
			-			0*
	0*			-
					-
+		0*	0’			-

Пометили найденный 0 штрихом. Сняли выделение со 1-ого столбца и пометили 4-ю строку.

Метки				+		+
	-			0*
		-
			-			0*
+	0*	0’		-
					-
+		0*	0’			-

В невыделенной части нулей нет. Находим минимальное значение. Это -- 1.

Метки				+		+
	-			0*
		-
			-			0*
+	0*	0’		-
					-
+		0*	0’			-

Вычитаем 1 из всех элементов невыделенной области и прибавляем ко всем элементам, находящимся на пересечении выделенных строк и столбцов.

Метки				+		+
	-			0*
		-
			-			0*
+	0*	0’		-
					-
+		0*	0’			-

Находим 0 в невыделенной части. В соответствующей строке нет 0*.

Метки				+		+
	-			0*
		-
			-			0*
+	0*	0’		-
					-
+		0*	0’			-

Помечаем найденный 0 штрихом и выявляем L-цепь

Метки				+		+
	-			0*
	0’	-
			-			0*
+	0*	0’		-
					-
+		0*	0’			-

Меняем разметку L-цепи. Количество 0* увеличилось на один.

Метки				+		+
	-			0*
	0*	-
			-			0*
+		0*		-
					-
+			0*			-

Снимаем пометки строк и столбцов и начинаем новый цикл поиска L-цепи.

Метки
	-			0*
	0*	-
			-			0*
		0*		-
					-
			0*			-

Перебрали столбцы и выявили систему из 5-х нулей 0*. Пометили столбцы +.

Метки	+	+	+	+		+
	-			0*
	0*	-
			-			0*
		0*		-
					-
			0*			-

Просматриваем невыделенную часть. Нашли 0, находящийся в одной строке с 0*.

Метки	+	+	+	+		+
	-			0*
	0*	-
			-			0*
		0*		-
					-
			0*			-

Пометили найденный 0 штрихом. Сняли выделение со 3-ого столбца и пометили 6-ю строку.

Метки	+	+		+		+
	-			0*
	0*	-
			-			0*
		0*		-
					-
+			0*		0’	-

В невыделенной части нулей нет. Находим минимальное значение. Это -- 2.

Метки	+	+		+		+
	-			0*
	0*	-
			-			0*
		0*		-
					-
+			0*		0’	-

Вычитаем 2 из всех элементов невыделенной области и прибавляем ко всем элементам, находящимся на пересечении выделенных строк и столбцов.

Метки	+	+		+		+
	-			0*
	0*	-
			-			0*
		0*		-
					-
+			0*		0’	-

Просматриваем невыделенную часть. Нашли 0, находящийся в одной строке с 0*.

Метки	+	+		+		+
	-			0*
	0*	-
			-			0*
		0*		-
					-
+			0*		0’	-

Пометили найденный 0 штрихом. Сняли выделение со 2-ого столбца и пометили 4-ю строку.

Метки	+			+		+
	-			0*
	0*	-
			-			0*
+		0*		-	0’
					-
+			0*		0’	-

В невыделенной части нулей нет. Находим минимальное значение. Это -- 2.

Метки	+			+		+
	-			0*
	0*	-
			-			0*
+		0*		-	0’
					-
+			0*		0’	-

Вычитаем 2 из всех элементов невыделенной области и прибавляем ко всем элементам, находящимся на пересечении выделенных строк и столбцов.

Метки	+			+		+
	-			0*
	0*	-
			-			0*
+		0*		-	0’
					-
+			0*		0’	-

Просматриваем невыделенную часть. Нашли 0, находящийся в одной строке с 0*.

Метки	+			+		+
	-			0*
	0*	-
			-			0*
+		0*		-	0’
					-
+			0*		0’	-

Пометили найденный 0 штрихом. Сняли выделение со 6-ого столбца и пометили 3-ю строку.

Метки	+			+
	-			0*
	0*	-
+			-		0’	0*
+		0*		-	0’
					-
+			0*		0’	-

Находим 0 в невыделенной части. В соответствующей строке нет 0*.

Метки	+			+
	-			0*
	0*	-
+			-		0’	0*
+		0*		-	0’
					-
+			0*		0’	-

Помечаем найденный 0 штрихом и выявляем L-цепь

Метки	+			+
	-			0*
	0*	-
+			-		0’	0*
+		0*		-	0’
					-	0’
+			0*		0’	-

Меняем разметку L-цепи. Количество 0* увеличилось на один.

Метки	+			+
	-			0*
	0*	-
+			-		0*
+		0*		-	0’
					-	0*
+			0*		0’	-

Снимаем пометки строк и столбцов.

Метки
	-			0*
	0*	-
			-		0*
		0*		-
					-	0*
			0*			-

Имеем систему независимых нулей. Проецируем её на исходную матрицу.

Метки
	-			0*
	0*	-
			-		0*
		0*		-	0’
					-	0*
			0*		0’	-

Получаем

-
	-
		-
			-
				-
					-

Z*=6

Дата добавления: 2015-09-28