Universitatea Tehnica de Constructii Bucuresti

Anul I Master Managementul proiectelor in Constructii

PROIECT

Cercetari Operationale

Greblescu Andra Maria Grupa 2

Proiect Tema 10

Problema IFirma Porumbeii din Enserune este specializata in cresterea si comercializarea porumbeilor de carne. Aceasta opereaza printr-o gestionare riguroas cresterea extensive si moderna a porumbeilor adulti. Avnd n vedere noile reglementri europene, GAEC a decis sa construiasca n locul fostului un abator nou care sa corespunda noilor standarde europene. Acest lucru a determinat o problema majora care se refer la problema de baz de exploatare. GAEC, prin urmare, a realizat programarea activitatilor i a obinut urmatorul tabel, introducand activitati, activitati precedente, durate, costuri:ActivitateActivitate precedentaDurata

( zile)Costuri

( mii Euro)

A-1012

BC,E118

CF314

DF,H811

EA,I63

FA517

GD712

HA410

I-96

1. S se reprezinte graful asociat

2. S se determine DS, DF, TS, TF i marja pentru fiecare activitate

3. S se precizeze activitile drumului critic i durata minim proiectului

4. S se rezolve utiliznd MS sau/i WinQSB

5. S se ataeze listingul cu rezultate

6. S se prezinte suportul teoretic aferent

7. Toate companiile selectate pentru a efectua munca au fost de acord sa ofere un discount de 5% cu privire la costurile enumerate in tabelul de mai sus, cu conditia sa li se ofere 20% timp in plus.

(a) Dterminez toutes les tches dont la dure peut augmenter de 20% sans que cela empche les tches (a) Determinati toate activitatile a cror durat poate crete cu 20%, fr a mpiedica urmtoarele sarcini, pentru a ncepe la data lor de ncepere cel mai devreme i fr prelungirea performanei minime de lucru. (b) Dterminez la somme maximale que l'on peut ainsi conomiser sur le cot total si l'on se xe pour rgle(b) Determinati suma maxim care poate fi economisita din costurile totale, n cazul n care am stabilit o regul pentru a ncepe toate sarcinile de la data nceperii lor cel mai devreme, i nu pentru a lungi finalizarea minim de lucru.Rezolvare

ActivitateDurataDSDFTSTFM

A100100100

I9094134

E6101613193

F5101510150

H4101411151

C3151816191

D8152315230

B11182919301

G7233023300

1. Drumul critic a fost evidentiat si pe graful asociat din pct. 1 si este reprezentat de:

iar durata minima a proiectului este de 30 zile.

6. Metoda PERT

Metoda PERT (Program Evaluation and Review Technique) sau CPM (Critical Path Method metoda drumului critic) este un instrument pentru gestionarea (planificarea i controlul) proiectelor mari cu multe activiti separate care necesit coordonare. n realizarea unui proiect unele activiti trebuie s aib o anume succesiune, altele se defoar n paralel. Tehnica PERT a fost conceput pentru a oferi factorului de decizie un ajutor n planificarea i controlul unui astfel de proiect. Ea permite stabilirea timpului necesar realizarii intregului proiect, asigurand controlul evolutiei procesului si atrage atentia asupra acelor intarzieri in realizarea acelor activitati care ar determina o ntrziere n realizarea proiectului.

Sunt necesare dou tipuri de informaii pentru fiecare activitate din proiect:

a) succesiunea activitilor care preced o activitate,

b) timpul necesar realizrii activitii, care poate fi determinist sau aleatoriu.

Diagrama activitilor este reprezentarea grafic a ntregului proiect (graf orientat valuat). Activitile sunt arcele, iar nodurile, momentele de nceput i sfrit ale activitilor.

Drumul critic este o mulime de activitati din proiect care are cea mai mare durata de timp asociata.

Lungimea drumului critic determin timpul minim n care proiectul poate fi terminat.

Drumul critic este important pentru c arat c:

timpul necesar pentru realizarea complet a proiectului nu poate fi redus sub valoarea dat de drumul critic,

orice ntrziere n realizarea activitilor de pe drumul critic va produce intarziere n realizarea proiectului.

Pentru reducerea duratei totale a proiectului trebuie reduse duratele activitilor incluse in drumul critic

O cale de aflare a drumului critic este descris n continuare. Se noteaz cu:

DS i momentul cel mai devreme de ncepere a activitii i,

DFi momentul cel mai devreme de terminare a activitii i,

TSi momentul cel mai trziu de incepere a activitatii i,

TF momentul cel mai trziu de terminare a activitii i.

Momentul cel mai devreme de ncepere a unei activiti este cel mai devreme moment posibil la care acea activitate poate s nceap, presupunnd c toate activitile care o preced au nceput la cel mai devreme moment posibil.

Momentul cel mai devreme de terminare a unei activiti este suma momentului de nceput cel mai devreme posibil cu timpul necesar realizarii activitatii respective.

