7/25/2019 exempu organizare

1/7

Exemplul 1:Pentru realizarea unui obiect de construcii s-a elaborat graficul reea de mai jos,

figura 1.1.Se cere s se realizeze analiza i optimizarea costului acestui program, dac se

cunosc:

Duratele normale/minime ale activitilor i costurile corespunztoare(vezi tabelul1.1);

Valoarea costurilor indirect CI=3768 u.v. aferente duratei totale DN; Variaia costului indirect pentru reducerea duratei DNcu o unitate de timp: CI*=14

u.v.

A B C D

H

E

G

I

F

Figura 1.1-Modelul grafic pentru execuia obiectului de constructie

Tabelul 1.1- Datele iniiale pentru rezolvarea problemei

Activitatea

Durata(Uniti de timp)

Costul(Uniti valorice- u.v.)

Normal MinimPentru durata

normal(qij)

Pentru durataminim

(pij)1 2 3 4 6A 14 10 2163 2203B 16 13 2215 2239C 11 8 1989 2010

D 9 6 997 1012E 16 11 2013 2053F 13 10 1872 1881G 20 16 2566 2582H 20 15 2417 2467I 6 6 1020 1020

7/25/2019 exempu organizare

2/7

Rezolvare:Utilizarea algoritmului euristic Kelly-Fulkerson presupune parcurgerea mai multor

pai, astfel:Pasul 1: Conine secvenele urmtoare:Secvena 1:Pe activitile graficului reea se trec duratele normale din tabelul 1.1,

coloana 2;

A B C D

H

E

G

I

F

1 2

3

4 6

5 7 8t=14 t=16 t=11 t=9

t=20

t=16

t=13

t=6

t=20

Figura 1.2-Graficul reea cu duratele activittilor

Secvena 2:Se calculeaz termenele nodurilor;

A B C D

H

E

G

I

F

1 2

3

4 6

5 7 8t=14 t=16 t=11 t=9

t=20

t=16

t=13

t=6

t=20

0 14 30 46 55

16

20 4020 40

46 5535190

20

Figura 1.3-Calculul termenelor minime i maxime

Secvena 3:Se calculeaz rezervele totale ale activitilor, punndu-se n evidendrumul critic, figura 1.4;

A B C D

H

E

G

I

F

1 2

3

4 6

5 7 8t=14 t=16 t=11 t=9

t=20

t=16

t=13

t=6

t=20

0 14 30 46 55

16

20 40

554635190

22

4020

RT=5 RT=5 RT=5 RT=0

RT=6

RT=6

RT=0

RT=0

RT=0

Figura 1.4-Rezerve totale, evidenierea drumului critic;

7/25/2019 exempu organizare

3/7

Secvena 4:Se calculeaz pentru fiecare activitate costul marginal sau coeficientulde cost (bij), rezultatele centralizndu-se n tabelul 1.2.

bij=

Secvena 5:Se calculeaz costul total al proiectului (C);C=CD+CI, unde:

- CD- reprezint costul direct, calculate prin nsumare coloanei 4 din tabelul 1:

- CI- reprezint costul indirect, precizat n enunul problemei;Rezult : C=17252+3768=21020 (u.v.)

Datele obinute pentru pasul 1 si pentru paii urmtori se sintetizeaz n tabelul 1.2

de forma :

Tabelul 1.2-Rezultatele pailor de rezolvare

Activitatea

bij

Paii algoritmului Kelley-Fulkerson( KF)Codactiv

.Pas 1 Pas 2 Pas 3 Pas 4 Pas 5 Pas 6

A 10

14 14 14 14 14 14

B 8 16 16 16 16 16 15

C 3 11 11 11 11 8 8D 5 9 9 6 6 6 6E 8 16 16 16 16 16 16F 3 13 13 13 13 13 13G 4 20 16 16 16 16 16H 1

020 20 19 19 16 15

I - 6 6 6 6 6 6Reducerea duratei - -4 -3 -1 -3 -1Durata 55 51 48 47 46 45Reducerea costului - -40 -27 -4 -3 +4

COSTUL 21020

20980

20953

20949

20946

20950

7/25/2019 exempu organizare

4/7

Pas 2: Identificm activitivitatea critic sau combinaia de activiti critice cu costul

