*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.
Definim *matricea de afectare* astfel: $X$ = $(x{~ij~})$, $1$ ≤ $i$ ≤ $m$, $1$ ≤ $j$ ≤ $n$, $x{~ij~}$ = $1$ daca muncitorul $x{~i~}$ efectueaza lucrarea $y{~j~}$, si $x{~ij~}$ = $0$ in caz contrar. Cand $∑{~ij~}$ = $min(m, n)$, matricea de afectare se numeste *saturanta*. Voi prezenta algoritmul elaborat in 1955 de Kuhn, numit de acesta _algoritmul ungar pentru rezolvarea problemelor de afectare definite de matrice saturante_, cunoscut si sub numele de _metoda ungara_, deoarece se bazeaza pe rezultatele a doi matematicieni maghiari: D. König si E. Egerváry. Demonstratia va presupune ca $m$ = $n$; se va vedea apoi ca algoritmul se poate extinde foarte usor la matrice care nu sunt patrate.
Definim *matricea de afectare* astfel: $X$ = $(x{~ij~})$, $1$ ≤ $i$ ≤ $m$, $1$ ≤ $j$ ≤ $n$, $x{~ij~}$ = $1$ daca muncitorul $x{~i~}$ efectueaza lucrarea $y{~j~}$, si $x{~ij~}$ = $0$ in caz contrar. Cand $∑{~ij~}$ = $min(m, n)$, matricea de afectare se numeste *saturanta*. Voi prezenta algoritmul elaborat in 1955 de Kuhn, numit de acesta _algoritmul ungar pentru rezolvarea problemelor de afectare definite de matrice saturante_, cunoscut si sub numele de _metoda ungara_, deoarece se bazeaza pe rezultatele a doi matematicieni maghiari: D. König si E. Egerváry. Demonstratia va presupune ca $m$ = $n$; se va vedea apoi ca algoritmul se poate extinde foarte usor la matrice care nu sunt patrate.
h2. Descrierea algoritmului
Algoritmul utilizeaza urmatoarea proprietate:
*Propozitia 1*: _Multimea solutiilor minime ale unei probleme de afectare nu se modifica daca la toate elementele unei linii sau coloane a matricei costurilor se aduna acelasi numar real λ._
De asemenea, este necesara cunoasterea urmatoarei teoreme:
*Teorema 1 (Teorema lui König)*: _Fie $G$ un graf bipartit, $ν(G)$ cardinalul unui cuplaj maxim in acest graf, si $τ(G)$ cardinalul unui suport minim. Atunci exista egalitatea: $ν(G)$ = $τ(G)$, adica numarul maxim de muchii ale unui cuplaj este egal cu numarul minim de varfuri ale unui suport._
Deoarece $m$ = $n$ si matricea de afectare este saturanta, orice solutie a problemei de afectare contine un singur $1$ in fiecare linie si in fiecare coloana, deci, prin transformarea matricei costurilor, costul asociat oricarei solutii creste cu λ. Din acest motiv, multimea solutiilor minime ale problemei de afectare nu se modifica prin transformari de acest tip ale matricei costurilor.
Algoritmul lui Kuhn se bazeaza si pe faptul ca o solutie a problemei de afectare corespunde unui cuplaj al grafului bipartit cu partile $X$ = {$x{~1~}$, $x{~2~}$, ..., $x{~n~}$} si $Y$ = {$y{~1~}$, $y{~2~}$, ..., $y{~n~}$}, si se desfasoara in mai multi pasi, fiind prezentat aici intr-o varianta modificata si simplificata fata de cea originala.
