Пример решения задачи о назначениях

На предприятии необходимо выполнить последовательно 6 видов работ (R₁÷R₆). 6 сотрудников предприятия (S₁÷S₆) затрачивают на выполнение каждого вида работ различное время в часах. Распределить работников по видам работ так, чтобы общее время на выполнение работ было минимально. Очередность выполнения работ не имеет значения. Составить экономико-математическую модель задачи и решить задачу с помощью венгерского алгоритма.

Сотрудник	Вид работ
R1	R2	R3	R4	R5	R6
S1			3,5			6,5
S2	2,5	0,5			7,5
S3			2,5
S4		0,5	2,5		8,5	5,5
S5		1,5		4,5	8,5
S6	2,5	0,7			8,5

Составляем экономико-математическую модель задачи

1. Форматируем задачу в виде транспортной таблицы

	R1	R2	R3	R4	R5	R6
S1			3,5			6,5
S2	2,5	0,5			7,5
S3			2,5
S4		0,5	2,5		8,5	5,5
S5		1,5		4,5	8,5
S6	2,5	0,7			8,5

2. Выполним приведение матрицы

3. Произведем назначение каждого сотрудника на один из видов работ:

4. Решение не оптимально, невозможно назначить всех сотрудников на выполнение работ.

5. Делаем дальнейшее преобразование матрицы

Минимальное число, через которое не проходит ни одна линия 0,5.

6. Составляем новую матрицу

7. Производим новые назначения

8. Окончательно

9. Решение

Оптимально и единственно.

Время, затрачиваемое на выполнение всех работ, составит 7+3+1+5,5+2+0,7=19,2 часов.