17 Utilizarea pachetului de programe WINQSB n managemenul proiectelor. Planificarea activitilor. Programa WINQSB: PERT/CPM.

Pachetul de programe informatice Quantitative System for Business(WinQSB) este un sistem software realizat de Y.I.Chang de la Georgia Institute ofTechnology, care ruleaz sub Windows i este compus din 19 module, formate larndul lor din mai multe submodule. Lansarea n execuie a unui anumit modulpermite prelucrarea datelor de intrare, obinerea rezultatelor, analiza i interpretareaacestora. Extensiile fiierelor salvate sunt particulare fiecrui modul apelat

n WinQSB, problemele de programare liniara pot fi introduse si rezolvate utiliznd doua forme de reprezentare, si anume: Forma matricialaAcest mod de reprezentare a problemelor de programare liniara presupune dispunerea pe linii a functiei obiectiv si a restrictiilor si a variabilelor decizionale, a tipului si valorii restrictiei pe coloane. Fiecare celula va reprezenta coeficientul respectivei variabile decizionale pentru fiecare restrictie si pentru functia obiectiv. Primul rnd si prima coloana din matrice sunt statice si specificadenumirea variabilelor, criteriul functiei obiectiv, numele constrngerilor, etc.Meniul Edit contine optiuni ce permit modificarea tipului functiei obiectiv, numelor pentru restrictii, introducrea sau stergerea unor variabile, adaugarea sau stergerea de restrictii. Tipul restrictiei se poate modifica prin dubu-clic asupra celulei ce contine semnul acelei restrictii. n acelasi mod se poate modifica tipul variabilelor. Forma normalaForma normala este foarte asemanatoare cu reprezentarea conventionala a problemelor de programare liniara. Problema e dispusa pe mai multe rnduri, dar pe doar doua coloane.Pe rnduri se reprezinta functia obiectiv, restrictiile, tipul variabilelor,intervalul n care pot lua valori variabilele. Valorile efective se nscriu n coloana a doua din acest tabel. Meniul Edit contine optiuni ce permit modificarea tipului functiei obiectiv, numelor pentru restrictii, introducrea sau stergerea unor variabile, adaugarea sau stergerea de restrictii.Functia obiectiv si restrictiile se introduc sub forma unor functiiliniare obisnuite.18. Diagrame Gantt. Planificarea in reea a activitilor proiectelor.

Creata n la nceputul sec. XX i denumit dup cel care a folosit pentru prima dat aceast procedur - Henry Gantt, Adamiecki .Uor accesibil i prezint perioadele de nceput i ncheiere, precum i durata activitilor .Reprezint un instrument foarte important de vizualizare, care subliniaz secvena i durata tuturor sarcinilor ntr-un proiect. Este o diagram cu bare care arat relaia dintre activiti de-a lungul timpului. n cadrul diagramei, pe vertical sunt listate activitile componente ale proiectului, iar n orizontal, prin bare (casete) sunt reprezentate duratele acestora la scara timpului n ordinea de desfurare impus de relaiile de preceden .

Avantaje

simplitate/claritate n transmiterea informaiilor

extensii: culori/forme diverse pentru

departamente diferite

diferite stri ale realizrii activitilor

marcarea activitilor ce dau durata minim a proiectului

(drumul critic)

Dezavantaje

plus de complexitate -> diagramele nu mai sunt uor de

nteles

nu se poate stabili cu uurin dependenele ntre

activiti

proiecte mari necesit actualizri laborioase29. Bazele planificrii n reea. PERT. Aflarea drumului critic. Construirea grafului reea; Diagrame Gantt.

