НАЗНАЧЕ́НИЙ ЗАДА́ЧА
-
Рубрика: Математика
-
Скопировать библиографическую ссылку:
НАЗНАЧЕ́НИЙ ЗАДА́ЧА, задача поиска такого распределения работ (должностей) по исполнителям (работникам, машинам и т. п.), при котором получается наибольший эффект. Точнее, пусть имеется $n$ вакантных должностей (работ), на которые претендуют $m$ работников, $m{⩾}n$. Эффективность $j$-го претендента на $i$-й должности задаётся величиной $c_{ij}$. Требуется назначить на каждую должность работника (из числа претендентов) так, чтобы общая эффективность назначений была максимальной. В наиболее известном варианте Н. з. $m=n$.
В Н. з. обычно вводятся переменные $x_{ij}$, которые принимают значение 1 в случае назначения $j$-го претендента на $i$-ю должность и 0 в противном случае, тогда Н. з. формализуется следующим образом: $$\sum_{i=1}^n \sum_{j=1}^m c_{ij}x_{ij}\rightarrow \text{max,}$$ $$\sum_{j=1}^m x_{ij}=1, i\in N=\{1, ..., n\},$$ $$\sum_{i=1}^n x_{ij} {⩽} 1, j \in M=\{1, ..., m\},$$ $$x_{ij}∈\{0, 1\}, i∈N, j∈M.$$
Эта задача является задачей целочисленного линейного программирования и решается методами, разработанными в этом разделе математики.