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.