PERT a aprut la sfritul anilor 1950, n cadrul forelor navale ale SUA (Programul de lansare a rachetelor Polaris) Termenul PERT (Program Evaluation and Review Technique Tehnic de Evaluare i Revizuire a Pogramului) vine de la o tehnic folosit pentru a calcula rezultatul cel mai probabil al unui proiect. Folosirea termenului de PERT se datoreaz primelor versiuni de MP care foloseau aceast terminologie pentru a denumi diagramele de dependene (denumite acum network chart). O diagram PERT (sau Network Chart, Diagram de dependene, diagram de predecesori) este un mod de a crea i prezenta un proiect afind activitile ca nite cutii, iar dependenele dintre acestea cu sgei. reprezint ilustrarea/modelarea grafic a unui proiect prin intermediul relaiilor logice i cronologice dintre activitile i evenimentele ce compun proiectul. ea reprezint un instrument de planificare i control al conducerii proiectului. poate fi vzut ca o hart pentru un anume program sau proiect n care toate elementele majore au fost complet identificate, mpreun cu relaiile dintre ele.Drumul Critic l depistam n felul urmtor:

Analizm segmentele lucrrii [i,n] (ncepnd cu sfritul evenimentului n captul drept ),care se sfrete n timpul critic.Captul drept a acestor lucrri se gsete pe verticala timpului critic.Mai apoi termenul ndeplinirii lucrrii l identificm astfel:

Micm n dreapta pn la verticala drumului critic toate segmentele lucrrii [i,n] ,terminndu-se cu sfritul evenimentului ,apoi coborndu-ne de sus n jos,micm unul dup altul [k,i] n dreapta pe segmentele maximale permise , astfel nct captul segmentelor micate [k,i] s nimereasc pe o vertical cu captul stng al segmentelor micate [i,n] , dup care analogic vom mica segmentele [ j,k]. Acest proces l vom sfri cnd vom ajunge pn la lucrarea critic,ncepndu-se cu evenimentul x1 .Capetele stngi a segmentelor micate [i,n]; [k,i]; [j,k]; ne vor reprezenta timpul trziu al ndeplinirii evenimentului xi ,xk,xj.

Rezerva total de timp:

=(-)- a lucrrii (xi ,xj ) se identific dup distana micrii segmentului [i,j] ,lungimea segmentului de la locul anterior j pn la noul loc j.

Rezerva de timp liber: =(-)- a lucrrii (xi ,xj ) pe diagrama liniar se poate identifica dup cea mai mare lungime a segmentului, pe care se poate de micat n dreapta segmentul lucrrii [i,j] ,fr a mica nici unul din segmentele lucrrii [j,k],n acelai timp neschimbnd nceputul a lucrrii (xj ,xk ) ,care reiese din evenimentul xj.

Pentru a identifica rezerva de timp independent:

a lucrrii (xi ,xj ), micm segmentul [i,j] pn la coincidena captului cu verticala momentului corespunztor de timp t=.

Rezerva independent de timp a lucrrii (xi ,xj ) este egal cu lungimea segmentului de la captul j al segmentului micat pn la momentul de timp t=

19. Cteva criterii de primire a deciziilor in condiiile de risc sau incertitudine. (Criterii Wald, Savage, Laplace, Hurwicz).

Teoria deciziei ofer modalitatea alegerii celei mai bune alternative din mai multe posibiliti,oferind un proces logic de luare a deciziilor.

n cazul dat decidentul nu are informaii complete asupra evenimentelor care pot aprea independent de el i care pot influiena decizia sa. Aceste evenimente se mai numesc stri ale naturii.

Ele nu depind de decident, deci nu sunt sub controlul su .

Exemple de stri ale naturii sunt: condiii climaterice,cererea pe pia, preferinele clienilor, apariia pe pia a unor produse similare.

Pentru luarea celei mai bune decizii ,trebuie precizate urmtoarele:

1. S se identifice toate alternativele sau variantele posibile, adic modurile n care decidentul poate aciona.

2. S se precizeze toate strile naturii posibile, dar definite n aa fel ca aceste evenimente s fie mutual exclusive.

3. S se evalueze rezultatele alegerii oricrei variante n oricare dintre strile naturii. Aceste evaluri sau rezultate, reprezint beneficii sau costuri i se pot prezenta sub forma unor tabele ori matrice.

n funcie de gradul de cunoatere a apariiei lor ,se poate face urmtoarea clasificare:

I. Luarea deciziei n condiii de certitudine.

Decidentul tie variantele ,tie prcis ce stare a naturii va aprea i cunoate i rezultatele alegerii variantelor n toate strile naturii.