marginal (coeficientul de cost) cel mai mic.Pentru aceasta reprezentm grafic drumurile complete din graficul reea, figura 1.4,

i determinm dutata acestora, figura1. 5:D1,4,6,7,8=55 u.t.

D1,3,5,7,8=49 u.t.

D1,2,5,7,8=50 u.t.

RT

=6 u.t.

RT=5 u.t.

55

49

50

Figura 1.5-Identificarea drumurilor complete n graficul reea corespunztor pasului 1

Se observ c durata total de execuie Dcrt=55 u.t. se poate reduce cu 4 u.t.corespunztoare activitii G , fr a schimba traiectoria drumului critic.

Bilanul costului:c=t*bG-t* CI*=4*4-4*14=-44 u.v.

Completm rezultatele din pasul 2 n tabelul 1.2, i recalculm termenele nodurilor

graficului reea, figura 1.6.

A B C D

H

E

G

I

F

1 2

3

4 6

5 7 8t=14 t=16 t=11 t=9

t=20

t=16

t=13

t=6

t=16

0 14 30 42 51

16

16 36

514231150

18

3616

RT=1 RT=1 RT=1 RT=0

RT=2

RT=2

RT=0

RT=0

RT=0

Figura 1.6-Calculul termenelor, dup pasul 2

Pas 3: Identificm activitivitatea critic sau combinaia de activiti critice cu costul

marginal (coeficientul de cost) cel mai mic.Pentru aceasta reprezentm grafic drumurile complete din graficul reea, figura 1.6 i

determinm dutata acestora, figura 1.7:D1,4,6,7,8=51 u.t.

D1,3,5,7,8=49 u.t.

D1,2,5,7,8=50 u.t.

RT=2 u.t.

RT=1 u.t.

51

49

50

Figura 1.7 -Identificarea drumurilor complete n graficul reea corespunztor pasului 2

Se observ c durata total de execuie Dcrt=51 u.t., se poate reduce cu t=1 u.t. ,diferena ntre drumul critic D1,4,6,7,8 i drumul necritic D1,2,5,7,8. Reducem durata activitiiD cu bD=5 (cel mai mic), cu t=3 u.t.

Bilanul costului:c=t*bD-t* CI*=3*5-3*14=-27 u.v.

Completm rezultatele din pasul 3 n tabelul 1.2, i recalculm termenele nodurilorgraficului reea.

7/25/2019 exempu organizare

5/7

A B C D

H

E

G

I

F

1 2

3

4 6

5 7 8t=14 t=16 t=11 t=6

t=20

t=16

t=13

t=6

t=16

0 14 30 42 48

16

16 36

484231150

18

3616

RT=1 RT=1 RT=1 RT=0

RT=2

RT=2

RT=0

RT=0

RT=0

Figura 1.8-Calculul termenelor, dup pasul 3

Pas4: Identificm activitivitatea critic sau combinaia de activiti critice cu costul

marginal (coeficientul de cost) cel mai mic.Pentru aceasta reprezentm grafic drumurile complete din graficul reea, figura 1.8

i determinm dutata acestora, figura 1.9:D1,4,6,7,8=48 u.t.

D1,3,5,7,8=46 u.t.

D1,2,5,7,8=47 u.t.

RT=2 u.t.

RT=1 u.t.

48

46

47

Figura 1.9-Identificarea drumurilor complete n graficul reea corespunztor pasului 3

Se observ c durata total de execuie Dcrt=48 u.t., se poate reduce cu t=1 u.t.,diferena ntre drumul critic D1,4,6,7,8= 48 u.t. i drumul necritic D1,2,5,7,8=47 u.t.

Reducem durata activitii H cu bH=10, cu t=1 u.t.Bilanul costului:

c=t*bH-t* CI*=1*10-1*14=-4 u.v.Completm rezultatele din pasul 4 n tabelul 1.2, i recalculm termenii graficului

reea, figura 1.10.

A B C D

H

E

G

I

F

1 2

3

4 6

5 7 8t=14 t=16 t=11 t=6

t=19

t=16

t=13

t=6

t=16

0 14 30 41 48

16

16 35

484130140

17

3516

RT=0 RT=0 RT=0 RT=0

RT=1

RT=1

