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

Задача о назначениях - это одна из задач линейного программирования, которая предназначена для оптимального подбора n "предложений" к n "потребностям", например, для назначения вида работы машине, назначения вида работы производственному отделу, назначения человека на должность и т.д.

Метод назначений применяется при решении задач, имеющих следующие характеристики:

1. Имеется n "предметов", которые должны быть распределены по n "пунктам назначения".

2. Каждый "предмет" должен быть назначен единственному "пункту назначения". В понятие "предмет" и "пункт назначения" может вкладываться различное смысловое значение, определяемое конкретной задачей менеджмента. Так в качестве предмета может выступать определенный вид деятельности (работы), должность, человек и т.д.

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

Например, пусть имеются четыре должности, на которые необходимо назначить четырех кандидатов, которые в этом случае становятся работниками. Каждому работнику может быть назначена единственная должность. Заметим, что количество должностей равно количеству работников. Необходимо составить матрицу, чтобы показать все возможные взаимосвязи между четырьмя должностями и четырьмя работниками. Работники представляются строками матрицы, а должности - столбцами, как показано в табл. 5.15. Ячейки матрицы содержат стоимости каждой возможной комбинации “должность-работник”. Например, стоимость назначения должности 2 работнику 2 составляет 19 условных денежных единиц. Содержимое ячеек матрицы определяет интегральную меру эффективности, которая должна минимизироваться, поскольку является стоимостью. Если содержимое ячеек матрицы представляет собой прибыль, мера эффективности должна максимизироваться.

Таблица 5.15

Матрица назначений работников на должности

Должности
Канди-
даты

Замечание: Содержимое ячеек - стоимости соответствующих комбинаций должность-работник. Cтоимость в этом примере может зависеть от квалификации потенциального работника, его опыта и т.п. Одно из возможных решений приведенной выше задачи выглядит следующим образом:

Назначить на должность 1 работника 2 - стоимость: 7;

Назначить на должность 2 работника 3 - стоимость: 6;

Назначить на должность 3 работника 1 - стоимость: 14;

Назначить на должность 4 работника 4 - стоимость: 4.

Общая стоимость этих назначений - 31. Является ли эта стоимость наименьшей? Может быть, да, а может быть, и нет. В этом примере существует 24 возможных назначения (4!). Процедура, используемая в компьютерной модели, должна определять минимальную суммарную стоимость. Приведенная выше задача может быть сформулирована как задача линейного программирования и решена с использованием модуля линейного программирования. Однако легче и эффективнее для решения задач подобного типа использовать метод назначений, который состоит из следующих четырех шагов.

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

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

3. "Линейный тест". В матрице назначений провести минимальное число линий (горизонталей (по строкам) и/или вертикалей (по столбцам)), вычеркивающих все нулевые ячейки матрицы. Если минимальное число вычеркнутых строк и столбцов равно n, оптимальное решение найдено, т.к. назначения должны быть произведены в "пункты", соответствующие нулевым ячейкам матрицы. В противном случае, если минимальное число вычеркнутых строк и столбцов< n, перейти к шагу 4.

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

Проиллюстрируем этот алгоритм на примере решения задачи о назначении 5 видов работ любой из 5 машин (n=5). Матрица стоимостей каждой комбинации работа/машина приведена в табл. 5.16.

Таблица 5.16

Матрица назначений, содержащая затраты на выполнение работ

каждой машиной, тыс.руб.

Машины
Работа	A	B	B	D	E

Процедура решения задачи приведена ниже.

Шаг 1: приведение строк - наименьшее значение вычитается из содержимого всех ячеек в строке матрицы.

Машины
Работы	A	B	B	D	E

Шаг 2: приведение столбцов - наименьшее значение вычитается из содержимого всех ячеек в столбце матрицы.

Машины
Работы	A	B	C	D	E

Шаг 3: выполнение "линейного теста" - число линий, вычеркивающих все нулевые ячейки, равно 4; т.к. n=5, перейти к шагу 4.

Машины
Работы	A	B	C	D	E
		3	1		0
		0	5		1
		1	0		2
		0	2		1
	0	3	1	0	2

Шаг 4: Наименьшее значение среди содержимого невычеркнутых ячеек равно 1, 1 вычитается из содержимого всех невычеркнутых ячеек матрицы, 1 добавляется к содержимому ячеек, находящихся на пересечении строк и столбцов матрицы.

Машины
Работы	A	B	C	D	E
		3			0
		0			1
	2	2	0	1	3
		0			1
	0	4	1	0	3

Оптимальное решение, найденное с помощью "линейного" теста

Машины
Работы	A	B	C	D	E
	1	3	0	2	0
	1	0	4	1	1
			0
	4	0	1	0	1
	0	4	1	0	3

Оптимальные назначения и их стоимости:

работа 1 - машине E (стоимость 3);

работа 2 - машине B (стоимость 4);

работа 3 - машине C (стоимость 2);

работа 4 - машине D (стоимость 5);

работа 5 - машине A (стоимость 3).

Суммарная стоимость 17 тыс. р.

Нематематическое логическое обоснование метода назначения - минимизировать потери прибыли. Например, при назначении работы 1 машине A вместо машины E убыток составит 2 тыс. р. (5-3).

Метод решения задачи назначений требует, чтобы количество должностей и кандидатов было равным. Если это условие не выполняется, компьютер должен увеличить матрицу так, чтобы она стала квадратной. Например, если 5 работников претендуют на 4 должности, компьютер дополнит матрицу до размера 5х5 за счет введения фиктивной должности. Все значения стоимостей для фиктивной должности должны полагаться равными нулю, как показано в табл. 5.17. Заметим, что стоимость назначения работника 5 должна быть определена и включена в соответствующие ячейки матрицы.

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

Таблица 5.17

Расширенная матрица назначений - 4 должности для 5 кандидатов

Должности
Канди-
даты

Замечание: Ячейки содержат стоимости назначений.

Таблица 5.18

Расширенная матрица назначений - 6 должностей для 4 кандидатов