Barb acioru Iuliana Carmen - Universitatea "Constantin · PDF file ·...

Cercet¼ari operationale

B¼arb¼acioru Iuliana Carmen

SEMINARUL 2

Determinarea drumului de valoare optim¼a* Retele de transport

2

Cuprins

2 Determinarea drumului de valoare optim¼aRetele de transport 52.1 Algoritmul Bellman- Kalaba . . . . . . . . . . . . . . . . . . . . . . 62.2 Algoritmul Ford-Fulkerson . . . . . . . . . . . . . . . . . . . . . . . 9

Index 15

Pentru etapele algoritmului Bellman- Kalaba studiaz¼a Cursul 2Pentru etapele algoritmului Ford-Fulkerson studiaz¼a Cursul 3

3


4

Seminarul 2

Determinarea drumului devaloare optim¼aRetele de transport

5


2.1 Algoritmul Bellman- Kalaba

cij =

8>><>>:v (xi; xj) dac�a (xi; xj) 2 U (i 6= j)1 dac�a (xi; xj) =2 U (i 6= j)0 dac�a i = j

(3.6)

cij =

8<: vi = mini6=j

(vi + cij) i = 1; n� 1, j = 1; n� 1

vn = 0(3.7)

8<: v(k)i = min

i6=j

�v(k�1)i + cij

�i = 1; n� 1, j = 1; n , k = 1; 2; :::

v(k)n = 0

(3.8)

Observatia 2.1.1 Pentru aplicarea algoritmului Bellman- Kalaba în vederea de-termin¼arii drumului de valoare maxim¼a se introduc urm¼atoarele modi�c¼ari:

1. La de�nirea elementelor matricei C, dac¼a (xi; xj) =2 U atunci cij = �1.

2. În relatiile (3.7) si (3.8) se înlocuieste operatorul de minim cu operatorulde maxim.

Exemplul 2.1.2 S¼a presupunem c¼a graful de mai jos pune în evident¼a leg¼aturiletehnologice si economice dintre activit¼atile necesare în derularea unui proiect com-plex ce constau în construirea unui obiectiv economic. Fiecare arc al grafuluiconstituie o activitate a proiectului iar indicatorii vij = v(xi; xj) � 0 atasatiacestora reprezint¼a duratele de executie a activit¼atilor (xi; xj). Se pune problemadetermin¼arii duratei totale de executie a proiectului.

Pentru etapele algoritmului Bellman- Kalaba studiaz¼a Cursul 2

6

Cercet¼ari Operationale Seminarul 2

Solutie: Durata total¼a de executie a proiectului este dat¼a de drumul devaloare maxim¼a care uneste vârful initial cu cel �nal al grafului. Atas¼am grafuluimatricea C = (cij)1�i;j�6 în care elementele cij sunt de�nite de relatia (3.6) sitinând cont de observatia 2.1.1.

x1 x2 x3 x4 x5 x6

C =

x1

x2

x3

x4

x5

x6

0BBBBBBBBB@

0 5 14 15 10 �1�1 0 �1 11 4 �1�1 �1 0 12 �1 18

�1 �1 �1 �1 0 10

�1 �1 �1 6 0 19

�1 �1 �1 �1 �1 0

1CCCCCCCCCAVom trece matricea atasat¼a grafului în tabelul Tabelul 3.3. Acest tabel maicontine, pe lâng¼a elementele matricei C , vectorii linie v(k)i ,k = 1; 2; 3; ::: calculati pe baza relatiei (3.8) în care se înlocuieste operatorulde minim cu cel de maxim (vezi observatia 2.1.1). Se observ¼a c¼a vectorul v(0)is-a obtinut prin transpunerea ultimei coloane a matricii C. Pentru calculareaelementelor v(1)i s-a efectuat suma între elementele vectorului v(0)i si elementelecorespunz¼atoare ale rândului i (i = 1; 2; :::; 6) a matricii C pentru i 6= j. Dintresumele corespunz¼atoare �ec¼arui rând s-a ales valoarea maxim¼a.

Tabelul 3.3

x1 x2 x3 x4 x5 x6

x1 0 5 14 15 10 �1x2 �1 0 �1 11 4 �1x3 �1 �1 0 12 �1 18

x4 �1 �1 �1 0 �1 10

x5 �1 �1 �1 6 0 19

x6 �1 �1 �1 �1 �1 0

v(0)i �1 �1 18 10 19 0

v(1)i 32 23 22 10 19 0

v(2)i 36 23 22 10 19 0