RT=0

RT=0

RT=0

Figura 1.10-Calculul termenelor, dupa pasul 4

Pas5: Identificm activitivitatea critic sau combinaia de activiti critice cu costul

marginal (coeficientul de cost) cel mai mic.Pentru aceasta reprezentm grafic drumurile complete din graficul reea, figura1.10, i determinm dutata acestora, figura 1.11:

D1,4,6,7,8=47 u.t.

D1,3,5,7,8=46 u.t.

D1,2,5,7,8=47 u.t.

RT=1 u.t.

47

46

47

Figura 1.11-Identificarea drumurilor complete in graficul retea corespunzator pasului 4

7/25/2019 exempu organizare

6/7

Se observ c durata total de execuie Dcrt=47 u.t.,(dou activiti critice) se poatereduce cu t=3 u.t.

Cum activitatea C are bC=3, coeficientul de cost cel mai mic pe drumul critic D1,2,5,7,8=47 u.t., se va reduce durata acesteia cu t=3 u.t., concomitent cu reducerea durateiactivitii critice H, cu t=3 u.t. Costul marginal cumulate pentru cele doua activiti este:

bCH=bC+bH=3+10=13 u.v./u.t.Bilanul costului:c=t*bCH-t* CI*=3*13-3*14=-3 u.v.

Completm rezultatele din pasul 5 n tabelul1.2, i recalculm termenele nodurilorgraficului reea, figura 1.12.

A B C D

H

E

G

I

F

1 2

3

4 6

5 7 8t=14 t=16 t=8 t=6

t=16

t=16

t=13

t=6

t=16

0 14 30 38 44

16

16 32

443830140

17

3216

RT=0 RT=0 RT=0 RT=0

RT=1

RT=1

RT=0

RT=0

RT=0

Figura 1.12-Calculul termenelor,dup pasul 5

Pas6: Identificm activitivitatea critic sau combinaia de activiti critice cu costul

marginal (coeficientul de cost) cel mai mic.Pentru aceasta reprezentm grafic drumurile complete din graficul reea ,figura

1.12, i determinm dutata acestora, figura 1.13:

D1,4,6,7,8=44 u.t.

D1,3,5,7,8=43 u.t.

D1,2,5,7,8=44 u.t.

RT=1 u.t.

44

43

44

Figura 1.13-Identificarea drumurilor complete n graficul reea corespunztor pasului 5

Se observ c durata total de execuie Dcrt=44 u.t.,(dou activiti critice) se poate

reduce cu t=1 u.t. bAH=bA+bH=10+10=20 u.v./u.t.bBH=bB+bH=8+10=18 u.v./u.t.

Cum activitatea B are bC=8, coeficientul de cost cel mai mic pe drumul critic D1,2,5,7,8=44 u.t., se va reduce durata acesteia cu t=1 u.t., concomitent cu reducerea durateiactivitii critice H, cu t=1 u.t. Costul marginal cumulate pentru cele doua activiti este:

bBH=bB+bH=8+10=18 u.v./u.t.Bilanul costului:

c=t*bBH-t* CI*=1*18-1*14=+4 u.v.Completm rezultatele din pasul 6 n tabelul 1.2, i recalculm termenele nodurilor

graficului reea, figura 1.14.

7/25/2019 exempu organizare

7/7

A B C D

H

E

G

I

F

1 2

3

4 6

5 7 8t=14 t=15 t=8 t=6

t=15

t=16

t=1

3

t=6

t=16

0 14 29 37 43

16

16 31

433729140

16

3116

RT=0 RT=0 RT=0 RT=0

RT

=0RT=0

RT=0

RT=0

RT=0

Figura 1.14-Calculul termenelor, dupa pasul 6

n final parametrii optimi Doptimi Cminrezult din urmtoarea reprezentare grafic,figura 1.15.

1 40 41 4 2 4 3 4 4 45 46 47 48 49 50 51 5 2 53 54 55 56 57

21020

20980

20953

20950

20946

1(55,21020)

2(51,20980)

3(48,20953)

4(47,20949)

5

(Dopt,Cmin)

6(43,20950)

C(u.v.)

D

(u.t.)

Figura 1.15-Reprezentarea grafica a parametrilor optimi

corespunztori exemplului 1