II. Luarea deciziei n condiii de incertitudine

Decidentul tie alternativele, nu are nici o informaie asupra probabilitii de apariie a nici uneia den strile naturii ,dar poate evalua rezultatele alegerii fiecrei alternative n toate strile naturii.

III. Luarea deciziilor n condiii de risc.

Decidentul cunoate alternativele ,are informaii suficiente pentru a determina probabilitatea de apariie a fiecrei dintre strile naturii i poate evalua rezultatele.

1. Criteriul Wald (sau criteriul maxi-min) Criteriul pesimistului care crede c natura acioneaz mpotriva lui: arice variant ar allege el ar obine cea mai proast ncasare posibil deci cel mai ru rezultat

Decidentul va allege ,pe linie ,rezultatul minim pentru fiecare dintre variante apoi va selecta valoarea maxim a acestor rezultate minime:2. Criteriul Savage. Bazat pe matricea de regret,

o msur a pierderii datorat nealegerii celei mai bune variante.

Regretul este msurat prin diferena dintre rezultatul cel mai bun pe care l-am fi putut realize dac am fi tiut ce stare a naturii urma s apar i rezultatul obinut prin luarea deciziei.

3. Criteriul Laplace . Bazat pe ipoteza lui Bernuly fiecare posibilitate a strii naturii este egal.

Ses acord anse egale de apariie fiecrei stri a naturii ,deci pentru n stri ,probabilitatea de apariie este egal cu 1/n.

4. Criteriul Hurwicz . Criteriul este aplicabil decidenilor optimiti ,pesimiti ori celor situai ntre dou extreme.Atribuim - probabilitatea celei mai nefavorabile stri a naturii :

20. Modele liniare de cercetri operaionale. Regulamentele de baz a teoriei programrii liniare.

Programarea liniar (PL) este o metod matematic de optimizare cu aplicaii n diverse domenii ca: industrie, agricultur, probleme de transport i repartiie, investiii, reclame, finane.

Scopul principal const n determinarea alocrii optime a unor resurse, de care se dispune n cantiti limitate, pentru a se obine valoarea optim a unui anumit obiectiv, de exemplu minimizarea costurilor de producie sau maximizarea profitului. Pentru rezolvarea oricrei probleme de programare liniartrebuie creat un model matematic.22.Modelarea n numere ntregi. Exemple de modele soluia crora se expune n numere ntregi:Oficiul Postal.

e binecunoscut faptul cmodelarea prin programare liniarreprezint un mijloc puternic i eficace pentru studiul proceselor economice n vederea mbuntirii performanelor acestora.O proprietate foarte important a variabilelor de decizie, dintr-un program liniar era aceea c, o dat cu dou valoripermise, puteau lua orice alt valoareintermediar;aceast proprietate de a putea varia continuu era esenial n fundamentarea metodelor de determinare a soluiilor optime.Nu puine sunt situaiile practice, modelate cu ajutorul programrii liniare n care unele variabile de decizie nu au sens economic dect dac au numai valorintregi.De exemplu, dac outputul unei activiti este msurat n unitiindivizibileeste clar c valorile permise ale variabilei care indic nivelul activitii respective trebuie s fie numere ntregi. La fel, repartizarea personalului muncitor, al utilajelor sau al mijloacelor de transport pe diverse activiti trebuie exprimat tot prin cantiti ntregi.Situaiile practice a cror modelare necesit utilizarea variabilelor ntregi sunt extrem de numeroase i exemplele urmtoare nu acoper nici pe departe aceast varietate. Dup cum vom vedea n urmtorul capitol,situaiile combinatorialepot fi modelate cel puin n principiu ca probleme de programri n numere ntregi.2.1. Problema monezilorCum poate fi pltit o sum de bani astfel nct:numrul tipurilor valorice de monezi utilizate la plat s nu depeasc o limit dat;numrul total al monezilor necesare plii s fie minim.Pentru formalizare avem nevoie de urmtoarele notaii:S = suma de plat,n = numrul total al tipurilor valorice de monezi disponibile pentru plat;p = numrul maxim de tipuri valorice de monezi ce pot fi utilizate la plata sumei S;ajvaloarea monezii de tip j;mjnumrul monezilor de tip j disponibile n cas.Introducem variabilele:xj= numrul monezilor de tip j utilizate la plata sumei S;Rezult urmtorul program ntreg