Momentul cel mai trziu de terminare a unei activiti reprezint cel mai trziu moment posibil de terminare a activitii respective fr ntrzierea proiectului, presupunnd c toate activitile sunt desfurate conform planului iniial.

Momentul cel mai trziu de ncepere a unei activitati este diferenta dintre cel mai trziu moment posibil de terminare a activitii respective i timpul necesar realizrii acestei activiti.

Procedeu pentru determinarea momentelor DS , DF , TS i TF

1. Pentru prima activitate se ia DS egal cu zero. Dac se adaug la DS timpul t necesar realizrii primei activiti se obine DF pentru prima activitate.

2. Pentru o activitate oarecare i, care pentru toate activitatile care o preced imediat are determinate DS i DF , se ia DSi=max{DFk | activitatea k precede imediat activitatea i} i DFi=DSi+ti,deoarece activitatea i nu poate ncepe pn cnd toate activitile care o preced

nu sau terminat.

3. Pentru ultima activitate se ia TF=DF al acestei activiti. Atunci TS=TFtn , tn fiind timpul necesar realizarii ultimei activitati

4. Pentru o activitate oarecare i, avnd pentru activitile care o succed imediat determinate TS i TF , se ia TFi=min{TSk | activitatea k succede imediat activitatea i} i TSi=TFit.

Marja, M, a unei activiti reprezint numrul de zile cu care o activitate poate ntrzia fr ca termenul de ncheiere al proiectului s fie afectat. Dup determinarea valorilor DS, DF, TS, TF pentru toate activitatile, se pot calcula marjele ca fiind: Mi=DSi - TSi sau Mi=DFi - TFi .

Dac proiectul are termenul finalizare egal cu lungimea drumului critic, atunci orice ntrziere n realizarea unei activitati incluse in drumul critic va cauza ntrziere n finalizarea proiectului. n schimb, activitatile care au marja pozitiv pot fi decalate, cu un numar de zile egal cu marja, fara ca termenul de finalizare a proiectului sa se modifice.

Analiza numai sub aspectul duratei poate fi completat cu costuri asociate activitilor. De exemplu, durata unei activit i poate fi redus dac se aloc resurse suplimentare. Aceasta implica si costuri suplimentare. Se introduce astfel si o functie de cost in luarea deciziei. Marja total a unei activitati este ntrzierea care pot fi luate n calcul la realizarea acestei activitati fr a ntrzia ntregul proiect:

Mti= TSi- DSi

Marja libera a unei activitati este ntrzierea ce pot fi luate n calcul la ndeplinirea unei activitati fr a ntrzia data de nceput cel mai devreme dect orice alt sarcin care urmeaz:

Mli= DSj- DSi -dii activitatea precedenta activitatii j7.

(a) Pentru acesta trebuie sa determinam marja totala si marja libera.

ActivitateDurata (d)DSTSMtMl20% din d

A1000002

I904411.8

E61013321.2

F51010001

H41011110.8

C31516100.6

D81515001.6

B111819112.2

G72323001.4

Activitatile pentru care marja libera este mai mare decat 20 % din durata activitatilor initiale sunt E i H.(b) Beneficiind de un discount de 5 % pentru activitatile E si H, vom economisii: mii de Euro, adica 650 EuroProblema II

O comapnie livreaza un produs la trei clienii europeni (Clientul 1, 2 i 3), si dispune de dou centrale de fabricaie (Usine1 i 2). Transportul este asigurat de un sistem logistic care utilizeaz o reea de 5 platforme (PF1 la PF5). Capacitile de transport pe fiecare linie de reea sunt limitate la valorile indicate n urmtorul grafic.

Cantitatea de produs disponibila n stoc n fabrica sunt de 35 pentru Usine1 i 25 pentru Usine 2. Cererile celor 3 clienti sunt 15 pentru Client 1 si 2 si 20 pentru Client 3. Gasiti un program de transport care satisface cererile clientilor.Atentie!Este o problema de flux maxim care poate fi modelata indicand cantitatea de produs care tranziteaza fiecare arc ce trebuie sa ramana inferioara capacitatii sale, fluxurile sunt stocate in toate nodurile.

1. S se modeleze problema

2. S se prezinte algoritmul Ford-Fulkerson

3. S se rezolve utiliznd WiQSB

4. S se ataeze listingul cu rezultate

1. Teoretic modelarea unei probleme de transport cu centre intermediare are urmatoarea forma:

unde:xik cantitatea ce urmeaza a fi transportata de la sursa i la centrul intermediar k

cik costul unitar de transport dintre centrele i si k

xkj cantitatea ce urmeaza a fi transportata de la centrul k la consumator j

ckj costul unitar de transport dintre centrele k si j

k capacitate centre intermediarea cantitile disponibile la fiecare furnizor

b cantitile necesare la fiecare beneficiar

