Решение задачи традиционными методами. Алгоритм решения. Для решения задач данного типа разработано множество методов

Алгоритм решения. Для решения задач данного типа разработано множество методов. Рассмотрим самый распространенный – итерационный метод Эгервари-Куна. Студент должен в нем разобраться и уметь объяснить.

Алгоритм включает четыре основных этапа. Для поиска оптимального решения потребуется не более чем m ‑ 2 последовательно проводимых итераций.

1. Получение нулей в каждой строке и каждом столбце. Находим наименьший элемент в каждой строке исходной таблицы (табл. 1), вычитаем его из всех ее элементов и получаем новую таблицу (табл. 2). Аналогично производим действия для каждого столбца новой таблицы (табл. 2). Получаем табл. 3.

2. Проверка решения на оптимальность. Ищем строку с наименьшим числом нулей (в нашей задаче это строка 3), отмечаем звездочкой один из них и зачеркиваем все остальные нули строки и столбца, где есть нуль со звездочкой

 

Таблица 1.

В этой таблице и ниже О(i) и К(i) – соответственно блоки и группы.

	O(1)	O(2)	O(3)	O(4)	O(5)
K(1)
К(2)
К(3)
К(4)
К(5)

 

 

Таблица 2

	O(1)	O(2)	O(3)	O(4)	O(5)
K(1)
К(2)
К(3)
К(4)
К(5)

 

Аналогичные операции последовательно выполняем для всех строк. Если число нулей, отмеченных звездочкой, равно m, то решение является неоптимальным, в противном случае следует переходить к очередному шагу. В нашей задаче количество отмеченных звездочкой нулей не равно m, следовательно, решение неоптимально (табл. 4). Переходим к следующему этапу.

 

Таблица 3

	O(1)	O(2)	O(3)	O(4)	O(5)
K(1)
К(2)
К(3)
К(4)
К(5)

 

Таблица 4

	O(1)	O(2)	O(3)	O(4)	O(5)
K(1)	0D				0*
К(2)	0*
К(3)			0*
К(4)			0D
К(5)			0D	0*

 

Замечание:

0 D- в таблице 4 и других означает «перечеркнутый ноль»

 

3. Поиск минимального набора строк и столбцов, содержащих нули. Необходимо отметить звездочкой:

а) все строки, не имеющие ни одного отмеченного звездочкой нуля (табл. 5, строка 4);

б) все столбцы, содержащие перечеркнутый нуль хотя бы в одной из отмеченных звездочкой строк (табл. 5, столбец 3);

в) все строки, содержащие отмеченные звездочкой нули хотя бы в одном из помеченных столбцов (табл. 5, строка 3), Далее поочередно повторяются действия б) и в) до тех пор, пока есть что отмечать.

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

4. Перестановка некоторых нулей. В не вычеркнутых клетках (табл. 5, число 20) наименьший элемент вычитается из каждого элемента для непомеченных столбцов и прибавляется к каждому элементу непомеченной строки. Результаты расчета вносятся в новую таблицу (см. табл. 6).

 

Таблица 5

	O(1)	O(2)	O*(3)	O(4)	O(5)
K(1)	0D		20		0*
К(2)	0*
К*(3)			0*
К*(4)
К(5)	30			0*

 

Таблица 6

	O*(1)	O(2)	O*(3)	O*(4)	O*(5)
K*(1)	0*		20	20	0
К*(2)	0D			0*
К*(3)	20D		0D
К*(4)			0*	20D
К(5)	30	0*		0D

 

Эта операция не изменяет оптимального решения. После нее выполняется новая итерация, цикл расчета начинается с этапа 2, и так до тех пор, пока не будет получено оптимальное решение. Поскольку число нулей, отмеченных звездочкой, не равно m, выполняется новый итерационный цикл, по завершении которого находится оптимальное решение (табл. 7).

 

Таблица 7

	O(1)	O(2)	O(3)	O(4)	O(5)
K(1)	0D				0*
К(2)	0*	0D		0D
К(3)	0D		0*
К(4)		0D	0D	0*
К(5)		0*

 

Согласно ему распределение групп по блокам должно быть проведено так:

• первая группа разрабатывает пятый блок;

• вторая - первый;

• третья - третий;

• четвертая - четвертый;

• пятая - второй,

при этом себестоимость выполнения всех работ будет минимальной и составит Y_мин. = 220 условных единиц