Algoritmul lui Kuhn(Ungar)

Introducere

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₁ , x₂, ..., x_m, lucrarile cu y₁, y₂ , ..., 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.