In cazul de fata modelarea devine:

a. cantitatea ce pleaca de la sursa < decat stocul disponibil

b. cantitatea care intra pe o platforma = cantitatea care iese de pe platforma

c. cantitatea transportata in retea capacitatea maxima a retelei

d. cantitatea ce ajunge la client = cu cererea clientului

unde:

xij cantitatea de produs ce urmeaza a fi transportata de la sursa i la centrul intermediar j

ykl cantitatea de produs ce urmeaza a fi transportata de la centrul k la centrul intermediar l

zmn cantitatea de produs ce urmeaza a fi transportata de la centrul m la client n

2. Algoritmul lui Ford-FulkersonETAPA I Se determin un flux complet.

Pasul 1. Se numeroteaz nodurile reelei de transport astfel nct x1 = x0 i xn = Z;

Pasul 2. Se asociaz grafului fluxul nul ((u = 0 pentru orice arc u din graf);

Pasul 3. n ordine lexicografic, se ia pe rnd fiecare drum D de la nodul iniial la cel final, se calculeaz valoarea (D = i se adaug la fluxul de pe fiecare arc al drumului. Arcul(arcele) unui drum D pentru care s-a obinut valoarea minim (D va fi dup aceast adugare, n mod evident, saturat i deci drumul D va fi complet.

Dup epuizarea tuturor drumurilor se obine un flux complet, de valoare ( = . Deoarece alegerea drumurilor n ordine lexicografic nu ine cont de structura reelei, aa cum se poate vedea pe un exemplu, acest procedeu nu asigur ntotdeauna gsirea fluxului maxim. Acest impediment poate fi depit fie prin gsirea unei ordini de parcurgere a tuturor drumurilor, care s dea pentru fiecare reea fluxul maxim, n urma procedeului de mai sus, fie prin redistribuirea judicioas a fluxului gsit la etapa I. A doua variant este cea care se aplic la etapa II.

ETAPA II Se determin fluxul maxim.

Pasul 4. Se marcheaz nodul iniial x0 cu +(plus);

Pasul 5. Pentru fiecare vrf marcat xi se marcheaz cu: [+xi] toate vrfurile nemarcate xj pentru care exist arcul (xi,xj) i ((xi,xj) < c(xi,xj) (adica nodurile spre care mai e loc pentru a se transporta ceva din xi); [xi] toate vrfurile nemarcate xj pentru care exist arcul (xj,xi) i ((xj,xi) > 0 (adic toate nodurile spre care pleac deja ceva din xi);Pasul 6. Se repet pasul 5 pn este marcat nodul final sau pn cnd nu mai poate fi marcat nici un vrf;Pasul 7. Dac nodul final a fost marcat atunci fluxul este maxim i algoritmul se oprete, n caz contrar trecndu-se la pasul 8;Pasul 8. Construim un lanul L = ,, , unde = x0, = Z i marcajul oricrui vrf este +sau . Se calculeaz:

(L = min(,)

care se adaug la fluxul fiecrui arc al lanului de tipul (,) i se scade din fluxul fiecrui arc de tipul (,).

Pasul 9. Se terge marcajul i se reia algoritmul de la pasul 4.

n final, tietura de valoare minim este cea n care V = mulimea nodurilor marcate iar W = mulimea nodurilor nemarcate.

Observaia 1. Algoritmul nu asigur ntotdeauna gsirea fluxului maxim, deoarece se poate ca creterea fluxului la fiecare iteraie s se fac cu cantiti din ce n ce mai mici astfel nct suma lor s nu ating niciodat marginea superioar dat de valoarea tieturii minime, algoritmul avnd o infinitate de pai. Teorema de mai jos d o condiie suficient pentru ca algoritmul s se termine ntr-un numr finit de pai:

Teorem Dac toate capacitile rutelor reelei sunt numere raionale atunci algoritmul lui Ford-Fulkerson are un numr finit de pai.

Observaia 2. Teorema de mai sus asigur doar o limitare superioar a numrului de iteraii ale algoritmului, fa de capacitatea tieturii minime. Aceast valoare poate fi ns, n anumite cazuri, foarte mare i, dac nu se iau precauii suplimentare, algoritmul nu va da soluia n timp util. Depirea acestei situaii este asigurat de urmtoarea teorem:

Teorem Dac la fiecare iteraie se alege drumul (lanul) de lungime minim atunci algoritmul va avea cel mult (m(n iteraii, unde n = numrul de noduri iar m = numrul de muchii.Page 1 of 8

_1324559525.unknown

_1324560788.unknown

_1324561786.unknown

_1324561916.unknown

_1324561938.unknown

_1324561993.unknown

_1324561908.unknown

_1324561437.unknown

_1324561656.unknown

_1324561358.unknown

_1324560769.unknown

_1324560778.unknown

_1324559630.unknown

_1324475696.unknown

_1324559495.unknown

_1324464984.unknown