Метод оптимальных решений

В данной задаче требуется  максимизировать целевую функцию Р, представляющую суммарную производительность. Для перехода к стандартной транспортной модели надо заменить функцию Р на противоположную функцию Р'= -Р, которую нужно будет минимизировать.

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

 

4.5.2. Формирование  оптимального штата фирмы         

 

Фирма набирает штат сотрудников. Она располагает и группами различных  должностей по b_j вакантных единице каждой группе,  . Кандидаты для занятия должностей проходят тестирование, по результатам которого их разделяют на т групп по  , кандидатов в каждой группе,  . Для каждого кандидата из i -й группы требуются определенные затраты с_ij на обучение для занятия j -й должности,  , . (В частности, некоторыес_ij = 0, т. е. кандидат полностью соответствует должности, или с_ij: = ∞, т. е. кандидат вообще не может занять данную должность.) Требуется распределить кандидатов на должности, затратив минимальные средства на их обучение.

Предположим, что общее  число кандидатов соответствует  числу вакантных должностей. (Если это не так, то следует просто проделать  преобразования параграфа 3.3). Тогда  данная задача соответствует транспортной модели. В роли поставщиков выступают  группы кандидатов, а в роли потребителей — группы должностей. Предложением является число кандидатов в каждой группе, спросом – число вакансий в каждой группе должностей. В качестве тарифов на перевозки рассматриваются  затраты на переобучение.

Математическая модель записывается в виде

 

 

Методы решения этой задачи такие же, как и транспортной задачи.  

 

4.6. Задача  о назначениях

В общем виде задача о  назначениях формулируется следующим  бразом.

Имеется п работ и п кандидатов для их выполнения. Затраты i -го кандидата на выполнение j -й работы равны c_ij ( ). Каждый кандидат может быть назначен только на одну работу, и каждая работа может быть выполнена только одним кандидатом. Требуется найти назначение кандидатов на работы, при котором суммарные затраты на выполнение работ минимальны.

Запишем формально данную задачу. Пусть х_ij — переменная, значение которой равно 1, если i -й кандидат выполняет j-ю работу, 0 — в противном случае. Тогда условие о том, что каждый кандидат выполняет только одну работу, запишется в виде

                                          

Условие о том, что каждая работа может выполняться одним  кандидатом, запишется в виде

Целевая функция задачи имеет  вид

В функцию входят только те значения c_ij ( , ), для которых x_ij отличны от 0, т. е.. входят затраты, соответствующие назначенным работам.

Математическая модель выглядит следующим образом:

                                    

Решить задачу о назначениях  – значит найти х_ij, удовлетворяющие (4.14)–(4.16) и доставляющие минимум функции (4.13). Задача  
(4.14)–(4.16) является, очевидно, задачей линейного программирования (целевая функция линейна, ограничения линейны) и может быть решена симплекс-методом. Также задача (4.14)–(4.16) – это транспортная задача, в которой правые части ограничений равны 1, а переменные могут принимать только два значения. Однако относительно простая форма задачи позволила разработать для ее решения достаточно простые методы, один из которых – венгерский. 

 

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

 

Для решения задачи о назначениях  составляют таблицу (табл. 4.8): 

 

Таблица 4.8

№	1	2	…	j    ■	...	n
1	c11	c12	...	c1j	...	c1n
2	c21	с22	…	c2j		c2n
...	...	...	…	...	...	...
i	ci1	ci2	…	cij	...	cin
…	…	…	…	…	…	…
n	cn1	cn2	…	cnj	…	cnn

 

 

В левой колонке записаны номера кандидатов, в верхней строке – номера работ. В i-й строке j-м столбце стоят затраты на выполнение i-м кандидатом j -й работы.

В венгерском методе используется следующий принцип: оптимальность  решения задачи о назначениях  не нарушается при уменьшении (увеличении) элементов строки (столбца) на одну и ту же величину. Решение считается  оптимальным, если все измененные образом  затраты с'_ij 0, ( , ) и можно отыскать такой набор х_ij, что 

Алгоритм метода содержит следующие шаги.

Шаг 1. Получение нулей в каждой сроке. Для этого в каждой строке определяют наименьший элемент, и его значение отнимают от всех элементов этой строки. Переход к шагу 3.

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

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

Шаг 4. Поиск минимального набора строк и столбцов, содержащих все нули.

Для этого необходимо отметить:

1) все строки, в которых  не имеется ни одного отмеченного  нуля;

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

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

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

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

Шаг 5. Перестановка некоторых нулей.

Взять наименьшее число из тех клеток, через которые проведены  прямые. Вычесть его из каждого  числа, стоящего в невычер-кнутых столбцах и прибавить к каждому числу, стоящему в вычеркнутых строках. Эта операция не изменяет оптимального решения, после чего весь цикл расчета  повторить, начиная с шага 3.

Пример 4.6

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

Матрица времен приведена  ниже

В i -й строке j -м столбце матрицы T стоит время на выполнение i-м ученым j-го проекта.

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

Решение.

Данная задача, очевидно, является задачей о назначениях. В качестве работ рассматриваются  исследовательские проекты, в качестве кандидатов — ученые, претендующие на роль научных руководителей.

Введем переменные x_ij. 

 

	если i-й ученый – научный руководитель j-го проекта,
	в противном случае.

 

 

Целевая функция задачи имеет  вид

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

Таблица 4.9

№	1	2	3	4
1	3	7	5	8	3
2	2	4	4	5	2
3	4	7	2	8	2
4	9	7	3	8	3

 

 

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

Таблица 4.10

№	1	2	3	4
1	0	4	2	5
2	0	2	2	3
3	2	5	0	6
4	6	4	0	5
	0	2	0	3

 

 

Отнимем минимальные элементы из соответствующих столбцов. Перейдем к табл. 4.11.

Таблица 4.11

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

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

Число отмеченных нулей равно 3, т. е. назначение не является полным. Перейдем к шагу 4 алгоритма.

Найдем минимальный набор  строк и столбцов, содержащий все  нули (табл. 4.12).

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