0xjmjyjj=1, ...nxj0 ntregi; yj{0, 1}j = 1, ...n23. Elemente din teoria grafurilor. Moduri de reprezentare ale unui graf. Exemplu1. Moduri de reprezentare ale unui graf

A. O prim modalitate de reprezentare este listarea efectiv a tuturor nodurilor i a arcelor sale.

B. Putem reprezenta graful dnd pentru fiecare nod mulimea nodurilor cu care formeaz arce n care el este pe prima poziie.

C. Putem reprezenta geometric graful, printr-un desen n plan, reprezentnd fiecare nod printr-un punct(cercule) i fiecare arc printr-un segment de curb care are ca extremiti nodurile arcului i pe care este trecut o sgeat orientat de la nodul iniial spre cel final.

D. Putem folosi o reprezentare geometric n care nodurile sunt reprezentate de dou ori, n dou iruri paralele, de la fiecare nod din unul din iruri plecnd sgei spre nodurile cu care formeaz arce n care el este pe prima poziie, de pe al doilea ir (reprezentarea prin coresponden).

E. Un graf poate fi reprezentat printr-o matrice ptratic boolean, de dimensiune egal cu numrul de noduri, n care o poziie aij va fi 1 dac exist arcul (xi,xj) i 0 n caz contrar, numit matricea adiacenelor directe.

F. Un graf poate fi reprezentat printr-o matrice ptratic latin, de dimensiune egal cu numrul de noduri, n care pe o poziie aij va fi xixj dac exist arcul (xi,xj) i 0 n caz contrar.

24. Problema determinrii arborelui minimal. Algoritmul Cruscal. Algoritmul Sollin.

Algoritmul lui Kruskal

