Probleme cercetări operaționale

Problema 1

Definirea problemei

Se considera problema de afectare simpla a 5 lucrari la 5 angajati cu datele din tabelul 1.

Sa se determine cu METODA TABLOULUI numarul maxim de lucrari atribuite. Se va pleca de la atribuirea : L2->A5, L3->A3, L4->A4, L1 si L5 ramanand nerepartizate. La fiecare iteratie se va diagrama marcajelor.

tabelul 1

A1 A2 A3 A4 A5

L1 x x x x 1

L2 1 x x 1 1

L3 x x 1 x 1

L4 1 1 x 1 x

L5 x x 1 x x

Rezolvarea problemei

-se porneste de la cuplajul dat respectiv M={ (L2,A5), (L3,A3), (L4,A4)}

-se marcheaza celule care fac parte din cuplaj si liniile care nu fac parte din cuplaj

A1 A2 A3 A4 A5

*L1 x x x x 1

L2 1 x x 1 1*

L3 x x 1* x 1

L4 1 1 x 1* x

*L5 x x 1 x x

situatia 1

P: (DA) lant de augmentare

cuplajul M’ devine: M’= ={(L1,A5),(L2,A4),(L3,A3),(L4,A2)}

|M’|=4

tabloul corespunzator cuplajului M’

A1 A2 A3 A4 A5

L1 x x x x 1*

L2 1 x x 1* 1

L3 x x 1* x 1

L4 1 1* x 1 x

*L5 x x 1 x x

P’: (NU) lant alternant

Cuplajul M’ nu poate fi inbunatatit deoarece nu se poate gasi nici un lant de augmentare.

situatia 2

P: (DA) lant de augmentare

M’= ={(L1,A5),(L2,A4),(L3,A3),(L4,A1)} |M’|=4

tabloul corespunzator cuplajului M’

A1 A2 A3 A4 A5

L1 x x x x 1*

L2 1 x x 1* 1

L3 x x 1* x 1

L4 1* 1 x 1 x

*L5 x x 1 x x

P’: (NU) lant alternant

Cuplajul M’ nu poate fi inbunatatit deoarece nu se poate gasi nici un lant de

augmentare.

situatia 3

P: (DA) lant de augmentare

M’= ={(L1,A5),(L2,A1),(L3,A3),(L4,A4)} |M’|=4

A1 A2 A3 A4 A5

L1 x x x x 1*

L2 1* x x 1 1

L3 x x 1* x 1

L4 1 1 x 1* x

*L5 x x 1 x x

P’: (NU) lant alternant

Cuplajul M’ nu poate fi inbunatatit deoarece nu se poate gasi nici un lant de

augmentare

Soutia problemei si interpretarea solutiei

Numarul maxim de lucrari ce pot fi atribuite este de 4. Desi este mai mic decat numarul de muncitori si decat numarul de lucrari, numarul lucrarilor repartizate nu poate creste datorita faptului ca in nici una din cele 3 situatii care pot exista, induse de modul de alegere a celulelor, nu exista nici un lant de augmentare care sa permita cresterea cardinalitatii cuplajului M’, si deci nici atribuirea unei lucrari unui muncitor.

Acest lucru se poate constata si privind pe tabelul 1 ca, daca lui L5 i se atribuie A3 (singura celula admisibila de pe linia 5) si lui L1 i se atribuie A5 (singura celula admisibila de pe linia 1) atunci se va observa ca pe linia 3 nu vor mai exista celule admisible care sa fie repartizate si deci L3 va remane nerepartizat.