v(3)i 36 23 22 10 19 0

(Tabelul 3.3)

7


Spre exemplu:

v(1)1 = max f�1+ 0;�1+ 5; 18 + 14; 10 + 15; 19 + 10; 0�1g = 32v(1)2 = max f�1�1;�1+ 0; 18�1; 10 + 11; 19 + 4; 0�1g = 23; etc:

Pentru obtinerea lui v(2)i se însumeaz¼a elementele vectorului v(1)i cu elementelecorespunz¼atoare ale rândului i (i = 1; 2; :::; 6) a matricei C, retinându-se pentru�ecare rând valoarea maxim¼a. Spre exemplu:

v(2)1 = max f32 + 0; 23 + 5; 22 + 14; 10 + 15; 19 + 10; 0�1g = 36v(2)2 = max f32�1; 23 + 0; 22�1; 10 + 11; 19 + 4; 0�1g = 23; etc:

Cum v(3)i = v

(2)i rezult¼a c¼a ne oprim, obtinându-se solutia optim¼a. Valoarea

maximal¼a a drumului de la x1 la x6 este v(3)1 = 36. Determinarea vârfurilor prin

care trece drumul se face astfel:

v(3)1 = max

j 6=1

�v(2)j + c1j

�= max

nv(2)2 + c12; v

(2)3 + c13; v

(2)4 + c14; v

(2)5 + c15; v

(2)6 + c16

o= max f23 + 5; 22 + 14; 10 + 15; 19 + 10; 0�1g = 36:

Deci:

v(3)1 = max

j 6=1

�v(2)j + c1j

�= v

(2)3 + c13 = 36 x3

v(3)3 = max

j 6=1

�v(2)j + c3j

�= v

(2)4 + c34 = 22 x4

v(3)4 = max

j 6=1

�v(2)j + c4j

�= v

(2)6 + c46 = 10 x6

Drumul de valoare optim¼a este � = (x1; x3; x4; x6).

8


2.2 Algoritmul Ford-Fulkerson

Exemplul 2.2.1 Fie problema de transport ilustrat¼a în �gura 4.2, cu capacit¼atilimitate (primele cifre pe arce) dar si cu costuri unitare de transport (cifra depe arce din parantez¼a). S¼a se stabileasc¼a un plan de transport de la a la b astfelîncât cantitatea transportat¼a s¼a �e maxim¼a (x1 posed¼a un disponibil su�cientpentru acoperirea transportului necesar în retea).

Figura 4.2

Solutie: Introducem în retea urm¼atorul �ux:

a

