Voi prezenta in continuare problema afectarii impreuna cu una din cele mai eficiente solutii pentru rezolvarea ei: _Algoritmul lui Kuhn_. In ultima parte a articolului, voi oferi un exemplu de implementare usor de folosit in concursurile de informatica. Se presupun cunoscute notiunile de *cuplaj maxim* si *suport minim* intr-un graf bipartit, precum si modul de obtinere a unui cuplaj maxim intr-un graf bipartit cu ajutorul drumurilor de crestere. Sa incepem cu definitia problemei discutate.

*Problema de afectare*: Exista {$m$} muncitori si $n$ lucrari, fiecare muncitor putand efectua una sau mai multe lucrari. Notam muncitorii cu $x{~1~}$ , $x{~2~}$, ..., $x{~m~}$, lucrarile cu $y{~1~}$, $y{~2~}$ , ..., $y{~n~}$, si asociem costul $v{~ij~}$ ≤ $0$ efectuarii de catre muncitorul $x{~i~}$ a lucrarii $y{~j~}$, faptul ca $v{~ij~}$ = ∞ avand semnificatia ca muncitorul $x{~i~}$ nu poate efectua lucrarea $y{~j~}$. Sa se gaseasca o repartizare a celor $m$ muncitori la cele $n$ lucrari astfel incat un muncitor sa efectueze cel mult o lucrare, iar o lucrare sa fie efectuata de cel mult un muncitor, cu conditia ca costul total de executie sa fie minim.
 
 

*Problema de afectare*: Exista _m_ muncitori si _n_ lucrari, fiecare muncitor putand efectua una sau mai multe lucrari. Notam muncitorii cu _x ~1~_ , _x ~2~_ , ..., _x ~m~_ , lucrarile cu _y ~1~_ , $y ~2~$ , ..., _y ~n~_ , si asociem costul _v ~ij~_  ≤ $0$ efectuarii de catre muncitorul _x ~i~_  a lucrarii _y ~j~_ , faptul ca _v ~ij~_  = ∞ avand semnificatia ca muncitorul _x ~i~_  nu poate efectua lucrarea _y ~j~_ . Sa se gaseasca o repartizare a celor _m_ muncitori la cele _n_ lucrari astfel incat un muncitor sa efectueze cel mult o lucrare, iar o lucrare sa fie efectuata de cel mult un muncitor, cu conditia ca costul total de executie sa fie minim.