Практикум по дискретной математике в среде виртуальной лаборатории системы ДО ИТМО (стр. 11 )

+			+
2	3	5	0*
0*	0	2	4
0	0*	0’	4	+
0	0	5	3

Во 2-м столбце есть еще один невыделенный нуль, он располагается во второй строке, в которой также имеется 0*. Помечаем этот невыделенный нуль штрихом. Над первым столбцом снимаем знак выделения.

			+
2	3	5	0*
0*	0’	2	4	+
0	0*	0’	4	+
0	0	5	3

Просматриваем нули первого столбца. Элемент с31 = 0 нельзя выделить, так как он находится в ранее выделенной строке. Поэтому выделяем с41 = 0, помечаем его штрихом. В 4-й строке нет 0*, поэтому выделение нулей заканчивается:

			+
2	3	5	0*	+
0*	0’	2	4	+
0	0*	0’	4	+
0’	0	5	3

Строим цепочку нулей, начиная с последнего выделенного 0'. Это элемент с41. Включаем в цепочку 0*, расположенный в одном столбце с элементом с41. Это элемент с21. Далее ищем и включаем в цепочку 0', расположенный в одной строке с с21 и т. д. В результате образуется цепочка с41 -> с21 -> с22 -> с32 -> с33:

			+
2	3	5	0*	+
0*	0’	2	4	+
0	0*	0’	4	+
0’	0	5	3

Изменяем метки у нулей цепочки. Уничтожаем метку «*» у 0*, а 0' меняем на 0*. Убираем все метки строк и столбцов:

2	3	5	0*
0	0*	2	4
0	0	0*	4
0*	0	5	3

Подсчитываем число независимых нулей k=4=n. Задача решена. Получаем оптимальный план:

	0	0	0	1
Х* =	0	1	0	0
	0	0	1	0
	1	0	0	0

1+4+12+11=28

2.8.2. Метод на основе принципа максимина

1.  Присваиваем s=0, где s - суммарная цена назначения.

2.  В каждой строке i матрицы А определяем минимальный элемент аij0, где j0 - номер столбца, в котором расположен минимальный элемент.

3.  В каждом столбце j матрицы А определяем минимальный элемент ai0j, где i0 - номер строки, в которой находится минимальный элемент.

4.  Определяем максимальный элемент ai*j* = max (aij0, ai0j).

5.  Элемент ai*j* определяет назначение строки i* столбцу j*. Удаляем строку i* и столбец j* из матрицы (записываем в них Б -¥).

6.  Определяем s = s + ai*j*.

7.  Если удалены все строки и столбцы, то переходим к п.8, в противном случае - к п.2.

8.  Конец алгоритма.

Пример: Рассмотрим в качестве примера следующую матрицу назначений [15]:

	5	7	10	3	3
	4	11	7	6	3
С =	3	5	6	7	4
	4	7	6	10	9
	5	5	7	6	5

1-ое назначение:

							Сij0		j0
	5	7	10	3	3		3		5
	4	11	7	6	3		3		5
С =	3	5	6	7	4		3		1
	4	7	6	10	9		4		1
	5	5	7	6	5		5		1
Сi0j	3	5	6	6	3
i0	3	3	3	2	1

Выбран элемент С33, имеющий максимальный минимум (6).