Probleme Cercetari Operationale

Extras din referat Cum descarc?

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.

Fisiere in arhiva (1):

 Probleme Cercetari Operationale.doc