Probleme de afectare

Notiuni fundamentale:

in general, pentru situatiile care necesita la rezolvare un oarecare efort mintal (si un caz tipic este cel al celor din economie), se cauta, in primul rand, o metoda de reprezentare a lor care sa permita receptarea intregii probleme dintr-o privire (pe cat posibil) si prin care sa se evidentieze cat mai clar toate aspectele acesteia.

in acest scop se folosesc imagini grafice gen diagrame, schite, grafice etc. O reprezentare dintre cele mai utilizate este cea prin grafuri. Acestea sunt utilizate in special pentru vizualizarea sistemelor si situatiilor complexe. in general, vom reprezenta componentele acestora prin puncte in plan iar relatiile (legaturile, dependentele, influentele etc) dintre componente prin arce de curba cu extremitatile in punctele corespunzatoare. intre doua puncte pot exista unul sau mai multe segmente (in functie de cate relatii dintre acestea, care ne intereseaza, exista) iar segmentelor li se pot asocia sau nu orientari (dupa cum se influenteaza cele doua componente intre ele), numere care sa exprime intensitatea relatiilor dintre componente etc.

Este evident, totusi, ca aceasta metoda are limite, atat din punct de vedere uman (prea multe puncte si segmente vor face desenul atat de complicat incat se va pierde chiar scopul pentru care a fost creat - claritatea si simplitatea reprezentarii, aceasta devenind neinteligibila) cat si din punct de vedere al tehnicii de calcul (un calculator nu poate "privi" un desen ca un om).

Din acest motiv, alaturi de expunerea naiv-intuitiva a ceea ce este un graf, data mai sus, se impune atat o definitie riguroasa cat si alte modalitati de reprezentare a acestora, adecvate in general rezolvarilor matematice.

in practica economica sunt foarte des intalnite probleme in care se doreste asocierea optima a elementelor unei multimi X = {x1, x2, , xn} cu elementele unei alte multimi Y = {y1, y2, , ym} in conditiile unor limitari existente (si cunoscute) ale posibilitatilor de asociere.

in general, fiecare asociere posibila xi - yj aduce un anumit efect aij (profit, cost etc) care poate fi calculat si vom presupune ca este cunoscut.

Limitarile asupra asocierilor se traduc de obicei prin faptul ca:

1.Un element xi poate fi asociat doar cu anumite elemente din Y si reciproc;

2.La sfarsit, fiecarui element din X i s-a asociat cel mult un element din Y si reciproc.

Asocierea optima presupune, de obicei, doua obiective:

1.Sa se faca maximul de asocieri;

2.Suma efectelor asocierilor sa fie maxima (sau minima, in functie de semnificatia acestora).

Reprezentarea geometrica a situatiei de mai sus este un graf de forma:

numit graf bipartit.

Definitia 1: Se numeste graf bipartit un graf G = (X, U) in care multimea nodurilor poate fi impartita in doua multimi disjuncte A si B astfel incat orice arc are extremitatea initiala in A si cea finala in B.

Definitia 2: Se numeste cuplaj al unui graf bipartit o submultime de arce W - U cu proprietatea ca nu exista doua arce adiacente (sau altfel spus, pentru orice nod exista cel mult un arc incident acestuia).

Definitia 3: Se numeste cuplaj maxim un cuplaj cu proprietatea ca orice arc care nu face parte din cuplaj este adiacent cu un arc din cuplaj ( - orice arc am adauga, nu mai ramane cuplaj - nu exista nici un cuplaj in care sa se includa strict - contine numarul maxim de arce neadiacente)

Este evident ca numarul de arce ale unui cuplaj este mai mic sau egal cu numarul de elemente din fiecare din multimile A si B (- min (a- ,- B- ). Este interesant de vazut insa cat de mare este el efectiv si in ce conditii este egal chiar cu min (a- ,- B- ).

Referitor la prima intrebare, in 1931 Konig a demonstrat o teorema care permite stabilirea numarului de arce ale unui cuplaj maxim:

Teorema: Numarul maxim de arce ale unui cuplaj intr-un graf bipartit G = (A- B, - ) este egal cu

in ceea ce priveste a doua problema, observam mai intai ca putem presupune ca intotdeauna a- - - B- , in caz contrar inversand sensul tuturor arcelor grafului, problema ramanand aceeasi.

in acest caz:

= a- - - a- = 0 - = 0 -

- = 0 - oricare ar fi C - A

Olaru E.,Introducere in teoria grafurilor, UAIC 1975

Tomescu I.,Grafuri si programare liniara, EDP 1975

Sursa Internet:

http://infoarena.ro/algoritm-kuhn