Задача о назначениях является частным случаем транспортной задачи, в котором все значения ai и bj равны 1. Такая задача возникает при распределении людей на должности или работы, водителей на машины, рабочих на станки, автомашин на маршруты, групп по аудиториям и т.п.
Постановка задачи (об оптимальном закреплении исполнителей на работы). Имеется n видов работ и n исполнителей этих работ. Известна эффективность cij выполнения исполнителем i работы j. Требуется так назначить исполнителей по видам работ, чтобы суммарный эффект от назначений был максимальным.
Часто исходные данные задачи о назначениях записывают в виде таблицы (матрицы) планирования:
Работы Исполнители | B 1 | B 2 | ¼ | B n | Число исполнителей |
A 1 | c 11 | c 12 | ¼ | c 1n | |
A 2 | c 21 | c 22 | ¼ | c 2n | |
¼ | ¼ | ¼ | ¼ | ¼ | ¼ |
A n | c n1 | c n2 | ¼ | c nn | |
Количество работ | ¼ |
Составим экономико-математическую модель (задача о назначениях относится к двухиндексным задачам линейного программирования):
|
|
1) вводим переменные: , где
2) задаем целевую функцию , которая выражает суммарный эффект от назначений;
3) из условий задачи составляем ограничения:
a) каждый исполнитель должен быть назначен на работу, т.е.
;
b) на каждую работу должен быть назначен исполнитель, т.е.
.
Таким образом, модель задачи о назначениях имеет следующий вид:
Найти минимальное значение целевой функции | |
(11.1) | |
при ограничениях | |
, | (11.2) |
, | (11.3) |
, , . | (11.4) |
Замечание. Если число исполнителей m не равно числу работ n (т.е. задача является открытой), то возможно применение двух способов:
1) решение открытой задачи о назначениях сводим к решению закрытой задачи о назначениях; для этого вводим фиктивных исполнителей или фиктивные виды работ;
2) изменяем ограничения 11.2 и 11.3:
a) если число исполнителей m больше числа работ n, то
; ;
b) если число исполнителей m меньше числа работ n, то
; .