Algoritm Ungar - Kuhn

ALGORITMUL UNGAR (KUHN)

Problemele de repartitie sunt probleme în care se urmareste cuplarea a p subiecti cu q subiecti, iar rezolvarea unei probleme de repartitie consta în determinarea cuplajului maxim care se face cu ajutorul algoritmului ungar. Acesta cuprinde 6 etape:

1) Se formeaza matricea C patratica de ordinul p daca p > q si de ordinul q daca p < q.

2) Obtinerea de zerouri. Se scade minorantul fiecarei linii din toate elementele liniei respective obtinând astfel cel putin câte un „0” pe fiecare linie a matricei C. Daca în urma acestei operatii exista coloane care nu contin „0”, se scade minorantul fiecarei coloane în cauza din toate elementele coloanei respective. Se obtine astfel cel putin câte un „0” pe fiecare linie si coloana a matricei C.

3) În matricea C1 obtinuta din matricea C dupa parcurgerea etapei a doua se cauta un cuplaj maxim prin operatia de încadrare si barare de zerouri astfel:

- se încadreaza un „0” situat pe linia cu cele mai putine zerouri si se bareaza (taie) toate celelalte zerouri asezate pe linia si coloana zeroului încadrat;

- se repeta aceasta operatie pâna când toate zerourile matricei C1 au fost încadrate sau barate.

Daca se obtine câte un „0” încadrat pe fiecare linie si coloana, s-a obtinut cuplajul maxim. În caz contrar se trece la etapa urmatoare.

4) Cautarea unui cuplaj maxim printr-o marcare a liniilor si coloanelor astfel:

- se marcheaza liniile care nu contin nici un „0” încadrat;

- se marcheaza coloanele care contin zerouri taiate pe liniile deja marcate;

- se marcheaza liniile care contin un „0” încadrat pe coloanele deja marcate;

- se repeta aceste operatii pâna când nu mai este posibil sa se obtina alte linii sau coloane marcate.

5) În matricea C1 se taie toate liniile nemarcate si coloanele marcate. Minorantul elementelor ramase netaiate se adauga elementelor dublu taiate, se scade din elementele netaiate, lasând neschimbate elementele simplu taiate. Se obtine o noua matrice C2.

6) Pe matricea C2 se repeta procedeul de încadrare si taiere a zerourilor. Se procedeaza în continuare asa cum s-a aratat mai sus, pâna când se obtine câte un „0” încadrat pe fiecare linie si coloana, deci se obtine cuplajul maxim. Solutia optima poate sa nu fie unica.

Aplicatie 1. Se considera 4 beneficiari care urmeaza sa se aprovizioneze cu marfa de la 7 centre de distributie. Distantele de transport (în km) sunt date în tabloul urmator. Sa se determine repartitia optima a beneficiarilor pe centre de distributie careia îi corespunde o distanta totala de transport minima cu conditia ca fiecare beneficiar sa aprovizioneze cel putin de la un centru si cel mult de la doua.