Задача назначений

Зада́ча назначе́ний, задача поиска такого распределения работ по исполнителям (работникам, машинам и т. п.), при котором получается наибольший эффект. Точнее, пусть имеется ${\displaystyle n}$ вакантных должностей (работ), на которые претендуют ${\displaystyle m}$ работников, ${\displaystyle m{\geqslant }n}$. Эффективность ${\displaystyle j}$-го претендента на ${\displaystyle i}$-ю должность задаётся величиной ${\displaystyle c_{ij}}$. Требуется назначить на каждую должность работника (из числа претендентов) так, чтобы общая эффективность назначений была максимальной. В наиболее известном варианте задачи назначений ${\displaystyle m=n}$.

В задаче назначений обычно вводятся переменные ${\displaystyle x_{ij}}$, которые принимают значение 1 в случае назначения ${\displaystyle j}$-го претендента на ${\displaystyle i}$-ю должность и 0 в противном случае, тогда задача назначений формализуется следующим образом:

${\displaystyle {\ce {\sum \limits _{i=1}^{n}\sum \limits _{j=1}^{m}c_{ij}x_{ij}->{\text{max,}}}}}$

${\displaystyle \sum \limits _{j=1}^{m}x_{ij}=1,\,i\in N=\{1,...,n\}}$,

${\displaystyle \sum \limits _{i=1}^{n}x_{ij}{\leqslant }1,\,j\in M=\{1,...,m\}}$,

${\displaystyle x_{ij}\in \{0,1\},\,i\in N,\,j\in M}$.

Эта задача является задачей целочисленного линейного программирования и решается методами, разработанными в этом разделе математики.