НАЗНАЧЕ́НИЙ ЗАДА́ЧА

НАЗНАЧЕ́НИЙ ЗАДА́ЧА, за­да­ча по­ис­ка та­ко­го рас­пре­де­ле­ния ра­бот (долж­но­стей) по ис­пол­ни­те­лям (ра­бот­ни­кам, ма­ши­нам и т. п.), при ко­то­ром по­лу­ча­ет­ся наи­боль­ший эф­фект. Точ­нее, пусть име­ет­ся $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.$$

Эта за­да­ча яв­ля­ет­ся за­да­чей це­ло­чис­лен­но­го ли­ней­но­го про­грам­ми­ро­ва­ния