2015-02-27
1752
Задача о назначениях является частным случаем транспортной задачи, в котором все значения 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, то
; 
.
