I. Математическая модель задачи.
1) Переменные задачи.
Ведем переменные xij принимающие два значения:
xij=0, если i-й претендент (Pi) не принимается на j-ю вакансию (Vj).
xij=1, если i-й претендент (Pi) принимается на вакансию (Vj).
i=1,2,...7; j=1,2,...5.
2) Ограничения на переменные задачи.
Очевидно, что все переменные задачи неотрицательные и целые числа: xij 0 и xij - целые.
Кроме того, так как каждый претендент может занять только одну вакансию и все вакансии должны быть заняты, должны удовлетворяться следующие ограничения:
, j=1,2,...7 ,
, i=1,2,...5 ,
другими словами в матрице (xij) суммы элементов по каждой строке и суммы элементов по каждому столбцу должны быть равны единицам. Это условие означает, что выбор претендентов должен быть таким, чтобы в матрице (xij), представляющей решение задачи, было бы по одной единице в каждой строке и по одной единице в каждом столбце, остальные элементы матрицы должны равняться нулю.
3) Целевая функция в задаче о назначениях.
Необходимо выбрать претендентов так, чтобы суммарное число очков, набранное ими было бы максимальным. Суммарное число набранных очков вычисляется по формуле:
;
Z=c11x11+c12x12+...+c75x75=7x11+5x12+...+4x75;
Окончательная математическая модель задачи записывается так:
найти max ;
при ограничениях:
xij 0 и xij - целые числа, i=1,2,...7; j=1,2,...5;
, j=1,2,...7 ;
, i=1,2,...5 .
Таким образом, задача о назначениях есть частный случай транспортной задачи (Пример 2).