('(a; x1) = 8

'(a; x2) = 6x1

('(x1; x3) = 5

'(x1; x4) = 4x2

('(x2; x3) = 6

'(x2; x6) = 2

x3

('(x3; x4) = 1

'(x3; x5) = 2x4 f'(x4; b) = 4 x3

8>><>>:'(x5; x4) = 1

'(x5; x6) = 6

'(x5; b) = 4

x6 f'(x6; b) = 2

Compar¼am valorile �uxului cu capacit¼atile de pe �ecare arc in parte, pe un drum

Pentru etapele algoritmului Ford-Fulkerson studiaz¼a Cursul 3

9


care uneste a cu b.

'(a; x1) = 8

c = 10

)' < c =) (a; x1) nesaturat si marc¼am x1 cu + a

'(x1; x4) = 4

c = 5

)' < c =) (x1; x4) nesaturat si marc¼am x4 cu + x1

'(x4; b) = 4

c = 6

)' < c =) (x4; b) nesaturat si marc¼am b cu + x4

Deci am g¼asit lantul

l1 = fa; x1; x4; bg

prin care s-a marcat iesirea b; deci �uxul existent nu este maxim. Avem:

l+1 = f(xi; xj) 2 l1 j xj are eticheta xig = f(a; x1); (x1; x4); (x4; b)gl�1 = f(xj ; xi) 2 l1 j xi are eticheta � xjg = ?

"1 = minu2l+1fc(u)� '(u)g = min f10� 8; 5� 4; 6� 4g = 1

"2 nu avem

Lu¼am

" = min f"1; "2g = "1 = 1

M¼arim �uxul cu o unitate pe arcele lui l+1 si-l micsor¼am cu o unitate pe arcele luil�1 (nu e cazul). Noul �ux va �:

a

('(a; x1) = 9

'(a; x2) = 6x1

('(x1; x3) = 5

'(x1; x4) = 5x2

('(x2; x3) = 6

'(x2; x6) = 2

x3

('(x3; x4) = 1

'(x3; x5) = 2x4 f'(x4; b) = 5 x3

8>><>>:'(x5; x4) = 1

'(x5; x6) = 6

'(x5; b) = 4

x6 f'(x6; b) = 2

Deci pe lantul l1 = fa; x1; x4; bg nu se mai poate marca iesirea b;întrucât s-a

10


saturat arcul (x1; x4):

C¼aut¼am un alt lant plecând din x1:

'(a; x1) = 9

c = 10


'(x1; x3) = 5

c = 7


'(x3; x4) = 1

c = 2


'(x4; b) = 5

c = 6


Întrucât am g¼asit lantul:

l2 = fa; x1; x3; x4; bg

prin care s-a putut marca iesirea b; �uxul existent nu este maxim. Avem:

"1 = minu2l+2fc(u)� '(u)g = min f10� 9; 7� 5; 2� 1; 6� 5g = 1

"2 nu avem

Lu¼am

" = min f"1; "2g = "1 = 1

11



a

('(a; x1) = 10

'(a; x2) = 6x1

('(x1; x3) = 5

'(x1; x4) = 6x2

('(x2; x3) = 6

'(x2; x6) = 2

x3

('(x3; x4) = 2

'(x3; x5) = 2x4 f'(x4; b) = 6 x3

8>><>>:'(x5; x4) = 1

'(x5; x6) = 6

'(x5; b) = 4

x6 f'(x6; b) = 2

S-au saturat arcele (a; x1); (x1; x4); (x3; x4); (x4; b):

C¼aut¼am un alt lant plecând din a:

'(a; x2) = 6

c = 8


'(x2; x3) = 6

c = 8


'(x3; x5) = 2

c = 3


'(x5; b) = 4

c = 5


Întrucât am g¼asit lantul:l3 = fa; x2; x3; x5; bg

12



l+3 = f(xi; xj) 2 l3 j xj are eticheta xig = f(a; x2); (x2; x3); (x3; x5); (x5; b)gl�3 = f(xj ; xi) 2 l3 j xi are eticheta � xjg = ?

"1 = minu2l+3fc(u)� '(u)g = min f10� 9; 8� 6; 3� 2; 5� 4g = 1

"2 nu avem

Lu¼am

" = min f"1; "2g = "1 = 1


a

('(a; x1) = 10

'(a; x2) = 7x1

('(x1; x3) = 5

'(x1; x4) = 6x2

('(x2; x3) = 7

'(x2; x6) = 2

x3

('(x3; x4) = 2

'(x3; x5) = 3x4 f'(x4; b) = 6 x3

8>><>>:'(x5; x4) = 1

'(x5; x6) = 6

'(x5; b) = 5

x6 f'(x6; b) = 2

S-au saturat arcele (a; x1); (x1; x4); (x3; x4); (x3; x5); (x4; b); (x5; b):

13


C¼aut¼am un alt lant plecând din a:

'(a; x2) = 7

c = 8


'(x2; x6) = 2

c = 4


'(x6; b) = 2

c = 5


Întrucât am g¼asit lantul:

l4 = fa; x2; x6; bg


l+4 = f(xi; xj) 2 l4 j xj are eticheta xig = f(a; x2); (x2; x6); (x6; b)gl�4 = f(xj ; xi) 2 l4 j xi are eticheta � xjg = ?

"1 = minu2l+4fc(u)� '(u)g = min f8� 7; 4� 2; 5� 2g = 1

"2 nu avem

Lu¼am

" = min f"1; "2g = "1 = 1


a

('(a; x1) = 10

'(a; x2) = 8x1

('(x1; x3) = 5

'(x1; x4) = 6x2

('(x2; x3) = 7

'(x2; x6) = 3

x3

('(x3; x4) = 2

'(x3; x5) = 3x4 f'(x4; b) = 6 x3

8>><>>:'(x5; x4) = 1

'(x5; x6) = 6

'(x5; b) = 5

x6 f'(x6; b) = 3

14


S-au saturat arcele (a; x1); (a; x2); (x1; x4); (x3; x4); (x3; x5); (x4; b); (x5; b):

Algoritmul se termin¼a întrucât iesirea retelei nu mai poate �marcat¼a.

15

Index

AlgoritmulBellman - Kalaba, 6Ford - Fulkerson, 9

Reteade transport, 5

16

Barb acioru Iuliana Carmen - Universitatea "Constantin · PDF file ·...

Documents

Transcript of Barb acioru Iuliana Carmen - Universitatea "Constantin · PDF file ·...