Pasul 1. Dintre toate muchiile grafului se alege muchia de valoare minim (maxim). Dac minimul este multiplu se alege la ntmplare una din muchiile respective. Deoarece acest "la ntmplare" trebuie cumva tradus n limbajul calculatorului, n cazul implementrii unui program bazat pe acest algoritm, vom perturba din start valorile muchiilor, la k muchii cu aceiai valoare V adunnd respectiv valorile (, 2(, ... , k(, unde ( este foarte mic (n orice caz, k( mai mic dect diferena dintre valoarea acestor arce si valoarea imediat superioar a unui arc), pozitiv.

Pasul 2. Dintre toate muchiile rmase, se alege cea de valoare minim (maxim);

Pasul 3. Dintre toate muchiile rmase, se alege cea de valoare minim (maxim), astfel nct s nu se formeze cicluri cu cele deja alese;

Pasul 4. Se reia algoritmul de la pasul 3 pn se colecteaz n-1 muchii.

Dei s-a demonstrat c algoritmul gsete ntotdeauna arborele optim, el are dezavantajul c este foarte laborios (de fiecare dat trebuie calculat minimul unei mulimi mari sau foarte mari exist situaii n practic n care graful are sute de mii de arce) i, n plus, trebuie aplicat un algoritm special ca s respectm condiia de a nu se forma cicluri, la alegerea unui nou arc.

O metod posibil este ca, dup adugarea fiecrui arc, s se mpart graful n componente conexe i s alegem apoi un arc care nu are ambele extremitile n aceeai component conex.De asemenea este clar c, n cazul existenei arcelor de valori egale, deoarece se alege la ntmplare, exist mai multe variante de evoluie a alegerii arcelor. Totui, cu toate c pot fi mai multe grafuri la care se poate ajunge prin acest algoritm, ele vor avea toate aceeai valoare (minima (sau maxima) posibil).Algoritmul lui SollinPasul 1. Pentru fiecare nod se alege muchia adiacent de valoare minim (maxim).

Pasul 2. Se evideniaz componentele conexe, existente n graful parial format din arcele alese pn n acest moment.

Pasul 3. Pentru fiecare component conex se alege muchia adiacent de valoare minim (maxim). Prin muchie adiacent unei componente conexe nelegem o muchie care are o singur extremitate printre nodurile componentei respective.

Pasul 4. Se reia algoritmul de la pasul 2 pn rmne o singur component conex. Aceasta este arborele optim cutat.

Acest algoritm asigur de asemenea gsirea arborelui optim, necesit mult mai puine calcule (la fiecare alegere se calculeaz minimul doar pentru muchiile adiacente unui singur nod), evit automat formarea ciclurilor, dar, pentru grafuri foarte mari, la un moment dat pot exista att de multe componente conexe care trebuie memorate succesiv, nct calculul devine greoi sau, pe calculator, depete posibilitile de memorare ale calculatorului.

25 Determinarea drumului optim. Algoritmul lui Ford simplificat. Algoritmul Ford generalizat. Algoritmul lui DijkstraAlgoritmi de gsire a drumului optim:A. Algoritmul lui Ford simplificatAlgoritmul lui Ford simplificat se aplic doar n grafuri care nu admit circuite. Cu ajutorul lui se gsete drumul de valoare optim ntre dou noduri fixate xi i xj. Printr-o eventual renumerotare a nodurilor putem presupune c nodul de la care pornete drumul este x1, care va fi numit nod iniial, iar nodul la care se termin este xn, numit nod final.

Algoritmul este:Pasul 1. I se d vrfului iniial valoarea 0 (zero): w(x1) = 0

Pasul 2. Se construiete mulimea A format din nodul iniial: A = {x1}

Pasul 3. Se analizeaz nodurile din afara mulimii A.

Pasul 4. Se analizeaz mulimea A:

Dac xn ( A atunci valoarea sa reprezint valoarea drumului de valoare optim de la x1 la xn. Pentru gsirea acestui drum se pornete napoi de la nodul final xn i se gsesc nodurile ,, ..., care formeaz drumul cutat, unde = xn, = x1 i fiecare alt indice ki+1 este cel pentru care:

w() + v(,) = w() STOP Dac xn ( A se reia algoritmul de la pasul 3.

Algoritmul Ford generalizatAlgoritmul lui Ford generalizat a fost creat cu scopul de a putea gsi drumul optim i n grafurile care au circuite. Cu ajutorul lui se gsete drumul de valoare optim ntre dou noduri fixate xi i xj. Printr-o eventual renumerotare a nodurilor putem presupune c nodul de la care pornete drumul este x1, care va fi numit nod iniial, iar nodul la care se termin este xn, numit nod final.

Algoritmul este: Pasul 1. I se d vrfului iniial valoarea 0 (zero): w(x0) = 0 i tuturor celelalte valoarea +( (ntr-o problem de minim) sau -( (ntr-o problem de maxim).

Pasul 2. n ordinea cresctoare a indicilor nodurilor se calculeaz pentru fiecare nod, pe baz fostelor valori, noile valori cu formula:

Pasul 3. Se compar noile valori w*(xi) cu fostele valori w(xi):

Dac w*(xi) = w(xi) pentru orice nod xi atunci:

dac w(xn) < ( (la problema de minim) sau w(xn) > -( (la problema de maxim), valoarea nodului xn reprezint valoarea drumului de valoare minim(maxim) de la x1 la xn. Pentru gsirea acestui drum se pornete napoi de la nodul final xn i se gsesc nodurile ,, ..., care formeaz drumul cutat, unde = xn, = x1 i fiecare alt indice ki+1 este cel pentru care:

w() + v(,) = w() STOP

dac w(xn) = +( (-() atunci nu exist nici un drum de la x1 la xn. STOP

Dac exist cel puin un nod pentru care w*(xi) < w(xi) se reia algoritmul de la pasul 2 pentru noile valori ale vrfurilor.

Observaie: Algoritmul poate gsi drumul i n grafuri cu circuite dar este evident mult mai lent dect cel simplificat. Pentru scurtarea duratei de execuie se poate modifica algoritmul n sensul c o valoare nou calculat a unui vrf va fi folosit imediat ca atare la calculul noilor valori ale celorlalte, nu doar dup ce se calculeaz noile valori ale tuturor vrfurilor.

Algoritmul lui Dijkstran algoritmul Ford simplificat, pentru a gsi valoarea nodului final, deci a drumului minim, plecm de la nodul iniial n toate direciile posibile, pstrnd de fiecare dat toate nodurile analizate. Acest fapt duce la un consum inutil de timp, deoarece foarte multe din aceste noduri nu vor face parte din drumul optim. Pentru a elimina acest neajuns, algoritmul lui Dijkstra ncearc s pstreze, la fiecare iteraie, mulimea minim de noduri care s le conin pe toate cele care vor forma efectiv drumul optim. n plus, algoritmul se poate aplica i n drumuri cu circuite. Ca un minus este faptul c se aplic doar la probleme de minim. Algoritmul are urmtorii pai:

Pasul 1. I se d vrfului iniial valoarea 0 (zero): w(x0) = 0

Pasul 2. Se construiete mulimea A format din nodul iniial: A = {x1}

Pasul 3. Se analizeaz nodurile din afara mulimii A.

Dac exist noduri n care se poate ajunge prin arce directe de la noduri din A (nu doar de la nodurile mulimii A, ca la algoritmul lui Ford simplificat) se calculeaz pentru toate acestea:

w(xi) = n problemele de minim

dar, spre deosebire de algoritmul lui Ford simplificat, se adaug la mulimea A doar cel pentru care se obine valoarea minim, apoi se trece la pasul 4. Dac nu exist nici un nod de acest tip atunci nu exist nici un drum de la x1 la xn. STOP

Pasul 4. Se analizeaz mulimea A:

Dac xn ( A atunci valoarea sa reprezint valoarea drumului de valoare optim de la x1 la xn. Pentru gsirea acestui drum se pornete napoi de la nodul final xn i se gsesc nodurile ,, ..., care formeaz drumul cutat, unde = xn, = x1 i fiecare alt indice ki+1 este cel pentru care:

w() + v(,) = w() STOP

Dac xn ( A se reia algoritmul de la pasul 3.

26. Reele de transport. Fluxuri in reele.

O reea de transport G=(V,E) este un graf orientat n care fiecrui arc (u,v)E i este asociat o capacitate pozitiv c(u,v) 0. Dac (u,v)E vom considera c c(u,v)=0. Vom distinge dou vrfuri n reea: un vrf surs s i un vrf destinaie t.

Fie G=(V,E) o reea de transport cu o funcie f:V*V

EMBED Equation.3 cu valori reale care satisface urmtoarele trei condiii:

Restricie de capacitate: Pentru orice u,vV avem f(u,v) c(u,v).

Antisimetrie: Pentru orice u,vV avem f(u,v)= -f(v,u).

Conservarea fluxului: Pentru orice uV-{s,t} avem .

_1472362355.unknown

_1472362371.unknown

_1472362379.unknown

_1472362383.unknown

_1472362385.unknown

_1472362387.unknown

_1472362388.unknown

_1472362389.unknown

_1472362386.unknown

_1472362384.unknown

_1472362381.unknown

_1472362382.unknown

_1472362380.unknown

_1472362375.unknown

_1472362377.unknown

_1472362378.unknown

_1472362376.unknown

_1472362373.unknown

_1472362374.unknown

_1472362372.unknown

_1472362363.unknown

_1472362367.unknown

_1472362369.unknown

_1472362370.unknown

_1472362368.unknown

_1472362365.unknown

_1472362366.unknown

_1472362364.unknown

_1472362359.unknown

_1472362361.unknown

_1472362362.unknown

_1472362360.unknown

_1472362357.unknown

_1472362358.unknown

_1472362356.unknown

_1472362347.unknown

_1472362351.unknown

_1472362353.unknown

_1472362354.unknown

_1472362352.unknown

_1472362349.unknown

_1472362350.unknown

_1472362348.unknown

_1472362343.unknown

_1472362345.unknown

_1472362346.unknown

_1472362344.unknown

_1472362341.unknown

_1472362342.unknown

_1472362340.unknown