Cercetari Operationale

MELNIC LUCIA ZĂGAN REMUS CHIRCOR MIHAEL

CERCETĂRI OPERAŢIONALE

FUNDAMENTAREA DECIZIILOR ÎN MANAGEMENTUL SISTEMELOR DE PRODUCŢIE

2004

2

CUPRINS

1. INTRODUCERE

1.1. Scurt istoric al evoluţiei ştiinţei „Cercetare Operaţională”

1.2. Teoria Deciziei şi Cercetare Operaţională

1.3. Modelarea matematică în Cercetarea Operaţională

2. PROGRAMARE LINIARĂ

2.1. Probleme de programare liniară

2.1.1. Formularea problemei de programare liniară

2.1.2. Forme ale problemei de programare liniară

2.1.3. Modelul matematic al problemei de programare liniară

2.2. Consideraţii generale privind problemele de programare liniară

2.2.1. Soluţii şi fundamente ale problemei de programare liniară

2.2.2. Baze ale problemei de programare liniară

2.2.3. Interpretarea geometrică a problemei de programare liniară

2.3. Metoda Simplex

2.3.1. Fundamente teoretice în aplicarea metodei Simplex

2.3.2. Algoritmul simplex primal

2.3.3. Metode de determinare a unei soluţii de bază iniţiale

2.3.4. Interpretarea economică a algoritmului simplex primal

2.4. Dualitatea în programarea liniară

2.4.1. Problema duală. Fundamente teoretice

2.4.2. Algoritmul simplex dual

2.4.3. Interpretarea economică a dualităţii

3. PROGRAMAREA LINIARĂ DE TIP TRANSPORT

3.1. Formularea unei probleme de transport

3.2. Exemple de probleme de tip transport

3.3. Determinarea unei soluţii de baza iniţiale a problemei de transport

3.4. Metoda de determinare a soluţiei optime pentru probleme de transport.

Metoda potenţialelor.

3

4

5

7

7

7

9

12

16

16

20

22

26

26

28

35

39

41

41

45

49

53

53

55

57

59

Cercetări operaţionale- Fundamentarea deciziilor în managementul sistemelor de producţie

3

4. ELEMENTE DE TEORIA GRAFURILOR

4.1. Fundamente în teoria grafurilor

4.1.1. Noţiunea de graf

4.1.2. Orientare şi neorientare în graf

4.1.3. Drumuri şi circuite în graf

4.1.4. Lanţuri şi circuite în graf

4.2. Matrici ataşate grafurilor

4.2.1. Matricea arcelor (conexiunilor directe)

4.2.2. Matricea drumurilor (conexiunilor totale)

4.2.3. Descompunerea grafului în componente tari conexe

4.3. Drumuri hamiltoniene în graf

4.4. Drumuri de valoare optimă în graf

4.5. Cuplaje. Probleme de repartiţie (afectare)

5. TEHNICA DIAGRAMELOR DE TIP REŢEA

5.1. Generalităţi privind modelarea prin reţele

5.2. Metoda drumului critic (Critical Path Method - C.P.M.)

5.3. Metoda potenţialelor (Metro Potential Method - M.P.M.)

5.4. Metoda PERT (Program Evaluation and Review Technique)

5.5. Tehnica GERT (Graphical Evaluation and Review Technique)

6. ELEMENTE DE TEORIA DECIZIEI

6.1. Procesul şi sistemul decizional al întreprinderii

6.2. Utilităţi decizionale

6.3. Optimizarea deciziilor în condiţii de certitudine

6.3.1. Metoda utilităţilor globale

6.3.2. Metoda Electre

6.3.3. Metoda Ledear-ului

6.4. Optimizarea deciziilor în condiţii de risc

BIBLIOGRAFIE

64

64

64

69

70

71

71

73

75

78

87

93

97

97

99

106

108

111

114

114

117

121

121

121

122

123

131

Cercetări Operaţionale- Fundamentarea deciziilor în managementul sistemelor de producţie

3

CAPITOLUL 1 INTRODUCERE

1.1. Scurt istoric al evoluţiei ştiinţei „Cercetare Operaţională” Cercetarea operaţională ca ştiinţă a apărut către sfârşitul primei jumătăţi a secolului

nostru şi s-a dezvoltat spectaculos în special în ultimii ani, în strânsă legătură cu ştiinţa organizării şi conducerii, teoria sistemelor, cibernetica, informatica şi analiza sistemelor.

Şcoala clasică are marele merit al abordării unui domeniu nou, considerându-se pionieră a organizării ştiinţifice (F.W. Taylor-1900, H.L.Gantt-1901, A.Fayol-1915) şi aceasta pune pentru prima dată problema abordării raţionale a mecanismului funcţionării unei întreprinderi.

În perioada următoare se lărgeşte considerabil problematica organizării şi conducerii, iar aspectele informaţional-decizionale (până atunci ignorate) şi aspectele relaţiilor umane dau un alt sens abordării mecanismului funcţionării întreprinderii.

Cercetare operaţională exista înaintea declanşării celui de al doilea război mondial prin lucrările elaborate de Erlang (1917) – firele de aşteptare, Harrris (1915) – gestiunea ştiinţifică a stocurilor, Vorra (1931) – reînnoirea echipamentelor.

Utilizarea cercetării operaţionale în practică era dificil de realizat deoarece din punct de vedere intelectual exista o anumită aversiune fată de modele şi de caracterul descriptiv al ştiinţei, iar din punct de vedere material datorită complexităţii mici a organizaţilor şi talia relativ modestă a întreprinderilor din aceea perioadă, investiţiile în mijloace de calcul eficace, respectiv a ordinatoarelor nu era justificată.

În ceea ce priveşte procesele de decizie, pentru prima oară se pune în mod riguros şi pe scară largă problema găsirii unor soluţii optime sau apropiate de cele optime, în marea diversitate de probleme organizatorice şi de conducere.

Prima aplicaţie a cercetării operaţionale moderne la scară largă o constituie aplicarea regulilor definite de Sir Blackett în timpul celui de al doilea război mondial cu deosebit succes în Anglia şi care a debutat în 1937.

Termenul de Cercetare Operaţională (Operational Research)a fost utilizat pentru prima dată în 1939, fiind legat de contribuţia oamenilor de ştiinţă la utilizarea eficientă a radiolocatoarelor în sistemul apărării antiaeriene al Angliei.

În S.U.A. pătrunderea ştiinţei cercetării operaţionale (Management Science) în dezvoltarea problemelor de conducere a industriei se datorează celei de-a doua revoluţii industriale şi posibilităţilor de comercializare a calculatoarelor electronice.

În prezent, mai mult de jumătate din firmele americane au sau folosesc specialişti în cercetarea operaţională.

În 1953 s-a format Societatea Americană de Cercetări Operaţionale, iar în 1957 s-a constituit Federaţia Internaţională a Societăţilor de Cercetări Operaţionale. Au apărut reviste şi s-au introdus cursuri şi seminarii de cercetare operaţională atât în S.U.A. cât şi în alte ţări ale lumii.

În practică, întreprinderea poate fi privită ca un sistem ale cărui elemente componente (oameni, capital, materiale, informaţie) sunt intercorelate prin fluxuri materiale, informaţionale şi energetice ce au un comportament orientat spre atingerea unor obiective precise.

Cercetările operaţionale au consacrat în domeniul optimizării deciziei, un mod de abordare ştiinţific asupra problemelor ce intervin în cadrul unei întreprinderi industriale şi totodată nu se concepe conducerea şi gestionarea întreprinderii, fără a face apel la metodele cercetării operaţionale, împreună cu celelalte tehnici moderne ca informatica, cibernetica, teoria sistemelor, statistica.

Obiectul cercetării operaţionale îl constituie sistemele şi ele îşi propun elaborarea unor metode de analiza a operaţiilor îndreptate spre un anumit scop, precum şi estimarea obiectivă

Introducere

4

a deciziilor ce pot fi adoptate. Cercetarea operaţională este un ansamblu de metode care îşi propune, în vederea

pregătirii deciziilor, să determine în mod raţional soluţiile cele mai eficiente.

1.2. Teoria Deciziei şi Cercetare Operaţională Creşterea productivităţii şi obţinerea rentabilităţii întreprinderii industriale pe termen

lung, într-un mediu dinamic şi într-o continuă schimbare, depinde, într-o mare măsură de capacitatea managementului întreprinderii de a anticipa schimbarea şi de a adapta decizia noilor situaţii într-un mod planificat.

Accelerarea evoluţiei tehnologice în industrie, influenţează şi comportamentul consumatorilor, care se va orienta spre noi concepte şi produse, mai inovate, mai atractive şi adaptate modului şi ritmului lor de viaţă.

Utilizarea raţională a celor patru tipuri de resurse conduc la flexibilitatea organizaţiei şi astfel activitatea poate fi planificată în prognoze pentru a releva anumite aspecte semnificative ale viitorului. În aceste condiţii, managerul trebuie să adopte decizii, fundamentate ştiinţific şi performant.

Decizia reprezintă soluţia aleasă, din mai multe variante posibile cu scopul atingerii unui obiectiv prestabilit în condiţii de eficienţă maximă. Este actul deliberat al unui individ sau al unui grup de oameni investiţi cu puterea de a alege varianta de concepere/realizare a unui scop şi de a declanşa acţiuni.

Procesul de decizie porneşte de la un anumit rezultat care trebuie să fie obţinut, iar decidentul trebuie ca prin prelucrarea diferitelor informaţii să aleagă cea mai bună variantă pentru atingerea acestuia (fig. 1.1).

Rezultat dorit Obiective Variante Criterii DECIZIE Actiune

Control

Rezultat dorit

Fig.1.1.

Cercetare operaţională alături de Teoria deciziei a absorbit noile dezvoltări în domeniul activităţii de management industrial şi al sistemelor economice.

Necesitatea modelării în managementul producţiei industriale rezultă din faptul că efectuarea unor experimente asupra organizaţiilor este foarte greu de realizat, dar experimente de acest fel (de exemplu modificarea parametrilor funcţionali) se pot face uşor în condiţiile folosirii unui model.

Utilizarea modelelor este impusă şi de complexitatea sistemelor industriale, care necesită existenţa unei activităţi desfăşurată astfel încât deciziile să fie în concordanţă cu evoluţia eficientă a acestora.

Operaţia de investigarea a sistemelor reale prin reprezentări convenţionale se numeşte modelare. Ea reprezintă mulţimea activităţilor care se extind de la simpla prezentare a problemei la proceduri abstracte şi raţionale. Ele produc în final premisele cantitative formale ale dinamicii procesului.

Modelul este o reprezentare izomorfa a realităţii ce oferă o imagine intuitivă dar riguroasă în sensul structurii logice a fenomenului studiat.

Modelarea ca metodă de fundamentare a deciziilor în activitatea economică oferă următoarele avantaje: - reprezintă riguros fenomenele şi legăturile lor la nivelul sistemului; - permite verificarea prin analogie a teoriei cu practica;


5

- înlesneşte descoperirea unor corelaţii între fenomene şi predeterminarea performanţelor firmei, necesare pentru adoptarea unor decizii raţionale; - reflectă teorii ale proceselor cuantificabile şi necuantificabile; - urmăreşte obţinerea unor soluţii optime.

Modelarea utilizează un suport material fizic (de exemplu simulatoarele), o reprezentare grafică (de exemplu un grafic reţea), un model abstractizat sub forma unui model matematic. Din impactul între modelele fizice cu dispozitive logice de calcul şi cele matematice au rezultat modelele de simulare.

În managementul producţiei industrial se aplică toate aceste tipuri de modele, de exemplu: modelele fizice se pot folosi pentru studiul privind planul general al firmei, modelele grafice la analiza relaţiilor om – maşină, modelele matematice pentru alocarea resurselor sau analiza proceselor aleatoare.

Corelaţia teorie-model-realitate reprezintă un aspect logic - privind corespondenţa dintre teorie şi model – şi un aspect gnoseologic – urmărind corespondenţa dintre model şi realitate. Modelul intervine între teorie şi obiectul real şi trebuie testat în raport cu realitatea exprimată ca obiect.

În funcţie de modul în care se ajunge la soluţia optimă există două direcţii principale de lucru:

• atingerea obiectivului prin deducerea soluţiei optime; • atingerea aceluiaşi obiectiv prin practici oferite de teoria deciziei

Deducerea soluţiei se caracterizează prin certitudinea rezultatului obţinut pe baza unor informaţii obiective şi complete. Dificultatea constă în formularea problemei într-un limbaj matematic adecvat şi în volumul mare al calculelor.

Metoda a doua solicită decidentului să estimeze consecinţele posibile ale acţiunilor sale pe baza unor informaţii obiective, dar incomplete, introducându-se în rezolvarea problemei elemente subiective.

Prima direcţie a condus la dezvoltarea unui ansamblu de discipline în cadrul CERCETĂRII OPERAŢIONALE.

A doua direcţie de lucru a condus la constituirea unei discipline aparte – TEORIA DECIZIEI. Între cele două direcţii există raporturi strânse, biunivoce, ceea ce a condus la apariţia unei ştiinţe multidisciplinare: TEORIA DECIZIEI şi CERCETARE OPERAŢIONALĂ

Teoria deciziei este legată intrinsec de cercetarea operaţională care poate fi considerată „pregătirea ştiinţifică a deciziilor”.

1.3. Modelarea matematică în cercetarea operaţională Condiţiile în care se desfăşoară activitatea analizată din cadrul întreprinderii, conduc la

un sistem de relaţii tip ecuaţii şi inecuaţii ce cuprind variabilele problemei şi coeficienţii tehnico – economici ce o caracterizează. Aceste relaţii reprezintă – restricţiile problemei matematice.

Obiectivul studiului îl constituie optimizarea unui anumit rezultat dependent de aceleaşi variabile ce figurează în restricţii. Obiectivul este sub forma unei funcţii ale cărei valori maxime sau minime le căutăm şi care se numeşte funcţia obiectiv (scop, eficienţă).

Restricţiile problemei şi funcţia obiectiv formează modelul matematic al problemei. Modelele matematice se preferă pentru capacitatea lor de condensare riguroasă a

esenţialului. Modelele cercetării operaţionale se caracterizează prin căutarea unei soluţii optime sau apropiate de optim pentru operaţia studiată.

Modelele cercetării operaţionale se bazează pe o mare diversitate de procedee matematice şi au aplicaţii la nivel macro, dar în special la nivel microeconomic. Ele reprezintă principalul instrument pentru optimizarea deciziilor în analiza de sistem.

Introducere

6

Decizia obţinută cu ajutorul modelului nu poate fi recomandată nemijlocit pentru realizare, deoarece modelul face abstracţie de o serie de aspecte ale fenomenului studiat. Principalele faze ale elaborării unui model matematic într-o problema de organizare – conducere sunt următoarele: • Prima fază a modelării este cunoaşterea realităţii în organismul studiat, în scopul îmbunătăţirii mecanismului informaţional decizional şi descrierea logicii proceselor decizionale, această fază având un caracter pregătitor;

• A doua fază a modelării constituirea propriu - zisă a modelului–acesta cu ajutorul unui instrument clasic de modelare.

Elaborarea unui model matematic realmente original reclamă, pe lângă profunda cunoaştere a realităţii care urmează a fi modelată, o foarte solidă cultură matematică, imaginaţie şi talent.

Modelelor clasice ale cercetării operaţionale, sunt diverse funcţie de structura matematica şi logică, şi variază de la modele simple cum sunt cele ale programării liniare, la modele combinatorice, în probleme de teoria grafelor, analiza drumului critic şi programarea operativă a producţiei şi până la modele complexe cum sunt cele ale utilităţii sau deciziilor de grup.

• A treia fază a modelării este confruntarea modelului cu realitatea prin implementarea rezultatului obţinut şi eventual experimentarea sa. Există o gamă largă de probleme tehnico – economice care se pretează a fi modelate matematic cu ajutorul procedeelor cercetării operaţionale, dintre care putem menţiona: • programarea operativă a producţiei; • repartizarea raţională a resurselor; • gestiunea stocurilor; • eşalonarea în timp a activităţilor unei investiţii. In contextul celor arătate mai sus trebuie subliniată importanţa metodelor cercetării operaţionale în fundamentarea şi elaborarea deciziilor. Sarcina cercetării operaţionale este de a pregăti decizia şi nu de a o adopta . Conducerea executivă care va lua decizia finală trebuie să ţină seama pe lângă recomandările cercetării operaţionale şi de o serie de factori ce nu pot fi formalizaţi.

Una din principalele caracteristici ale tuturor metodelor cercetării operaţionale este faptul că problemele cercetării operaţionale sunt privite, din perspectivă pur teoretică, ca probleme de matematică pură.

În cele ce urmează vom privi metodele cercetării operaţionale strâns legate de problemele practice.

În prezent nu se mai poate concepe conducerea unei activităţi tehnico-economice importante fără a face apel la metodele cercetării operaţionale, bineînţeles împreună cu celelalte tehnici moderne cum ar fi informatica, analiza de sistem ş.a..


7

CAPITOLUL 2 PROGRAMAREA LINIARĂ

2.1. Probleme de programare liniară

Orice activitate industrială se desfăşoară în condiţiile existenţei unor resurse limitate

de materii prime şi materiale, de resurse umane, iar folosirea eficientă, a acestora, conduce la rezultate optime atât din punct de vedere tehnic cât şi economic.

Modelele de programare matematică şi mai ales modelele de programare liniară, constituie o clasă specială, atât în teorie cât şi în practica industrială.

Pentru decizii referitoare la structura optimă de producţie, la cantitatea ce urmează a se produce, la sortimente, abordarea acestora cu modele ale programării matematice conduce la rezultate optime.

Programarea matematică reprezintă un instrument deosebit de util fundamentării deciziilor în practica industrială. 2.1.1. Formularea problemei de programare liniară

Principala problemă cu caracter decizional, cu care se confruntă producţia o constituie determinarea structurii optime de producţie pe termen mediu şi scurt printr-o folosire eficientă a resurselor.

Condiţiile în care se desfăşoară activitatea de producţie analizată, conduc la un sistem de relaţii tip ecuaţii şi inecuaţii ce cuprind variabilele problemei şi coeficienţii tehnico – economici ce o caracterizează .

Modelul matematic de programare liniară se constituie din mulţimea de activităţi (operaţii){A1, A2, ..Aj,.. An}, (j=1,...,n) pentru producerea unei unităţi din produsul Pj (ca rezultat al activităţii Aj), mulţimea de resurse disponibile materiale, financiare, de capacităţi de producţie {b1, b2, ... bm}, (i = 1,...,m) precum şi din relaţiile tehnico-economice dintre acestea.

În practica industrială, legătura dintre activităţi (operaţii) şi resurse este determinată de procesul tehnologic de fabricaţie corespunzător realizării produsului.

Elementele aij, (i = 1,...,m; j = 1,...,n) se numesc coeficienţi tehnico-economici, aceştia fiind constanţi într-un interval de timp determinat şi arată ce cantitate din resursa bi (i = 1,...,m) se consumă pentru producerea unei unităţi din produsul Pj.

Toate aceste legături (restricţii) definite de vectorii coloană a(j) se pot organiza într-o matrice A cu m linii şi n coloane (2.1); fiecare linie se referă la o resursă bi şi fiecare coloană se referă la o activitate aj.

A∈Mm.n; A= ( ai,j ), i = 1,..,m, j= 1,...,n; A = ��

�

�

��

�

�

mn1m

n111

a..........a

a.........a (2.1)

b m

R∈ , b =

��

�

�

��

�

�

m

2

1

b

bb

. (2.2)

Notând cu xj (j = 1,...,n) (2.3) programul activităţii aj într-o perioadă dată şi cu bi

cantităţile disponibile din resursele bi, se pot scrie matematic restricţiile tehnico-economice. Aceste restricţii reprezintă – restricţiile problemei de programare liniară (2.4).

Programare liniară

8

x ∈ R n , x =

��

�

�

��

�

�

nx

xx

.2

1

(2.3)

mnmn2m21m1

2n2n222121

1n1n212111

bxa...xaxa

bxa...xaxabxa...xaxa

≤+++

≤+++≤+++

��

�

��

�

�

��

(2.4)

Fiecare restricţie (inecuaţie de tipul „ ≤ ”) cuprinde afirmaţia prin care cantitatea

consumată dintr-o resursă nu poate depăşi volumul disponibil din resursa respectivă. Obiectivul studiului îl constituie optimizarea unui anumit rezultat dependent de

aceleaşi variabile ce figurează în restricţii. Obiectivul este sub forma unei funcţii ale cărei valori maxime sau minime le căutam şi

care se numeşte funcţia obiectiv (scop, eficienţă). În practica industrială, ea reprezintă criteriul de performanţă urmărit: maximizarea

beneficiului, maximizarea producţiei marfă, minimizarea costului producţiei, maximizarea gradului de încărcare al utilajelor sau minimizarea timpului de staţionare al acestora, maximizarea veniturilor etc.

Variaţia funcţiei obiectiv arată evoluţia volumului activităţilor, prin intermediul coeficienţilor jc , ce pot fi costuri unitare în cazul problemelor de minim, sau profituri unitare pentru probleme de maxim (2.5).

Rc j ∈ , c ∈ R n c =

��

�

�

��

�

�

n

2

1

c

cc

. ; )......( nj21

T ccccc = (2.5)

Decizia cu scopul unei eficienţe maxime presupune minimizarea efortului şi

maximizarea rezultatului, Conceptul de optim se defineşte, în acest caz, ca un program (soluţie) x∈ Rn care

minimizează sau maximizează o funcţie obiectiv şi, în acelaşi timp, satisface toate restricţiile tehnico-economice.

Presupunând că fiecare coeficient .cj măsoară eficienţa unei unităţi din rezultatul activităţii Aj, atunci se poate introduce funcţia obiectiv liniară (2.6) :

z = c1⋅x1 + c2⋅x2 + ... + cn⋅xn (2.6)

Sintetizând toate datele de mai sus, obţinem următorul model (2.7, 2.8, 2.9)de

programare liniară. Relaţiile (2.7), (2.8) şi (2.9) constituie împreună modelul matematic al unei probleme

de programare liniară, având fiecare un rol specific: 1. relaţia (2.7), denumită funcţia obiectiv a problemei, evaluează eficienţa/performanţa

fiecărei soluţii (program) x;


9

��

�

��

�

�

≤≤≥

≤≤+� ≥⋅

≤≤� ≤⋅

�=

=

=

=

nj10x

li1kbxa

ki1bxa

xcz

j

n

1jijij

n

1jijij

n

1jjj

xmin(max)

2. relaţiile (2.8) de tipul � ≤⋅=

n

1jijij bxa reprezintă restricţii ce corelează volumul consumului

activităţilor cu cel al disponibilului pentru fiecare resursă; iar restricţiile de tipul

� ≥⋅=

n

1jijij bxa impun un consum peste limitele minimale, sunt restricţii tehnico-economice

de tip calitativ; 3. relaţia (2.9) xj ≥ 0 j = 1,...,n, numită condiţia de nenegativitate a variabilelor, asigură

obţinerea unei soluţii realizabile în practica industrială. Decizia obţinută cu ajutorul modelului nu poate fi recomandată nemijlocit pentru

realizare, deoarece modelul face abstracţie de o serie de aspecte ale fenomenului studiat, cele ce au la bază o serie de factori ce nu pot fi formalizaţi.

În practica industrială programarea liniară oferă soluţii care pot motiva ştiinţific luarea unor decizii de natură strategică, tactică sau a unor decizii cu conţinut tehnico – organizatoric. 2.1.2. Forme ale problemei de programare liniară

O problemă de programare liniară este, un caz particular al problemelor de programare matematică şi, ţinând cont de forma oricărei funcţii liniare, se poate defini forma generală a problemei de programare liniară.

Funcţia liniară (2.10), notată cu z reprezintă funcţia obiectiv a problemei. Relaţiile (2.11) reprezintă sistemul de restricţii ale problemei, iar membrul stâng al

fiecărei relaţii aste o funcţie liniară în variabilele x1, x2,…,xn, la fel ca şi funcţia obiectiv. Problema de programare liniară constă în optimizarea unei funcţii liniare cu restricţii

liniare.

• Forma generală a problemei de programare liniară

( )( )( )( )

( )( )��

�

��

�

�

=≥≤++

=≥≤++=≥≤++

+++=

mnmn22m11m

2n222121

1nn1212111

nn2211

bxaxaxa

bx2axaxabxaxaxaxcxcxcz

.........................................................

......

...min(max)

unde: ),(),,,,(),,( m1iRbn1jm1iRan1jRc iijj =∈==∈=∈ Din analiza mai multor probleme de programare liniara deducem că într-o astfel de problema pot apare restricţii scrise sub forma de inegalităţi sau egalităţi, iar criteriul de optimizare ales impune în unele cazuri maximizarea iar în alte cazuri minimizarea funcţiei obiectiv.

(2.7)

(2.8)

(2.9)

(2.10)

(2.11)

Programare liniară

10

Rezolvarea problemei de programare liniară presupune determinarea valorilor variabilelor xi, care satisfac restricţiile şi optimizează funcţia obiectiv a problemei. • Forma standard a problemei de programare liniară O problema de programare liniară este dată sub formă standard dacă toate restricţiile sale sunt date sub formă de ecuaţii (egalităţi) şi tuturor variabilelor li se impun condiţii de nenegativitate. Problema de programare liniară dată în formă standard se scrie în mod explicit (2.12):

��

�

��

�

�

≤≤≥

� ≤≤=

�=

=

=

njx

mibxa

xcz

j

n

jijij

n

jij

10

1

max(min)

1

1

(2.12)

Problema de programare liniară în formă standard poate fi scrisă şi sub formă matricială (2.13) :

��

��

�

≥=0xbAx

xcTmin(max), unde

��

��

�

∈∈

∈

mnm

n

RbRMARxc

,)(,

(2.13)

unde cT reprezintă componentele matricei c transpusă. Sistemul de restricţii liniare ( Ax=b ) poate fi un sistem compatibil, compatibil unic determinat sau nedeterminat de m ecuaţii şi n necunoscute. Pentru ca problema de optimizare să aibă sens, numărul de ecuaţii trebuie să fie mai mic decât numărul de necunoscute (m<n)(sistem compatibil nedeterminat). • Forma canonică a problemei de programare liniară O restricţie a unei probleme de programare liniară se numeşte concordantă (neconcordantă) dacă pentru o inegalitate de tip “ ( )""" ≤≥ funcţia obiectiv este minimizată sau respectiv pentru o inegalitate de tip ( )"""" ≥≤ funcţia obiectiv este maximizată . O problemă de programare liniară este data sub formă canonică dacă toate restricţiile sale sunt concordante şi toate variabilele sunt supuse condiţiei de nenegativitate. Problema de programare liniară dată în formă canonică se scrie în mod explicit (2.14):

��

�

��

�

�

≤≤≥

≤≤≤≥

=

�

�

=

=

njx

mibxa

xcz

j

n

jijij

n

jij

10

1)(

min(max)

1

1

(2.14)

Problema de programare liniară în formă canonică poate fi scrisă şi sub formă matricială (2.15) :


11

��

��

�

≥≤≥0x

bAxxcT

)(min(max)

unde ��

��

�

∈∈

∈

mnm

n

RbMA

RxC

,

, (2.15)

Orice problemă de programare liniară în formă generală poate fi adusă la forma standard sau canonică cu ajutorul unor transformări elementare efectuate asupra operatorului aplicat funcţiei obiectiv restricţiilor şi variabilelor: a) o problemă de minimizare în formă matricială se poate transforma într-o problemă de

maximizare şi invers, schimbând semnul coeficienţilor din funcţia obiectiv, astfel:

max c xcx TT )min(−−= ; min c xcx TT )max(−−= (2.16)

b) o variabilă x arbitrară (variabilă căreia nu i se impune restricţie de semn) se poate înlocui cu două variabile nenegative 2,1 xx , prin relaţia :

0xxundexxx 2121 ≥−= ,, (2.17)

c) o variabilă x supusă condiţiei de nepozitivitate ( 0≤x ) se transformă într-o variabilă

nenegativă prin substituţia

0xundexx 11 ≥−= , (2.18)

d) Restricţiile de tip inecuaţie se transformă în restricţii de tip ecuaţii ţinând cont de următoarele :

��

≥=−⇔

��

≥≥

0yxbyxa

0xbxa TT

,şi

��

≥=+⇔

��

≥≤

0yxbyxa

0xbxa TT

, (2.19)

unde y se numeşte variabilă ecart. Variabilele ecart nu apar în funcţia obiectiv sau astfel spus apar în funcţia obiectiv dar cu coeficienţi nuli: 0=e

jc (unde =ejc coeficienţi ai variabilelor ecart).

e) sensul unei inegalităţi se schimbă prin înmulţirea cu “–1“. În aplicaţiile practice apar frecvent situaţii în care modelul conţine simultan restricţii de toate tipurile (concordante, neconcordante, egalităţi), problema fiind dată în formă generală, iar rezolvarea ei poate fi abordată fără a restrânge generalitate. Exemplul 2.1 Să se scrie formele echivalente ale problemei de programare liniară:

Problema dată este în forma generală. Pe baza transformărilor echivalente vom construi formele echivalente ale problemei iniţiale. Deoarece variabila x3 nu are restricţii de semn, o vom înlocui, cu diferenţa a două variabile

Programare liniară

12

( )

��

�

��

�

�

≥≤−+

≥+−−≥+−

=−+−

oarecarex0xx0x2x3x2

2x4x3x2x5x

4xx3x2xx3

321

321

31

321

21

321

,,,,

,,

,max

)()()()(

4321

pozitive: x3 = x4 – x5. Pentru ca problema să aibă forma standard, toate restricţiile trebuie să fie egalităţi, de aceea în restricţiile (2), (3) şi (4) vom introduce variabilele de egalizare x6, x7, x8. Forma standard va fi:

( )

��

�

��

�

�

≥=++−+

=−−+−−=−−+−

=−−+−

0xxx0xxxx3x2

2xx4x4x3xx2x2x5x

4xx3x2x2xx3

821

85421

7541

65421

21

5421

,...,,,

,,

,max

Forma canonică se obţine transformând restricţia (1) în două inegalităţi şi toate

inegalităţile „ ≥ ” le transformăm în inegalităţi „ ≤ ” deoarece problema este dată de maximizare. Astfel, x3 trebuie înlocuit cu diferenţa x4 – x5.

Se obţine astfel forma canonică

( )

.

,,,,

,,

,,

max

��

�

��

�

�

≥≤+−+

−≤+−−≤+−+−

−≤+−≤−

−+−

0xxxx0xxx3x2

2x4x4x3x2x2x5x

4xx34xx3

x2x2xx3

5421

5421

541

5421

21

21

5421

2.1.3. Modelul matematic al problemei de programare liniară Pentru a înţelege modelul matematic al problemelor de programare liniară sub forma generală, vom analiza câteva exemple din practica industrială:

• Alocarea optimă a resurselor în producţia industrială O firmă urmează să producă n tipuri de produse Pj , nj ,1= , folosind m tipuri de

resurse Ri mi ,1= . Se cunosc coeficienţii tehnologici aij ; cantităţile disponibile bi din resursele Ri ;

profitul unitar cj pentru fiecare produs Pj. Să se întocmească planul optim de producţie al firmei astfel încât profitul total realizat

să fie maxim.


13

Elaborare modelului matematic al problemei Condiţii generale de desfăşurare a activităţii analizate :

- restricţiile problemei apar din următoarea condiţie: cantitatea totala din resursa i folosită pentru producerea celor n produse nu poate fi mai mare decât cantitatea disponibila:

mibxa ijn

jij ,1,

1=∀≤�

= (2.20)

- condiţiile de nenegativitate asigură obţinerea unei soluţii realizabile din punctul de

vedere al logicii practice industriale.

xj ≥ 0 , nj ,1=∀ (2.21)

Sistemul de inecuaţii (2.20) şi (2.21) poate avea o infinitate de soluţii, deci putem organiza procesul de producţie pentru realizarea produsului P într-o infinitate de moduri dar respectând condiţiile anterioare .

Acest fapt face evidentă imposibilitatea practică a managerului de a compara toate variantele de plan posibile deci este necesară introducerea unui alt criteriu.

Adoptarea unei variante de plan (în fapt fundamentarea deciziei) se face, preferabil, pe baza unui criteriu economic (cel mai uzual – maximizarea profitului sau în alte cazuri minimizarea costurilor). Aplicarea acestui criteriu economic, presupune cunoaşterea profitului total.

Deci : jjn

jxc�

=1reprezintă profitul total pentru produsele Pj

Funcţia obiectiv (scop, eficienţă) va fi :

max jn

jj xcf �

==

1 (2.22)

Deci, modelul de programare liniară ce urmează a fi rezolvat pentru determinarea

planului optim de producţie astfel încât profitul total realizat să fie maxim este:

��

�

��

�

�

≥

� ≤

�==

0x

bxa

xcf

j

ijij

n

1jjjmax

(2.23)

• Problema de transport

Un produs omogen P este stocat în m depozite Di, în cantităţile ai , mi ,1= şi este cerut de spre a fi transportat la n centre de consum Cj ,în cantităţile bj, nj ,1= . Se cunosc costurile cij pe unitatea de produs transportată de la centrul Di la centrul Cj . Se cere determinarea unui plan de transport astfel încât costul total de transport să fie minim.

Programare liniară

14

Elaborarea modelului matematic al problemei Notaţii : ai = cantitatea din produs care se află în depozitul i; bj = cantitatea cerută de consumatorul j ( 1<j<n); xij= cantitatea ce urmează a fi transportată de la depozitul i la consumatorul j ; cij= costul unitar al transportului din depozit la consumator. Cu aceste notaţii se pot exprima următoarele mărimi ce ne ajută să stabilim restricţiile

problemei şi funcţia obiectiv: • cantitatea transportată de la depozitele Di la toate cele n centre de consum este cantitatea

sa disponibilă:

i

n

jij ax =�

=1 , mi ,1= (2.24)

• cantitatea transportată de la toate cele m depozite la consumatorul Cj reprezintă necesarul

acestuia, bj , nj ,1= .

�=

=m

ijij bx

1

nj ,1= (2.25)

• pentru scrierea modelului se pleacă de la forma echilibrată a problemei de transport şi

anume cantitatea totală expediată de la cele m depozite este egală cu cantitatea sa disponibilă:

��==

=n

jj

m

ii ba

11 (2.26)

• variabilele satisfac evident condiţia de nenegativitate :

xij ≥ 0 (2.27)

• funcţia obiectiv este următoarea :

ij

m

i

n

jij xc��

= =1 1min (2.28)

Se obţine un program liniar, ce se va supune metodelor programării liniare şi poartă

denumirea de program de transport :

��

�

��

�

�

==∀≥

==

==

=

�

�

� �

=

=

= =

njmix

njbx

miax

xcf

ij

n

jiij

n

jiij

m

i

n

jijij

,1,,1,0

,1,

,1,

)min(

1

1

1 1

(2.29)


15

• Problemă de repartizare a sarcinilor de producţie Într-un atelier de montaj echipele njE j ,1, = , pot monta cu randamente diferite,

produsele m1iPi ,, = . Activitatea atelierului este caracterizată de următoarele date cunoscute: ija - timpul necesar pentru montajul unei cantităţi de produs Pi de către echipa

;jE ijc - cheltuielile necesare pentru montajul unei unităţi de produs Pi de către echipa ;jE ib

- cantitatea planificată din produsul Pi , mi ,1= ; jt - timpul de lucru disponibil al echipei

njE j ,1, = . Să se stabilească o repartizare a produselor, echipelor, din atelierul de montaj astfel

încât cheltuielile totale necesare să fie minime. Elaborarea modelului matematic al problemei: Variabilele de decizie (necunoscutele) se notează cu ijx şi reprezintă cantitatea din produsul Pi ce trebuie realizată de echipa Ej. Funcţia obiectiv este o funcţie de cost, respectiv, cheltuielile celor n echipe, necesare pentru montajul cantităţilor repartizate din cele m produse; funcţia trebuie minimizată:

� �== =

m

1i

n

1jijij xcfmin (2.30)

Cantitatea de produse de fiecare tip planificată trebuie realizată:

mibx i

n

jij ,1,

1==�

= (2.31)

Oricare echipă poate executa produse în limita fondului de timp disponibil:

�=

=≤m

ijijij njtxa

1,1, (2.32)

Variabilele ijx se supun condiţiei de nenegativitate:

njmixij ,1,,1,0 ==∀≥ (2.33) Deci, modelul matematic al problemei este:

==∀≥

∑ =≤

==∑

∑ ∑=

=

=

= =

n1jm1i0x

n1jtxa

m1ibx

xcf

ij

m

1ijijij

in

1jij

m

1i

n

1jijij

,,,,

,,

,,

min

(2.34)

• Problemă de utilizare a capacităţii utilajelor

Programare liniară

16

O firmă produce n tipuri de produse care pot fi fabricate pe m utilaje care au capacităţi de producţie limitate pe o anumită perioadă. Se cunosc: procentul ija din capacitatea utilajului

i necesar pentru producerea unei unităţi din produsul j; profitul unitar cj al produsului nj ,1= . Să se stabilească un program de fabricaţie care să permită utilizarea optimă a

capacităţii disponibile a celor m utilaje.

Elaborarea modelului matematic al problemei: Variabilele problemei sunt cantităţile de produse fabricate în perioada considerată. Se

notează cu xj, numărul de produse de tipul nj ,1= . Funcţia obiectiv este profitul total obţinut de firmă pentru cele n tipuri produse; funcţia

trebuie maximizată:

�==

n

1jjj xcfmax (2.35)

Restricţiile de capacitate ale celor m utilaje se exprimă sub forma:

�=

=≤m

jijij mixa

1,1,1 (2.36)

Variabilele xj se supun condiţiei de nenegativitate:

njx j ,1,0 =≥ (2.37)

Atunci, modelul matematic al problemei este:

��

�

��

�

�

=≥

� =≤

�=

=

=

n1j0x

m1i1xa

xcf

j

m

1jijij

n

1jjj

,,

,,

max

(2.38)

2.2. Consideraţii generale privind problemele de programarea liniară

2.2.1. Soluţii şi fundamente ale problemei de programare liniară Fie problema de programare liniară dată în formă standard matricial:

��

��

�

≥=0xbAx

xcTmin(max), unde

��

��

�

∈∈

∈

mnm

n

RbMA

RxC

,

, (2.39)

Sistemul de ecuaţii Ax=b are o infinitate de soluţii, deci trebuie să se găsească în mulţimea soluţiilor o soluţie ce realizează valoarea optimă (minimă sau maximă ) a funcţiei obiectiv.


17

• Soluţie admisibilă Un vector x = ( ) n

n Rxxx ∈...21 care satisface restricţiile si condiţia de nenegativitate se numeşte soluţie admisibilă sau posibilă a problemei de programare liniară. Mulţimea soluţiilor admisibile, S, este:

}{ 0xbAxRxS n ≥=∈= ,/ (2.40) Sistemul de ecuaţii, având m ecuaţii şi n necunoscute, cu m<n şi rang A=m are m necunoscute principale şi n-m necunoscute secundare. O soluţie de bază se obţine prin anularea celor n-m necunoscute secundare, deci are cel mult m componente nenule. • Soluţie admisibilă de bază

Se numeşte soluţie admisibilă de bază pentru sistemul Ax=b, vectorul −x , ce satisface

condiţiile : a) x soluţie a sistemului : Ax=b ; b) coloanele din A, corespunzătoare componentelor lui x nenule, formează o

mulţime liniar independentă. În cazul când o soluţie de bază are mai puţin de m componente diferite de zero, atunci ea se numeşte soluţie degenerată, în caz contrar ea fiind nedegenerată. • Soluţie optimală O soluţie admisibilă care face optimă funcţia z=min(max)c T x se numeşte soluţie optimală. Este posibil ca problema de programare liniara să aibă soluţie optimă unică, să aibă mai multe soluţii optime sau să nu admită soluţie optimă. • Soluţie grafică

Acest tip de soluţie va fi studiat detaliat în paragraful 2.2.3. Teoremele şi definiţiile care urmează, specifică unele proprietăţi ale soluţiilor

ce justifică clasificarea realizată anterior. Teorema 2.1 (Teorema fundamentală a programării liniare): Dacă problema de programare liniară în formă standard admite un program (soluţie

admisibilă), atunci ea are cel puţin un program de bază. Dacă problema are un program optim, atunci are un program optim de bază.

Demonstraţie: Fie x∈S un program al următoarei problemei de programare liniară:

��

��

�

≥=

0xbAxxc Tmin

. (2.41)

Notăm cu p numărul componentelor nenule ale vectorului x. Fără a restrânge generalitatea problemei putem presupune că cele p componente

nenule sunt chiar primele componente din cele n ale vectorului x adică:

Programare liniară

18

x = ( x1 , x2 , x3 , …xp , 0, 0 ,0)T (2.42)

• Dacă p = 0, atunci x = 0 deci afirmaţia teoremei este evidentă. • Dacă p > 0, atunci există două posibilităţi:

- dacă vectorii a1 , a2 , ..ap ∈ A corespunzători celor p componente nenule ale lui x sunt liniari independenţi, atunci x este program de bază.

- dacă vectorii a1 , a2 , ..ap ∈ A corespunzători celor p componente nenule ale lui x sunt liniari dependenţi atunci există numerele reale: y1, y2,.. …yp nu toate nule astfel încât să fie satisfăcută relaţia:

a1y1 + a2y2 +…..+apyp = 0 (2.43)

Relaţia (2.43) se poate scrie sub următoarea formă echivalentă : Ay = 0 cu y ≠0. Notăm cu y vectorul cu primele p componente nenule şi următoarele componente n-p

nule: y = (y1, y2 , …yp, 0, 0 .0 )T. Atunci, obţinem: A( x + λy ) = Ax + λAy = b, ( ∀ ) λ ∈ R Deci, x + λy este soluţia sistemului Ax=b astfel putem determina valori ale lui λ

pentru care x + λy este program pentru problema (2.41), deci este îndeplinită şi condiţia: x + λy > 0

Notăm: I1 = mulţimea indicilor i , 1< i < p , yi > 0; I2 = mulţimea indicilor i , 1< i <p , yi < 0. Fie:

λ1 = ��

��

�

Φ=∞−

Φ≠−∈

1

1i

i

Ii

I

Iyx

1

,

),(max λ2 =

��

��

�

Φ=∞+

Φ≠−∈

2

2i

iIi

I

Iyx

2

,

),(min (2.44)

Deci pentru oricare ],[ 21 λλλ ∈ , avem îndeplinită condiţia: x + λy ≥ 0, deci vectorul

x + λy este program. Rezultă că 0ycT = ,deoarece în caz contrar alegând pe λ de semn contrar valorii lui

ycT , avem următoarele: xcycxcyxc TTTT <λ+=λ+ )( , ceea ce contrazice faptul că x este program optim. Prin urmare xcyxc TT =λ+ )( , adică x+ λy este program optim.

Astfel putem alege o valoare λ0 pentru care vectorul x + λ0y să aibă cel mult p-1 componente nenule, deci λ0 )( 21 λλ +∈ ( 21,λλ nu pot fi ambele infinit)

În caz particular, λ = λ0 = )(min0 i

i

iy yx

< deci se va obţine programul soluţie x + λ0y cu p-1

componente pozitive şi astfel vom avea două cazuri : • Dacă coloanele corespunzătoare componentelor sunt liniar independente atunci programul

anterior este program de bază. • Dacă coloanele corespunzătoare componentelor sunt liniar dependente atunci se reia

algoritmul într-un număr finit de paşi, cel mult p până se va ajunge la primul caz şi se obţine un program optim de bază pentru problema dată.

Definiţia 2.1: Fie V un spaţiu liniar peste corpul R şi x, y doi vectori din V. Mulţimea

vectorilor [ ] { }10yx1XVXyx ≤λ≤λ+λ−=∈= ,)(/, se numeşte segment al lui V (uneşte vectorul x cu vectorul y ).

Definiţia 2.2: O mulţime M de vectori din V se numeşte mulţime convexă dacă (∀) x, y ∈ M şi


19

(∀) λ ∈[ 0,1] , atunci [ x, y] ⊆ M . Deci se poate spune că mulţimea M din V este convexă, dacă odată cu doi vectori x, y

∈ M conţine şi segmentul determinat de aceşti vectori. Definiţia 2.3: Vectorul X ∈ M se numeşte vârf sau punct extrem al mulţimii M dacă nu

există vectorii x, y ∈ M astfel încât { }10,)1( ≤≤+−= λλλ yxX . În caz contrar X se numeşte punct interior mulţimii M .

Definiţia 2.4 : Prin combinaţie liniară convexă a vectorilor x1 ,x2 …,xm ∈ M se

înţelege o expresie de forma λ1x1 + λ2x2 + …+ λmxm cu λ ∈[ 0,1 ] şi λ1 + λ2 + …+ λm = 1 Concluzie: Orice punct interior X al unei mulţimi convexe M se poate exprima ca o

combinaţie liniară convexă de un număr finit de puncte extreme. Teorema 2.2: Mulţimea soluţiilor admisibile ale unei probleme de programare liniară

este o mulţime convexă . Demonstraţie : Fie mulţimea soluţiilor admisibile dată de relaţia (2.40). Fie două soluţii: x1 , x2 ∈ S. Atunci pentru λ ∈ [0,1] avem

x = λx1 +(1- λ)x2 ≥0 (2.45) Înlocuind relaţia (2.45) în relaţia (2.40) obţinem : Ax= A[λx1 +( 1- λ)x2]=λAx1 + (1- λ) Ax2 = λb + (1- λ)b = λb+ b - λb = b, deci mulţimea soluţiilor problemei de programare liniară este o mulţime convexă. Teorema 2.3: Orice soluţie admisibilă de bază a unei probleme de programare liniară

este vârf sau punct de extrem al mulţimii soluţiilor admisibile. Demonstraţie.

Presupunem că soluţia admisibilă de bază x are forma x=(x1 x2 … xm 0 …0T.

Aceasta înseamnă că 0≥ix (i = 1, m), vectorii p1, p2, …,pm sunt liniar independenţi şi x satisface sistemul de restricţii, deci

x1P1 + x2P2 +… + xmpm +0pm+1 + … + 0pn = p0 (2.46) Trebuie arătat că x este vârf al mulţimii S a soluţiilor admisibile. Presupunem prin absurd că x nu este vârf, ci punct interior, adică există doi vectori

Sxx ∈'',' astfel încât: ( ) ''1' xxx λλ −+= , ( )1,0∈λ Scris pe componente:

( ) '1

'11 1 xxx λλ −+= , ( ) ''

2'22 1 xxx λλ −+= ,……., ( ) ''' 1 mmm xxx λλ −+= ,.….…, ( ) ''' 10 nn xx λλ −+=

Însă ( )1,0∈λ , deci 01 >− λ , iar 0' ≥ix ( )ni ,1= şi 0'' ≥ix ( )ni ,1= deoarece Sxx ∈'',' , astfel că, din cele n – m relaţii se obţin:

00 ''1 ==+ nm xx � ; 00 ''''

1 ==+ nm xx � şi deci vectorii '',' xx au formele:

Programare liniară

20

( )Tmxxxx 00' ''

2'1 ��= , ( )T

mxxxx 00'' ''''2

''1 ��= (2.47)

Exprimăm faptul că Sxx ∈'',' verifică restricţiile

0mm2211 ppxpxpx =+++ '''� (2.48)

0mm2211 ppxpxpx =+++ ''''''� (2.49)

Însă vectorii pi ,…,pm sunt liniari independenţi. Rezultă:

'''''2

'2

''1

'1 ,, mm xxxxxx === � adică ''' xx = (2.50)

Aceasta înseamnă că nu există vectorii Sxx ∈'',' astfel ca ( ) ( )1,0''1' ∈−+= λλλ xxx

prin urmare x este vârf sau punct de extrem în S. Teorema 2.4: Funcţia obiectiv a unei probleme de programare liniară ia valoare

optimă într-un punct extrem a mulţimii convexe M a tuturor soluţiilor admisibile ale problemei de programare liniară.

Demonstraţie: Presupunem că se cere ca funcţia obiectiv să fie minimizată. Notam cu M~ = { xi , i ∈ I } mulţimea punctelor extremale ale lui M şi fie x1 punct

extrem pentru care 1T xc = }{min i

T

Iixc

∈= z1

Presupunem prin absurd că această afirmaţie nu este adevărată, atunci există x0 ∈{ }MM ~− astfel încât : 0

T xc = z0 < z1, deoarece x0 nu este punct extrem atunci :

x0 = iIi

i x�∈

λ , λI ≥ 0 , �∈Ii

iλ = 1 (2.51)

Dar z0 = 0

T xc = iT

Iii xc '

�λ∈

> 1T

Iii xc�λ

∈ = cT x1 = z1, ceea ce este o contradicţie. Deci

x1 este un program minimal pentru problema de programare liniară. Consecinţă : Dacă funcţia obiectiv ia aceeaşi valoare optimă în mai multe puncte extremale, atunci

orice combinaţie liniară convexă a acestora este soluţie optimă a problemei de programare liniară.

2.2.2. Baze ale problemei de programare liniară

Fie problema de programare liniară în forma standard (2.13), în care matricea A are m

linii şi n coloane, iar rang A = m < n. Ecuaţiile ce compun sistemul liniar Ax = b sunt liniar independente, iar sistemul are o infinitate de soluţii.

Astfel, în matricea A există cel puţin un grup de m coloane liniar independente, care formează o bază a spaţiului Rm.

Definiţiile ce urmează reprezintă fundamente ce stau la baza rezolvării modelelor de programare liniară. Definiţia 2.5 Se numeşte bază a problemei de programare liniară în formă standard un grup de m coloane liniar independente.


21

Problema (2.13) are un număr finit de baze şi anume mnC .

Fie B o bază formată cu m coloane, ale matricei A. Matricea A se poate scrie partiţionat sub forma:

[ ]SBA ,= , cu ( )[ ] Ii

iaB ∈= , ( )[ ] JjjaS ∈= (2.52)

unde prin I şi J s-au notat mulţimile de indici corespunzători coloanelor din baza B şi, respectiv, a celorlalte coloane:

( ){ }

{ } InJ

BaniI i

/,...,2,1

,1

=

∈== (2.53)

Partiţionarea vectorului x al variabilelor problemei este următoarea:

��

��

�= S

B

xxx , cu [ ] Iii

B xx ∈= , [ ]Jjj

S xx∈

= (2.54)

iar partiţionarea vectorul c al coeficienţilor funcţiei obiectiv este:

��

��

�= S

B

cc

c , cu [ ] IiiB cc ∈= , [ ]

JjjS cc

∈= (2.55)

În raport cu baza B aleasă, variabilele ( )Iixi ∈ se vor numi variabile de bază, iar

( )Jjx j ∈ variabile secundare. Sistemul de ecuaţii Ax = b se poate scrie după partiţionare sub forma:

[ ] bSxBxbxx

SB SBS

B

=+⇔=��

��

�⋅, (2.56)

Matricea B fiind o bază a spaţiului Rm este inversabilă. Astfel prin înmulţirea relaţiei

(2.56) la stânga cu B-1 se obţine forma explicită a sistemului de ecuaţii:

SB SxBbBx 11 −− −= (2.57)

Notăm cu:

bBxB 1−= (2.58)

( ) njaBy jBj ,1,1 == − (2.59)

Înlocuind relaţiile (2.58) şi (2.59) în relaţia (2.57) obţinem:

�∈

−=Jj

Bj

Bj

BB xyxx (2.60)

Scrisă pe componente relaţia (2.60) devine:

Programare liniară

22

IixyxxJj

Bj

Bij

Bi

Bi ∈−= �

∈, (2.61)

Definiţia 2.6. Soluţia de bază corespunzătoare bazei B este:

nB

B Rxx ∈��

�

��

�=

0 (2.62)

O soluţie de bază este o soluţie admisibilă (program) a unei probleme de programare

liniară dacă 0≥B

x . Definiţia 2.7 Baza B care satisface condiţia

01 ≥− bB (2.63)

se numeşte bază primal admisibilă. Ţinând seama de relaţiile (2.54) şi (2.55), funcţia obiectiv a problemei de programare

liniară, xcz T= , poate fi exprimată prin:

[ ] ( ) STS

S11TB

STS

BTBS

BSB xcSxBbBcxcxc

xxccz +−=+=�

�

��

�⋅= −−'

( ) STS

1TB

1TB xcSBcbBcz '' −−= −− (2.64)

Notăm cu:

BTB

Bxcz = (2.65)

n1jycz Bj

TB

Bj ,, == (2.66)

Înlocuind relaţiile (2.65) şi (2.66) în relaţia (2.64) obţinem:

( )�∈

−−=Jj

Bjj

Bi

Bxczzz (2.67)

Definiţia 2.7. Constanta

Bz din relaţia (2.67) reprezintă valoarea funcţiei obiectiv în soluţia

asociată bazei B.

Diferentele jBj cz − ( )Jj ∈ se mai numesc costuri reduse şi au rolul esenţial în

caracterizarea optimalităţii unei soluţii admisibile de bază a unei probleme de programare liniară.

2.2.3. Interpretarea geometrică a problemei de programare liniară O interpretare geometrică a unei probleme de programare liniara se poate obţine

simplu în cazul când problema are două variabile (spaţiu R2) şi se prezintă sub forma canonică.


23

Fie modelul de programare liniară (2.11) exprimat în funcţie de două variabile de decizie x1 şi x2.

1) Restricţiile unui astfel de model pot fi exprimate prin a) egalităţi : 1212111 bxaxa =+

b) inegalităţi : sau 2222121

2222112

bxaxabxaxa

≤+≥+

(2.68)

2) Condiţii de nenegativitate : 0,0 21 ≥≥ xx (2.69)

3) Funcţia obiectiv (2.10) poate fi: 2211 xcxcz +=min(max) (2.70)

Realizând o analiză din punct de vedere grafic putem observă următoarele : • egalitatea 1212111 bxaxa =+ , reprezintă o dreapta. Mulţimea soluţiilor ( )21 xx , aparţine

acestei drepte (d), iar această dreaptă (curbă de nivel), împarte planul ( )210 xx în două semiplane.

• inegalitatea 1212111 bxaxa <+ , - mulţimea soluţiilor fiind reprezentată în acest caz printr-o arie, dreapta împarte planul ( )210 xx în doua semiplane ce au o arie comună şi în final un punct comun.

Pentru aflarea soluţiei optime, dacă ea există, trebuie aflată mai întâi mulţimea soluţiilor admisibile S – mulţime ce satisface sistemul de restricţii şi condiţiile de nenegativitate. În reprezentarea grafică acesta va fi o mulţime convexă, reprezentată printr-un domeniu, numit admisibil. Exemplul 2.2 Să se rezolve problema de programare liniară

0x0x5xx

2x2x2xx2

xx2z

21

21

21

21

21

≥≥

��

�

��

�

�

≤+≤−

−≥−+=

,

)max(

Pentru determinarea domeniului admisibil se procedează în modul următor: se află

domeniul care satisface cele trei restricţii şi condiţiile 0,0 21 ≥≥ xx . Se figurează dreptele:

(d1) 2x1- x2 = -2, trece prin A1(-1,0), B1(0,2) (d2) x1- 2x2 = 2, trece prin A2(2,0), B2(0,-1) (d3) x1+ x2 = 5, trece prin A3(5,0), B3(0,5) şi apoi se ia, în cadranul întâi intersecţia domeniilor ce reprezintă soluţiile, respectiv, ale celor trei inecuaţii, fig. 2.1.

Prin intersecţia celor trei semiplane s-a obţinut domeniul admisibil, ce este o mulţime convexă. Coordonatele oricărui punct din acest domeniu satisfac toate restricţiile şi condiţiile de nenegativitate ale problemei. Conform teoremei 2.4, dacă funcţia obiectiv îşi atinge valoarea maximă, atunci z ia valoarea maximă într-un vârf ( punct extrem al mulţimii convexe). Acestea sunt vârfurile poligonului, notate cu: O, A, B, C, D.

Programare liniară

24

Coordonatele acestor puncte se află uşor astfel:

0

d2

x1

D(0,2)

x2

d1

A(2,0)

B(4,1)

C(1,4)

d3

(D)

Fig.2.1

( ) ( )��

=+=−

∈5

22

21

2132 xx

xxddB � ( )1,4B

( ) ( )��

=+−=−

∈5

222

21

2131 xx

xxddC � ( )4,1C

Aflarea soluţiei optime se bazează pe faptul că funcţia obiectiv, având două variabile se

poate reprezenta printr-o dreaptă (D).

(D): c1x1 + c2x2 = z

Adusă la forma y = mx + n unde m este panta, iar n ordonata la origine, rezultă:

(D): 1

12

12 c

zxccx +−=

care reprezintă o mulţime de drepte paralele între ele, având panta constantă2

1

ccm −=

şi ordonata la origine variabilă, 1czn = .

În problemele de maxim vom alege poziţia care are ordonata la origine astfel ca ea să furnizeze valoarea maximă pentru z.

Analog pentru problemele de minim. Pentru exemplul de mai sus rezultă: (D) : x2 = -2x1 + z ; se alege acea dreaptă ce trece prin unul din vârfuri, ce are m = -2

şi ordonata n = z = max Ea este figurată punctat în figura 2.1. Ordonata la origine maximă corespunde punctului

B deci

x1 = 4 şi x2 = 1 z = 2*4 +1*1 = 9 = max

Deoarece panta dreptei (D) este m = -2 = tg α, rezultă că unghiul α = 116,560.


25

Exemplul 2.3. Pentru fabricarea a două produse P1 şi P2, o firmă dispune de patru tipuri de resurse Ri

( )4,1 . Cantităţile de resurse Ri folosite pentru fabricarea fiecărei unităţi din produsele P1 şi P2, în unităţi convenţionale (tone etc) sunt date în tabelul 2.1.

Se mai cunosc cantităţile disponibile ale firmei din fiecare resursă Ri ( )4,1=i şi beneficiile pentru fiecare unitate din cele două produse.

Să se determine planul de producţie astfel ca beneficiul total să fie maxim. Tabelul 2.1

Introducând variabilele de decizie: x1 = numărul de unităţi din produsul P1 şi x2 =

numărul de unităţi din produsul P2 , rezultă următorul model matematic de P.L.:

��

�

��

�

�

≤≤

≤+≤+

124164

821222

2

1

21

21

xx

xxxx

max,, =+=≥≥ 2121 x3x2z0x0x

Soluţia grafică (2.2) se obţine determinând domeniul admisibil:

( )( )( )( )��

�

��

�

�

==

=+=+

12x4d16x4d

8x2xd12x2x2d

24

13

212

211

(D) 2x1 + 3x2 = z Se observă că dreptele ( )1d , ( )2d şi ( )3d sunt concurente în punctul B(4,2), iar

( ) ( )32 ddC �∈ are coordonatele C(2,3).

0

d2

x1

D(0,3)

x2

d1

A(4,0)

B(4,2)

C(2,3)

(D)

d3

d4

Fig.2.2

Resurse R1 R1 Disponibil R1 2 2 12 R2 1 2 8 R3 4 0 16 R4 0 4 12 Beneficiu 2 um 3 um

Programare liniară

26

Soluţia optimă a problemei este:

x1 = 4; x2 = 2 f(x) = 14 = max Verificăm soluţia în restricţiile problemei.

Rezultă că resursele R1, R2 şi R3 sunt resurse rare, utilizate în întregime în timp ce resursa R4 nu a fost în întregime utilizată.

Cantitatea din resursa R4, ce rămâne disponibilă poate fi determinată şi ulterior folosită cunoscând preţul umbră (dual).

Această analiză urmează a fi detaliată în subcapitolul 2.4.

2.3. Metoda Simplex

Metoda Simplex sau “ metoda îmbunătăţirilor succesive “ evită cercetarea exhaustivă a tuturor soluţiilor de bază ale unei probleme de programare liniară, construind succesiv soluţii realizabile de bază din ce în ce mai bune ale modelului până când este obţinută o soluţie de bază optimă. Prin soluţie „mai bună” înţelegând soluţia ce dă funcţiei de eficienţă (obiectiv) o valoare mai mică, respectiv mai mare decât cele precedente după cum funcţia de eficienţă este de minim sau de maxim.

Deci acest algoritm este o metodă de examinare sistematică a programelor de bază ce dă funcţiei de eficienţă o valoare optimă.

Această metodă pune în evidenţă cazul în care problema admite un optim infinit sau mulţimea programelor este vidă. 2.3.1. Fundamente teoretice în aplicarea metodei Simplex

Prezentarea metodei simplex se realizează pe un model de programare liniară dat în formă standard şi în care funcţia obiectiv este o funcţie de minimizare.

��

��

�

≥=0xbAxxcTmin

, unde ��

��

�

∈∈

∈

mnm

n

RbMA

RxC

,

, (2.71)

Fie B o bază primal admisibilă extrasă din matricea A şi bBBx 1−= o soluţie de bază iniţială a problemei de programare liniară.

Pentru ordonarea şi facilitarea calculelor se utilizează în aplicarea practică a algoritmului tabele ce poartă denumirea de tabele simplex.

Aceste tabele sunt tabele simple ce au m+1 linii şi n+1 coloane şi cuprind coeficienţii numerici al problemei (2.71) corespunzători bazei primal admisibile B (tab 2.2). Tabelul conţine în prima coloană, variabilele de bază (V.B.), în coloana a doua valoarea variabilelor de bază (V.V.B), iar în următoarele n coloane vectorii n1jy B

j ,, = . Pe ultima linie a tabelului se trece valoarea funcţiei obiectiv pentru baza B notată cu

Bz şi diferenţele n1jcz jBj ,, =− .

Acestui tabel se ataşează o linie deasupra variabilelor jx şi o coloană la stânga

coloanei V.B cu coeficienţii corespunzători funcţiei obiectiv n1jc j ,, = .


27

Tabelul 2.2

Bix

Blx

Bmx

cl ck cj cn... ... ...

xl ... xk ... xj... xnV.V.BV.B.CB

c1

ci

cl

cm

...

...

...

...

...

...

......

z ... ... ...

yB

11

yB

i1

yB

l1

yB

m1

yB

1k

yB

ik

yB

lk

yB

mk

yB

1j

yB

ij

yB

lj

yB

mj

yB

1n

yB

in

yB

ln

yB

mn

x1Bx1B

xiB

xlB

xmB

z B1 - c 1 z B

k - c k zBj - c j zB

n - cn

...

...

...

...

B

Tabelul simplex se ataşează fiecărei baze B din algoritm şi are ca fundamente rezultatele teoretice ce sunt prezentate în continuare. Teorema 2.5 Criteriu de optimalitate Fie B o bază primal admisibilă pentru probleme de programare liniară (2.71). Dacă

0≤− jcz Bj , oricare ar fi j J∈ , atunci programul de bază asociat bazei B, bBBx 1−= este o

soluţie optimă a problemei de programare liniară considerată. Teorema 2.6 Criteriu de infinitudine a soluţiilor Fie B o bază primal admisibilă pentru probleme de programare liniară (2.71). Dacă există indicele k J∈ astfel încât 0≥− kcz B

k şi 0≤Biky , oricare ar fi Ii ∈ atunci problema

are un optim infinit. Teorema 2.7 Criteriu de îmbunătăţire a soluţiilor Fie B o bază primal admisibilă pentru probleme de programare liniară 2.71. Fie k J∈ astfel încât 0>− kcz B

k (2.72) şi { } Φ≠>∈=+ 0/ BikyIiI . Pentru

indicele +∈ Ii determinat cu relaţia:

Blk

Bl

Bik

B

y

x

yix

Ii=

+∈min (2.73)

se obţine un nou program de bază Bx~

cel puţin la fel de bun ca Bx , corespunzător unei noi

baze B~ care are aceleaşi coloane ca şi B, cu excepţia coloanei )(la ce se înlocuieşte cu

coloana )(ka . Observaţii: � Baza B~ este primal admisibilă şi verifică toate teoremele anterioare. � Relaţia (2.73) reprezintă criteriul de ieşire din bază şi ne arată indicele +∈ Il , al

coloanei )(la ce urmează să părăsească baza B.

Programare liniară

28

� În cazul în care există mai mulţi indici k J∈ pentru care se îndeplinesc (2.72) şi (2.73) atunci se pot construi mai multe baze primal admisibile şi fiecare dintre acestea modifică valoarea funcţiei obiectiv.

Pentru a obţine mai repede optimul căutat este indicat a alege acel indice pentru care se verifică relaţia.

)())((max kczyx

yx

jcBjz B

kBlk

Bl

Blk

Bl

Jj−=−

∈ (2.74)

În practică utilizându-se pentru evitarea calculelor următorul criteriu:

kcBkzjcB

jzJj

−=−∈

)(max (2.75)

� Relaţia 2.75 reprezintă criteriul de intrare în bază şi ne arată indicele

Jk ∈ al coloanei )(ka ce urmează să intre în baza B. � Elementul lky din tabelul simplex poartă denumirea de pivot.

Pentru calculul elementelor tabelului simplex asociat bazei B~ în raport cu elementele tabelului simplex asociat bazei B se utilizează formulele de schimbare a bazei în cadrul unei operaţii numită pivotare gaussină. În practică formulele de schimbare a bazei se echivalează cu următoarele reguli de transformare a tabelelor simplex :

� Elementele situate pe linia pivotului se împart la valoarea pivotului ; � Elementele situate pe coloana pivotului devin zero cu excepţia

pivotului ce va avea valoarea unu ; � Celelalte elemente ale tabelului simplex se transformă după regula

dreptunghiului. Se consideră dreptunghiul imaginar a cărui diagonală este determinată de

elementul Bijy şi pivotul B

ijy (fig. 2.3) ; noua valoare Bijy~

se obţine împărţind la pivot diferenţa

dintre produsul Blk

Bij yy şi B

ikBlj yy după formula :

Blk

Bik

Blj

Blk

BijB

ij yyyyy

y−

=~

(2.76)

Bijy

Bijy

Biky

Biky

elementul detransformat

pivotul Fig.2.3 2.3.2. Algoritmul simplex primal. Rezultatele teoretice obţinute anterior permit enunţarea algoritmului simplex. Acest algoritm pentru rezolvarea problemelor de programare liniară date în formă standard (2.13) este diferit în raport cu tipul funcţiei obiectiv, respectiv, probleme de minimizare sau maximizare.


29

Algoritmul simplex primal pentru probleme de minimizare • Pasul 1 : Se determină o baza B primal admisibilă.

• Pasul 2 : Se determină următoarele elemente : BjyjcB

jzBzBx ,,, −

• Pasul 3 : Se analizează toate diferenţele jcz Bj − :

� Dacă toate diferenţele jcz Bj − 0≤ , nj ,1=∀ atunci programul Bx este optim.

� Dacă există cel puţin un indice j +∈ J , { }0/ >−∈=+ jBj czJjJ astfel încât

jcz Bj − > 0 se trece la pasul 4.

� Pasul 4 Se determină indicele k +∈ J cu criteriul de intrare în bază

=− kcz Bk )(max jcz B

jJj

−+∈

� Dacă 0≤Bky atunci problema are un optim infinit.

� Dacă +∈∃ Jk)( pentru care 0>Bky se trece la pasul 5.

� Pasul 5: Se determină indicele l I∈ cu criteriul de ieşire din bază:

Blk

Bl

Bij

Bi

Biky

Ii yx

yx =

��

�

�

��

�

�

>

∈min

0

• Pasul 6 : Se înlocuieşte în baza iniţială B vectorul )(la cu vectorul )(ka , obţinându-se astfel o nouă bază B~ , iar pivotul corespunzător este lky . Mărimile tabelului simplex corespunzător noii baze B~ , se vor determina cu ajutorul unei reguli denumită regula dreptunghiului (pivotare în jurul elementului lky ), după care se trece la Pasul 2. Algoritmul simplex primal pentru probleme de maximizare Acest algoritm are paşii 1,2,5,6 identici cu algoritmul pentru probleme de minimizare. • Pasul 3 : Se analizează toate diferenţele jcz B

j − :

� Dacă toate diferenţele jcz Bj − 0≥ , nj ,1=∀ atunci programul Bx este optim.

� Dacă există cel puţin un indice j −∈ J , { }0/ <−∈=− jBj czJjJ astfel încât

jcz Bj − < 0 se trece la pasul 4.

� Pasul 4 Se determină indicele k +∈ J cu criteriul de intrare în bază

=− kcz Bk )(min jcz B

jJj

−−∈

� Dacă 0≤Bky atunci problema are un optim infinit.

� Dacă +∈∃ Jk)( pentru care 0>Bky se trece la Pasul 5.

Algoritmul simplex poate fi exprimat sintetic sub următoarea schemă logică ( fig.2.4).

Programare liniară

30

START

Construiestetabel simplex initial

Exista valori pozitive (negative) pe linia diferentelor?

Indica solutia optima STOP

Nu

Da

Determina coloana pivotului

Exista valori pozitive in coloana pivotului?

Nu Indica solutia optima STOP

Da

Determina linia pivotului

Calculeaza un nou tabel simplex

Fig.2.4

Exemplul 2.4 . Să se rezolve următoarea problemă de programare liniară:

( )��

�

��

�

�

+≥

≤+−≤−

≤−

.2max0,

,62,183

,4

21

21

21

21

21

xxxx

xxxx

xx

Pentru a aplica algoritmul simplex, vom aduce mai întâi problema la forma standard. În acest scop introducem variabilele ecart x3, x4 şi x5:

( )��

�

��

�

�

+≤

=++−=+−

=+−

.2max0,...,,

,62,183

,4

21

621

521

421

321

xxxxx

xxxxxx

xxx

Iteraţia 1 Pasul 1 Fie B o bază admisibilă a problemei formată din coloanele matricii A şi anume a3, a4 şi a5:

( )��

�

�

��

�

�

==100010001

aaaB 543 ,,

Pasul 2 Baza B este matricea – unitate, astfel vom calcula următoarele elemente:

IBB ==−1 şi [ ]61841 === − bbBxB ;


31

1−= By Bj jj aa = , elementele matricii A.

( ) )00012(0001' −=−=−⋅=−⋅=− −jjjjj

Bj

Bj ccacaBccz

.01 =⋅= − bBcz BB Cunoscând toate aceste date, putem forma tabelul simplex iniţial ( tab.2.3). Pasul 3. Deoarece există j −∈ J , { }0/ <−∈=− j

Bj czJjJ astfel încât 0<− j

Bj cz , baza

iniţială nu este optimă. Pasul 4 Se determină indicele k +∈ J cu criteriul de intrare în bază

=− kcz Bk )(min jcz B

jJj

−−∈

=min ( 1,2 −− )=-2. Deci indicele k = 1, astfel variabila x1 va intra

în noua bază B~ şi +∈∃ Jk)( pentru care 0>Bky .

Pasul 5: Se determina indicele l I∈ cu criteriul de ieşire din bază

Blk

Bl

Bij

Bi

Biky

Ii yx

yx =

��

�

�

��

�

�

>

∈min

0

=14

318,

14min =

��

�� ,

deci indicele l = 3. Variabila x3 va părăsi baza B. Pivotul este y31= 1 Pasul 6: Se înlocuieşte în baza iniţială B variabila x3 cu variabila x1 obţinându-se astfel o noua baza B~ ceea ce însemnă că se vor transforma toate mărimile următorului tabel simplex cu regula dreptunghiului. Interaţia 2 Se realizează un pivotaj în jurul elementului y42 (tab.2.3).

Interaţia 3. Se realizează un pivotaj în jurul elementului y53 (tab.2.3).

Interaţia 4 Deoarece 0≥− jj cz pentru toţi j, baza actuală este optimă. Deci programul optim

al problemei noastre este 542

1 =x , 5

362 =x ,

514

3 =x , 04 =x , 05 =x ( 4x şi 5x au valoarea

0, deoarece sunt variabile secundare). Interpretare geometrică.

Pentru problema examinată mai sus se poate da o interpretare geometrică simplă în spaţiu R2.

În planul x1Ox2, mulţimea punctelor (x1, x2) care satisfac restricţia 421 ≤− xx constituie unul din semiplanele determinate de dreapta 4xxd 211 =−:)( , şi anume semiplanul care conţine originea.

Celelalte două restricţii determină analog alte două semiplane. Mulţimea programelor problemei va fi formată din mulţimea punctelor din primul

cadran ( )0,0 21 ≥≥ xx care se află la intersecţia celor trei semiplane. Această mulţime este poligonul OABCD (fig. 2.5). Funcţia obiectiv este max(2x1 +x2). Ecuaţia 2x1 +x2 = z reprezintă o familie de drepte

paralele între ele. În figura 2.4 sunt reprezentate punctat câteva din aceste drepte. Pentru z=z2, funcţia

obiectiv ia valori mai mari decât pentru z = z1, iar pentru z = z3 valori şi mai mari.

Programare liniară

32

Tabelul 2.3

2

V.V.BV.B.CB x2 x3 x4 x5

1 0 0 0

x3

x4

x5

0

0

0

xl

4

18

6

1

3

-1

-1

-1

2

0 -2 -1 0 0 0

1 0 0

0 1 0

0 0 1

CB V.B. V.V.B x2 x3 x4 x5xl

x2 x3 x4 x5xl

x2 x3 x4 x5xl

2 1 0 0 0

2 1 0 0 0

2 1 0 0 0

2

0

0

x1

x4

x5

x1

x2

x5

x3

2

1

0

2

1

0

CB V.B. V.V.B

CB V.B. V.V.B

4

6

10

1

0

0

-1

2

1

1

-3

1

0

0

0

01

1

8 0 -3 2 0 0

7

3

7

17

1

0

0

1

0

0

-1/2

-3/2

5/2

1/2

1/2

-1/2

0

0

1

0 0 -5/2 -3/2 0

42/5

36/5

14/5

24

1

0

0

1

0

0

0

0

1

2/5

1/5

-2/5

1/5

3/5

2/5

0 0 0 1 1

x1

x2

536,

542C

B(7,3)

A(4,0)O (0,0)

D (0,3)

x2

x1

(d2)

(d1)

Fig.2.5

Însă, după cum se vede din figură, nu există nici un program care să dea funcţiei

obiectiv valoarea z3 (dreapta 2x1 +x2 =z3 nu intersectează poligonul OABCD – domeniul soluţiilor).

Cea mai mare valoare pe care o poate lua z pentru punctele din poligonul OABCD se obţine atunci când dreapta 2x1 +x2 = z trece prin punctul C. Valoarea lui z în acest caz este 2. 42/5 + 36/5 = 24.


33

Când am aplicat algoritmul simplex, drept bază iniţială am luat baza B = (a3, a4, a5). Variabilele x1 şi x2 sunt variabile secundare, deci au valoarea 0; reiese că ne-am găsit în vârful O (0,0) al poligonului OABCD, iar valoarea funcţiei obiectiv era z = 0. În continuare, variabila x1 intră în bază şi am obţinut programul x1 = 4, x2 = 0.

Geometric aceasta înseamnă că din vârful O ne-am deplasat până în vârful A (4,0) de-a lungul muchiei OA. În continuare, din vârful A am ajuns în vârful B, mergând pe muchia AB (variabila x3 a păstrat tot valoarea 0, deci ne găseam pe dreapta d1). De aici am ajuns în vârful optim C, urmând muchia BC.

Valoarea funcţiei obiectiv a crescut de la 0 la 8, apoi la 17 (în vârful B) şi, în sfârşit, la valoarea maximă 24.

Acest lucru este valabil şi în cazul general: fiecărei baze admisibile a problemei adusă la forma standard îi corespunde un vârf al domeniului soluţiilor.

Concluzie: Fiecare iteraţie simplex reprezintă o deplasare de la un vârf al domeniului soluţiilor, pe o muchie, până la un vârf, care conferă funcţiei obiectiv o valoare „mai bună”. Exemplul 2.5.

O companie produce trei tipuri de produse A, B, C. Fiecare dintre aceste produse trebuie prelucrate tehnologic aceeaşi maşină unealtă, timp de 2 ore, 3 ore respectiv 1 oră. Maşina unealtă este disponibilă pentru perioada analizată, 400 ore.

Pentru produsele A şi C se folosesc componente speciale, câte o bucată pentru fiecare produs, firma având un stoc disponibil pe perioada analizată de 150 de unităţi din aceste componente. Tot pentru produsele A şi C se utilizează un aliaj special: pentru o unitate din produsul A se utilizează 2 kg de aliaj special, iar pentru o unitate din produsul C, 4 kg. Stocul disponibil este de 200 kg din acest aliaj special.

Studiul de piaţă pentru produsul B arată că se pot vinde pe perioada analizată cel mult 50 de unităţi din acest produs.

Beneficiul unitar al produselor A, B şi C este respectiv: 8 um (unităţi monetare), 5 um, 10 um.

Compania doreşte să stabilească planul de producţie care maximizează beneficiul total pe perioada analizată. Elaborarea modelului matematic

Notăm x1 = numărul de produse A x2 = numărul de produse B x3 = numărul de produse C

unde x1, x2, x3 pentru modelul analizat reprezintă variabilele de decizie.

��

�

��

�

�

≤≤+

≤+≤++

5020042

15040032

2

31

31

321

xxx

xxxxx

01 ≥x , 02 ≥x , 03 ≥x )1058max( 321 xxxz ++=

Se observă că problema nu are formă standard. Introducem variabilele de compensare x4, x5, x6, x7 şi înlocuim max(z)=min(-z),

dorind să aplicăm algoritmul simplex pentru probleme de minim. Calculele efectuate sunt grupate în tabelele simplex reunite în tabelul 2.4. Soluţia optimă este: x = (100, 50, 0, 50, 50, 0, 0), iar funcţia obiectiv este min (f)= -

1050, deci max(z) = 1050 Interpretarea soluţiei:

Variabilele de decizie au valorile : x1 = 100, x2 = 50, x3 = 0

Programare liniară

34

��

�

��

�

�

=+=++

=++=+++

5020042

15040032

72

631

531

4321

xxxxx

xxxxxxx

0≥ix )7,1( =i )1058min( 321 xxxf −−−=

Matricea coeficienţilor tehnico - economici este:

��

�

�

��

�

�

=

1000010010040200101010001132

A

Se vor fabrica 100 unităţi din produsul A, 50 unităţi din produsul B, zero unităţi din produsul C.

Se va obţine beneficiul maxim, egal cu 1050 unităţi monetare. Semnificaţia variabilelor de compensare rezultă din modul cum au fost introduse.

Verificând restricţiile iniţiale ale problemei cu soluţia optimă x1 = 100, x2 = 50, x3 = 0 şi comparând cu sistemul de restricţii în care s-au introdus variabilele de compensare, rezultă:

- orele de lucru pe maşină nu s-au folosit integral, rămânând disponibile x4 = 50 ore; - componentele nu s-au folosit integral, rămânând x5 = 50 unităţi. - stocul de aliaj după efectuarea prelucrărilor este nul x6 = 0 - este satisfăcută condiţia de vânzare pentru B, x7 = 0.

Tabelul 2.4

CB

CB

CB

CB

-8

V.V.BV.B. x2 x3 x4 x5

-5 -10 0 0

x4

x6

x5

0

0

0

xl

400

150

200

2

1

2

3

0

0

0 8 5 10 0 0

1 1 0

1 0 1

4 0 0

V.B. V.V.B x2 x3 x4 x5xl

x2 x3 x4 x5xl

x2 x3 x4 x5xl

-8 -5 -10 0 0

0

0

0

x3

x4x5

00

-8

V.B. V.V.B

V.B. V.V.B

350100

50

3/21/2

3

0

0

0

0

1

1

0

010

0

-500 3 5 0 0 0

200

100

50

-750

3/2

1/2

0

0

0

0

0

1

0

0

0

1

0

3 0 0 0 0

-1050

0

0

1

00

0

-3

-1

2

1

0

0

0

1

0

0 0 -6 0 0

x6 x7

0 0

0 0

0 0

0 0

01

0 0

-1/4

1/4

00-1/4

0

5/2 0

-1/4

1/4

1/4

-3

0

0

5/2 -5

-1

-1/2

1/2

-3

0

0

-4 -5

0 x7 0 1 0 0 0 0 150

-5 -10 0 0 0 0-8x6 x7

x7

-10

50

1/2

0 1 0 0 0 0 1

x6 x7

0

0

-5-10 x3

x4

x5

x2 50

1/2

10 1 0 0 0 0 1

-5 -10 0 0 0 0-8

x6 x7

x1

x4

x5

x2-5

50

50

50100

0 1 0 0 0 0 1


35

2.3.3. Metode de determinarea unei soluţii de bază iniţiale Algoritmul simplex necesită, pentru pornire, ca problema să fie dată în forma standard

şi să aibă o soluţie admisibilă de bază. Prima dintre condiţii se realizează folosind transformări utilizate în programarea

liniară. Pentru cea de-a doua condiţie alegerea la întâmplare a unei baze formată din m vectori

ai matricei A, conduce la soluţii de bază nerealizabile cu care algoritmul simplex nu poate începe.

Găsirea unei baze pur şi simplu prin încercări repetate nu este indicată, această căutare putând dura foarte mult.

Rezolvarea problemei pleacă de la observaţia că singura bază pentru care calculul de mai sus se poate face imediat este matricea unitate, caz în care soluţia de bază corespunzătoare este chiar vectorul termenilor liberi.

Aceasta presupune ca problema să aibă toţi termenii liberi mai mari sau egali cu 0 şi în matricea A să existe toate coloanele matricei unitate.

În acest sens plecăm de la observaţia că existenţa unui vector din matricea unitate este echivalentă cu existenţa unei variabile care apare doar în ecuaţia corespunzătoare lui 1 din acel vector, cu coeficientul 1. Acest lucru poate fi obţinut în două moduri:

1) Alegem o nouă funcţie obiectiv care să-şi atingă extremul printre soluţiile pozitive chiar pentru y = 0 şi în momentul când am obţinut soluţia respectivă pornim cu aceasta ca soluţie iniţială algoritmul simplex pentru fosta problemă (Metoda celor două faze). 2) Adăugăm la vechea funcţie obiectiv noi variabile y cu coeficienţi aleşi astfel încât aportul variabilelor la valoarea funcţiei să fie contrar scopului dorit (infinit pozitiv într-o problemă de minim şi infinit negativ într-o problemă de maxim) (Metoda coeficienţilor de penalizare)

Vom detalia în continuare cele două metode: Metoda celor două faze Fie dată problema de programare liniară la forma standard de maxim:

��

��

�

≥=⋅

⋅

0xb xA

xcT'max (2.77)

în care am aranjat deja ca toţi termenii liberi să fie pozitivi . Faza 1

Constă în rezolvarea unei probleme de programare liniară auxiliară, asociată problemei iniţiale. Astfel construim problema:

��

��

�

≥=+

+++= +++

0x,xbxIAx

xxxxf

a

am

anm

a2m

a1m

a )...min()( (2.78)

unde xa sunt variabilele artificiale ce se introduc în restricţiile problemei atât cât sunt

necesare în scopul formării bazei unitare; Im matricea unitate de ordin m. Rezolvăm cu algoritmul simplex această problemă, pornind rezolvarea de la baza

matrice unitate, putem ajunge la două situaţii:

Programare liniară

36

1. minimul funcţiei f este strict pozitiv, aceasta fiind echivalent cu faptul că egalitatea Ax + Imxa = b se poate obţine doar pentru Imxa > 0 sau altfel spus Ax > b pentru orice x ≥ 0, deci sistemul Ax = b nu are soluţii admisibile şi în concluzie problema iniţială nu are soluţie. 2. minimul funcţiei f este 0, în acest caz, soluţia optimă obţinută verifică Ax = b, fiind în concluzie o soluţie admisibilă de bază a primei probleme.

Faza 2

Începând de la soluţia găsită la Faza 1 se rezolvă problema iniţială cu algoritmul simplex. Se îndepărtează din tabelul simplex toate elementele corespunzătoare variabilelor artificiale (cu excepţia celor care rămân în bază), introducând coeficienţii funcţiei obiectiv din problema iniţială.

Dezavantajul metodei constă în faptul că tabelul simplex final de la faza 1 trebuie modificat pentru a se obţine tabelul simplex iniţial de la faza 2, eliminându-se coloanele corespunzătoare lui y şi totodată nu vom avea în tabelele simplex ale problemei iniţiale inversa bazei (se găsea în dreptul coloanelor matricei unitate din prima fază) necesară în anumite variante ale algoritmului simplex.

Metoda coeficienţilor de penalizare

Fie problema de programare liniară la forma standard de minimizare:

��

��

�

≥=⋅0x

bxAxcTmin

(2.79)

în care toţi termenii liberi sunt pozitivi şi matricea A nu conţine nici un vector coloană unitar.

Construim problema:

��

��

�

≥=+⋅−=

0yx,byxAMy)xcf Tmax(

(2.80)

în care M este o constantă presupusă foarte mare (mai mare decât orice constantă care

ar putea apare în rezolvarea problemei). Rezolvăm problema cu algoritmul simplex pornind rezolvarea de la baza matrice

unitate, putând ajunge la trei situaţii: 1) problema are optim infinit, în acest caz, problema iniţială are optim infinit ( nu prezintă interes din punct de vedere tehnico-economic). 2) problema are optim finit şi în soluţia de bază avem cel puţin o variabilă din vectorul y. În acest caz problema iniţială nu are soluţii admisibile. 3) problema are optim finit şi în soluţia de bază nu avem nici o variabilă din vectorul y. În acest caz problema iniţială are optim finit, soluţia optimă şi maximul funcţiei fiind aceleaşi cu cele ale problemei modificate. Se remarcă faptul că variabilele y nu au aceeaşi semnificaţie economică ca celelalte

variabile, ele fiind introduse doar ca un artificiu de calcul pentru a putea porni algoritmul simplex.

Observaţii : • Dacă matricea restricţiilor conţine vectori unitari, atunci numărul variabilelor artificiale introduse este egal cu m, numărul vectorilor unitari, indiferent de tipul funcţiei obiectiv.


37

• Dacă la aplicarea algoritmului simplex, o variabilă artificială iese din bază ea nu va mai intra niciodată, ceea ce arată eliminarea din calculele ulterioare.

Exemplu 2.6 Un atelier de prelucrări mecanice fabrică două produse P1 şi P2. Din structura de dezagregarea produselor se deduce că pentru realizarea produsului P1

sunt necesare 3 componente de tip A şi un component de tip B, iar pentru realizarea produsului P2 sunt necesare 1 component de tip A şi 4 componente de tip B.

Atelierul dispune în stoc de 10 componente de tip A. Contractele cu furnizorii pentru componentele de tip B, arată că se poate realiza aprovizionarea cu acesta în cantitate de cel puţin două componente B.

Beneficiul unitar pentru produsele P1 şi P2 sunt de 2 um, respectiv de 3um. Se doreşte să se stabilească planul de producţie care să maximizeze beneficiul total. Modelul matematic este următorul:

��

��

�

≥≥+≤++=

0xx2x4x

10xx3x3x2f

21

21

21

21

,

)max(

unde 21 xx , , reprezintă numărul de produse de tip P1 respectiv P2. Forma standard a problemei va fi:

( )

��

��

�

≥=−+

=+++=

0xxxx2xx4x

10xxx3x3x2fmax

4321

421

321

21

,,,

În matricea A vom introduce variabila x5 cu coeficientul 1 în a doua ecuaţie şi

împreună cu coeficienţii variabilei x3 în final vom avea de rezolvat problema prin cele două metode:

Metoda celor două faze Metoda coeficienţilor de penalizare

��

��

�

≥=+−+

=++

0xxxxx2xxx4x

10xxx3x

54321

5421

321

5

,,,,

)min(

��

��

�

≥=+−+

=++−+

0xxxxx2xxx4x

10xxx3Mxx3x2

54321

5421

321

521

,,,,

)max(

Aplicând Metoda celor două faze vom obţine succesiv tabele:

0 0 0 0 1 cB xB xB x1 x2 x3 x4 x5 0 x3 10 3 1 1 0 0 1 x5 2 1 4 0 -1 1 2 1 4 0 -1 0 0 0 0 0 1 cB xB xB x1 x2 x3 x4 x5 0 x3 19/2 11/4 0 1 1/4 -1/4 0 x2 1/2 1/4 1 0 -1/4 1/4 0 0 0 0 0 -1

Programare liniară

38

Am obţinut optimul egal cu 0 în soluţia de bază (x3,x2) care va fi soluţia iniţială pentru algoritmul simplex aplicat problemei iniţiale în a doua fază.

Eliminăm din tabel coloana lui x5, înlocuim valorile coeficienţilor funcţiei obiectiv şi deci şi valoarea acesteia, valorile j

Bj cz − şi rezolvăm problema în continuare, plecând de la

baza primal admisibilă determinată, cu algoritmul simplex primal, obţinând tabelele de mai jos:

2 3 0 0 cB xB xB x1 x2 x3 x4 0 x3 19/2 11/4 0 1 1/4 3 x2 1/2 1/4 1 0 -1/4 3/2 -5/4 0 0 -3/4 2 3 0 0 cB xB xB x1 x2 x3 x4 0 x3 4 0 -11 1 3 2 x1 2 1 4 0 -1 4 0 5 0 -2 2 3 0 0 cB xB xB x1 x2 x3 x4 0 x4 4/3 0 -11/3 1/3 1 2 x1 10/3 1 1/3 1/3 0 20/3 0 -7/3 2/3 0 2 3 0 0 cB xB xB x1 x2 x3 x4 0 x4 38 11 0 4 1 3 x2 10 3 1 1 0 30 7 0 3 0

Soluţia optimă a primei probleme este deci x1 = 0 şi x2 = 10 care dă un maxim al funcţiei

egal cu 30. Aplicând Metoda coeficienţilor de penalizare vom obţine succesiv următoarele tabele:

2 3 0 0 -M

cB xB xB x1 x2 x3 X4 x5 0 x3 10 3 1 1 0 0

-M x5 2 1 4 0 -1 1 -2M -M -4M 0 M -M -M-2 -4M-3 0 M 0 2 3 0 0 -M

cB xB xB x1 x2 x3 x4 x5 0 x3 19/2 11/4 0 1 ¼ -1/4 3 x2 1/2 1/4 1 0 -1/4 1/4 3/2 -5/4 0 0 -3/4 M+3/4 2 3 0 0 -M

cB xB xB x1 x2 x3 x4 x5 0 x3 4 0 -11 1 3 -3 2 x1 2 1 4 0 -1 1 4 0 5 0 -2 2+M 2 3 0 0 -M

cB xB xB x1 x2 x3 x4 x5 0 x4 4/3 0 -11/3 1/3 1 -1 2 x1 10/3 10/3 1 1/3 0 0 20/3 0 -7/3 2/3 0 M 2 3 0 0 -M

cB xB xB x1 x2 x3 x4 x5 0 x4 38 11 0 4 1 -1 3 x2 10 3 1 1 0 0 30 7 0 3 0 M


39

2.3.4. Interpretarea a algoritmului simplex primal

Se consideră problema de optimizare a activităţii unei firme producătoare. Aceasta realizează n produse , cu un profit unitar cj , n,j 1= . Firma utilizează mai multe resurse prime Ri , m,i 1= , disponibile în cantităţile limitate bi. Consumurile specifice de resurse pentru fiecare produs sunt aij , m,i 1= , n,j 1= .

Obiectivul firmei este obţinerea unui profit total maxim, cu restricţiile ce provin din consumul integral al resurselor disponibile . Modelul de optimizare a activităţii firmei este reprezentat de problema de programare liniară în forma standard :

��

��

�

≥==

0xbAx

xcz T(max) (2.81)

în care xj , nj ,1= , este cantitatea din produsul j ce urmează a fi fabricată.

Consumarea (utilizarea) integrală a resurselor nu este strictă, deoarece în lista operaţiilor productive se poate include un număr de operaţii fictive (corespunzătoare variabilelor ecart) ale căror valori să reprezinte cantitatea din resurse neconsumată. În soluţia de bază a algoritmului simplex numărul componentelor nenule nu depăşeşte numărul restricţiilor.

De aceea, în orice soluţie optimă a problemei, numărul produselor ce urmează a fi fabricate nu depăşeşte numărul resurselor folosite . Coloanele a(j) din baza B ce corespund operaţiilor j le vom numi operaţii de bază, celelalte fiind operaţii secundare.

Programul optim prevede obţinerea, numai prin operaţiile de bază, a produselor, astfel încât să fie consumate integral resursele disponibile.

O posibilitate de a obţine un program mai bun constă în identificarea unor operaţii secundare care să înlocuiască o parte din operaţiile de bază curente. Pentru acesta este necesar un criteriu de comparare a operaţiilor secundare cu cele de bază . În ipoteza că baza B=[a(1), a(2), …..,a(m)], din relaţia (2.59)

yBj=B-1a(j) , nj ,1= (2.82)

deducem :

A(j)= ByBj , nj ,1= (2.83)

care se poate scrie

)()()()( ... mBmj

2Bj2

1Bj1

j AyAyAyA +++= (2.84) Relaţia de mai sus are următoarea semnificaţie din punct de vedere tehnico-economic,

fabricarea unei unităţi de produs j este echivalentă cu fabricarea cantităţilor Bmj

Bj2

Bj1 yyy ,...,,,

din produsele operaţiilor de bază. Ca urmare, pentru fabricarea unei unităţi din produsul j este necesar a diminua producţia operaţiilor de bază cu cantităţile B

mjB

j2B

j1 yyy ,...,, .

Programare liniară

40

Aportul produsului j la creşterea profitului firmei poate fi comparat cu aportul valoric al cantităţilor B

mjB

j2B

j1 yyy ,...,,, . În consecinţă, dacă:

0cycycyccz jBmjm

Bj22

Bj11j

Bj ≥−+++=− ... (2.85)

fabricarea produsului j nu este rentabilă întrucât nu conduce la o majorarea valorii (profitului) producţiei curente. Dacă pentru toate operaţiile secundare avem

n,j,cz j

Bj 10 =≥− (2.86)

atunci programul de fabricaţie curent este optim. Acesta este, criteriul de optimalitate al algoritmului simplex. Dacă 0<− j

Bj cz , atunci activitatea secundară j conduce la o majorare a profitului

realizabil prin programul curent, egală cu )cz( jBj −− .

Dintre operaţiile secundare Jj ∈ rentabile în raport cu operaţiile de bază se va alege acea operaţie k care asigură cea mai mare viteză de creştere a valorii curente a producţiei ( interpretarea criteriului de intrare în bază). O altă problemă care se mai pune este stabilirea cantităţii din produsul j care se poate realiza în condiţiile date. Fabricarea unei cantităţi θ din acest produs implică diminuarea producţiei din produsele operaţiilor de bază astfel:

Bmk

Bmm

Bk

BBk

B yxx,...,yxx,yxx θθθ −=−=−= 222111 (2.87) Evident, desfăşurarea unei activităţi la un nivel negativ este lipsită de sens economic. Astfel este necesar ca :

m,i,yxx Bik

Bii 10 =≥−= θ (2.88)

de unde obţinem condiţia:

Bik

Bi

Biky

i yxmin

0

0

>

=≤θθ (2.89)

Presupunem că valoarea 0θ se obţine pentru indicele 1. Atunci:

00 =−=−= BlkB

lk

BlB

lBlk

Bll y

yxxyxx θ (2.90)

Ca urmare, operaţia l nu va mai fi folosită, iar în locul ei se va utiliza operaţia k, care asigură creşterea maximă a valorii curente a producţiei şi, implicit, maximizează profitului firmei.


41

Aceasta este interpretarea a criteriului de ieşire din bază al algoritmului simplex. Cazul optimului infinit, ca soluţie a problemei de programare liniară, nu este semnificativ din punct de vedere economic.

2.4. Dualitatea în programarea liniară 2.4.1. Problema duală. Fundamente teoretice. Problema duală Dualitatea în programarea liniară ocupă un rol important atât din punct de vedere teoretic cât şi din punct de vedere practic. Pe teoremele de dualitatea se bazează mulţi algoritmi de rezolvare a problemelor de programare liniară.

Fie problema de programare liniara dată sub forma generală numită problema primală :

( )��

�

��

�

�

++≤≥

≤++=++≥++

332211

321

3333232131

2331222121

1313212111

00xcxcxcmin

x;arbitrarx;xbxaxaxabxaxaxabxaxaxa

problema primală (2.91)

Numim problemă duală a problemei de programare liniara următoarea problema de

programare liniara:

( )

��

�

��

�

�

≤≥≥′+′+′=′+′+′≤′+′+′

′+′+′

00 321

3333223113

2332222112

1331221111

332211

u;arbitraru;ucuauauacuauauacuauaua

ubububmax

problema duală (2.92)

Observăm că duala problemei dualei este chiar problema primală. Datorită legăturii

strânse ce se stabileşte între aceste probleme care sunt duale una celeilalte, vom spune ca problema (2.91) şi problema (2.92) formează un cuplu de probleme duale.

Problema duală se obţine din problema primală folosind următoarele transformări :

- Termenii liberi din problema primală devin coeficienţi ai funcţiei obiectiv din problema duală.

- Coeficienţii funcţiei obiectiv din problema primală devin termeni liberi în problema duală.

- O problemă de maximizare primală devine problemă de minimizare duală. - Matricea coeficienţilor din problema duală este transpusa matricei coeficienţilor

din problema primală - Variabilele duale corespunzătoare unor restricţii concordante din problema primală

sunt nenegative, iar cele corespunzătoare unor restricţii primale neconcordante sunt nepozitive.

- Variabilele primale negative le corespund în problema duală restricţii concordante, iar variabilelor primale pozitive le corespund în problema duală restricţii neconcordante.

Programare liniară

42

- Variabilele duale corespunzătoare restricţiilor primale care sunt ecuaţii, pot fi de semn oarecare. - Variabilelor primale oarecare le corespund restricţii duale care sunt ecuaţii.

Exemplul 2.7 Determinaţi duala problemei de programare liniară:

f = max(2x1 – 5x2 + 4x3)

��

�

��

�

�

≥−+−≤+

=+−≥+−

85232

63574

213

31

312

321

xxxxx

xxxxxx

x1 ≤ 0, x2 oarecare, x3 ≥ 0

Conform regulilor de mai sus vom avea: − duala este de minim deoarece primala este de maxim; − variabilele dualei vor fi:

u1 corespunzătoare restricţiei: x1 – x2 + 4x3 ≥ 7 u2 corespunzătoare restricţiei: x2 – 5x1 + 3x3 = 6 u3 corespunzătoare restricţiei: x1 + 2x3 ≤ 3 u4 corespunzătoare restricţiei: –x3 + 2x1 - 5x2 ≥ 8

− funcţia obiectiv a dualei va fi produsul dintre termenii liberi ai restricţiilor primalei cu

variabilele corespunzătoare din duală: g = 7u1 + 6u2 + 3u3 + 8u4

− duala va avea 3 restricţii, câte variabile are primala, ele obţinându-se astfel: Prima restricţie (asociată variabilei x1) - termenul stâng al restricţiei se obţine înmulţind coeficienţii variabilei x1 din cele 4 restricţii ale primalei cu variabilele corespunzătoare acestora din duală: u1 –5u2 + u3 + 2u4 - termenul liber al restricţiei va fi coeficientul lui x1 din funcţia obiectiv a primalei, adică b1 = c1 = 2 - deoarece variabila corespunzătoare acestei restricţii, x1, este negativă, restricţia va fi neconcordantă şi deoarece duala este problemă de minim rezultă că va fi cu ≤. În concluzie, prima restricţie va fi: u1 –5u2 + u3 + 2u4 ≤ 2 Analog se vor determina şi celelalte două restricţii:

-u1 + u2 - 5u4 = -5 4u1 + 3u2 + 2u3 - u4 ≥ 4

− restricţiile de semn ale variabilelor dualei vor fi: � u1 ≤ 0, deoarece restricţia corespunzătoare este neconcordantă; � u2 oarecare, deoarece restricţia corespunzătoare este egalitate; � u3 ≥ 0, deoarece restricţia corespunzătoare este concordantă; � u4 ≤ 0, deoarece restricţia corespunzătoare este neconcordantă.

În final, problema duală este: (min) 7u1 + 6u2 + 3u3 + 8u4

��

��

�

≥−++−=−+−≤++−

423455

425

4321

421

4321

uuuuuuu

uuuu

u1 ≤ 0, u2 oarecare, u3 ≥ 0, u4 ≥ 0


43

Exemplul 2.8 Să se scrie duala problemei de programare liniară dată în formă canonică:

( )

��

�

��

�

�

≥≤−+≤−−

≤++−+++

0,...,10252

153523max

41

432

431

4321

4321

xxxxxxxx

xxxxxxxx

Se construieşte tabelul cu datele problemei iniţiale:

Aşadar, problema duală este:

( )

��

�

��

�

�

≥≥−−

≥+−≥+−

≥+++

0,,1

5232

310515min

321

321

321

31

21

321

xuuuuu

uuuuu

uuuuu

Fundamente teoretice

Fără a restrânge din generalitate ne vom ocupa în continuare de cuplul de probleme duale (2.91) - (2.92), prima fiind considerată problema primală, iar cea de-a doua, problema duală.

Se notează

{ }0, ≥=∈= xbAxRxP n (2.93)

{ }0, ≥≤∈= ucuARuD Tm 2.94) Mulţimile soluţiilor admisibile (sau programelor) ale problemei primale (2.91),

respectiv, duale (2.92). Teorema 2.8. Dacă Px ∈ şi Du ∈ , atunci ubxc TT ≥ . Teorema 2.9. Fie Px ∈* , Du ∈* şi ** ubxc TT ≥ . Atunci x* nu este soluţie optimă a problemei primale, iar u* este soluţie optimă a problemei duale Propoziţia 2.1. Dacă L este o matrice antisimetrică (LT = -L), atunci sistemul de inegalităţi liniare

maxmin 3 2 15

15

10

u1u2u3

1 -1 3 1-1 -1

-12 00 1 2

5

x1 x2 x3 x4

Programare liniară

44

��

≥≥⋅0

0t

tl (2.95)

are cel puţin o soluţie t astfel încât

0>⋅ tL (2.96) Teorema 2.10. (Teorema fundamentală a dualităţii) Fie cuplul de probleme duale (2.91) - (2.92). Atunci una şi numai una din următoarele situaţii este posibilă :

a) Ambele probleme au soluţii admisibile. În acest caz, ambele probleme au soluţii optime şi valori optime ale funcţiilor obiectiv sunt egale.

b) Una din probleme are soluţii admisibile, iar cealaltă nu are (este incompatibilă). În acest caz, problema compatibilă are optim infinit.

c) Nici una dintre probleme nu are soluţii admisibile. Teorema 2.11. (Teorema ecarturilor complementare). Fie cuplul de probleme duale canonice (2.91) - (2.92). Atunci Px ∈ şi Du ∈ sunt soluţii optime pentru cele două probleme dacă şi numai dacă:

( )( )��

��

=−

=−

0

0

uAcu

bxAuTT

T

(2.97)

Exemplul 2.9

Într-un atelier mecanic se produc două de tipuri de piese P1, P2. Timpii unitari de prelucrarea celor două piese pe cele două maşini unelte M1, M2,

profitul unitar şi disponibilul de timp al maşinilor unelte sunt date în tabelul de mai jos:

P1 P2 Disponibil resurse

M1 4 3 16sp M2 1 2 6sp

Profit unitar

3um 7um

Modelul matematic pentru problema dată este:

��

�

��

�

�

≥≤+≤+

+=

0xx6x2x16x3x4

x7x3f

21

21

21

21

,

)max(

Mulţimea soluţiilor admisibile ale problemei (primale) este reprezentată în fig. 2.6. Problema admite soluţia optimă 0

*1 =x , 3

*2 =x , pentru fiecare funcţia obiectiv are

valoarea 21max =f .


45

d2

0 x1

x2

A(4,0)

C(0,3)

d1

B(14/5,8/5)

Fig.2.6 Problema duală este:

��

�

��

�

�

≥≥+

≥++=

0uu7u2u3

3uu4u6u16g

21

21

21

21

,

)min(

Mulţimea soluţiilor admisibile ale problemei duale este reprezentată în fig.2.7.

Fig.2.7

Problema admite soluţia optimă 0

*1 =u , 2/7

*2 =u .Valoarea funcţiei obiectiv este

21min =g , evident aceeaşi ca şi în cazul problemei primale. Din cele arătate se constată că prin rezolvarea uneia dintre cele două probleme duale

se poate determina şi soluţia celeilalte. Tabelul simplex final corespunzător uneia dintre probleme conţine componentele soluţiilor optime ale ambelor probleme. Aceste rezultate teoretice se utilizează în practica industrială în cazul când planul de producţie conţine o varietate mare de produse ce se fabrică în aceleaşi condiţii tehnico economice. 2.4.2. Algoritmul simplex dual

Fie problema de programare liniară în forma standard

��

��

�

≥=0x

bAxxcTmin

(2.98)

unde nRcx ∈, , mRb ∈ , nmMA ×∈ , cu rang A = m < n.

d2

B(0,7/2)A(0,3/4)0 u1

u2

d1

Programare liniară

46

Duala acestei probleme este :

��

��

�

≤arbitraru

cuA

ubT

'

max

(2.99)

Definiţia 2.9 O bază B formată cu m coloane liniar independente a lui A se numeşte dual admisibilă dacă sunt satisfăcute condiţiile

njcz jBj ,1,0 =≤− (2.100)

Propoziţia 2.2. Dacă B este o bază dual admisibilă, atunci

1−= Bcu TB

TB (2.101)

este o soluţie a problemei duale (2.98). Teorema 2.12. (Teorema de optimalitate). Fie B o bază dual admisibilă pentru problema

primală (2.98). Fie mulţimea { }0_ <∈=BixIiI I_=∅, atunci soluţia de bază asociată bazei

B, bBxB 1−= , este o soluţie optimă a problemei (2.98).

Teorema 2.13. (Teorema de incompatibilitate a problemei primale). Fie B o bază dual admisibilă pentru problema primală (2.92), iar I_≠∅, Deci există _Ii ∈ astfel încât

Jjy Bij ∈∀≥ ,0 , atunci problema (2.92) nu are soluţii.

Teorema 2.14. (Teorema de îmbunătăţire a soluţiei) Fie B o bază dual admisibilă pentru problema primală (4.29), iar I_≠∅. Dacă pentru orice _Ii ∈ există Jj ∈ astfel încât

0<Bijy , şi dacă se alege _Il ∈ arbitrar, iar Jk ∈ astfel încât să fie satisfăcută condiţia :

Blk

kBk

Blj

jBj

yj y

czy

cz

Blj

−=

��

��

��

�� −

<0

min (2.102)

atunci matricea B’ obţinută din B prin înlocuirea coloanei A(l) cu coloana A(k) este o bază dual admisibilă, iar programul dual asociat uB’ este cel puţin la fel de bun ca programul uB Algoritmul simplex dual Pentru problema primală de minimizare sau maximizare este: Pasul 1. Se determină o bază dual admisibilă iniţială B. Pasul 2. Se calculează

Bx ,

Bz , B

jy , Bjz , jc− , nj ,1= .


47

Pasul 3. Se determină mulţimea

{ }0_ <∈=BixIiI

Dacă I_≠∅, atunci STOP : B

x este program optim al problemei; astfel se trece la pasul următor. Pasul 4. Se determină indicele _Ik ∈ cu criteriul de ieşire din bază

{ } Bl

Bi

Iixx =

∈ _min

Dacă njy B

ij ,1,0 =≥ , atunci STOP : problema nu are soluţii; astfel se determină indicele Jk ∈ cu criteriul de intrare în bază:

Blk

kBk

Blj

jBj

yj y

czy

cz

Blj

−=

��

��

��

�� −

<0

min

Pasul 5. Fie baza B’ obţinută din B prin înlocuirea coloanei A(l) cu coloana A(k). Se trece la Pasul 2, înlocuind peste tot baza B cu baza B’. Algoritmul simplex dual poate fi exprimat sintetic sub forma schemei logice din fig.2.8

START

Exista variabile de baza cu valori negative ?

STOPNu

Da

Determina linia pivotului

Nu

Determina coloana pivotului

Construiestetabel simplex initial

Indica solutia optima

Exista valori negative in linia pivotului?

STOP

Da

Calculeaza un nou tabel simplex

Nu exista solutii

Fig.2.8

Programare liniară

48

Exemplul 2.10 Să se rezolve problema de programare liniară:

( )

��

�

��

�

�

≥≥−+≥+−

−−

0,,22432

23max

321

321

321

21

xxxxxxxxx

xx

Se aduce problema la forma standard prin introducerea variabilelor de compensare x4, x5 şi se înmulţesc cu –1 cele două restricţii:

( )

��

�

��

�

�

≥−=++−−−=+−+−

−−

0,...,22432

23max

51

5321

4321

21

xxxxxxxxxx

xx

Baza iniţială B este matricea unitate formată cu coloanele A(4), A(5) . Tabelul simplex asociat are ca variabile de bază pe x4 şi x5:

cB V.B. V.V.B.

-3 -2 0 0 0x1

0

0

x2 x3 x4 x5

-1 2 -1 1 0-2

x4

x5 -23

-1 1 0 100020

-4

Baza iniţială este dual admisibilă deoarece 0≥− j

Bj cz . Se poate aplica deci

algoritmul simplex dual. Soluţia asociată bazei B admisibilă întrucât: 0321 === xxx , 44 −=x , 25 −=x . Mulţimea { }5,4_ =I . Conform criteriului de ieşire din bază avem:

{ } { } B

Ii

Bi xx 4

_42,4minmin =−=−−=

∈; se obţine 4=l , deci din bază va ieşi vectorul A(4).

Conform criteriului de intrare în bază avem:

04

min<B

jyj ��

��

��

�� −

Bj

jBj

ycz

4

=04

min<B

jyj B

B

ycz

43

3301

0,1

3 −==��

��

−−;

se obţine k = 3, deci în bază va intra vectorul corespunzător variabilei x3. Noul tabel simplex este:

cB V.B. V.V.B.

-3 -2 0 0 0x1

0

0

x2 x3 x4 x5

1 -2 -11 0-6

x4

x5 -33

1 10 100020

4


49

Soluţia nu este optimă întrucât 65 −=x . Din bază va ieşi vectorul corespunzător variabilei x3=5 şi va intra vectorul corespunzător variabilei x1. Se obţine tabelul simplex :

cB V.B. V.V.B.

-3 -2 0 0 0x1

0

-3

x2 x3 x4 x5

0 -5/3 12

x4

x5

11030

2 -2/3 1/3-1/3-1/30-1/31

0 2.4.3 Interpretarea economică a dualităţii Introducerea dualităţii este motivată din mai multe puncte de vedere: Teoretic. Una din problemele centrale ale programării matematice este caracterizarea situaţiilor în care există optimul unei probleme şi găsirea unor metode prin care să recunoaştem optimalitatea unei soluţii. Teorema fundamentală a dualităţii şi teorema ecarturilor complementare reprezintă rezultate chiar în acest sens, în care se foloseşte dualitatea. Practic. Putem rezolva o problemă rezolvând problema duală a acesteia sau cunoscând soluţia dualei. În unele cazuri, rezolvarea dualei este mult mai uşoară decât rezolvarea primalei, de exemplu când numărul de restricţii al primalei este mai mare decât numărul de variabile al acesteia sau când primala necesită mai multe variabile suplimentare decât duala. Economic. În cele mai multe probleme economice, a căror rezolvare se face printr-un model de programare liniară, soluţia dualei aduce o serie de informaţii suplimentare despre problema studiată. Semnificaţia economică a soluţiei dualei depinde de specificul problemei şi trebuie găsită de la caz la caz.

Având în vedere că max[f(x)] = min [g(u)], rezultă că, dacă, cantitatea disponibilă din resursa Ri creşte cu o unitate, atunci valoarea funcţiei obiectiv creşte cu ui, deci ui măsoară creşterea valorii funcţiei obiectiv determinată de creşterea cu o unitate a cantităţii disponibile bi.

Aceste evaluări obţinute dintr-un program optim au fost denumite în literatura de specialitate "preţuri umbră"(„shadow price”).

Preţul umbră ui arată cu cât se modifică funcţia obiectiv a problemei duale, atunci când termenul liber al restricţiei Ri se "relaxează" cu o unitate. A "relaxa" are semnificaţia de a spori cantitatea disponibilă bi a unei resurse deficitare sau, pentru restricţiile de tip calitativ cu

limită inferioară impusă (�=

n

1jjijxa ≥ bi), de a reduce nivelul termenului liber bi.

Este evident că, dacă o resursă nu este utilizată în întregime pentru satisfacerea

programului optimal xB (�=

n

1jjijxa < bi), atunci ui = 0 iar funcţia obiectiv nu este afectată de

sporire a cantităţii disponibile bi. Preţurile umbră (preţuri duale) aduc informaţii suplimentare pentru analiza eficienţei economice a resurselor şi a diferiţilor indicatori economici sau tehnici care apar în restricţiile unei probleme de programare liniară. Pe baza lor se pot fundamenta deciziile privind alocarea judicioasă a resurselor, se pot stabili măsuri de stimulare a consumului raţional al resurselor, se determină cât mai corect nivelul minim şi maxim al diferiţilor indicatori tehnici şi economici de care depinde structura planului optim.

Programare liniară

50

Soluţia optimă obţinută prin utilizarea datelor iniţiale poate constitui un punct de plecare pentru analiza economică privind alocarea eficientă a resurselor.

Pentru problemele în care se cere maximizarea funcţiei f(x), indicatorii zj reprezintă costul unitar de fabricaţie al produsului j, rezultat din evaluarea coeficienţilor aij prin preţurile umbră ataşate restricţii1or.

Rezultă că, prin calcularea diferenţei zj-cj, se compară acest cost unitar cu coeficientul cj (preţ unitar, beneficiu unitar etc.) din funcţia obiectiv.

Dacă există diferenţe negative (zj-cj < 0) înseamnă că, la activităţile respective, preţul umbră al produsului j (costul unitar de fabricaţie exprimat în indicatori ui) este mai mic decât venitul realizat şi de aceea activitatea aj este eficientă.

Aşa se explică faptul că va intra în bază vectorul a(k) ce corespunde diferenţei (zj-cj) minime.

În momentul în care toate diferenţele sunt pozitive (zj-cj ≥ 0) rezultă că nu mai există activităţi eficiente şi prin urmare soluţia de bază analizată este optimă.

În cazul problemelor de minim, indicatorii zj se pot interpreta ca venituri, exprimate în preţurile umbră ale restricţiilor, ce se obţin prin realizarea unei unităţi din produsul j.

Prin urmare, dacă există diferenţe pozitive (zj-cj > 0), activităţile aj corespunzătoare sunt eficiente, deoarece se realizează un venit unitar mai mare decât costul unitar de fabricaţie (zj > cj).

De aceea, va intra în bază activitatea ak, corespunzătoare diferenţei maxime, iar soluţia de bază se consideră optimă atunci când toate diferenţele (zj-cj) sunt nepozitive . Exemplul 2.11

O firmă fabrică trei tipuri de produse P1, P2, P3, utilizând patru tipuri de resurse R1, R2, R3, R4.

Procesul tehnologic de realizare a celor trei produse, timpul disponibil al fiecărei resurse, cererea minimă şi maximă din fiecare produs conform studiului de marketing, precum şi profitul unitar sunt date în tabelul 2.5.

Tabelul 2.5 Cerere Timp de prelucrare pe unitatea de

produs Produs

min max R1 SN 400

R2 FU32

R3 RU320

R4 Banc de control

Profitul unitar

um/buc

P1 20 200 0.10 0.06 0.18 0.13 10 P2 0 100 0.12 0.05 0 0.10 12 P3 70 180 0.15 0.09 0.07 0.08 15 Timp disponibil pe resursă 36 30 37 38 -

Să se determine programul de producţie astfel încât să se asigure satisfacerea cererii cu

un profit total maxim.

Notă m cu x1, x2 x3 variabilele de decizie ce reprezintă cantităţile din produsele P1, P2 respectiv P3 ce trebuie fabricate astfel încât să se atingă obiectivul propus. Modelul matematic liniar al problemei cuprinde restricţiile problemei, ce provin din limitarea disponibilităţii resurselor şi a cererii produselor pe piaţă, funcţia obiectiv ce maximizează profitul total şi condiţiile de nenegativitate care sunt evidente din punct de vedere economic. Modelul matematic al problemei este următorul:


51

��

�

��

�

�

≥≤≤≤≤≤≤

≤++≤+

≤++≤++

++=

0xxx180x70100x0200x20

38x080x10x13037x070x180

30x090x050x06036x150x120x10x15x12x10f

321

3

2

1

321

21

321

321

321

,,

.....

......

)max(

Programul de producţie este dat de variabilele de decizie şi este următorul:

��

�

��

�

�

==

==

mu6003OF70x100x135x

3

2

1

....

Din produsul P1 se produc 135 unităţi, din produsul P2 se produc 100 unităţi, din produsul P3 se produc 70 unităţi. În aceste condiţii valoarea funcţiei obiectiv este de 3.600 unităţi monetare. Variabilele de compensare (ecart) arată utilizarea resurselor astfel:

• 100Y0x 14 == , - preţ umbră 36367015010012013510 ==⋅+⋅+⋅ ...

Prima restricţie este satisfăcută cu semnul „=” ceea ce înseamnă că resursa R1 este utilizată în totalitate, deci R2 este o resursă rară – resursă a cărei lipsă / indisponibil ar limita sau modifica.

În acelaşi timp dacă în prima restricţie mărim timpul disponibil cu o unitate (din 36u.t. la 37u.t.), valoarea F.O. se modifică în sens pozitiv tocmai cu valoarea preţului umbră, deci profitul va fi de 3.700 u.m.

• 0Y610x 25 == . - preţ umbră 3041970090100050135060 <=⋅+⋅+⋅ .... cu 10.6 u.t.

A doua restricţie este satisfăcută cu semnul „<”, deci din resursa R2 rămâne un timp disponibil de 10.6 u.t. care nu este utilizat în procesul de producţie, astfel resursa R2 nu este o resursă rară însă lipsa ei poate limita producţia, preţul ei umbră fiind nul.

• 0Y75x 36 == . - preţ umbră 37331100070135180 <=⋅+⋅ ... cu 5.7 u.t.

A treia restricţie este satisfăcută cu semnul „<”, deci din resursa R3 rămâne un timp disponibil de 5.7 u.t. care nu este utilizat în procesul de producţie, astfel resursa R3 nu este o resursă rară însă lipsa ei poate limita producţia, preţul ei umbră fiind nul.

• 0Y854x 47 == . - preţ umbră 3815337008010010135130 <=⋅+⋅+⋅ .... cu 4.85 u.t.

A patra restricţie este satisfăcută cu semnul „<”, deci din resursa R4 rămâne un timp disponibil de 4.85 u.t. care nu este utilizat în procesul de producţie, astfel resursa R4 nu este o resursă rară însă lipsa ei poate limita producţia, preţul ei umbră fiind nul.

• 0Y65x 58 == - preţ umbră 2001351351 <=⋅ cu 65 unităţi de produs P1.

Programare liniară

52

Restricţia cinci este satisfăcută cu semnul „<”, deci din produsul P1 rămân nevândute o cantitate de 65 unităţi de produs (u.p), astfel P1 nu este o resursă rară deci are preţul umbră nul.

• 0Y115x 69 == - preţ umbră 201351351 >=⋅ cu 115 unităţi de produs P1.

Restricţia şase este satisfăcută cu semnul „>”, deci produsul P1 are o cerere maximă de 115 u.p., astfel P1 nu este o resursă rară deci are preţul umbră nul.

• 0Y0x 710 == - preţ umbră 1001001001 ==⋅

Restricţia şapte este satisfăcută cu semnul „=” ceea ce arată că produsul P2 este vândut în totalitate – deci este o resursa rară, deci preţul umbră ar trebui să fie nenul. El totuşi este nul, lucru uşor de explicat din teorema ecarturilor complementare: condiţia necesară şi suficientă ca două soluţii admisibile X,Y să fie soluţii optime respectiv la problema primală şi duală este să fie simultan satisfăcute relaţiile:

��

=−=−

0XCAY0AXPY

T0

T

)()(

Pentru ca un produs să fie zero este necesar ca un termen sa fie zero sau ambii egali cu zero. Prin creşterea cu o unitate a restricţiei în loc de 100 să avem 101 valoarea funcţiei obiectiv rămâne aceeaşi F.O.=3.600u.m.

• 0Y110x 811 == - preţ umbră 18070701 <=⋅ cu 110 unităţi de produs P3

Restricţia opt este satisfăcută cu semnul „<”, deci din produsul P3 rămân nevândute o cantitate de 110 unităţi de produs (u.p), astfel P3 nu este o resursă rară deci are preţul umbră nul.

• 0Y0x 912 == - preţ umbră 7070701 ==⋅

Restricţia şapte este satisfăcută cu semnul „=” ceea ce arată că produsul P3 este vândut în totalitate şi cererea maximă este corectă – deci este o resursa rară, deci preţul umbră ar trebui să fie nenul.

El totuşi este nul, lucru uşor de explicat din teorema ecarturilor complementare. Prin creşterea cu o unitate a restricţiei în loc de 70 să avem 71 valoarea funcţiei obiectiv rămâne aceeaşi F.O.=3.600u.m. În concluzie acelaşi plan de producţie se putea face, cu acelaşi profit şi dacă restricţiile problemei erau următoarele:

��

�

��

�

�

≥≤≤

≤≤≤≤

≤++≤+

≤++≤++

++=

0xxx70x65

100x0135x115

1533x080x10x130331x070x180

419x090x050x06036x150x120x10x15x12x10f

321

3

2

1

321

21

321

321

321

,,

.......

.......

)max(


53

CAPITOLUL 3 PROGRAMAREA LINIARĂ DE TIP TRANSPORT

3.1. Formularea unei probleme de transport

Se consideră că un produs este disponibil în m centre producătoare (fabrici, depozite) notate cu iP (i = 1,…m ). Acest produs trebuie transportat la n centre consumatoare (de desfacere, destinatari), notaţi cu ( )mjC j …,1= .

Transportul se poate efectua de la orice iP la orice ( )m1jC j …,= , iar costul unitar de transport este jic . Acest cost depinde de distantele respective, de mijloacele de transport folosite şi altele, ceea ce se presupune cunoscut. Se cunosc de asemenea şi cantităţile disponibile, aflate în cele m centre producătoare, notate cu ia cu ( )mi …,1= şi cantităţile necesare în cele n centre consumatoare, notate jb cu ( )nj …,1= . Se notează cu jix , cantitatea transportată în condiţiile de mai sus iar datele problemei de transport sunt sintetizate conform tabelului 3.1 ce este prezentat mai jos: Tabelul 3.1

nj21j

mmnmj2m1mm

iinij2i1ii

2n2j222212

1n1j112111

inj21j

i

bbbbbaccccP

accccP

accccPaccccP

aCCCCCP

��

��

��

��

��

��

��

��

Caracteristicile unei probleme de transport clasice sunt:

- fiecare centru producător aprovizionează cel puţin un centru consumator şi fiecare centru consumator este aprovizionată de la cel puţin un centru producător; - pot exista perechi producător - consumator între care nu se poate face transfer; - nu există limitări în ceea ce priveşte cantitatea transportată pe fiecare rută; - fiecărei rute i s-a asociat un cost care nu depinde de sensul de parcurgere.

Obiectivul problemei de transport este găsirea cantităţilor care trebuie transportate pe fiecare rută astfel încât să se asigure necesarul fiecărui centru consumator, în limitele cantităţilor aflate în centru producător, şi aceasta cu costuri minime.

Teorema 3.1 : O problemă de transport echilibrată admite întotdeauna programe (soluţii); orice program este mărginit dacă valorile sale ia , jb sunt mărginite (finite ).

Numim model matematic echilibrat, dacă cantitatea disponibila totală este egală cu cererea totală.

Modelul matematic de mai sus se poate înlocui cu un model echivalent în care toate restricţiile sunt ecuaţii. In forma sa matematică modelul problemei de transport se poate scrie ca în relaţia 3.1.

Programare liniară de tip transport

54

��

�

��

�

�

≥≥>

−∈≥

∈≤

��

��

� �

�

�

��

=

−

=

=

−

=

=

−

=

,

1

1

1

1

_______

1

1

_____1

1

1

0,0,

1,1,

,1,

min

m

iji

n

jji

m

ijji

n

jiji

m

i

n

jjiji

baba

njbx

miax

xc

(3.1)

Astfel în urma acestor transformări se va obţine următorul model matematic echilibrat (3.2):

��

�

��

�

�

≥

−∈=

∈=

��

��

�

�

��

=

−

=

=

−

=

0

1,1,

,1,

min

1

_______

1

1

_____1

1

1

ji

m

ijji

n

jiji

m

i

n

jjiji

x

njbx

miax

xc

(3.2)

Orice problemă poate fi transformată într-o problemă de tipul (3.2). Acest caz este

foarte rar în practică, însă el este cel mai simplu din punct de vedere matematic şi astfel va fi ales pentru formalizarea problemei.

O astfel de problemă se numeşte problemă de transport echilibrată. In practică pot exista următoarele cazuri:

- Dacă �<�==

n

1jj

m

1ii ba , se poate adăuga un depozit fictiv 1mP + care are un disponibil

1+ma , astfel încât costurile de transport de la depozitul 1mP + la centrele jC sunt nule.

- Daca �>�==

n

1jj

m

1ii ba , se poate adăuga un centru fictiv 1+nC ce necesita 1+nb unităţi,

astfel încât costurile să fie nule. Numărul total de restricţii este de m+n şi sunt o combinaţie liniară de celelalte, deci

numărul celor independente este de m+n-1. Orice problema de transport admite soluţii admisibile, adică sistemul de ecuaţii este

compatibil. O astfel de problema are soluţia următoare :

�=

= n

ii

jiji

a

bax

1

(3.3)

Aplicarea algoritmului simplex este dificilă în acest caz datorită numărului foarte mare

de necunoscute şi a determinării soluţie admisibile de bază. Într-o problemă de transport nu poate apărea decât varianta de optim finit, existând

întotdeauna soluţii admisibile, iar minimul –∞ nu este posibil, ţinând cont că avem de minimizat o funcţie liniară cu toţi coeficienţii pozitivi pe o mulţime de soluţii cu toate componentele pozitive.


55

Algoritmul specific problemelor de transport au următoarele etape: 1. Se determină o soluţie admisibila de baza de pornire X, prin folosirea uneia din

următoarele metode : coltului N-V, metoda costului minimal, metoda costului minim pe linie, metoda costului minim pe coloană.

2. Determinarea soluţiei optime pornind de la soluţia X.

3.2. Exemple de probleme de tip transport Probleme de transport cu capacităţi limitate

Se consideră o problemă de tip transport în care există limitări ale capacităţilor de

transport pe anumite rute. Se notează cu 0ij >α capacitatea maximă ce poate fi transportată pe ruta de la centru producător i la centrul consumator j.

Modelul matematic al acestei probleme, cu păstrarea semnificaţiilor notaţiilor cunoscute, este următoarea:

��

�

��

�

�

==≤≤

� ==

� ==

� �

=

=

= =

n1jm1ix0

n1jbx

m1iax

xc

ijij

m

1ijij

n

1jiij

m

1i

n

1jijij

,,,,

,,

,,

)min(

α

(3.4)

Condiţiile necesare şi suficiente de existenţa a soluţiilor pentru problema (3.4) sunt:

��

�

��

�

�

=≥

=≥

=

�

�

� �

=

=

= =

n

jjij

n

jiij

m

i

n

jji

njb

mia

ba

1

1

1 1

,1,

,1,

α

α (3.5)

Acestei probleme i se poate asocia un tabel de forma celui de la problema de transport,

în care se specifică şi capacităţile maxime de transport njmiij ,1,,1, ==α . Tabelul 3.2

Pi Cj Cl Cj... ... Cn ai

P1c1lα1l x1l

c1jα1j x1j

c1nα1n x1n

al...

... ... ... ... ... ... ...Pi

cilαil xil

cijαij xij

cinαin xin

ai...

... ... ... ... ... ... ...Pm

cmlαml xml

cmjαmj xmj

cmnαmn xmn

am...

bj bl bj bn

...

...

......

/


56

Probleme de transport cu centre intermediare

În practica industrială există cazuri în care transportul direct de la un centru producător la un centru consumator nu este economic.

Ca urmare, el poate trece prin mai multe centre intermediare, de tranzit, o astfel de problemă numindu-se problemă de transport cu centre intermediare sau problemă de transfer.

Se consideră p centre intermediare şi se notează cu pkk ,1, =β , capacităţile acestora. Modelul matematic al acestei probleme are forma:

===≥

∑ ==

∑ ==

==∑

==∑

∑ ∑+∑ ∑

=

=

=

=

= == =

n1jp1km1i0xx

n1jbx

p1kx

p1kx

m1iax

xcxc

kjik

n

1kjkj

n

1jkkj

km

1iik

i

p

1kik

p

1k

n

1jkjkj

m

1i

p

1kikik

,,,,,,,

,,

,,

,,

,,

)min(

'''

''

''

'

'

''''''

β

β (3.6)

unde:

'ikx - reprezintă cantitatea ce urmează a fi transportată de la centrul producător i la centrul

intermediar k ; 'ikc - costul unitar de transport dintre centrele i şi k ; ''

kjx - cantitatea ce urmează a fi transportată de la centrul k la centrul consumator j ; ''

kjc - costul unitar de transport dintre centrele k şi j. Condiţia necesară şi suficientă de existenţă a soluţiilor pentru problema (3.6) este:

��===

==n

jj

p

kk

m

ii ba

111β (3.7)

Având în vedere faptul că fiecare intermediar este atât centru destinaţie cât şi centru

sursă, se pot considera următoarele două probleme de transport:

��

�

��

�

�

==≥

==�

==�

� �

=

=

= =

p1km1i0x

p1kx

m1iax

xc

ik

km

1iik

i

p

1kik

m

1i

p

1kikik

,,,,

,,

,,

)min(

'

'

'

''

β

(3.8)


57

şi

��

�

��

�

�

==≥

==�

==�

� �

=

=

= =

n1jp1k0x

n1jbx

p1kx

xc

kj

j

p

1kkj

kn

1jkj

p

1k

n

1jkjkj

,,,,

,,

,,

)min(

''

''

''

''''

β (3.9)

Se poate arăta că ( )'

ikx şi ( )''kjx reprezintă o soluţie optimă a problemei de transport cu

centre intermediare (3.6) dacă şi numai dacă ( )'ikx este o soluţie optimă a problemei de

transport (3.8), iar ( )''kjx este o soluţie a problemei de transport (3.9).

În consecinţă, rezolvarea problemei (3.6) este echivalentă cu rezolvarea celor două probleme (3.8) şi (3.9).

Probleme de repartiţie

Într-un atelier mecanic există m utilaje, care au disponibilul de timp miai ,1, = .

Pe acestea se vor prelucra n tipuri de piese, în cantităţile nib j ,1, = . Se cunosc randamentul orar, ijr , şi cheltuielile de producţie, ijc , la utilajul i ale piesei

j. Se pune problema de a determina o repartiţie a sarcinilor, respectiv a timpului în care utilajul i prelucrează piesele de tip j astfel încât cheltuielile totale de producţie sa fie minime. Se notează cu ijx numărul de ore în care utilajul i prelucrează piesele de tip j.

Modelul matematic al problemei este de forma (3.10):

==≥

∑ ==

=≤∑

∑ ∑

=

=

= =

n1jm1i0x

n1jbxr

m1iax

xc

ij

m

1ijijij

in

1jij

m

1i

n

1jijij

,,,,

,,

,,

)min(

(3.10)

3.3. Determinarea unei soluţii de baza iniţiale a problemei de transport.

Soluţia admisibile de baza iniţiale, care are cel mult (m+n-1) componente nenule, este

o soluţie nedegenerată. Dacă numărul soluţiilor este mai mic decât (m+n-1) soluţia este degenerată. Metoda colţului Nord-Vest (NV) Această metodă se mai numeşte Metoda diagonalei principale sau Metoda lui Dantzing.

Metodă nu ţine cont de costurile de transport cij şi numai de cantităţile disponibile în centrele producătoare şi cererea centrelor consumatoare.


58

Etapele metodei: • Se alege ( )1111 bax min= ( (1,1) fiind colţul stânga sus – NV). Sunt posibile următoarele

cazuri: 1) 111 aba =),min( � 111 ax = , iar n1j0x j1 ,, == . Necesarul centrului C1 devine 11 ab − .

2) 111 bba =),min( � 111 bx = , iar m1i0x 1i ,, == . Disponibilul centrului P1 devine 11 ba − .

3) 11 ba = � 1111 bax == , iar n1j0x j1 ,, == şi m1i0x 1i ,, == . • Se elimină de sus în jos sau de la stânga la dreapta prima linie respectiv prima coloană din tabel. Următoarele componente strict pozitive ale soluţiei de bază iniţiale se determină în mod analog, considerând colţul NV rămas după eliminarea anterioară. Exemplul 3.1 : Pentru problema de transport ale cărei date sunt centralizate în tabelul 3.3 să se determine soluţia de bază iniţială utilizând metoda lui Dantzing. Tabelul 3.3

30799582136119542113587

3

2

1

4321

PPP

QQQQ

Notăm cu ijx cantităţile ce urmează a fi transportate în condiţiile indicate în tabelul iniţial. Pasul 1 Problema dată poate fi scrisă ca în tabelul 3.4.

111 bba =),min( � 5511x11 == ),min( , iar m1i0x 1i ,, == şi 6511baa 111 =−=−=' (tab.3.5)

79958xxxx11xxxx11xxxx

34333231

24232221

14131211

79908xxx011xxx06xxx5

343332

242322

141312

tabelul 3.4 tabelul 3.5 Pasul 2 Calculăm: 121 aba =),min( � 696x12 == ),min( , iar m1i0x j1 ,, == şi

369abb 122 =−=−=' (tab.3.6) Pasul 3 Calculăm: 222 bba =),min( � 3311x22 == ),min( , iar m1i0x 2i ,, == şi

8311baa 222 =−=−=' (tab.3.7)

79308xxx011xxx000065

343332

242322

79008xx008xx3000065

3433

2423


59

tabelul 3.6 tabelul 3.7 Pasul 4 Calculăm: 232 aba =),min( � 898x23 == ),min( , iar m1i0x j2 ,, == şi

189abb 232 =−=−='' (tab.3.8)

Pasul 3 Calculăm: 333 bba =),min( � 118x33 == ),min( , iar m1i0x 3i ,, == şi

718baa 333 =−=−=' (tab.3.9)

71008xx000083000065

3433

0000071000083000065

tabelul 3.8 tabelul 3.9

Soluţia admisibila de baza X este data de tabelul 3.9 . Dacă notăm cu V(X) valoarea funcţiei de optimizat a problemei date, pentru soluţia admisibilă X, avem: V(X) = 7*6 + 8*6 + 3*4 + 8*5 + 1*1 + 7*2 =150 Metoda costului minimal

Metodă ţine cont atât de costurile de transport cij cât şi de cantităţile disponibile în centrele producătoare şi cererea centrelor consumatoare. • Se alege ( )ijlk cc min= . Se determină ),min( kllk bax = Sunt posibile următoarele cazuri:

1) lkl aba =),min( � llk ax = , iar n1j0xlj ,, == . Necesarul centrului Cj devine lk ab − .

2) kkl bba =),min( � klk bx = , iar m1i0xik ,, == . Disponibilul centrului Pi devine kl ba − .

3) kl ba = � kllk bax == , iar n1j0xlj ,, == şi m1i0xik ,, == . • Se elimină de sus în jos sau de la stânga la dreapta linia respectiv coloană din tabel. Se determină în mod analog, considerând variabila de cost minim din subtabelul rămas după eliminarea anterioară. Dacă sunt mai multe costuri minime egale, atunci se ia în considerare mai întâi variabile care ia valoare maximă.

3.4. Metoda de determinare a soluţiei optime pentru probleme de transport. Metoda potenţialelor. Generalităţi

Rezolvarea problemei de transport prin metoda simplex este, în general, puţin eficientă. Câteva dintre motive sunt următoarele:

- numărul mare de variabile, egal cu m, n - absenţa unei baze iniţiale. Varianta de rezolvare prin considerarea unor variabile

auxiliare pentru fiecare linie şi coloană şi aplicarea metodei celor două faze este laborioasă;

- apariţia frecventă a cazurilor de degenerare datorită numărului mare de elemente ale matricei coeficienţilor A egale cu 0 şi 1 .

Metoda potenţialelor reprezintă o metodă specială de testare şi îmbunătăţire a soluţiei unei probleme de transport.


60

Procesul de îmbunătăţire a unei soluţii constă în a trece de la o soluţie la o alta mai bună. Pentru aceasta se recurge la problema duală a problemei de transport şi anume :

��

�

��

�

�

==

==≤+

��

�

�

��

+� �

= =

njarbitrarvmiarbitraru

njmicvu

vbua

j

i

ijji

m

i

n

jjjii

,1,,1,

,1,,1,

max1 1

(3.11)

Conform teoremei ecarturilor complementare aplicată cuplului de probleme duale,

rezultă că soluţia de bază ijx a problemei primale şi soluţia ),( ji vu a problemei duale sunt optime dacă şi numai dacă satisfac condiţiile:

njmixvuc ijjiij ,1,,1,0)( ===⋅−− ) (3.12)

Pentru ca relaţia de mai sus să fie satisfăcută este suficient ca ),( ji vu să fie soluţii ale sistemului

Jjicvu ijji ∈∀=+ ),(, (3.13) în care s-a notat mulţimea de indici ijxjiJ ),{(= este variabila de bază }.

Propoziţia 3.1 Sistemul de ecuaţii are o infinitate de soluţii. Dacă ),( 0j

0i vu este o soluţie

particulară şi k o constantă oarecare, atunci orice soluţie a sistemului este de forma:

��

��

=−==+=

n1jkvvm1ikuu

0jj

0ii

,,,,

(3.14)

Pentru rezolvarea sistemului se poate fixa arbitrar una dintre necunoscute, fără a influenţa optimalitatea soluţie problemei de transport; de obicei se alege 0=iu .

Observaţie. Rezolvarea sistemului se poate efectua direct pe tabelul de rezolvare al problemei. Valorile variabilelor iu şi jv se înscriu la marginile tabelului ; din acest motiv ele se mai numesc şi valori marginale . Algoritmul metodei potenţialelor Pasul 1. Se determină o soluţie de bază iniţială )( ijx . Pasul 2. Se calculează valorile variabilelor duale iu şi jv ca soluţii ale sistemului de ecuaţii Jjicvu ijji ∈∀=+ ),(, Pasul 3. Se calculează valorile Jjicvu ijjiij ∉∀−+= ),(,δ

Dacă Jjiij ∉∀≤ ),(,0δ , atunci STOP: soluţia )( ijx este optimă; în caz contrar se trece la pasul 4


61

Pasul 4. Se calculează cu criteriu de intrare în bază }),(max{ Jjiijij ∉∀= δδ

Variabila lkx ce va intra în bază . Se construieşte pentru căsuţa (l, k) un ciclu care porneşte din căsuţa (l, k), care trece numai prin căsuţe (i, j) ocupate cu valori 0xij > , cu treceri alternative pe linii şi coloane, şi care revine la căsuţa (l, k). Se adoptă un sens oarecare de parcurgere al acestui ciclu şi se numerotează căsuţele sale începând cu căsuţa (l, k). Pasul 5. Se calculează criteriul de ieşire din bază ),(min{ jixx ijst ==θ este căsuţă de rang

par în ciclu }şi se determină variabila stx va ieşi din bază. Pasul 6. Se determină o nouă soluţie de bază admisibilă ( )ijx~ cu ajutorul formulelor de schimbare a bazei

��

��

�

+−

=cicluluiapartinenujix

cicluinimparrangarejixcicluinparrangarejix

xij

ij

ij

ij

),(,),(,),(,

~ θθ

Se revine la pasul 2 cu noua soluţie de bază obţinută. Observaţii :

1) Soluţia iniţială de bază obţinută la pasul 1 al algoritmului depinde de metoda folosită pentru determinarea ei. Aceasta nu influenţează, soluţia optimă a problemei, ci eventual numărul de iteraţii pentru obţinerea soluţiei optime.

2) Alegerea sensului de parcurgere al ciclului în cadrul pasului 4 al algoritmului este arbitrară.

3) Tabelele ce se vor construi la aplicarea algoritmului vor fi formate din căsuţe (i, j) ce

pot avea una din configuraţiile Prima indică o căsuţă corespunzătoare unei valori de bază ( 0xij > ), iar cea de-a doua

o căsuţă corespunzătoare unei valori nebazice ( 0xij = ) , pentru care se calculează valoarea .ijδ

Simbolurile + sau – apar dacă căsuţa face parte din ciclul construit la pasul 4 al algoritmului. Simbolul + indică o căsuţă de rang impar , iar simbolul – indică o căsuţă de rang par.

Exemplul 3.2 Fie date trei fabrici producătoare (P1, P2, P3) ale aceluiaşi produs, care trebuie să aprovizioneze cu acest produs patru consumatori (C1, C2, C3, C4). În tabelul 3.10 sunt date cantităţile disponibile în centrele producătoare (ai), cantităţile necesare în centrele consumatoare (bj) şi costurile pe unitatea de transport. Să se determine planul optim de transport în condiţiile costurilor minime.

cij +(-) xij

cij ijδ xij=0


62

Tabelul 3.10

Pi / Cj C1 C2 C3 C4 ai P1 8 7 3 6 19 P2 4 6 7 3 20 P3 3 4 2 5 16 bj 15 12 14 14 55

Problema de transport este echilibrată deoarece ��==

==4

1

3

155

jj

ii ba , iar pentru

rezolvarea ei se va aplica metoda potenţialelor si pentru determinarea soluţiei de bază se va aplica metoda costului minim din tabel.

Iteraţia 1. Pasul 1. Prin metoda costului minimal se determină soluţia de bază iniţială iar calculele sunt prezentate în tabelul 3.11: Tabelul 3.11

7 12 0 0 19 12 6 0 0 14 20 6 0 2 0 14 0 16 2 0 15 12 14 14 13 0 0 7 0

Se obţine următoarea soluţie de bază iniţială :

.14,2,14,6,12,7 333124211211 ====== xxxxxx Valoarea funcţiei obiectiv corespunzătoare acestei soluţii iniţiale este :

2401421436412778 =⋅+⋅+⋅+⋅+⋅=z . Soluţia de bază iniţială este înscrisă în tabelul 3.12 alături de costurile unitare de transport date iniţial: Tabelul 3.12

8 7 3 67 12 0 0

4 6 7 36 0 0 14

3 4 2 52 0 14 0

Pasul2. Se rezolvă sistemul:

)},3,3(),1,3(),4,2(),1,2(),2,1(),1,1{(,),(, =∈=+ JundeJjicvu ijji pornind de la 01 =u Tabelul 3.13

v1=8 v2=7 v3=7 v4=7u1=0 8 7 3 4 6 1

7 12 0 0u2=-4 4 6 -3 7 -4 3

6 0 0 14u3=-5 3 4 -2 2 5 -3

2 0 14 0

Pasul 3. Valorile Jjicvu ijjiij ∉−+= ),(,δ sunt scrise în tabelul 3.13.

Deoarece Jjiij ∉∀≤ ),(,0δ rezultă că soluţia nu este optimă.


63

Pasul 4. Se calculează ( )( ){ } �==∉∀= 4,/max 13δδδ Jjiijlk variabila x13 va intra în bază Se construieşte ciclul : (1,3), (1,1), (3,1), (3,3), (1,3) care este indicat în tabelul 3.13.

Pasul 5. Se determină ( ){ } �===== 7}14,7min{,/min 11xparordindecasutaestejixx ijstθ variabila x11 va

ieşi din bază. Pasul 6. Se modifică valorile căsuţelor din ciclul de mai sus:

7714,972,077,770 33311113 =−==+==−==+= xxxx . Noua soluţie de bază admisibilă este înscrisă in tabelul 3.14 Tabelul 3.14

v1=4 v2=7 v3=3 v4=3u1=0 8 -4 7 3 6 -3

7 12 7 0u2=0 4 6 1 7 -4 3

6 0 0 14u3=-1 3 4 2 2 5 -3

9 0 7 0

Valoarea funcţiei obiectiv devine : 21272931436473127 =⋅+⋅+⋅+⋅+⋅+⋅=z Iteraţia a 2 Pasul 2. Se rezolvă )},3,3(),1,3(),4,2(),1,2(),3,1(),2,1{(,),(, =∈=+ JundeJjicvu ijji iar soluţia este indicată în tabelul 3.14. Pasul 3. Se calculează valorile Jjicvu ijjiij ∉−+= ),(,δ

Deoarece Jjiij ∉∀≤ ),(,0δ , soluţia nu este optimă (tab.3.14). Pasul 4. �== 223δδ lk variabila x32 va intra în bază . Se construieşte ciclul (3,2), (3,3), (1,3), (1,2), (3,2) (tab.3.14) Pasul 5 . 3333 7}12,7min{ xx �===θ va ieşi din bază . Pasul 6. Se modifică valorile căsuţelor din ciclul de mai sus :

5712,1477,077,770 12133332 =−==+==−==+= xxxx (tab.3.15) Valoarea funcţiei obiectiv devine : 19874931436414357 =⋅+⋅+⋅+⋅+⋅+⋅=z Iteraţia 3 . Rezultatele sunt consemnate în tabelul 3.15, deoarece Jjiij ∉∀< ),(,0δ rezultă că soluţia este optimă . Tabelul 3.15

v1=6 v2=7 v3=3 v4=5u1=0 8 -2 7 3 6 -1

0 5 14 0u2=-2 4 6 -1 7 -6 3

6 0 0 14u3=-3 3 4 2 -2 5 -3

9 7 0 0

S-a obţinut soluţia optimă a problemei de transport :

.7,9,14,14,5 32*

31*

24*

13*

12* ===== xxxxx

Căreia îi corespunde costul total al transportului minim z*=198

Elemente de teoria grafurilor

64

CAPITOLUL 4 ELEMENTE DE TEORIA GRAFURILOR

4.1. Fundamente în teoria grafurilor

Teoria grafurilor s-a constituit ca un capitol de sine stătător în cadrul cercetărilor

operaţionale, datorită multiplelor avantaje pe care le oferă activităţii de planificare şi analiza tehnico - economică.

Cu ajutorul grafurilor se surprind şi se analizează în detaliu legăturile dintre componentele sistemului tehnico - economic, iar elaborarea modelului este mult mai uşoară. 4.1.1. Noţiunea de graf Prin definiţie un graf este o pereche (X,U ) unde mulţimea X este numită mulţimea nodurilor (sau vârfurilor) iar mulţimea U este mulţimea muchiilor. Notaţii utilizate : X = mulţime finită şi diferită de mulţimea vidă de orice natură. X = �x1, x2, …..xn� - unde xi = elemente numite vârfuri sau noduri X poate fi infinită, dar numărabilă. U = submulţime nevidă a produsului cartezian X x X U= �( xi,xj ) / ( xi,xj) ≠ ( xj , xi ) � - unde ( xi , xj) = pereche ordonată de vârfuri numită arc. Arcul u este orientat de la nodul xi, numit extremitatea iniţială, la nodul xj, numit extremitatea finală. A ( xj , xj ) se numeşte buclă. G =( X ,U) = graf orientat (digraf) U = mulţime de de arce neorientate care reprezintă perechi ordonate de vârfuri din X U = �( xi,xj ) / ( xi,xj)=( xj , xi ) � - ( xi,xj) este un arc neorientat numit muchie G =( X , U ) = graf neorientat

In practică un graf neorientat se poate înlocui cu un graf orientat astfel: fiecarei muchii ( xi,xj) ∈U îi corespund două arce de semne contrare (x1 , x2) şi (x2 , x1).

In cazul în care se asociază arcelor grafului o valoare sau o funcţie valoare v : U → R sau v : U → R unde v( xi,xj) ∈ R � funcţia valoare ataşată arcelor. G ( X, U, v ) = se numeşte graf valuat ( evaluat, ponderat ) 4.1.2. Orientare şi neorientare în graf Cazul grafurilor orientate

Prin următorul exemplu vom pune în evidenţă un graf orientat:

„În practica industrială pentru realizarea unei lucrări de investiţii sunt necesare o serie de activităţi distincte: alegerea amplasamentului, întocmirea proiectului, avizarea acestuia, aprobarea lui, contractarea utilajelor tehnologice, organizarea şantierului ş.a. Aceste activităţi sunt condiţionate între ele şi execuţia fiecărei activităţi nu poate fi începută înainte de terminarea altor activităţi. Există şi activităţi care se execută în paralel. Pentru realizarea modelului de graf corespunzător proiectului de investiţii se stabilesc condiţionările între activităţi. Nodul reprezintă momentul în care se termină o activitate şi începe o alta.


65

Activităţile proiectului sunt reprezentate prin muchii (arce) în graf. Orice activitate trebuie executată până la capăt ca să poată începe o alta pe care ea o condiţionează. Asemenea grafuri sunt orientate”

Dacă un graf orientat ( )UXG ,= are nX = şi mU = atunci graful G este un - graf orientat, iar numărul n reprezintă ordinul grafului G, iar m dimensiunea grafului G. Două arce având aceleaşi extremităţi sunt paralele. Un graf orientat care nu are nici bucle nici arce paralele este un graf simplu. Reprezentarea geometrică a unui graf orientat

Un graf orientat ( )UXG ,= se reprezintă geometric printr-o figură în plan în care nodurile Xxi ∈ se vizualizează prin puncte în plan încadrate în cercuri, iar arcele

( ) Uxxu ji ∈= , prin linii drepte sau curbate care unesc nodurile xi şi xj şi pe care se află o săgeată cu sensul de la xi la xj

Exemplul 4.1. Fie { }654321 ,,,,, xxxxxxX = şi { }10987654321 ,,,,,,,,, uuuuuuuuuuU =

unde ( )211 , xxu = , ( )312 , xxu = , ( )323 , xxu = , ( )424 , xxu = , ( )435 , xxu = , ( )536 , xxu = , ( )457 , xxu = , ( )648 , xxu = , ( )659 , xxu = , ( )4410 , xxu = . Arcul ( )4410 , xxu = este o buclă.

Reprezentarea geometrică a grafului ( )UXG ,= este cea din fig 4.1.

x1

x2

x3

x4

x5

x6

u1

u2

u3

u4

u5

u6

u7

u8

u9

u10

Fig. 4.1

Gradul unui nod. Fie ( )UXG ,= un graf orientat. Un vârf xi are următoarele caracteristici: - gradul de intrare ( )ixd − ca fiind numărul de arce Uu∈ de forma ( )ij xxu ,= care au extremitatea finală în xi. - gradul de ieşire ( )ixd + ca fiind numărul de arce Uu∈ de forma ( )ji xxu ,= care au extremitatea iniţială în xi. Dacă nX = şi mU = avem relaţia:

( ) ( ) mxdxdn

ii

n

ii ��

=

+

=

− ==11

(4.1)

Pentru graful din fig. 4.1 avem ( ) 01 =− xd , ( ) 21 =+ xd , ( ) 12 =− xd , ( ) 22 =+ xd ,

( ) 23 =− xd , ( ) 23 =+ xd , ( ) 44 =− xd , ( ) 24 =+ xd , ( ) 15 =− xd , ( ) 25 =+ xd , ( ) 26 =− xd , ( ) 06 =+ xd .

Dacă ( ) 0=−ixd nodul xi este nod de intrare în graf, iar dacă ( ) 0=+

ixd nodul xi este nod de ieşire din graf.


66

În graful din fig. 4.1 nodul de intrare este nodul x1, iar nodul de ieşire este nodul x6. Gradul unui nod Xxi ∈ , notat cu ( )ixd , în cazul grafurilor orientate, este dat de

relaţia: ( ) ( ) ( )iii xdxdxd +− += (4.2)

Gradul de incidenţă

Două noduri xi şi xj sunt noduri adiacente dacă există un arc ( ) Uxx ji ∈, sau

( ) Uxx ij ∈, . Două arce sunt adiacente dacă au în comun o extremitate. Arcele care converg într-un nod xi de forma ( )ij xx , sunt arce incidente spre interior,

iar arcele care ies din nodul xi de forma ( )ji xx , sunt arce incidente spre exterior. Fie XA ⊂ o submulţime a mulţimii X. Toate arcele ( )ji xxuUu =∈ , cu Axi ∉ şi Ax j ∈ sunt arce incidente spre interior în

A şi mulţimea lor se notează cu ( )AU − :

( ) ( ){ }AxAxUuxxuAU jiji ∈∉∈==− ,/,, (4.3)

Toate arcele ( )ji xxuUu =∈ , cu Axi ∈ şi Ax j ∉ sunt arce incidente spre exterior în

A şi mulţimea lor se notează cu ( )AU + :

( ) ( ){ }AxAxUuxxuAU jiji ∉∈∈==+ ,/,, (4.4)

Gradul de incidenţă al submulţimii A în raport cu graful G este dat de relaţia:

( ) ( ) ( )AUAUAU +− ∪= (4.5)

Dacă { }43 xxA = în graful din figura 4.1 atunci :

( ) ( ) ( ) ( ) ( ){ }45423231 ,,,,,,, xxxxxxxxAU =− ,

( ) ( ) ( ){ }6453 ,,, xxxxAU =+ ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }645345423231 ,,,,,,,,,,, xxxxxxxxxxxxAU =

iar gradul de incidenţă al submulţimii A este ( ) 6=AU . Graf parţial.

Un graf ( )** ,UXG = este un graf parţial al grafului orientat ( )UXG ,= dacă UU ⊂* . Un graf parţial se obţine din graful G prin suprimarea a cel puţin un arc din U. Prin suprimarea arcelor ( )23 , xx şi ( )42 , xx din graful de referinţă din figura 4.2 se

obţine graful parţial din figura 4.2b. Subgraf

Fie XY ⊂ şi UV ⊂ mulţimea tuturor arcelor din U care au ambele extremităţi în submulţimea Y. Graful ( )VYH ,= este un subgraf al grafului G. Un subgraf se obţine din graful G prin suprimarea nodurilor care nu sunt conţinute în Y şi arcelor corespunzătoare lor.


67

Prin suprimarea nodului x4 şi a arcelor ( )42 , xx , ( )43 , xx , ( )14 , xx din graful din figura 4.2a se obţine graful din figura 4.2c.

x1 x2

x3 x4

x1 x2

x3 x4

x1 x2

x3

a) G b) G* c) H Fig. 4.2

Grafuri simetrice şi antisimetrice.

Un graf orientat ( )UXG ,= este simetric dacă pentru oricare două noduri xi şi xj din ( ) ( ) UxxUxx ijji ∈�∈ ,, .

Într-un graf simetric între două noduri vor exista două arce de sens contrar sau nici unul. În fig.4.3a este reprezentat un graf simetric.

Un graf orientat G este antisimetric dacă pentru oricare două noduri xi şi xj din ( ) ( ) UxxUxx ijji ∉�∈ ,, .

Într-un graf antisimetric între două noduri există cel mult un arc. În figura 4.3b este reprezentat un graf antisimetric.

x1 x2

x3

x4

x1 x2

x3

x4

a) b) Fig.4.3

Graf complet Un graf orientat G este complet dacă pentru oricare două noduri xi şi xj din

( ) ( ) UxxUxx ijji ∈�∉ ,, . Într-un graf complet între oricare două noduri există cel puţin un arc. În figura 4.4 este

reprezentat un graf complet. Graful din figura 4.3b nu este complet pentru că nu există arce între nodurile x1 şi x4

sau x3 şi x4.

x1 x2

x3 x4 Fig.4.4

Cazul grafurilor neorientate Prin definiţie un graf neorientat G este o pereche ( X , U ) , unde mulţimea X este numită mulţimea nodurilor, iar U este mulţimea muchiilor.

Nodurile xi şi xj ale unei muchii },{ ji xxu = , definesc extremităţile muchiei.


68

Două muchii având aceleaşi extremităţi sunt muchii paralele, iar o muchie cu extremităţi identice },{ ii xxu = se numeşte buclă.

Un graf orientat care nu are nici bucle nici arce paralele este un graf simplu. Reprezentarea geometrică a unui graf neorientat

Un graf neorientat ( )UXG ,= (fig.4.5) se reprezintă geometric printr-o figură în plan. Nodurile Xxi ∈ se vizualizează prin puncte în plan încadrate în cercuri, iar muchiile

( ) Uxxu ji ∈= , prin linii ( drepte sau curbe ) care unesc nodurile xi şi xj. Exemplul 4.2 Graf neorientat

x1

x2

x3

x4

x5

u1u3

u2

u4

u5

u6

x6

Fig.4.5 Gradul unui nod.

Fie ( )UXG ,= un graf şi Xxx ji ∈, . Nodurile ix şi jx sunt noduri adiacente dacă

există o muchie },{ ji xxu = care le uneşte.

Dacă },{ ji xxu = , muchia u şi nodul ix sunt incidente. Două muchii 1u şi 2u ale grafului sunt muchii adiacente dacă sunt incidente în acelaşi nod. Gradul unui nod Xxi ∈ , notat cu ( )ixd reprezintă numărul de muchii din graful G incidente cu nodul xi.

Un nod izolat are gradul 0. Pentru graful din fig. 4.5 gradele nodurilor sunt: ( ) 21 =xd , ( ) 22 =xd , ( ) 23 =xd ,

( ) 34 =xd , ( ) 05 =xd , ( ) 36 =xd .

Dacă nX = şi mU = avem relaţia:

( ) mxdn

ii ⋅=�

=2

1. (4.6)

Această relaţie rezultă din faptul că fiecare muchie este incidenţă în două noduri.

Graf parţial

Un graf ��

��= ** ,UXG este un graf parţial al unui graf ( )UXG ,= dacă UU ⊂* .

Graful *G se obţine din graful G prin suprimarea a cel puţin unei muchii. Graful din fig.4.6b este un graf parţial al grafului de referinţă din fig.4.6a.

Subgraf.

Un graf ( )FYH ,= este un subgraf al grafului ( )UXG ,= dacă XY ⊂ , iar F conţine toate muchiile din U şi care au ambele extremităţi în mulţimea Y .


69

a) G b) G* c) H Fig.4.6

Sugraful H se obţine din graful G prin eliminarea a cel puţin un nod şi a tuturor

muchiilor incidente în nodurile eliminate. Graful din figura 4.6c este un subgraf al grafului din fig. 4.6a.

Graf complet

Graful ( )UXG ,= este complet dacă între orice două noduri Xxx ji ∈, există o

muchie { } Uxx ji ∈, . Un graf complet cu n noduri se notează Gn. În figura 4.7 sunt reprezentate cinci grafuri complete.

G1 G2 G3 G4 G5

Fig.4.7 4.1.3. Drumuri şi circuite în graf

Fie ( )UXG ,= un graf orientat şi nodurile a şi b, XbXa ∈∈ , . Un drum între nodurile a şi b, în graful G, este un şir ordonat de noduri:

( )b,x,...,x,x,a ip2i1i=µ (4.7)

cu proprietatea că ( )( ) ( ) Ub,x,...,x,xx,a ip2i1i1i ∈ sunt arce ale grafului G. Nodurile a şi b, sunt numite extremităţile drumului. Un drum este elementar dacă trece o singură dată prin fiecare din nodurile sale. Propoziţia 4.1 Într-un graf G cu n noduri, un drum elementar conţine cel mult n–1

arce. În graful din figura 4.8, ( )654211 ,,,, xxxxx=µ este un drum elementar, dar

( )64234212 ,,,,,, xxxxxxx=µ nu este un drum elementar.

x1

x2

x3

x4

x5

x6

Fig.4.8


70

Un drum elementar care trece prin toate nodurile grafului este un drum hamiltonian. În fig.4.8, ( )6542312 x,x,x,x,x,x=µ este un drum hamiltonian. Un circuit este un drum finit care începe şi se termină în acelaşi nod. Un circuit format

dintr-un singur arc este buclă. Un circuit este elementar dacă trece o singură dată prin fiecare din nodurile sale. Un

circuit este elementar este ( )23422 x,x,x,x=µ . Un circuit hamiltonian este un drum hamiltonian în care extremităţile sale coincid.

Drumul ( )165234216 x,x,x,x,x,x,x,x=µ este un circuit hamiltonian. Denumirile de drum hamiltonian şi circuit hamiltonian au fost introduse de

matematicianul Hamilton în anul 1865 Se numeşte lungimea unui arc l( d) numărul de arce componente (p). Se numeşte valoarea unui drum suma valorilor arcelor ce formează drumul respectiv

şi acesta sub forma :

[ ] ),(),( �= lkji xxvxxdv (4.8)

Numărul vârfurilor ce pot fi atinse da la vârful xk poartă denumirea de puncte de atingere de la virful xk 4.1.4. Lanţuri şi cicluri în graf

Fie ( )U,XG = un graf neorientat şi nodurile aşi b, XtXs ∈∈ , . Un lanţ între două noduri a şi b ale grafului G este o mulţime ordonată de noduri

notată:

[ ]bx,...,xx,aL ,ip2i,1i= (4.9)

cu proprietatea că [ ],1ix,a , [ ],21 , ii xx , …, [ ]bx ,ip sunt muchii ale grafului. Lanţul este definit prin succesiunea nodurilor, fiecare muchie componentă, exceptând-

o pe prima si pe ultima, are o extremitate comună cu muchia precedentă şi cealaltă extremitate în comun cu muchia următoare. Alternativ, un lanţ poate fi definit prin succesiunea muchiilor adiacente care-l formează:

[ ]puuuL ,...,, 21= (4.10)

Nodurile a şi b sunt extremităţile lanţului. De asemenea, în a doua reprezentare, ui şi

up sunt extremităţile lanţului. Lungimea unui lanţ este dată prin numărul de muchii din care se compune. O muchie este un lanţ de lungime 1. Un lanţ de lungime 2 este format din două muchii

adiacente. Exemplul 4.3

x1

x2

x3

x4

x5

x6

Fig.4.9


71

[ ]64211 ,,, xxxxL = este un lanţ între nodurile x1 şi x6 de lungime 3. lanţul [ ]532 , xxL = este o muchie de lungime 1.

Un lanţ este elementar dacă trece o singură dată prin fiecare din nodurile sale. [ ]534213 ,,,, xxxxxL = este simplu şi elementar, în timp ce lanţul

[ ]34534214 ,,,,,, xxxxxxxL = este compus şi nu este elementar. Un lanţ elementar care trece prin toate nodurile grafului este un lanţ hamiltonian.

[ ]6534215 ,,,,, xxxxxxL = este un lanţ hamiltonian. Lanţul în care extremităţile sale coincid este un ciclu, sau un ciclu este un lanţ care

începe şi se termină cu acelaşi nod. Un ciclu hamiltonian în care extremităţile coincid este un ciclu hamiltonian.

[ ]134216 ,,,, xxxxxL = formează un ciclu, iar lanţul [ ]13564217 ,,,,,, xxxxxxxL = este un ciclu hamiltonian.

Diferenţa între un drum şi un lanţ constă în faptul că într-un drum toate arcele sunt orientate în acelaşi sens pe când într-un lanţ ele pot avea orice orientare.

Orice drum este şi lanţ dar nu orice lanţ este un drum. Într-un graf orientat noţiunea de drum este echivalentă cu cea de lanţ.

4.2. Matrici ataşate grafurilor

Pentru rezolvarea unor grafuri de dimensiuni mari si a unor probleme practice, se asociază grafului o serie de matrici ce uşurează studiul acestora.

Cu ajutorul matricelor ataşate grafurilor se pot determina: succesiunile optime a unor procese de producţie, legăturile ce se stabilesc între-un proces tehnologic, modul de transmitere a unei informaţii direct sau indirect, rute strategice din punct de vedere economic, etc..

4.2.1. Matricea arcelor (matricea conexiunilor directe)

Fie ( )UXG ,= un graf orientat cu { }nxxxX ,...,, 21= . Grafului orientat G i se asociază o matrice booleană pătratică

( ) njniaA ij ,...1,,...,1, === numită matricea arcelor (conexiunilor directe) cu următoarele elementele:

( )( )��

��

∉

∈=

Ux,xdaca0

Ux,xdaca1a

ji

jiij (4.11)

Obsevaţii : - Dacă în matricea A se pune în locul valorii 1, valoarea arcului, se va obţine matricea capacităţilor arcului ; - Dacă pe diagonala principală nu există elemente egale cu 1, atunci graful dat nu are bucle ; - În linia ( )nii ≤≤1 a matricei A sunt marcate cu 1 arcele incidente spre exterior în nodul xi; - În coloana ( )njj ≤≤1 sunt marcate cu 1 arcele incidente spre interior în nodul xj; - În cazul unei bucle ( )ji xx , , elementul de pe diagonală ija este egal cu 1; - Gradul de intrare ( )jxd − pentru nodul xj este dat de relaţia ( ) �=

−

iijj axd ;

- Gradul de ieşire ( )jxd + pentru nodul xj este dat de relaţia ( ) �=+

jijj axd .


72

Exemplu 4.4 Unui graf orientat G cu patru noduri x1, x2, x3, x4 şi cu arcele ( )21 , xx , ( )31 , xx , ( )22 , xx ,

( )32 , xx , ( )42 , xx , ( )43 , xx , i se asociază matricea booleană:

��

�

�

��

�

�

=

0001100011100110

4

3

2

1

xxxx

A

Având în vedere matricea A avem următoarele proprietăţi:

P1. Dacă un graf este antisimetric, atunci în matricea asociată A:

( ) jiXxxaa jijiij ≠∈∀=⋅ ,,,0 (4.12)

P2. Matricea asociată unui graf parţial G* se obţine din matricea asociată grafului G prin înlocuirea cu zero a elementelor asociate arcelor suprimate. P4. Matricea asociată unui subgraf parţial H se obţine prin suprimarea din matricea asociată grafului G a liniilor şi coloanelor corespunzătoare nodurilor excluse. Matricea unui subgraf este o matrice pătratică extrasă din matricea grafului G.

Dacă graful ( )U,XG = este neorientat muchiile sale se orientează în ambele sensuri:

[ ] ( )jiji xxxx ,, ⇔ şi ( )ij xx , (4.13)

şi elementele matricei ( )ijaA = asociată grafului G se definesc prin:

[ ][ ]��

��

∉

∈=

Ux,xdaca0

Ux,xdaca1a

ji

jiij (4.14)

În cazul unui graf neorientat, matricea asociată A este o matrice simetrică. Pentru un graf cu patru noduri x1, x2, x3, x4 cu muchiile ( )21 , xx , ( )31 , xx , ( )32 , xx , ( )42 , xx , ( )43 , xx matricea asociată A este:

��

�

�

��

�

�

=

0110101111010110

4

3

2

1

xxxx

A

Astfel, matricei booleene pătratice A i se asociază un graf orientat cu arcele ( )ji xx , pentru toatele elementele 1=ija . Exemplul 4.5 Corespunzător matricei booleene:


73

��

�

�

��

�

�

=

0110100110100100001101100

A

se asociază graful din fig.4.10 cu cinci noduri, notate x1, x2, x3, x4,,x5

În matricea A, 122 =a semnifică existenţa unei bucle în nodul x2.

x1

x2

x3

x4

x5

Fig.4.10

4.2.2. Matricea drumurilor (matricea conexiunilor totale)

Fie ( )UXG ,= un graf orientat cu { }nxxxX ,...,, 21= şi A matricea arcelor. În matricea A avem:

- pe linia nii ≤≤1, sunt marcate cu 1 drumurile de lungime 1 care pleacă din nodul xi; - în coloana njj ≤≤1, sunt marcate cu 1 drumurile de lungime 1 care converg în nodul

xj; Astfel, matricea A este matricea booleană a drumurilor de lungime 1.

Adunarea şi înmulţirea booleană: +.

0 10 1

1110

x.

0 10

110 0

0 Dacă notăm cu A(k) matricea booleană obţinută prin ridicarea booleană la puterea k a

matricei A: ( ) ( )

…��

… ,,,.....

32kAAAAAAA 1k

orikde

k =×=××××= −

atunci, A(k) este matricea booleana a drumurilor de lungime k în graful G sau matricea conexiunilor totale.

Dacă un element ( ) 1=kija există un drum de lungime k de la xi la xj.

Astfel, în matricea booleană A(k): - elementele de pe linia nii ≤≤1, arată drumurile de lungime k de la nodul xj la nodurile

în coloanele cărora apare 1 pe această linie; - elementele de pe coloana njj ≤≤1, arată drumurile de lungime k de la nodurile pe a

cărora linie apare 1 în această coloană la nodul xj; Dacă ridicăm la puteri succesive matricea A prin operaţiile obişnuite de înmulţire şi

adunare a numerelor naturale reale se obţine numărul drumurilor de o anumită lungime. Pentru exemplul 4.5 avem următoarele puteri booleene succesive ale matricei A:


74

( )

=

1111010011011110111110110

2A ( )

=

1111101111111111111111111

3A , ….

Elementele acestor matrice egale cu 1 asigură existenţa drumurilor de lungime 2 şi 3,

iar cele cele de pe diagonală existenţa circuitelor. De exemplu, de la x1 la x4 nu există drum de lungime 2, dar există drum de lungime 3. În A(3) (elementul ( ) 03

45 =a ) nu există drum de lungime 3 de la x4 la x5. Circuite de ordinul 2 se realizează în nodurile x2, x3 şi x5, iar de ordinul 3 în toate nodurile. Puterea A(4) are toate elementele 1.

Pentru a determina numărul drumurilor şi circuitelor de lungime 2, 3 şi 4 se calculează puterile succesive A2, A3 şi A4:

( )

��

�

�

��

�

�

=

1122010021011120111110120

2A , ( )

��

�

�

��

�

�

=

2125302223123311123111133

3A ,

( )

��

�

�

��

�

�

=

2568723562324842239414554

4A

De la nodul 1 la nodul 2 există două drumuri de lungime 2:

241 xxx →→ şi 231 xxx →→ , trei drumuri de lungime 3:

2341 xxxx →→→ ; 2231 xxxx →→→ ; 2241 xxxx →→→ şi cinci drumuri de lungime 4.

Evident, multe drumuri sunt neelementare. Bucla din nodul x2 poate crea drumuri de orice lungime prin repetarea parcurgerii ei. Există trei circuite elementare de lungime 4:

34523 xxxxx →→→→

34123 xxxxx →→→→

34153 xxxxx →→→→ si un circuit de lungime 5:

124531 xxxxxx →→→→→ .

Dacă A este matricea asociată unui graf neorientat ( )EXG ,= , puterile succesive A(k) oferă informaţii despre existenţa si numărul lanţurilor şi circuitelor de lungime egală cu puterea matricei.

În acest caz matricea A este simetrică.


75

4.2.3. Descompunerea grafului în componente tari conexe

Un graf ( )U,XG = este conex dacă pentru oricare două noduri distincte Xxx ji ∈, există un lanţ cu extremităţile xi şi xj.

Graful din fig.4.9 este conex. Proprietatea că există un drum cu extremităţile xi şi xj este o relaţie de echivalenţă care

împarte graful G în clase de echivalenţă numite componente conexe. O componentă conexă a unui graful G este un subgraf conex al grafului G. Să considerăm un nod Xxi ∈ în graful ( )U,XG = . Componenta conexă xi se poate evidenţia printr-o mulţime C(xi) formată din xi şi din

toate nodurile legate prin drumuri de xi:

( ) { } { /XxxxC jii ∈∪= există un drum între ix şi }jx (4.15)

Evident ( ) XxC i ⊆ şi ( ) XxC iXxi

⊆∈� . Dar ( )i

XxxC

i∈� conţine toate elementele

mulţimii X, atunci =X ( )iXx

xCi∈� .

Un graf orientat este un graf tare conex dacă pentru oricare două noduri distincte ix şi ( )jix j ≠ , dacă există cel puţin un drum de la xi la xj sau de la xj la xi.

O componentă tare conexă a unui graf orientat G este un subgraf tare conex. Un graf G este tare conex numai dacă admite o singură componentă tare conexă.

Algoritm de descompunere a grafului în componente tari conexe Pas 1: Se determină mulţimea vârfurilor atinse de la vârful xi ( o notam cu Vi şi este formată din elementele egale cu 1 de pe o linie suplimentară atasată matricei ) Pas 2: Se determină mulţimea vârfurilor ce ating pe xi (o vom nota cu '

iV şi este formata din elementele egale cu 1 de pe coloana suplimentară ataşată matricei. Pas 3: Se determină componenta tare conexa care conţine vârful xi cu ajutorul relaţiei următoare :

{ }i'iii x)VV()x(C ∪∩= (4.16)

Pas 4 : Iterativ : se elimină din matricea A toate liniile şi toate coloanele corespunzătoare vârfurilor din C(xi) . Pas 5 : În matricea rămasă se caută în mod asemănător o nouă componentă tare conexă. Operaţiile continuă până când toate vârfurile grafului au fost luate în consideraţie (nu se va exclude nici un virf.) Exemplul 4.6 O întreprindere trebuie să fabrice succesiv opt tipuri de produse Pi (i =1,2,…,8). Pentru a trece de la producerea produsului Pi la producerea produsului Pj, trebuie suportat un cost de lansare sau un cost de trecere cij.

Cunoscându-se tabelul tuturor costurilor de lansare, dat sub forma matricei de mai jos, să se determine o asemenea ordine a producerii celor opt produse, astfel încât cheltuielile totale de lansare să fie minime


76

P10

P2 P3 P4 P5 P6 P7 P8P1P2

P3

P4P5

P6

P7

P8

00

00

00

0

3 5 2 7 6 4 47848565

887577

6

53446

64

4548

846

897

6676

76

68776

5

556547

Evident că există 8! = 40.320 de moduri de a trece prin fabricarea celor opt produse, fiecare nod având câte un cost de total de lansare.

O soluţie suficient de bună este aceea de a compara costurile de trecere cij şi cji de la producerea lui Pi la Pj şi invers şi astfel se va elimina posibilitatea unei variante cu cost mare, păstrând-o păstrându-o numai pe cea cu costul mai mic.

Astfel, dacă cij < cji, vom renunţa în graf la arcul (Pi, Pj) şi vom păstra arcul (Pj, Pi). Compararea celor două costuri de acest fel se poate face direct pe matricea dată, deoarece ele sunt simetrice faţă de diagonala principală;

În locul costului mai mare vom scrie zero, iar în locul costului mai mic vom scrie unu. În cazul în care avem cij = cji, vom schimba în mod arbitrar una din valori prin unu şi cealaltă prin zero.

Se obţine în acest fel matricea conexă a unui graf cu numai 28 de arce:

P10

P2 P3 P4 P5 P6 P7 P8P1P2

P3

P4P5

P6

P7

P8

00

00

00

0

1 1 1 1 0 1 10000100

001100

1

01110

11

1110

000

000

0001

00

10011

1

111110

(C)

Vom determina drumurile hamiltoniene cu algoritmul mai sus enunţat şi le vom

compara din punct de vedere al costului total de lansare. După cum vom vedea, numărul drumurilor hamiltoniene în acest graf este mult mai

mic faţa de cel al grafului dat de problemă. Cu ajutorul algoritmului ajutător descris, se determină componentele tare conexe ale

grafului G obţinut:

{ }{ }{ }87433

22

6511

;;;

;;

PPPPCPC

PPPC

===

Matricea conexă C* a grafului condensat G* este următoarea:


77

0 1 10 0

00 0

C1 C2 C3C1C2C3

1(C*)

Fig.4.11

Deci graful condensat G* are un drum hamiltonian dat de succesiunea C1, C2, C3. Toate drumurile hamiltoniene ale celor trei componente tare conexe se scriu uşor:

P1P5

P6

P5

P6

P1

P6

P1P5

I

x2

P3P4P7

P4P8P3

P8P7P4

P7P3P8

P8 P7 P3 P4

II III

Se observă că graful cercetat are 12 drumuri hamiltoniene, ce se obţin prin legarea

drumurilor parţiale prin arcele ce leagă componentele succesive. Câteva din aceste drumuri sunt scrise mai jos: pentru fiecare din ele s-a calculat costul

de lansare total corespunzător:

P1P1P1P1P5

P5P5P5P5P6

P6P6P6P6P1

P2P2P2P2P2

P3P4P7P8P3

P4

P8P3P7P4

P8P7P4P3P8

P7P3P8P4P7

: cost 39: cost 39: cost 38: cost 36: cost 35 etc.

Drumul hamiltonian, optim corespunde drumului µ(P5, P6, P1, P2, P8, P7,P3, P4). Aceasta trebuie să fie ordinea în care trebuie lansată producţia celor opt tipuri de

produse, ordine ce conduce la un cost total de lansare egal cu 32 de unităţi monetare. Practica arată că acest cost de lansare aflat în modul de mai sus, chiar dacă nu este cel

minim, este de obicei foarte aproape de cel minim.


78

4.3. Drumuri hamiltoniene

Pentru a înţelege noţiunea de drum hamiltonian cu aplicativitate practică vom pleca de la următorul exemplu:

O firma are de realizat în cursul unei săptămâni n produse Pi. Pentru trecerea de la fabricarea produsului Pi la fabricarea produsului Pi+1 pe linia de fabricaţie, trebuie suportat un cost de lansare sau de trecere cij de la un produs la un alt produs. Astfel, trebuie aleasă ordinea în care se vor succeda produsele pe linia de fabricaţie, astfel încât costul total pe săptămână să fie cât mai mic (minim).

Rezolvarea problemei se reduce la determinarea drumului hamiltonian optim din modelul de graf asociat problemei, unde produsele sunt reprezentate prin vârfurile grafului, sensul arcelor reflectă ordinea de lansare în lucru, iar valorile asociate arcelor fiind legate de costurile de lansare în fabricaţie.

În continuare vom prezenta algoritmi de determinare a drumurilor hamiltoniene din grafuri. Determinarea drumurilor hamiltoniene în grafuri cu circuite

Un drum hamiltonian este un drum care trece prin toate vârfurile unui graf, o singură dată. Fie G =(X,U) un graf orientat.

Vom prezenta în continuare un algoritm pentru determinarea drumurilor hamiltoniene bazată pe ideea împărţirii grafului G, în clase de echivalenţă adică în subgrafuri tari conexe ale grafului G. Algoritmul Foulkes Etapa 1.

Se scrie matricea booleana ă asociată grafului G (A) şi matricea AIM )1( ⊕= , unde matricea I este matricea unitate iar „⊕„ este adunarea booleană.

Etapa 2. Se ridică succesiv matricea AIM )1( ⊕= , la puterile 2, 22, 23,…,2r

Ridicările la putere sunt booleene şi se efectuează până când două puteri consecutive sunt egale Pentru scurtarea calculelor se determina : (I ⊕ M)2 k

până când (I ⊕ M)2 k= (I ⊕ M)2 1−k

Ridicarea la putere booleană: M(2)= M(1)*M(1) =| m ij |(2)= mi1*m1j + mi2*m2j + …….+ min*mnj Unde produsul mik*mkj = 1 ⇔ mik= 1 si mkj = 1 Etapa 3

În matricea (I ⊕ M)2k

, liniile pline i1, i2 ,….ip (acele linii care sunt formate numai cu cifra 1), determină clasa de echivalenta C1 (componentele tari conexe), formată din nodurile xi1 , xi2 , ……xip

Se elimină liniile şi coloanele care corespund nodurilor din clasa de echivalenţă stabilită. Se reia raţionamentul pe matricea redusă şi se obţine următoarea clasă de echivalenţă. Se continuă formarea claselor de echivalenţă până se epuizează toate liniile matricei.


79

Etapa 4. Nodurile care formează o clasa de echivalenţă sunt reprezentate prin puncte în

interiorul unui dreptunghi, iar între acestea se trasează arcele existente în graful iniţial G. Se trasează legăturile dintre clasele consecutive. Ele sunt reprezentate prin arcele

existente în graful iniţial G între nodurile clasei C1 şi cele ale clasei C2 , între nodurile clasei C2 şi cele ale clasei C3 ş.a.m.d.. Etapa 5. Un drum hamiltonian se identifică plecând de la un nod din clasa C1 trecând prin toate nodurile acesteia şi din ultimul nod se trece la un nod din C2. dacă există un astfel de arc. Dacă nu există un astfel de arc se pleacă de la un nod în clasa C1. În continuare se identifică drum hamiltonian în clasa C2 ş.a.m.d. până la ultima clasă.

Trecând prin toate clasele se parcurg toate nodurile grafului iniţial o singură dată, obţinându-se astfel un drum hamiltonian.

Aplicând acest procedeu, în toate modurile posibile, se obţin toate drumurile hamiltoniene în graful iniţial G.

Drumurile aflate prin trecere succesiva de la o clasa de echivalenţă la altă clasă de echivalenţă sunt drumurile hamiltoniene ale grafului. Observaţii - în graful G poate să nu existe nici un drum hamiltonian; - dacă un graf are o singură componentă tare conexă, algoritmul lui Foulkes nu este eficient, în acest caz se aplică alţi algoritmi. Exemplul 4.7 : Să considerăm graful din fig.4.12 cu matricea asociată A:

x1

x2

x3

x4

x5

Fig.4.12

��

�

�

��

�

�

=

1110000010010100100110100

A ,

Clasele C1 şi C2, deduse, pentru graful din fig4.12, se prezenta grafic, conform etapei IV din algoritmul Foulkes precum în fig. 4.13.

Drumurile hamiltoniene în graful G sunt următoarele: ( )423511 ,,,, xxxxx=µ , ( )245132 ,,,, xxxxx=µ , ( )243513 ,,,, xxxxx=µ , ( )411354 ,,,, xxxxx=µ .

x1

x2x3

x4x5

C1 C2 Fig.4.13


80

Exemplul 4.8 Problema succesiunii operaţiilor. În practica industrială, pentru realizarea unui produs pe baza unui proces tehnologic

trebuie parcurse o serie de operaţii tehnologice, fiecare efectuată în condiţiile tehnice specifice. Stabilirea unei succesiuni a operaţiilor, într-un graf asociat procesului tehnologic revine la determinarea unui drum hamiltonian.

În graful asociat procesului tehnologic pot fi evidenţiate diversele restricţii tehnologice, creând o mulţime de variante ale procesului tehnologic. Prin stabilirea unei succesiuni a operaţiilor se caută să se proiecteze un proces tehnologic în condiţiile tehnice date şi cu eficienţă economică. Să presupunem că astfel de proces este dat prin graful din fig.4.14.

x1

x2

x3

x4

x5

x6

x7 Fig.4.14

Fie A matricea booleană asociată grafului G şi AIM )1( ⊕= :

��

�

�

��

�

�

=

0100000100000010000000110010001100000001000000110

A ,

��

�

�

��

�

�

=⊕=

1100000110000010100000111010001110000001100000111

AIM )1(

Ridicând la puteri succesive matricea M(1) obţinem următoarea matrice:

��

�

�

��

�

�

=⊕

1100000110000011100001111110111111011111101111111

7654321

)MI( )4(

Prima clasa de echivalenţă este { }11 xC = (numai linia 1 este plină). Suprimând linia 1 şi coloana 1 obţinem matricea redusă B1:

��

�

�

��

�

�

=

110000110000111000111111111111111111

765432

1B


81

A doua clasă de echivalenţă este { }4322 ,, xxxC = (liniile 2, 3 şi 4 sunt cele pline). Suprimând liniile şi coloanele 2, 3 şi 4 obţinem matricea redusă B2:

��

�

�

��

�

�

=110110111

765

2B

A treia clasă de echivalenţă este { }53 xC = (linia 5 este plină). Suprimând linia şi

coloana 5 obţinem matricea redusă B3:

��

��

�=

1111

76

3B

Iar patra clasă de echivalenţă este { }764 , xxC = . Conform etapei IV între nodurile componentele C1, C2, C3, C4, se trasează graful din

fig.4.15:

x1 x2

x3

x4

x5

x6

x7

C1 C2 C3 C4 Fig.4.15

Trecând de la o componentă la alta obţinem drumul hamiltonian:

{ }6754321 ,,,,,, xxxxxxx=µ ,

care este şi succesiunea operaţiilor procesului tehnologic. Exemplul 4.9 Problema costurilor de trecere

Pe o linie de fabricaţie se execută cinci produse xi, i = 1, ..., 5. La trecerea de la un

produs xi la un alt produs xj pe linia de fabricaţie se efectuează diverse pregătiri tehnice care necesită un "cost" cij pentru lansarea în fabricaţie a produsului xj (vom înţelege prin cost variaţia unei anumite mărimi legate de procesul respectiv).

Exemple de acest tip pot fi: trecerea la fabricarea unui tip de oţel pe convertor, laminarea unui nou tip de lingou etc., care presupun diverse reglări, un anumit consum al cilindrilor în cajele de laminare ş.a., deci costuri de trecere. Costurile de trecere cij şi cji sunt, în general, diferite. Aceste costuri au semnificaţia, de exemplu, de timpi necesari de trecere de la un produs la altul.

Să se găsească succesiunea în care trebuie executate produsele pentru ca suma costurilor de trecere să fie minimă.

Această problemă revine la determinarea drumurilor hamiltoniene într-un graf fără bucle în care nodurile reprezintă cele cinci produse, iar arcele posibilităţile de trecere de la un produs la altul.

Se consideră matrice costurilor de trecere (C), unde liniuţa (-) în locul elementului (i, j) reprezintă faptul că trecerea de la produsul xi la produsul xj nu este posibilă.

Se asociază problemei o matrice booleană şi se defineşte matricea booleană A asociată problemei:


82

��

�

�

��

�

�

−−

−=

027340646110107

950862790

xxxxx

C

5

4

3

2

1

( )nnijaA

,= cu

��

��

≥

<=

jiij

jiijij cdacac

cdacaca

01

��

�

�

��

�

�

=

0100100110100000010101000

54321

A

Problema se rezolvă fie utilizând algoritmul clasic de determinarea a componentelor tare conexe, fie utilizând algoritmul Foulkes. Determinarea drumurilor hamiltoniene în grafuri fără circuite

Fie ( )UXG ,= un graf orientat. şi A matricea asociată grafului G. Puterea de atingere a unui nod Xxi ∈ în graful G este dată de numărul de noduri la care se poate ajunge din xi. Puterea de atingere se notează cu ( ) nixp i ≤≤1, .

Astfel, definim o matrice D numită matricea drumurilor cu elementele ijd ( d(xi , xj ) - reprezintă drumul de la nodul xi la nodul xj), ce se definesc în modul următor:

��

��

∃

∃=

)x,x(d)(daca0

)x,x(d)(daca1d

ji

jiij (4.17)

Deci, puterea de atingere p(xi) este dată de numărul de elemente egale cu 1 de pe linia i în matricea D. Dacă în matricea D elementele de pe diagonala principală sunt egale cu 0 atunci graful G nu are circuite, iar dacă există 1=ijd atunci în graful G există cel puţin un circuit care începe şi se termină în nodul xi. Matricea D a drumurilor într-un graf se poate obţine prin aplicarea următorului procedeu:

Etapa 1. În matricea arcelor ( conexiunilor directe ) A se consideră linia nii ≤≤1, . a) În linia i se identifică coloanele Sjjj ,,, 21 … cu elementele egale cu 1

( )1,...,11 == ijSij aa . b) Se adună boolean linia i cu liniile Sjjj ,,, 21 … şi se obţine linia i într-o nouă matrice

booleana D. c) Se repetă a) şi b) pentru liniile rămase.

Etapa 2. În matricea D se consideră linia nii ≤≤1, . a) În linia i se identifică coloanele pkkk ,,, 21 … cu elemente egale cu 1

( )1,...,11 == ikpik ad .


83

b) Se adună boolean linia i cu liniile pkkk ,,, 21 … rezultatul se înlocuieşte în linia i într-o nouă matrice booleana D.

c) Se repetă a) şi b) pentru liniile rămase.

Procedura se termină când matricea D nu se mai modifică (devine un invariant). D este matricea drumurilor numită matricea conexiunilor totale. Dacă în graful G există un drum de la nodul xi la nodul xj, evident, p(xi)>p(xj), deci orice nod atins de xj este atins din xi. Teorema 4.1 (Chen) Un graf fără circuite cu n noduri conţine un drum hamiltonian dacă şi numai dacă există relaţia:

�−=

=

n

1ii 2

)1n(n)x(p (4.18)

Teorema 4.2 (Chen) Dacă într-un graf orientat fără circuite există un drum hamiltonian atunci acesta este unic. Observaţie:

Conform proprietăţii că un graf condensat G* asociat unui graf G nu are circuite, se poate studia existenţa drumurilor hamiltoniene în graful condensat cu ajutorul teoremelor lui Chen.

Dacă graful condensat conţine un drum hamiltonian atunci şi graful iniţial are drum hamiltonian determinat de existenţa arcelor de legătură între componentele tari conexe ce formează graful condensat. Algoritmul Chen Fie ( )UXG ,= un graf orientat fără circuite. Etapa 1. Fie matricea arcelor A asociată grafului G şi se determină matricea D a drumurilor. Dacă toate elementele de pe diagonala principală sunt nule, graful nu are circuite şi se continuă cu etapa 2. În caz contrar, algoritmul se opreşte. Etapa 2. Se calculează puterile de atingere pentru fiecare nod. Dacă relaţia

( ) ( )�=

−=n

ii

nnxp1 2

1 se verifică, atunci graful G conţine un drum hamiltonian. În caz contrar, în

graful G nu există nici un drum hamiltonian şi algoritmul se opreşte.

Etapa 3. Un drum hamiltonian se găseşte prin ordonarea nodurilor descrescător după puterile de atingere.

Exemplul 4.10

În prelucrarea unui produs, acesta trebuie să treacă prin şapte secţii, folosind benzile de transport existente între aceste secţii, benzi reprezentate prin arce în graful din fig. 4.16

Presupunând că nu există o ordine preferenţială în prelucrarea produsului în cele şapte secţii, să se arate daca sistemul de benzi existent poate asigura transportul efectiv al produsului succesiv prin toate secţiile, iar dacă nu, ce benzi mai trebuie construite (cât mai puţine la număr), astfel încât să se rezolve problema transportului.


84

x1

x2 x3

x4

x5

x6x7

Fig.4.16

Matricea arcelor grafului este următoarea:

x1 0 0 0 0 0 01 0 01 1 11 0 0 0 0 00 0 1 0 1 0(A)

x2x3x4

x5x6x7

x1 x2 x3 x4 x5 x6 x7

0100

0 0 1 0 0 0 01 0 1 0 1 0 01 0 0 0 0 0 0

Din această matrice deducem matricea D:

0 0 0 0 0 01 0 11 0 1

01 0 0 0 01 0 1 0 1 01 0 1 0 0 01 0 101 0

(D)

P1 P2 P3 P4 P5 P6P1P2P3P4P5

P6

05

323

010000

P7

1 0 000 0P7 0 1

1

Pe diagonala principală nu avem nici un element egal cu unu, dar numărul de elemente

diferite de zero ale matricei D este: ( ) 212115 =−≠ nn .

Deci asigurarea transportului nu se poate face cu sistemul de benzi existent. Triunghiularizarea matricei D, se realizează în mai multe feluri, deoarece există două

vârfuri cu puterea de atingere 3 (x4 şi x6) şi alte două vârfuri cu puterea de atingere 1 (x3 şi x7).

Vom alege mai întâi pe aceea a cărei coloană corespunzătoare are mai puţine zerouri. În acest fel, vom obţine matricea din fig 4.17.

Se observă că adăugarea arcelor (x6, x4) şi (x3, x7) va asigura şi deasupra locurilor corespunzătoare încadrate cifre de unu, deci se impune construcţia a câte două benzi, una între secţiile x6 şi x4, iar cealaltă între secţiile x3 şi x7.

După aceasta, transportul produsului în cele şapte secţii trebuie organizat în ordinea

x2 x6 x4 x5 x3 x7 x1.


85

0 1 0 1 1 10 0 11 0

00 0 1 00 0 0 00 0 0 0 00 0 000 0

(D')0

01

10

x2 x3x4 x5x6 x7x2

0 0 000 0

11111

0

x1

x6x4

x5

x3x7x1

1

Fig.4.17

Exemplul 4.11

Fie şase produse care trebuie prelucrate conform proceselor tehnologice în cadrul unui sistem de producţie cu un număr limitat de resurse. Din acest motiv se definesc următoarele relaţii de ordine pentru realizarea produselor:

- Produsul P2 precede produsele P1, P3 şi P6; - Produsul P3 precede produsul P1; - Produsul P4 precede produsele P3, P5 şi P6; - Produsul P5 precede produsele P1, P2 şi P6; - Produsul P6 precede produsul P3. Problema care se pune este aceea de posibilitate de prelucrare a tuturor produselor,

fără să se încalce relaţiile de ordine stabilite. Relaţiile de ordine determină matricea arcelor (A) pentru cazul în care cele şase

produse se reprezintă ca vârfuri ale unui graf (fig.4.18) şi relaţia de succesiune prin arce . Evident că acest graf nu trebuie să conţină circuite, iar găsirea unei ordini de

prelucrare a tuturor produselor înseamnă găsirea unui drum hamiltonian în graf.

0 0 0 0 0 01 0 01 0 1

01 0 0 0 00 0 1 0 1 11 1 0 0 0 10 0 001 0

(A)


P6

x1

x2

x3 x4

x5

x6

Fig.4.18

Matricea drumurilor (D):


86

0 0 0 0 0 01 0 01 0 1

01 0 0 0 01 1 1 0 1 11 1 1 0 0 11 0 001 0

(D)


P6

031542

Deoarece această matrice nu conţine elemente egale cu unu pe diagonala principală, se

verifică că graful nu are circuite, iar deoarece numărul total al elementelor egale cu unu este ( )

2115 −= nn graful conţine un drum hamiltonian.

În partea dreaptă a matricei D s-au scris puterile de atingere ale vârfurilor corespunzătoare celor şase linii.

Punând aceste vârfuri în ordinea descrescătoare a puterilor de atingere, obţinem ( )136254 ,,,,, PPPPPPd H = . Aceasta va fi succesiunea optimă Triangularizarea matricei D se poate face scriind liniile în această ordine

descrescătoare a puterilor de atingere, şi schimbând apoi locurile coloanelor în aceiaşi ordine. Obţinem astfel matricea D’:

0 1 1 1 1 10 0 11 1

00 0 1 10 0 0 10 0 0 0 00 0 000 0

(D')


P6

0

11

11

Drumul hamiltonian găsit corespunde elementelor încadrate în această matrice.


87

4.4. Drumuri de valoare optimă în grafuri

Una dintre aplicaţiile teoriei grafurilor constă în determinarea drumurilor de valoare optimă minimă (maximă) între două vârfuri xl , xk care aparţin grafului G ( X,U ).

Fiecărui arc ui ∈ U, i se asociază o valoarea v(ui)>0 sau v(xl, xk)>0 numită valoarea arcului şi care în funcţie de problemă poate avea una din semnificaţiile: • Costul sau durata transportului pe ruta (xl, xk); • Costul de fabricaţie al unui produs pe locul de muncă reprezentat prin arcul (xl,xk) ; • Timpul de muncă necesar executării unui produs ; • Capacitatea maximă pe ruta (xl, xk);; • Câştigul realizat prin trecerea de la o stare la alta a sistemului (xl, xk); • Consum de energie pentru efectuarea trecerii de la o stare la alta (xl, xk);

Dacă considerăm drumul µ =(u1 , u2 uk ) atunci mărimea:

v(µ ) = �=

k

iiuv

1)( (4.19)

reprezintă valoarea drumului µ . Proprietăţi : • Într-un graf cu valori ale arcelor mai mari decât 0 şi finite există drumuri de valoare

minima finite între oricare 2 vârfuri ce sunt legate prin cel puţin un drum (orice drum de valoare minimă se numeşte drum elementar ).

• Într-un graf cu circuite, cu valori pozitive, există vârfuri între care se pot obţine valori oricât de mari. De aceea determinarea unui drum de valoare maximă îşi pierde sensul.

In continuare ne interesează valoarea optimă a drumului format din succesiunea de arce ui ce leagă x1 de xn . Algoritmul Ford

Pentru aflarea drumului de valoare oprimă între două vârfuri x1 şi xn ale grafului G(X,U) se parcurg următorii paşi :

Pasul 1: Fiecărui vârf xi al grafului i se asociază (ataşează) o variabilă λi ce are semnificaţia de valoare a drumului de la x1 la xi .

Prima valoare a acestei variabile este λ1 = 0 şi λi = ∞.

Pas 2 : Se caută un arc (xi , xj) pentru care să se îndeplinească condiţia:

λj -λi > v( xi , xj ) (4.20)

Dacă un astfel de arc a fost găsit se înlocuieşte λj cu λj’ unde acesta se scrie sub forma:

λj

’ = λi + v( xi , xj ) < λj (4.21)

Dacă există mai multe variante ce permit micşorarea variabilei λj se alege acel λj’ cu

valoarea cea mai mică. Se continuă în acest mod până când nici un arc nu mai poate micşora valorile lui λj.

Pas 3 : Deoarece pentru fiecare vârf xi valorile luate de λi ,formează un şir descrescător de numere nenegative, există nodul xp1 cu următoarea proprietate:


88

λn - λp1 = v( xp1 ,xn ) (4.22)

unde xp1 este vârful ce a contribuit ultima oară la micşorarea valorii lui λn . Anolog va exista şi xp2 pentru care se îndeplineşte condiţia:

λp1 - λp2 = v( xp2 ,xp1 ) până la:

λpk - λ1 = v( x1 ,xpk ) Deci valoarea minimă: v (µ0) = λn

µ0 = (x1 , …, xpk …. xp2 , xp1 , xn ) (4.23) Observaţie: În cazul în care se cere aflarea drumului de valoare maximă, apar următoarele diferenţe:

λ1 = 0 si λi = - ∞, λj -λi < v( xi , xj ), λj’ = λi - v( xi , xj ) < λj (4.24)

Exemplul 4.11 O firmă industrială are la dispoziţie mai multe variante tehnologice de prelucrare a unui produs. Variantele sunt redate prin succesiunea unor arce adiacente care reprezintă fazele de prelucrare a produsului, iar stadiile de prelucrare ale produsului sunt redate prin nodurile unui graf ce reprezintă modelul problemei de stabilire a variantei optime de prelucrare. Fiecărei faze îi corespunde un cost parţial de prelucrare. Conducerea firmei urmăreşte alegerea variantei tehnologice care permite obţinerea unui cost total minim. Problema urmează a se rezolva prin determinarea unui drum de valoare minimă în modelul graf asociat problemei.

Trebuie să se determine drumul de valoare minimă dintre vârfurile 61 xx → pentru graful G(X,U) de mai jos :

x1

x2

x3

x4

x5

x6

4

19

1814

5

15

1011 6

10

12

Fig.4.19

Se întocmeşte tabelul 4.1 ce conţine în primele 2 coloane arcele grafului şi valorile

asociate acestora. In celelalte coloane sunt trecute diferenţele jλ - iλ calculate la fiecare iteraţie.

(Se trec în acest tabel la început arcele incident interior lui nx şi apoi 1−nx ) Iteraţia 0: ∞==== ……321 0 λλλ şi toate aceste valori ale lui λ pe iteraţii se vor trece în tabelul 4.2. Iteraţia 1: Efectuând ij λλ − cu relaţia observăm că diferenţele:

12131415 ;;; λλλλλλλλ −−−− sunt mai mari (4.20) decât valoarea arcelor corespunzătoare (ele sunt marcate în tabelul 4.1 cu „*”).


89

( )jiij xxv ,>− λλ şi astfel se vor recalcula cu relaţia (4.21):

( ) ( )( ) ( )( ) ( )( ) ( ) 550

14140

15150

10100

2111

2

3111

3

4111

4

51151

=+=+=

=+=+=

=+=+=

=+=+=

xxv

xxv

xxv

xxv

λλ

λλ

λλ

λλ

Noile valori se vor trece în tabelul 4.2. Iteraţia 2 Se calculează ( ) ( )11

ij λλ − şi se compara cu ( )ji xxv

În cazul în care: ( ) ( ) ( ) ( ) ( ) ( )jiijjiij xxvxxv +=�>− 1211 λλλλ ,

analizând diferenţele: ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )ji xxv>−−−− 12

16

13

16

14

16

15

16 ;;; λλλλκλλλ

Se observă că există trei variante de micşorare a lui 6λ : ( ) ( ) ( )( ) ( ) ( )( ) ( ) ( ) 321814

251015

291910

631

32

6

641

42

6

651

52

6

=+=+=

=+=+=

=+=+=

xxv

xxv

xxv

λλ

λλ

λλ

Deoarece problema este de minim se va alege valoarea minima şi anume : ( ) 2526 =λ , iar

( ) ( ) ( ) 945521

22

5 =+=+= xxvλλ

Celelalte valori ( )2jλ se menţin aceleaşi.

Iteratia 3: Se calculează ( ) ( )2

i2

j λλ − . Observăm că aceste diferenţe nu mai pot fi micşorate

în raport cu valoarea arcului, deci ( ) 2526 =λ este valoarea minimă a drumului de la nodul x1

la nodul x6. În tabelul 4.1 se centralizează toate datele.

Pentru stabilirea succesiunii de arce ce formează drumul de valoare minimă se reţin

arcele adiacente pentru care în ultima coloană avem relaţia :

( ) ( ) ( ) { }{ } 25

25

645212

641122

==

==�=−

xxxxxxxxxxv jiij

µµλλ

Astfel există două variante tehnologice pentru care costul total este minim 25=)(µν

şi anume 21 µµ , . Algoritmul Bellman-Kalaba

Acest algoritm se bazează pe principiul general al programării dinamice care în cazul grafurilor capătă următoarea exprimare: dacă drumul de valoare minimă (maximă) care uneşte x1 → xn trece prin vârfurile intermediare xh , xk atunci drumul parţial xh → xk este un drum de valoare minimă.


90

Tabelul 4.1

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )

( )( )( )( )( )( )( )( )( )( )( ) 55*5xx

1414*14xx1515*15xx1010011xx11012xx6506xx910*10xx4*504xx11*018xx10*010xx14*019xx

xxvxx

21

31

41

42

43

45

51

52

63

64

65

2i

2j

1i

1j

0i

0jjiji

∞∞∞

∞

∞∞∞

−−− λλλλλλ

1

1

5

2

4

x

x

x

x

x

Tabelul 4.2

2591514502101514501

00654321

∞∞∞∞∞∞λλλλλλNr

În cazul în care se cere determinarea drumului de valoare minimă, grafului G( X ,U ) i

se ataşează matricea C cu componentele: c= ( cij ) şi i, j = 1,..,n şi

��

��

�

=≠∉∞

≠∈=

jijiUxx

jiUxxxxvc ji

jiji

ij

,0)(),(,

)(),(),,( (4.25)

Fiecărui vârf al grafului G i se asociază o variabilă vi, ce are semnificaţia de valoare a

drumului minim x1 → xn.. Rezolvarea sistemului de mai jos duce la aflarea soluţiei problemei:

��

=

+=≠

0)(min

n

ijjiji

vcvv

(4.26)

Pentru rezolvarea sistemului de mai sus se utilizează un procedeu iterativ, în acest mod

se pleacă de la informaţia iniţială definită în modul următor:

��

==

0)0(

)0(

n

ini

vcv

, i = 1,2,..,n-1 (4.27)

Pentru fiecare iteraţie k ( k = 1,2,..,n ) se rezolvă următorul sistem:

��

��

=+= −

≠

0)(min )1()(

n

ijk

jji

ki

vcvv

(4.28)


91

unde: Nk,n,1j,1n,1i ∈=−= Acest proces de calcul se închide în momentul în care:

)()1( ki

ki vv =− , i = 1,2,...,n-1. (4.29)

Atunci avem următoarele:

nk

nik

ii

xxvvxxvv

→==→==min

1)(

11

min)(

(4.30)

Determinarea arcelor drumului de valoare minima se face în modul următor: Fie xj1 vârful pentru care avem următoarea relaţie:

jk

jijjk cvcvv 1

)1(1

)(1 )min( +=+= − (4.31)

Analog xj2 vârful pentru care avem următoarea relaţie :

21)2(

221)1(

1 )min( jjk

jjjjk cvcvv +=+= −− (4.32)

Astfel drumul căutat este : µ =( x1,xj1,xj2,…..,xn ) Drumul de valoare minima trece prin xj1 si conform programării dinamice )1(

1−k

jv reprezintă valoare minimă a drumului xj1→ xn Exemplul 4.12 O întreprindere de montaj are la dispoziţie mai multe variante tehnologice de montaj a ansamblelor pentru un produs. Din datele existente în evidenţele întreprinderii reies costurile parţiale de trecere (tabelul 4.3). Conducerea urmăreşte alegerea variantei tehnologice care permite realizarea montajului cu obţinerea unui cost total minim. Tabelul 4.3

S1 S2 S3 S4 S5 S6 S7 M1 - 20 30 - - - - M1 - - 20 70 50 - - M1 - - - 10 - 50 - M1 - - - - - - 40 M1 - - - 10 - - 20 M1 - - - 20 - - 30 M1 - - - - - - -

Problema urmează a se rezolva prin determinarea unui drum de valoare minimă în modelul graf asociat problemei (fig.4.20).

Pentru calcularea elementului vectorului ( )1iv s-a efectuat suma dintre elementele

( )0iv si elementele corespunzătoare ale rândului I din C ji ≠ ( ) −∞=11v ( ) ( ) 1100;30;70;110;20;;max1

2 =+−∞∞−∞−−∞∞−∞−=v


92

( ) ( ) 800;3050;20;4010;;max1

3 =+−∞++−∞+∞−−∞∞−∞−=v

x1

x2

x3

x4

x5

x7

50

20

30

20 70 10

40

10

x630

20

20

50

Fig.4.20

Matricea asociata acestui graf :

( )( )( )( )( )( ) 0605040110130150v

0605040110130150v0605040110130140v0605040110110130v060504080110v0302040v0x30020x20010x400x

50100x5070200x

30200xxxxxxxx

5i

4i

3i

2i

1i

0i

7

6

5

4

3

2

1

7654321

∞−∞−∞−∞−

∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−

∞−∞−∞−∞−∞−∞−∞−∞−∞−

∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−∞−

C

In iteraţiile următoare se însumează elementele vectorului ( )1

iv cu elementele corespunzătoare liniei i din matricea C şi se reţine valoarea maximă. Întrucât ( ) ( ) →= 45

ii vv s-a obţinut soluţia optimă. Determinarea vârfurilor prin care trece drumul de valoare optima se realizează astfel:

( ) ( )( ) ( )

2124

214

15

1 1120130max xxcvcvv jjjjj =+=+=+= ≠

( ) ( )( ) ( )323

332

32

42 22

20110max xxcvcvv jjjjj =+=+=+= ≠

( ) ( )( ) ( )636

263

23

33 3

5060max xxcvcvv jjjj =+=+=+= ≠ ( ) ( )( ) ( )

4641

461

62

6 42040max xxcvcvv jjjj =+=+=+= ≠

( ) ( )( ) ( )747

074

04

14 5

400max xxcvcvv jjjj =+=+=+= ≠ ( )746321 xxxxxx=µ

( ) ( ) 150511 === vvv k

i


93

4.6. Cuplaje. Probleme de repartiţie (afectare) În practica industrială situaţii cum sunt: distribuţia produselor la locurile de vânzare,

repartizarea operaţiilor tehnologice pe o resursă tehnologică supraîncărcată, repartizarea activităţilor în cadrul unui proiect de producţie, repartizarea muncitorilor pe posturi de lucru etc, reprezintă momente în care afectarea activităţilor pe resurse are un rol esenţial în optimizarea procesului de producţie.

Această afectare se poate asimila cu o asocierea a elementelor unei mulţimi X = {x1, x2, ... , xn} cu elementele unei alte mulţimi Y = {y1, y2, ... , ym} în condiţiile unor condiţii impuse. Fiecare asociere conduce la un anumit efect (regim, profit, cost etc) care poate fi calculat.

Afectarea optimă între elementele celor două mulţimi presupune: să se realizeze maximul de afectări sau suma efectelor afectărilor să fie maximă (sau minimă, în funcţie de semnificaţia acestora).

Reprezentarea geometrică a situaţiei de mai sus este un graf bipartit de forma următoare :

Graful G = (X, U) se numeşte graf bipartit dacă mulţimea nodurilor poate fi împărţită în două mulţimi disjuncte A şi B astfel încât orice arc are extremitatea iniţială în A şi cea finală în B.

Submulţimea de arce W ⊆ U se numeşte cuplaj al unui graf bipartit dacă are proprietatea că nu există două arce adiacente (sau, pentru orice nod există cel mult un arc incident acestuia).

Un cuplaj cu proprietatea că orice arc care nu face parte din cuplaj este adiacent cu un arc din cuplaj se numeşte cuplaj maxim.

Numărul de arce ale unui cuplaj este mai mic sau egal cu numărul de elemente din fiecare din mulţimile A şi B.

Determinarea unei afectări optime a două mulţimi X şi Y, este echivalentă cu determinarea unui cuplaj maxim de valoare optimă (minimă sau maximă) în graful bipartit asociat.

În 1955, H.W. Kuhn a elaborat un algoritm, cunoscut în literatura de specialitate sub denumirea de algoritmul ungar, cu ajutorul căruia se poate determina un cuplaj maxim de valoare minimă într-un graf bipartit pentru care A=B= n.

Funcţia obiectiv pentru problema de repartiţie poate fi minimizată sau maximizată. Astfel se poate minimiza timpul total pentru a determina n sarcini sau se maximizează

beneficiul prin repartizarea produselor la locurile de vânzare. Din matricea C (matricea costurilor asociata sarcinilor) se aleg n componente în aşa fel

încât niciodată două elemente să nu figureze pe aceeaşi linie sau în aceeaşi coloana a matricei respective, alegerea fiind făcută astfel încât suma respectivelor elemente să fie minimă.

Astfel s-a obţinut permutarea optimă pentru problema dată Algoritmul ungar se bazează pe proprietatea că soluţia optimă a unei problemei să nu

se schimbe dacă se micşorează sau se măreşte cu o aceeaşi mărime fiecare element de pe o linie sau de pe o coloana a matricei .

x1

x2

xn

y1

y2

ym


94

Modelul matematic asociat unei astfel de probleme este sub forma :

==

==

∑

∑

∑∑

=

=

= =

n

jij

n

iij

n

i

n

jijij

ix

jx

xc

1

1

1 1

..2,1,1

..2,1,1

min

(4.37)

Fie matricea C= (cij)m,n unde cij> 0 si reprezintă valoarea cuplajului. In cazul in care nu

exista cuplaj atunci cij = ∞ .

Algoritmul de afectare ungar Pasul 1 :

Se transformă matricea C = ( cij ) într-o matrice de forma C(1) = (cij)(1) care să conţină câte un zero pe fiecare linie şi pe fiecare coloana . Acesta se efectuează alegând din fiecare linie elementul cel mai mic după care se scade din toate elementele liniei.

Dacă vor rămâne coloane fără elemente nule se repetă acest pas. Pasul 2 :

a. pe linia cu cele mai puţine zerouri se încadrează unul din zerouri şi se notează (barează)cu „X” toate zerourile situate pe linia şi pe coloana zeroului încadrat;

b. din cele n-1 linii rămase se considera linia cu cele mai puţine zerouri şi se procedează ca la punctul a;

c. în ultima linie neconsiderată până acum se alege un zero care se încadrează şi se vor bara toate zerourile. Dacă toate zerourile încadrate sunt în număr de n atunci algoritmul se întrerupe, soluţia fiind cuplajul definit de aceste zerouri şi care tot odată este cuplaj maxim.

Pasul 3: Se stabileşte un număr minim de linii şi coloane ale matricei C(1) care sa-i conţină

zerourile. Se va bifează cu (*) lateral următoarele: a) linii care nu au nici un zero se încadrează; b) coloanele care conţin zerouri barate pe linii marcate; c) linii care au cel puţin un zero încadrat în coloane marcate.

Operaţiile b) şi c) se repeta până când nu se mai poate marca nici o linie şi mici o coloană.

Suportul minimal este dat de mulţimea liniilor marcate reunite cu mulţimea coloanelor marcate. Pasul 4:

După terminarea suportului minimal în matricea C(1) se definesc trei tipuri de mulţimi de elemente : M1 – mulţimea elementelor netăiate (nesituate pe linii şi coloane tăiate) M2 – mulţimea elementelor situate la intersecţia liniilor tăiate cu coloane tăiate. M3- mulţimea elemente situate pe linii si coloane tăiate

Dacă m cel mai mic element din M1. Valoarea m se scade din toate elementele mulţimii M1 şi se aduna la toate elementele mulţimii M2 Elementele mulţimii M3 nu se vor modifica.

Astfel se va obţine o noua matrice C(2) pentru care se va aplica algoritmul ungar începând cu Pasul 1.


95

Exemplul 4.13 Un manager de proiect de producţie trebuie să repartizeze 5 echipe de muncitori (Mi) calificaţii la 5 lucrari de producţie (Lj). Managerul estimează în matricea C în cât timp (ore) execută o echipă fiecare lucrare, dorind să realizeze o repartiţie a echipelor pe lucrari astfel ca suma timpilor de execuţie să fie minimă.

C M1 M2 M3 M4 M5 L1 100 200 80 50 60 L2 225 75 325 350 450 L3 550 375 100 100 400 L4 500 400 300 700 600 L5 300 75 400 600 200

Se construieşte matricea pătratică C(1) care are elementele:

cij = ( ) ( )

( )��

∞ ji

jijix,x arculexista nudaca

x,x arculexista daca x,x arculuivaloarea

Pentru exemplul ales vom avea: C(1)=

��

�

�

��

�

�

2006004007530060070030040050040010010037555045032530075225605080200100

Pasul 1

Din fiecare linie se scade minimul acesteia apoi, în matricea obţinută, din fiecare coloană minimul acesteia.

Obţine succesiv matricele:

��

�

�

��

�

�

=

125525325022530040001002003000027545037525022501501003015050

C 11

)( şi

��

�

�

��

�

�

=

1155253250175290400010015029000275400365250225010000301500

C 12

)(

Pe fiecare linie şi pe fiecare coloană se află cel puţin un 0, care corespunde celui

mai mic timp.

Pasul 2 În finalul acestui pas, pe fiecare linie şi pe fiecare coloană va fi cel mult un zero încadrat. Dacă în final sunt n=5 zerouri, acesta este cuplajul maxim.

��

�

�

��

�

�

=

1155253250175290400010015029000275400365250225010000301500

C 12

)(

În total sunt 4 zerouri încadrate şi deci trecem la pasul 3.


96

Pasul 3 La acest se determină suportul minimal. Se va bifează cu (*) lateral următoarele: a) linii care nu au nici un zero se încadrează; se marchează linia L5 b) coloanele care conţin zerouri barate pe linii marcate; se marchează coloana M2; c) linii care au cel puţin un zero încadrat în coloane marcate; se marchează linia L2

Rezultă suportul minimal S={L1, L3,L4, M2} şi se trece la pasul 4.

Pasul 4 Cel mai mic element este m1=100 în linia L2, coloana L1. Matricea C(2) se obţine după regulă astfel: Dacă m cel mai mic element din M1. Valoarea m se scade din toate elementele mulţimii M1 şi se aduna la toate elementele mulţimii M2 Elementele mulţimii M3 nu se vor modifica. Matricea C(2) este următoarea, după care se reia pasul 2 şi obţinem:

��

�

�

��

�

�

=

154252250752904000200150290003754002651501250000302500

C 2)(

Deoarece avem 5 zerouri încadrate, am obţinut cuplajul maxim de valoare minimă,

căruia îi va corespunde repartizarea echipelor de muncitorilor pe lucrări astfel:

Cuplajul maxim are valoarea egală cu suma tuturor elementelor scăzute pentru obţinerea matricelor C(1) şi C(2).

V = 50+75+100+300+75+50+10+100=760ore

M1

M2

M3

M4

M5

L1

L2

L3

L4

L5


97

CAPITOLUL 5 TEHNICA DIAGRAMELOR DE TIP REŢEA

5.1. Generalităţi privind modelarea prin reţele

În practica industrială, proiectele de producţie presupun efectuarea unor activităţi (operaţii) intercondiţionate. Deoarece proiectele de acest tip durează săptămâni, luni sau chiar ani, în desfăşurarea lor pot interveni schimbări care au implicaţii directe asupra costurilor, resurselor sau tehnologiei. Pentru a modela arhitectura unui proiect de producţie se pot utiliza trei tipuri de reprezentări: relaţii de precedenţă, tabelare, reţele.

Analiza acestor reţele ce modelează sistemul analizat, îi permite managerului de producţie, să coordoneze, planifice, urmărească şi să reorganizeze resursele umane şi materiale astfel încât obiectivele propuse să se atingă în mod optim şi la timp.

Dezvoltarea tehnicilor de optimizarea în reţea a luat amploare îndeosebi după cel de-al doilea război mondial. Cele mai cunoscute astfel de tehnici: - tehnica diagramelor tip Gantt sau cu bare (dezvoltare a anilor 1910); - tehnica reţelele de tip:

- CPM (Critical Path Method) - Metoda Drumului Critic (1950); - MPM (Metro Potenţial Method) - Metoda Potenţialelor; - PERT (Program Evaluation and Review Technique) - Metoda PERT (1958); - GERT (Graphical Evaluation and Review Technique) - Tehnica GERT (1970)

La planificarea unui proiect de producţie, pentru a putea folosi o tehnică de tip reţea, trebuie ca acesta să fie definit în cadrul unui sistem pe la baza un proces, a unei tehnologii şi resurse de producţie şi totodată trebuie împărţit în părţile sale componente: activităţi (operaţii) şi evenimente (fig.5.1).

PRODUCŢIA – capacitatea de a mări utilitatea unui produs sau serviciu – motorul economiei. SISTEM – reprezintă ansamblul elementelor ce ascultă de un ansamblu de reguli de funcţionare bine definite în vederea îndeplinirii unui anumit scop. PROCES – reprezintă ansamblul operaţiilor desfăşurate între recepţionarea intrărilor şi elaborarea ieşirilor prin intermediul cărora sistemul îşi îndeplineşte o parte din funcţia sa. TEHNOLOGIA – reprezintă orice tip de produs se realizează pe baza unei tehnologii, ce poate fi de produs, de procedeu, etc. RESURSA – reprezintă elementul cheie cu ajutorul caruia se poate reliza tehnologia ACTIVITATEA – este specifică resursei, iar componentele de bază ale unei activităţi sunt: descrierea / denumirea activităţii şi codul acesteia; durata activităţii (minute, ore, zile, săptămâni, luni); resursele necesare realizării activităţii (umane, materiale, echipamente); costurile necesare realizării activităţii.

Activitatea este simbolizată în reţea prin litere majuscule (Ai). EVENIMENTUL – simbolizează momentul de început sau de terminare a unei activităţi şi este simbolizat în reţea cu cifre şi nu au durată, ele delimitând activităţile. Pentru proiectele de producţie, setul complet de activităţi (operaţii), necesare realizării acestuia ca conţine o combinaţie de activităţi în serie şi paralel, formând astfel reţeaua logică a proiectului de producţie ce poate fi reprezentată grafic.

Fig.5.1

Tehnica diagramelor de tip reţea

98

Eşalonarea în timp a operaţiilor componente proiectului de producţie, presupune determinarea duratei totale de realizare a proiectului adică intervalul dintre prima operaţie şi ultima operaţie. Acest interval de timp este mai mare sau egal cu suma intervalelor luate pe drumul cel mai defavorabil şi anume drumul critic. Algoritmul de determinare a drumului critic este acela de determinare a operaţiilor critice, acestea fiind operaţiile a căror întârziere perturbă desfăşurarea celorlalte operaţii şi necesită parcurgerea următoarelor etape:

a. etapa cantitativă în care se stabilesc: - activităţile (operaţiile) componente ale proiectului; - durata activităţilor (operaţiilor); - condiţionările ce exprimă legăturile dintre activităţi precizând pentru fiecare

activitate, activităţile imediat precedente; - reprezentarea grafică a proiectului de producţie prin reţeaua logică.

b. etapa calitativă în care se determină: - termenele activităţilor – datele la care pot sa înceapă sau sa se termine

activităţile; - termenul final a proiectului.

Drumul critic conduce la durata minimă de execuţie a proiectului de producţie.

Exemplul 5.1 În tabelul 1 este prezentat un proiect în care activităţile sunt notate prin litere mari A, B, C, D, E, F, G. Activităţile A şi B sunt activităţile de început ale proiectului. Activitatea A este direct precedentă activităţii C. De asemenea, activitatea C este direct precedentă activităţilor E şi F etc. Toate relaţiile de precedenţă sunt prezentate în tabelul 5.1

Tabelul 5.1 Nr. crt.

Activităţile proiectului

Activităţile direct precedente (condiţionări) Durate

1 A - 3 2 B - 2 3 C A 2 4 D B 6 5 E B 4 6 F C,D,E 4 7 G E 1

Există mai multe moduri de a reprezenta un proiect printr-o grafic-reţea. Cele mai folosite dintre aceste tehnici sunt CPM şi PERT. Metodele PERT şi CPM au

apărut în perioada 1958-1959, pentru a putea face faţă nevoilor epocii dezvoltării masive a ingineriei, în care tehnicile de planificare industrialã ale lui Taylor şi Gantt nu mai corespundeau. Diagramele Gantt presupun divizarea unei acţiuni complexe ( proiect) în parţi componente ( lucrări ) si apoi eşalonarea acestora în timp, ţinând seama de succesiunea operaţiilor în cazul proceselor tehnologice, resurse, termene impuse, etc. Diagrama Gantt conferă informaţii privind desfăşurarea lucrărilor şi informaţii derivate privind eşalonarea resurselor necesare ( forţă de muncă, resurse materiale). În cazul unor acţiuni complexe cu sute de operaţii se observă că avantajele acestor diagrame Gantt scad simţitor, datorită imposibilităţilor de corelare a lucrărilor componente.

Eventuale modificări de durată în cazul proiectelor de producţie, conduc la refacerea grafului Gantt (fig.5.1) la orice modificare ce apare.

Graficul Gantt reprezintă o formă de vizualizare şi de planificare a proiectelor, şi reprezintă o reţea în care activităţile şi evenimentele sunt transpuse calendaristic pe o axă orizontală a timpului.


99

Unei activităţi i se asociază o barã de lungime direct proporţională cu durata estimată. Graficele Gantt au dezavantajul că nu arată interdependenţele dintre activităţi şi evenimente. Exemplul 5.2 Este prezentat un proiect de construcţii sub forma codificată conform tabelului de precedenţa 5.2. Graficul Gantt pentru acest proiect este reprezentat în fig.5.1. Tabelul 5.2

Fig.5.1

5.2. Metoda drumului critic (C.P.M.) Metoda CPM este o metoda fundamentală de analiză a drumului critic şi un procedeu

de analiză în care singurul parametru analizat este timpul În funcţie de modalitatea de reprezentarea a reţelei CPM distingem două categorii şi

anume : reţea ADC de tip activitate – arc şi reţea CPM de tip activitate – nod. Avantaje ale modelelor cu reţele CPM: obligă la o analiză amănunţită a structurii

logice a proiectului; evidenţiază în mod explicit legăturile logice între activităţi, determină durata reală a proiectului, evidenţiază activităţile critice (activităţi cheie ) şi activităţile necritice – permiţând anumite rezerve de timp cu posibilitatea de distribuire spre activităţi critice; Graful întocmit îşi păstrează configuraţia chiar dacă au loc modificări de durate sau termene, permit optimizarea proiectelor în funcţie de timp.

Reţea CPM de tip Activitatea – Arc (A-A)

Construcţia reţelei CPM de tip A-A

În reprezentarea reţelei CPM de tip A-A se ţine seama de următoarele convenţii:

Nr.crt. Denumirea activitaţii Cod Activ. prec. Durată 1 Proiectare P - 7 2 Achiziţionare A P 2 3 Comenzi Utilaje CU P 3 4 Organizare şantier (etI) OS1 P 1 5 Formare cadre calificate F P 10 6 Execuţie dr interioare (et I) D1 A,OS1 2 7 Execuţie reţele electrice (etI) R1 A, OS1 5 8 Livrări, recepţie utilaje LU CU 6 9 Lucrări constr.montaj (etI) C1 A,OS1 4 10 Organizare şantier (et II) OS2 OS1 2 11 Execuţie dr interioare (et II) D2 D1,OS2,R1 3 12 Execuţie reţele (etII) R2 R1 5 13 Lucrări constr.montaj (etII) C2 LU,C1,R2 10

Evaluare calendaristica Activitate 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Proiectare(P) Achizitonare(A) Comenzi util(CU)

Org.santier (OS)

Exec dr.int ( D) Exec.retele ( R) Livr util (LU) Lucr.constr-mont (C)

Formare cadre (F)


100

− fiecărei activităţi este reprezentă printr-un arc cu orientarea dată de modul desfăşurării activităţii definit prin capetele sale; − fiecare arc este delimitat de două noduri (unul de început şi celălalt de sfârşit) ce simbolizează evenimentele (momentele) de început respectiv sfârşit. Evenimentele reprezentând stadii de realizare a activităţilor. − fiecărui arc i se asociază deasupra sa denumirea activităţii iar sub, o valoare egală cu durata activităţii pe care o reprezintă; Reţeaua poate fi notată G(X,U), în care X-mulţimea nodurilor şi U-mulţimea arcelor − condiţionarea a două activităţi se reprezintă prin succesiunea a două arce adiacente.

Tipurile de activităţi existente intr-o reţea CPM sunt: - propriu zise – cele ce consumă şi timp şi resursă pentru realizarea ei; - aşteptările – cele ce consumă numai timp pentru a fi realizate; - fictive – cele care nu consumă nici timp nici resursă pentru realizare, ele există datorită intercondiţionărilor şi reprezentării grafice.

Situaţii posibile de condiţionare (precedenţă) sunt reprezentate în fig.5.2 (a, b, c) - Activitatea A este direct predecesoare unei activităţi B (A şi B se numesc activităţi succesoare fig.5.2 a) - Activităţile B şi C au aceeaşi activitate predecesoare A (fig.5.2b) - Activităţile A şi B sunt precedate direct de activitatea C (fig.5.2c)

1 2 3BA 1 2A3

4

BC

12

A

34B

C

a) b) c) Fig.5.2

La trasarea reţelei CPM trebuie respectate următoarele reguli:

- activităţi care se execută în paralel, adică care pot începe în acelaşi moment şi se pot termina în acelaşi moment, este interzis ca cele două arce corespunzătoare activităţilor să aibă ambele extremităţi comune. În fig.5.3 care este reprezentarea corectă, F fiind o activitate fictivă:

- nu trebuie introduse dependenţe nereale între activităţile proiectului (neprevăzute în tabelul de condiţionări). Astfel, dacă în tabelul de condiţionări vom avea situaţia: Tabelul 5.3

Activitate Activitate direct precedentă (condiţionări)

A - B - C A,B D B

atunci reprezentarea din fig.5.4 este incorectă, deoarece introduce condiţionarea dintre activitatea A şi activitatea D, inexistentă în tabel.

A

B

A

B

F A

B F

incorect corect

sau

Fig.5.3


101

Reprezentarea corectă este dată în fig.5.5 în care a fost introdusă activitatea fictivă F care anulează condiţionarea între A şi D:

- în reţeaua CPM nu sunt admise circuite (existenţa unuia ar însemna că orice activitate a acestuia ar fi precedentă ei însuşi). - reţeaua CPM are un singur nod iniţial (semnificând "începerea proiectului") şi un singur nod final (semnificând "sfârşitul proiectului"); - orice activitate trebuie să aibă cel puţin o activitate precedentă şi cel puţin o activitate succesoare, exceptând activităţile care încep din nodul iniţial al proiectului şi pe cele care se termină în nodul final al proiectului; - forma, lungimea şi orientarea arcelor reţelei CPM sunt arbitrare. Exemplul 5.3 Cu ajutorul tabelului (tab.5.1, tab.5.2) intercondiţionărilor se construieşte reţeaua CPM (fig.5.6, fig.5.7).

Fig.5.6

0

62

54

3

1 8

7

P

CU

LU

A

OS1

C1

R1

D1

R2

C2

D2

OS2

f1

f2

f3

7

3

10

6

2 5 5

2

2

3

100

0

F10

1

2

3

5

4

6

Figura 5.7

A

B

C

D

E

F

G

A

B

C

D

Figura 5.4 A

B

C

D

Figura 5.5


102

Analiza reţelei CPM de ti A-A Această analiză constă în determinarea termenelor evenimentelor, termenelor şi

rezervelor de timp ale activităţilor, determinarea activităţilor critice şi determinarea duratei minime a proiectului (lungimea drumului de valoare maximă).

Avem deci de găsit drumul de lungime maximă dintr-un graf fără circuite, pentru care se poate aplica algoritmul lui Ford simplificat.

Conform acestui algoritm, se calculează pentru fiecare nod al grafului:

Pasul 1 Determinarea termenelor evenimentelor A. Termenul minim de realizare a evenimentului j ( -

jt ). - reprezintă momentul cel mai devreme posibil de terminare a mulţimii (U-(j)) activităţilor care converg în nodul j

Termenul cel mai devreme a evenimentului j, se calculează astfel:

-jt =

��

��

+−

∈)),((

)(jidtmax

0

ijUj -

(5.1)

B. Termenul maxim a evenimentului j ( +

jt ) reprezintă momentul cel mai târziu posibil de începere a mulţimii a activităţilor (U+(j)) care pleacă din nodul j . Termenul cel mai târziu de realizare a unui eveniment j se calculează astfel:

+jt =

��

��

−+

∈

−

+)),((

)(kjdtmin

t

kjUk

j (5.2)

Intervalul [ -

jt , +jt ] se numeşte intervalul de fluctuaţie al evenimentului j. Evenimentul j

se poate plasa în orice moment al acestui interval de fluctuaţie, fără a periclita durata totală a întregului proiect.

Termenele maxime şi minime pentru fiecare eveniment, calculate cu relaţiile (5.1) şi (5.2), se completează în reţeaua CPM în mici dreptunghiuri ataşate nodurilor (fig.5.8a), sau fiecare nod al reţelei se reprezintă printr-un cerc divizat în trei părţi (fig.5.8b), în care se trece în partea de sus numărul nodului j, în partea inferioară-stânga termenul minim de realizare -

jt

şi în partea inferioară-dreapta termenul maxim de realizare +jt .

1 2A

d(i, j)ti ti* tj tj*

i

tjm tj

M

a) b)

Fig.5.8 Exemplul 5.4 Pentru reţeaua din fig5.7

1

4

2

3

5CA

B 23 D

6

4E

6

G1

F4

2

8 83 6

2 2

0 0

6 8

12 12

Fig.5.9

, dacă U-(j)=∅ , dacă U-(j)≠∅

, dacă U-(j)=∅ , dacă U-(j)≠∅


103

Pasul 2 Determinarea termenelor şi rezervelor de timp ale activităţilor Se calculează pentru fiecare activitate (i,j), următoarele termene ale activităţilor:

a) Termenul minim de începere a activităţii (i,j):

-ît (i,j) = -

it (5.3)

b) Termenul minim de terminare a activităţii (i,j):

-tt (i,j) = -

ît (i,j)+d(i,j) = -it + d(i,j) (5.4)

c) Termenul maxim de terminare a activităţii (i,j):

+tt (i,j) = +

jt (5.5)

d) Termenul maxim de începere a activităţii (i,j):

+ît (i,j) = +

tt (i,j)-d(i,j)= +jt -d(i,j) (5.6)

Aceste termene arată în ce interval poate fi situată o activitate, dar nu dau informaţii în

legătură cu diferenţe dintre o plasare posibilă sau alta. În acest scop se vor calcula, pentru fiecare activitate (i,j), următoarele rezerve de timp:

a) Rezerva totală de timp (Rt) a unei activităţi (i,j) reprezintă intervalul maxim cu care poate fi amânată (întârziată) o activitate fără ca durata totală a proiectului să fie periclitată. Rezerva totală este diferenţa dintre termenul maxim de terminare şi termenul minim de terminare:

Rt(i,j) = +jt - -

it - d(i,j) (5.7)

b) Rezerva liberă de timp (Rl) a unei activităţi (i,j) reprezintă intervalul cu care poate fi prelungită activitatea cu respectarea termenelor minime de începere a tuturor activităţilor adiacente succesoare.

Rl(i,j) = −jt - -

it - d(i,j) (5.8) c) Rezerva independentă de timp (Rs) a unei activităţi (i,j) reprezintă intervalul în care poate fi plasată o activitate fără a consuma nici din rezervele de timp ale activităţilor ce o preced, nici din cele ale celor ce o succed.

Ri(i,j) = max( −jt - +

it -d(i,j)) (5.9)

Intervalele de fluctuaţie pentru termene şi rezervele libere de timp pentru activităţi caracterizează elasticitatea unui program de planificare. Cu cât aceste intervale sunt mai mici cu atât programul este mai rigid.

Drumul cel mai lung din reţea a cărui lungime este egală cu durata minimă de execuţie a proiectului se numeşte drum critic. Orice amânare a unei activităţi a acestui drum duce la lungirea duratei de execuţie a proiectului. Activităţile de pe drumul critic nu dispun de rezervă de timp şi se numesc activităţi critice.


104

O activitate critică (i,j) este caracterizată prin:

-it = +

it , -jt = +

jt , -jt – +

it = d(i,j) (5.10)

Rt(i,j) = Rl(i,j) = Ri(i,j) = 0 (5.11)

În practică industrială este nevoie să ne interesăm de activităţi, în ceea ce priveşte realizarea acestora, decât de termene. Activităţile (operaţiile) critice trebuind să fie realizate la datele calculate deoarece nu dispun de rezervă de timp şi aceasta pentru a nu depăşi termenul de finalizare al proiectului. Celelalte activităţi pot fi amânate cu rezervele lor de timp, dar consumarea acestora face ca proiectul să devină rigid.

Pentru activităţile proiectului analizat în fig.5.7, termenele activităţilor şi rezervele de timp sunt date în tabelul de mai jos:

Tabelul 5.4

Activităţi Cond. Durate -mt

+mt -

Mt +Mt Rt Rl Ri

A = (1,2) - 3 0 3 3 6 3 0 0 B = (1,3) - 2 0 2 0 2 0 0 0 C = (2,4) A 2 3 5 6 8 3 3 0 D = (3,4) B 6 2 8 2 8 0 0 0 E = (3,5) B 4 2 6 4 8 2 0 0 F = (4,6) C,D,E 4 8 12 8 12 0 0 0 G = (5,6) E 1 6 7 11 12 5 5 0

Printre avantajele metodei CPM evidenţiem: − determinarea cu anticipaţie a duratei de execuţie a proiectelor complexe; − explicitarea legăturilor logice şi tehnologice dintre activităţi; − evidenţierea activităţilor critice; − evidenţierea activităţilor necritice, care dispun de rezerve de timp; − permite efectuarea de actualizări periodice fără a reface reţeaua CPM − reprezintă o metodă operativă şi raţională care permite programarea în timp a

activităţilor ţinând seama de resurse. Dezavantajele acestei metode sunt în principal: − greutatea desenării reţelei CPM, reprezentarea exactă a tuturor condiţionările din

proiect, în condiţiile în care acestea sunt foarte complicate iar reţeaua logică trebuie să fie simplă, clară, completă încât să fie utilă;

− dacă se respectă toate regulile de construire a reţelei CPM, rămân variante de reprezentare astfel încât două reprezentări ale aceluiaşi proiect făcute de doi indivizi pot să nu semene aproape deloc.

Reţea CPM de tip Activitatea – Nod (A-N)

Construcţia reţelei CPM de tip A-N

În reprezentarea reţelei CPM de tip A-N se ţine seama de următoarele convenţii: − fiecare activitate este reprezentă printr-un nod notat printr-un dreptunghi; − fiecare arc al reţelei delimitat de două noduri (unul de început şi celălalt de sfârşit) simbolizează relaţiile de precedenţă între activităţi. − reţeaua CPM de tip A-N trebuie să aibă un singur nod iniţial şi un sigur nod final şi în mod curent se introduce un nod fictiv de început (START) şi un nod fictiv de final (FINISH), iar aceste două noduri (activităţi) sunt singurele fictive din cadrul reprezentării A-N.


105

În reprezentare A-N fiecare nod este simbolizat printr-un dreptunghi iar acesta este compartimentat în şase căsuţe (fig.5.11) unde se înscriu următoarele: - simbolul activităţii (operaţiei) i; - durata activităţii d(i); - termenul minim de începere -

ît (i)

- termenul minim de terminare -tt (i)

- termenul maxim de terminare +tt (i)

- termenul maxim de începere +ît (i)

t-î(i)t+î(i)

id(i)

t-t(i)t+t(i)

Fig.5.10 a) Termenul minim de începere a activităţii:

( )( )

( )( )

( )��

��

�

∅≠

∅== −

∈

−

−

−

−idacakt

idaca0it

iki

î ΓΓ

Γ,max

, (5.12)

b) Termenul minim de terminare a activităţii:

( ) ( ) ( )idititt += −−î (5.13)

c) Termenul maxim de terminare a activităţii:

( )( ) ( )

( )( )

( )��

��

�

∅≠Γ

∅=Γ= +

Γ∈

+

+−

+

+idacajt

idacaitit

ij,min

,

î

t

t (5.14)

d) Termenul maxim de începere a activităţii:

( ) ( ) ( )iditit −= ++tî (5.15)

Exemplul 5.5

Este prezentat un proiect de producţie, sub forma codificată, conform tabelului de precedenţa 5.5. Să se determine temenele activităţilor proiectului şi activităţile critice ale acestuia, ce determină durata maxima a proiectului utilizând ambele reprezentări ale reţelei CPM (A-A, A-N)

Tabelul 5.5 Denumire activitate

Activitati directe precedente Durata

ABCDEFGHIJKLMNP

--AAAA

B, CB, C

DD, E

F, G, HH

K, LI, J, MK, L

541454226465233


106

Reprezentarea A-A (fig.5.11):

1

2

3

4

59

87

6

10A

DI

N

PM

J

FCB

G

H L

8 9

5

5 5

9 11

17 176

0

3

3 20 20

15 155

6K

4

42

24

0 0

6 7

10 13

04

5E

1

2

9 9

Fig.5.11

Reprezentarea A-N (fig.5.12):

00

Y0

00

00

A5

55

03

B4

47

58

E51013

F4

99

C1

57

57

D4

911

55

66

J41417

911

I61517

1013

99

K61515

N3

1717

G2

6978

H2

6978 8

10L51315 15

17P31820

20 Z020

2020

2020

N3

1515

1717

Fig.5.12

Planificarea detaliată sub forma unei reţele permite echipei de management de proiect

să definească tot ceea ce trebuie efectuat într-un mod detaliat pentru atingerea la timp a obiectivului proiectului.

Crearea reţelei CPM şi analiza drumului critic evidenţiază interdependenţele şi zonele cu probleme care nu sunt nici evidente, nici bine definite prin alte metode de planificare.

Reprezentarea CPM reduce posibilitatea de a lua decizii la nivelul conducerii superioare şi totodată necesită mult timp pentru detalii conducând la o lipsă a unui istoric privind costurile.

5.3. Metoda potenţialelor (Metro Potenţial Method)

Metoda potenţialelor sau MPM este un procedeu de analiză a drumului critic care

încearcă să depăşească neajunsurile metodei CPM, în care, ca şi în metoda CPM, se analizează parametrul timp, diferenţa constând în felul în care se construieşte graful reţea:

− fiecărei activităţi A i se asociază un nod A; − fiecărui nod i se asociază o valoare dată de durata activităţii pe care o reprezintă; − condiţionarea (succesiunea) a două activităţi se reprezintă printr-un arc, orientat de

la o activitate la alta; − fiecărui arc dintre două activităţi A şi B i se asociază un număr reprezentând

valoarea tAB. Determinarea termenelor şi rezervelor:

a) Termenul minim de începere a activităţii:


107

( )( )

( ) ( ){ }( )

( )��

��

�

∅≠+

∅== −

∈

−

−

−idacaiktkt

idaca0it

ik

-î

î ΓΓ

Γ,,max

, (5.16)

b) Termenul minim de terminare a activităţii:î

( ) ( ) ( )iditit it += −− (5.17)

c) Termenul maxim de începere a activităţii:

( )( ) ( )

( ) ( ){ }( )

( )��

��

�

∅≠−

∅== +

+∈

+

+

+idaca,j,itjtmin

idaca,itit

ijî

-î

î Γ

Γ

Γ

(5.18)

d) Termenul maxim de terminare a activităţii:

( ) ( ) ( )iditit ît += ++ (5.19)

Rezerva totală Rt(i) a activităţii se calculează cu relaţia:

( ) ( ) ( )ititiRt î*î −= (5.20)

Exemplul 5.6 Condiţionările de precedenţă din cadrul unui proiect de producţie sunt sintetizate în tabelul 5.6. Să se determine activităţile critice ale proiectului. Tabelul 5.6

Denumire activitate Durata

ABCDEFGHIJK

-AAA

D

C, D, FG, I

4

42

2

4

6

Activitati directe precedente Conditionari

BB

E, F

H, J

-tAB = 2tAC = 3tAD = 2tBE = 3tBF= 3tDG = 1

tEH = 1, tFH = 2tCI=4, tDI=3, tFI=3

tGJ = 3, tIJ = 2tHK = 3, tJK = 3

3

3

530

Reţeaua asociată proiectului este dată în fig.5.13.

Se parcurge reţeaua în sens direct de desfăşurare şi se determină termenele minime de începere şi terminare a activităţilor proiectului cu relaţia (5.16, 5.17), după care acesta se parcurge în sens invers de desfăşurare şi se determină termenele maxime de începere şi terminare a activităţilor proiectului cu relaţiile (5.18, 5.19). Rezervele totale se determină cu relaţia 5.20. Drumul critic este format din activităţile critice :A, C, I, J, K.


108

00

A6 0

23

B4 7

58

E

F

C

D

5

J

I K

G

H7

66

6

33 2 5

5

244

68

83 11

6 2 87

77 5

1212

111349

33 96

6 99

1212

1212

1212

2

2

3

3

3

4

3

31

1

2

3

2

3

3

Fig.5.13

5.3. Metoda PERT Metodele CPM şi MPM furnizează informaţii care sunt utile în procesul de

management, însă ele nu ţin seama de posibilele variaţii ale duratelor de execuţie ale activităţilor şi lucrează cu timpi bine determinaţi asociaţi fiecărei activităţi permiţând atât estimarea costurilor, cât şi a timpului de execuţie a proiectului.

Aceste metode sunt deterministe, iar controlul timpului şi costului de execuţie a unui proiect se realizează prin determinarea drumului critic al acestuia.

Metoda PERT permite calcularea timpului mediu de finalizare a unui proiect, identificarea activităţilor critice, precum şi estimarea probabilităţilor de realizare a termenelor planificate.

Deoarece în practică, duratele activităţilor sunt insuficient cunoscute sau incerte prin considerarea conceptelor statistice, duratele activităţilor sunt considerate variabile aleatoare caracterizate prin media şi dispersia lor.

Metoda PERT foloseşte trei durate de timp asociate fiecărei activităţi (optimistă-a, probabilă-m şi pesimistă-b), formând o medie ponderată, care reprezintă durata aşteptată/estimată a proiectului.

Durata optimistă a unei activităţi i (ai), este considerată durata minimă de execuţie pentru activitatea i, în condiţii generale normale.

Durata probabilă a unei a unei activităţi i (mi) ca fiind estimaţia cu cea mai mare şansă de realizare a proiectului în condiţii normale;

Durata pesimistă a unei activităţi i (bi) este considerată durata maximă de realizare a activităţii i, atunci când există condiţiile cele mai defavorabile de realizarea a proiectului.

Astfel, timpul de execuţie a unui proiect este calculat pe baza teoriei probabilităţilor. Metoda PERT este o metodã probabilistă bazată pe distribuţia beta pentru timpul

fiecărei activităţi şi pe o distribuţie normală (Gauss) pentru durata de timp estimată, permiţând astfel planificarea şi controlul timpului de execuţie a întregului proiect.

Reţeaua PERT este o reţea CPM sau MPM în reprezentare, iar fiecare activitatea din reţea este caracterizată cu cele trei tipuri de durate (a, m, b).

Durata fiecărei activităţi a proiectului are o distribuţie β. Durata medie de execuţie ( t ) (speranţa matematica) a unei activităţi (i) este dată de

expresia:

E(t)= t = 6

bm4a +⋅+ (5.20)

Dispersia duratei de execuţie ( )(i2σ ) a activităţii (i) caracterizată şi ca o măsură a

gradului de nesiguranţă în estimarea duratei activităţii se calculează cu expresia:

)(i2σ = 2

6ab��

��

� − (5.21)


109

Durata totală a proiectului este o variabilă aleatoare cu distribuţie normală având media şi dispersia:

�=

∈ critDi(i)tT �=

∈ critDi

22 i)(σσ (5.22)

unde Dcrit reprezintă mulţimea tuturor activităţilor care sunt pe drumul critic.

Probabilitatea de realizare a duratei planificate Tplan a unui proiect se determină calculând, factorul de probabilitate Z, după relaţia (5.23) şi apoi se deduce din tabelul valorilor funcţiei Laplace probabilitatea p (T ≤ Tplan).

Z= 2

plan TT

σ

− (5.23)

Algoritmul PERT pentru determinarea probabilităţii de finalizare

a unui proiect la termenul planificat

Pasul 1 Se calculează durata medie a fiecărei activităţi din reţeaua PERT, utilizând relaţia (5.20); Pasul 2 Se calculează termenele activităţilor reţelei PERT, utilizând una din metodele CPM sau MPM; Pasul3 Se calculează dispersia duratei fiecărei activităţi cu relaţia (5.21); Pasul 4 Se calculează durata totală de execuţie a întregului proiect (T ) şi dispersia ( 2σ ) cu relaţiile (5.22); Pasul 5 Se determină probabilitatea de realizare a duratei planificate a proiectului după relaţia 5.23 folosind tabelul funcţiei Laplace; Pasul 6 Se face analiza proiectului, conform probabilităţilor de realizare a duratei a proiectului: - dacă p 25≤ % arată un risc foarte mare ca proiectul să nu se realizeze la termenul planificat şi se impune revizuirea duratelor de execuţie ale activităţilor în sensul urgentării desfăşurării acestora; - dacă p ≈ 50% planificarea activităţilor este corectă şi se poate aplica; - dacă p ≥ 60% se respectă termenul planificat dar există o risipă de resurse. Exemplul 5.7 Se consideră un proiect de producţie a cărui activităţi şi condiţionări sunt indicate în tab.5.7. Se cer următoarele:

- să se determine activităţile critice ale proiectului de producţie; - să se determine probabilitatea ca realizarea proiectului de producţie să se încadreze

într-o perioadă planificată de 41 u.t.


110


Activitati directe precedente

Durata [u.t.]

ABCDEFGHIJ

-

AA

B

H, I

B, C

B, CF, G

D, E

3452244265

67845564108

910119812116

2017

a m b

B

a) Pentru fiecare activitate a proiectului se determină durata medie de execuţie şi dispersia cu relaţiile (5.20), respectiv (5.21.)(tab.5.8), după care se construieşte reţeaua CPM în reprezentarea A-A (fig.5.14).


Durata

ABCDEFGHIJ

7

4,58

6

4

6

Dispersia

5

6,5

119

µ σ2

111

1,171

1,341,170,672,33

2 Se determină termenele minime şi maxime pentru ale evenimentelor proiectului şi se

înscriu în căsuţe alăturate nodurilor reţelei CPM.

1 2A6

0 0 6 6

3

4

5 6

7 8

B7C

8 E5

D4,5

F6

G6,5 H4

J9

I11

13 14,5

14 14

19 19

25,5 25,5

38,5 38,529,5 29,5

0

Fig.5.14 Activităţile critice ale proiectului sunt A, C, E, G, H, J, iar durata medie de execuţie a

proiectului este T = 38,5 u.t. b) Dispersia totală a proiectului este:

846JHGECA 2222222 .)()()()()()( =+++++= σσσσσσσ

Factorul de probabilitate Z este:

Z= 2

plan TT

σ

−= 950

62253841 .

.. ≅−

Pe baza tabelului lui Laplace obţinem probabilitatea P(Z<0.95)=0.83=83%.


111

Metodele PERT şi CPM nu sunt metode lipsite de dezavantaje. Complexitatea lor se adaugă problemelor de implementare. Prin urmare de cele mai multe ori aceste metode devin foarte costisitoare şi greu de folosit în cazul proiectelor complexe, de mare anvergură. Alte dezavantaje în folosirea metodelor PERT şi CPM sunt: - efort mare în ceea ce priveşte munca şi timpul necesare aplicării lor; - reducerea posibilităţii de a lua decizii la nivelul conducerii superioare; - lipsa datelor istorice pentru estimarea costurilor;

Metoda PERT permite specificarea probabilităţilor de realizare la termen, în avans sau cu întârziere a proiectelor

Metoda CPM permite evaluarea compromisului timp – cost (efectul costului mărit pentru reducerea timpului de execuţie faţă de costul în condiţii normale pentru unele activităţi).

5.4. Tehnica GERT

GERT (Grafical Evaluation and Review Technique – Tehnica de analiză şi evaluare grafică ) este o schemă-model dezvoltată pentru situaţii mai complexe decât cele care pot fi rezolvate de PERT/CPM.

GERT combină teoria grafurilor, schema probabilistică PERT/CPM şi arborele de decizie. Elementele utilizate de metodă sunt nodurile schemei logice (etapele) şi activităţile reprezentate prin săgeţi şi caracterizate prin doi parametri respectiv, probabilitatea ca o activitate dată să fie realizată şi funcţia de distribuţie care estimează timpul necesar realizării activităţii.

Evaluarea schemei GERT arată probabilitatea de realizarea a fiecărei etape şi intervalul de timp dintre acestea.

Câteva dintre diferenţele celor două metode sunt relevate în tabelul 5.1. Tabelul 5.1

Tehnica GERT Metoda PERT/CPM - ramificaţia în schema-model; este probabilistică

- ramificaţia în reţeaua logică este deterministă

- sunt posibile diverse distribuţii pentru estimarea timpului

- este utilizată numai distribuţia beta

- există flexibilitate în realizarea etapelor

- nu există flexibilitate în realizarea etapelor

- este acceptată întoarcerea la evenimentele anterioar

- întoarcerea la evenimentele anterioare nu este permisă

- este dificilă folosirea ca metodă de control

- poate fi folosită pentru control

Pentru optimizarea problemelor PERT/CPM există programe de calculelor.

Diversele probleme de tip GERT se rezolvă prin simulări cu ajutorul calculatorului. Cel mai nou model GERT se numeşte Q-GERT şi simulează reţele ale liniilor de aşteptare. Există şi alte variante ale metodei PERT care au trăsături similare cu GERT cum ar fi exemplu, Q-GERT-VERT, dar GERT se pare că are răspândirea cea mai mare.

Etapele folosite în GERT sunt următoarele:

- Transpunerea descrierii calitative a proiectului într-o schemă, după modelul folosit în PERT/CPM

- Strângerea informaţiilor necesare pentru a descrie activităţile schemei, cu accentul nu numai pe activităţile specifice care sunt luate ca model, dar şi pe cele cu posibilităţile de realizare, precum şi pe orice activităţi alternative care există

- Stabilirea funcţiilor de echivalenţă a reţelei.


112

- Transformarea funcţiei echivalente a schemei în următoarele două măsuri de performanţă: - probabilitatea ca etapele specifice să fie realizate - funcţia generatoare a momentului de timp.

- Analiza rezultatelor şi stabilirea concluziilor legate de sistem. Lista simbolurilor utilizate în metoda GERT, împreună cu câteva exemple este prezentată în fig.5.1: În această figură, în partea stângă sunt prezentate intrările cu noduri iar în partea dreaptă sunt ieşirile. Aşa cum se arată în exemplu, toate combinaţiile de intrare şi ieşire a simbolurilor sunt posibile. Această metodă poate fi utilizată în cazul proiectelor pentru introducerea de noi tehnologii de fabricaţie a produselor industriale, cercetarea şi dezvoltarea tehnologică ş.a.

Fig.5.1 Exemplu de utilizare a metodei GERT: Un subansamblu al unui produs este fabricat în 4 ore. Controlul tehnic de calitate refuză 25% dintre piesele subansamblului pentru că nu sunt corespunzătoare, sunt deci rebuturi şi trebuie refăcute.

Timpul necesar pentru control este variabil şi este distribuit exponenţial în intervalul de o oră. Refacerea pieselor rebuta necesită 3 ore dar, la controlul acestora sunt refuzate 30%, dintre ele. Piesele care sunt acceptate la primul control şi la cel de-al doilea (al pieselor refăcute) sunt transmise spre finisare, operaţie care necesită 10 ore şi respectiv 14 ore.

Controlul tehnic de calitate respinge 5% din piesele finisate care, deci, trebuie refinisate. Această situaţie poate fi modelată sub forma unei scheme GERT astfel încât să fie rezolvată pentru procentajul aşteptat şi timpul cerut de producerea unui subansamblu bun, corespunzător normelor de calitate.

Cu ajutorul simbolurilor grafice GERT prezentate în figura se întocmeşte schema modelului GERT din figură

A

B

A

B

A

B

A

B

> 2

a. Inceput la inceput (EST)

>3

b. Sfirsit la sfirsit (LST)

> 4

c. Sfirsit la inceput (EFT)

> 8

d. Inceput la sfirsit (LFT)

Activitatea = RDurata = 5

EST = 2

LFT = 8LST = 3

EFT = 4

e. Nomenclatura activitatii


113

Evenimentul intermediar ce rezulta cand dupa a, b, c se produc d sau e

Inceputul evenimentului cu ramificatii care trebuie sa se produca

Sfirsitul evenimentului ce rezulta oricind se produce a sau b

Evenimentul intermediar ce rezulta cand dupa a se produce b sau c

da

a

a

b

b

b

c

ce

Fig.5.2.

Finisare Control 3

a b

c

d e

f

g

h

i

j

Fabricare Control 1 Refacere Refacere

Piese bune

Control 2

Fig.5.3

Activitatea a reprezentării 4 ore de fabricaţie a pieselor unui subansamblu. Rezultatul acestei activităţi este verificat de către controlul tehnic de calitate în urma căruia rezultă următoarele categorii de piese : 75% din piesele fabricate sunt recepţionate ca bune (a) şi trimise spre finisare (c), iar 25% sunt rebutate (b).

Acestea din urmă se întorc pe linia de fabricaţie şi sunt refăcute (d). Controlul le verifică şi rezultă că 30% din ele sunt rebuturi şi trebuie refăcute (e=30%

din 25% rebuturi = 7,5% dn total ) . Piesele bune din lotul refăcut ( f=70% din 25% rebuturi =17,5% din total ) sunt trimise

împreună cu lotul c (c+f=70%+17,5%=87,5% din total ) spre finisare ; efectuarea operaţiei de finisare pentru 60% din piesele acestui (g) necesită 10 ore iar restul de 40 % din piesele (h) necesită 14 ore.

După controlul tehnic de calitate al pieselor finisate rezultă că 5% dintre ele sunt rebuturi (i) şi trebuie trimise spre refacere iar restul sunt piese bune ( j=955 din 87,55=83,125% din totalul pieselor componente ale subansamblului). Timpul pentru ca un lot ”mediu” să parcurgă traseul din schemă poate fi aflat în acelaşi mod în care s-a calculat şi rezultatul final. Rezultatul analizei este îmbogăţit faţă de simplu PERT/CPM, dar şi rezolvarea informatică este mai complexă, în special pentru schemele mari.

Elemente de teoria deciziei

114

CAPITOLUL 6 ELEMENTE DE TEORIA DECIZIEI

Actul de a decide este un atribut al fiinţei umane. Istoria preocupărilor pentru a aşeza procesul decizional pe baze raţionale coincide cu

însăşi istoria societăţii omeneşti, la început manifestându-se în activitatea individuală şi apoi în cele colective.

Se pot găsi elemente în legendă (fondarea Cartaginei), în istoria antică (asediul Siracusei şi intervenţia lui Arhimede) şi în Evul mediu. Marocanul Sidi bel’Abbes es – Sebti, în secolul al XII – lea, a inventat prima maşină cu program înregistrat, utilă predicţiei, şi este precursorul ameliorării optimumului.

Galileo Galilei a reabilitat teoria deciziilor, Pascal şi Fermat au introdus noţiunea de speranţă matematică, Bernoulli a avut preocupări în domeniul deciziilor în condiţii de incertitudine.

Decizia în activitatea managerială se prezintă sub două forme: actul decizional; procesul decizional.

O decizie ia forma unui act decizional dacă se desfăşoară într-o perioadă foarte scurtă de timp. Se referă la situaţii decizionale cu complexitate redusă sau cu caracter repetitiv, când variabilele implicate sunt bine cunoscute de decident. La baza actelor decizionale stau experienţa şi intuiţia managerilor.

Procesul decizional reprezintă ansamblul fazelor prin intermediul cărora se pregăteşte, adoptă, aplică şi evaluează decizia. 6.1. Procesul şi sistemul decizional al întreprinderii

Situaţiile decizionale in cadrul întreprinderii sunt variate şi conduc la procese decizionale eterogene din punct de vedere al parametrilor constructivi şi funcţionali. Acesta este motivul pentru care se impune o abordare analitică a principalelor elemente implicate în procesul decizional.

Principalele elementele care definesc procesul decizional sunt: - decidentul – o persoană sau un grup; - o situaţie complexă ce poate fi rezolvată pe mai multe căi; - variantele (criterii) de rezolvare ale situaţiei; - criteriile de apreciere a variantelor – care precizează punctul de vedere care se ia în considerare în alegerea celei mai bune variante; - rezultatele pentru fiecare variantă de rezolvare în condiţiile date – marchează nivelul cantitativ sau calitativ pentru fiecare variantă; - stările de condiţii obiective, formate din totalitatea condiţiilor interne şi externe ale firmei în care aplică variantele; - obiectivele decidentului ca elemente finale ale procesului de decizie, care pot să constituie atât cauza declanşării deciziei, cât şi efectul aplicării ei.

Pentru ca procesul decizional să fie eficient, decidenţii trebuie să progreseze într-un ritm rapid pentru a face faţă cerinţelor şi situaţiilor dificile generate de transformările survenite în mediul micro şi macroeconomic.

În funcţie de condiţiile din mediul decizional apar situaţii decizionale, care pot să fie: • Certitudine – unui criteriu îi corespunde o singură consecinţă, iar în proces intervin

variabile controlabile, ale căror caracteristici sunt cunoscute şi evoluţia lor poate fi preconizată;

• Risc - unui criteriu îi corespund două sau mai multe consecinţe O parte din variabile sunt necontrolabile şi chiar evoluţia unor variabile controlabile este greu de anticipat, iar fenomenele sunt de natură stohastică şi stările aleatoare;


115

• Incertitudine – probabilitatea de apariţie a consecinţelor nu este cunoscută şi nu poate fi determinată. Există un număr mare de variabile, cu puţine excepţii controlabile;

• Fuzzy –condiţiile obiective în care se desfăşoară procesul decizional şi funcţionarea sistemului nu pot fi descrise precis, fiind caracterizate prin concepte vagi.

În funcţie de stările de condiţii obiective în care se iau deciziile, procesul decizional se poate clasifica astfel:

a) Decizii deterministe (exacte) – consecinţele ataşate criteriilor sunt rezultatul unor calcule exacte;

b) Decizii probabilistice –consecinţele ataşate criteriilor nu au valoare certă, nici constantă, dar se cunoaşte prin mijloace matematice sau statistice evoluţia acestor imperfecţiuni;

c) Decizii apreciative – nu se cunosc probabilităţile de evoluţie a consecinţelor, care însă se apreciază.

Sistemul decizional al întreprinderii reprezintă ansamblul deciziilor adoptate şi aplicate în cadrul său, structurate conform obiectivelor urmărite şi ierarhiei manageriale.

Principalele funcţii ale sistemului decizional sunt: anticiparea şi pregătirea evoluţiei pe termen lung şi mediu a întreprinderii; armonizarea şi direcţionarea deciziilor de natură organizatorică (armonizarea activităţii resursei umane); declanşarea acţiunilor resursei umane al nivelul întreprinderii şi al compartimentelor sale.

Sistemul decizional alături de sistemul informaţional şi sistemul operaţional alcătuiesc sistemul managerial al întreprinderii (fig.6.1).

Fig.6.1

Activitatea desfăşurată în cadrul unei întreprinderi (sistemul managerial) este rezultatul interacţiunii a trei subsisteme . SUBSISTEMUL DECIZIONAL (S.S.D )– are rol de conducere a activităţilor desfăşurate în cadrul unui sistem în vederea realizării obiectivului fixat şi îndeplinirii scopului pentru care a fost creat. SUBSISTEMUL OPERAŢIONAL ( S.S.O.) – are rol de a executa deciziile conducerii folosind metode şi instrumente disponibile. SUBSISTEMUL INFORMAŢIONAL – asigură legătura în ambele sensuri între S.S.D. şi S.S.O. DATA – reprezintă elementele constitutive ale unei informaţii ce sunt supuse unor prelucrări pentru a obţine informaţia. INFORMAŢIA – acumulare cantitativă de date care se ordonează, combină, compară, transmite şi înregistrează.


116

Se poate face o sistematizare a deciziilor după apartenenţa la funcţiile managementului (tabelul 6.1).

Tabelul 6.1

În concepţie cibernetică modelul general privind etapele procesului decizional este prezentat în fig.6.2..

Se cere luata o decizie?

Nu

Da

Se aplica regulade decizieprogramata

Scanarea situatiei interne si externe

Este odecizie de rutina?

Nu

2

3

4

Se monotorizeaza rezultatul

Se genereaza o decizieneprogramata prinmetoda de rezolvare aproblemelor

Da

5

6

Fig.6.2

Eficientizarea procesului decizional reprezintă conceperea şi operaţionalizarea proceselor decizionale sub aspectul definirii conţinutului, a instrumentelor şi metodelor folosite, a modalităţilor de implementare subordonată permanent îndeplinirii unor obiective economice, tehnice, umane şi manageriale precis definite.

Variabilele care o influenţează sunt: potenţialul şi gradul de motivare a personalului, caracteristicile sistemului economic al firmei, parametrii sistemului tehnic şi trăsăturile definitorii ale sistemului managerial al organizaţiei, evoluţia pieţelor, starea economico-socială a regiunii/ţării în care funcţionează firma, strategia şi politicile naţionale şi regionale implicate, gradul de profesionalism al managerilor.

Avantajele eficientizării decizionale sunt: valorificarea superioară a resurselor organizaţiei, creşterea profitabilităţii, sporirea prestigiului firmei.

Desfăşurarea unor limite legate de resursele utilizabile, de complexitatea şi dificultăţile implicate, dovedesc că eficienţa decizională este o realitate în întreprinderilor contemporane.

FUNCŢIA EXEMPLE DE DECIZII

PLANIFICARE Care sunt obiectivele pe termen lung ale firmei Ce strategii rezolvă optimal aceste obiective Care sunt obiectivele pe termen mediu

ORGANIZARE

Câţi subordonaţi trebuie să raporteze direct unui manager Ce grad de centralizare este necesar în organizaţie Cum trebuie să fie proiectate sarcinile

COMANDĂ- COORDONARE

Cum trebuie lucrat cu salariaţii care par a fi slab motivaţi Care este stilul de îndrumare cel mai eficient într-o anumită situaţie Când este momentul potrivit pentru a dezamorsa un conflict

CONTROL

Ce activităţi ale firmei trebuie controlate Cum trebuie efectuat controlul Ce tip de sistem informaţional trebuie să aibă firma


117

6.2. Utilităţi decizionale

Utilitatea decizională exprimă efectul pe care îl urmăreşte decidentul în urma realizării unei anumite consecinţe a variantei alese. Ea reprezintă gradul de satisfacţie pe care îl înregistrează cel care ia o decizie optând pentru o cale de rezolvare a problemei manageriale în raport cu interesele şi obiectivele sale.

Creatorii teoriei utilităţii, care definesc funcţiile, proprietăţile şi modul în care se poate folosi aceasta în procesul decizional, sunt Von Neumann, şi Morgenstern. În lucrarea „Teoria jocurilor şi comportamentul economic”, elaborată în 1944, au formulat o serie de axiome, utilizând conceptele de preferinţă şi indiferenţă, care reprezintă reacţii subiective ale decidentului faţă de variantele între care trebuie să aleagă.

Obiectivele pot fi exprimate cantitativ sau calitativ, în funcţie de posibilitatea de a exprima numeric consecinţele.

De exemplu, considerând problema alegerii unei tehnologii pentru realizarea unui produs industrial şi admiţând două criterii: mărimea profitului şi calitatea produsului, consecinţele variantelor examinate pot fi exprimate cantitativ, pentru primul criteriu (în 109lei), şi calitativ, sub formă de calificativ, pentru al doilea criteriu.

Caracterul obiectivelor influenţează asupra nivelului de subiectivism care intervine în evaluarea utilităţii, calificativele oferind mai puţine informaţii pentru estimarea sa.

Este greu de stabilit o regulă precisă de dependentă între utilităţi şi valorile băneşti. Dacă S este o sumă de bani, iar u(S) este utilitatea ei, există relaţiile:

( )[ ] ( ) ( )SnunSuSnu <<−1 (6.1)

ceea ce exprimă faptul că utilitatea unei sume de bani creşte cu mărimea sumei, însă ritmul său de creştere este descrescător. Utilitatea este dependentă de timp, ea scade cu cât durata de timp până la realizarea consecinţelor este mai mare. Axiomele formulate de Von Neumann, şi Morgenstern sunt:

1. Un decident care compară două variante Vi şi Vj de rezolvare a unei probleme poate exprima una şi numai una din următoarele relaţii:

( ) ( ) ( )jiijji IVVPVVPVV ,, (6.2)

în care P este operatorul logic de preferinţă, iar I – operatorul logic de indiferenţă. 2. Relaţiile de preferinţă sunt tranzitive:

( )ji PVV şi ( ) ( )kikj PVVPVV � (6.3) ( ) ( )ijji PVVPVV ⇔ (6.4)

3. În afara mulţimii { }nVVVV ,,, 21 …= a variantelor simple, decidentul poate lua în considerare şi variante complexe, de tipul:

( ) ji VppVV −+= 1' (6.5)

unde p este probabilitatea utilizării variantei Vi, iar 1-p este probabilitatea realizării variantei Vj.

Se introduc astfel probabilităţile în teoria utilităţii acceptându-se că două variante simple pot alcătui împreună o nouă variantă, denumită mix probabilistic, dacă li se asociază probabilităţi, cu condiţia ca suma probabilităţilor respective să fie egală cu 1.


118

4. Fiind date trei variante V1, V2 şi V3 şi un decident care exprimă relaţia (V1PV2PV3), există un mix V’=[p’V1+(1-p’)V3], astfel încât (V’PV2) şi un alt mix V’’=[p’’V1+(1-p’’)V3], astfel încât (V2PV’’). Deci, folosind două variante (V1 şi V3), se poate construi o infinitate de mixuri probabilistice care variază continuu pe scara preferinţelor între V1 şi V3. 5. Fiind date trei variante V1, V2 şi V3, dacă un decident exprimă relaţia (V1PV2), atunci implicit va exprima şi relaţia [pV1+(1-p)V3]P[pV2+(1-p)V3]. Această axiomă evidenţiază faptul că o variantă V1 fiind preferată alteia V2, şi mixul lui V1 cu o a treia V3 va fi preferat mixului V2 cu V3. Cele cinci axiome prezentate permit să se definească funcţia de utilitate u(V) care asociază fiecărei variante o valoare din mulţimea numerelor reale sub forma (6.6).

U(V):V → R 6.6)

Utilitatea u(Vi) a variantei Vi se determină cunoscând utilităţile u(V1) şi u(V0) a doua variantă între care există relaţia (V1PV0). Admiţând u(V1)=1 şi u(V0)=0 se pot distinge următoarele trei cazuri: I. (V1PViPV0); în acest caz se apreciază probabilitatea p pentru care ViI[pV1=(1-p)V0], cu 0 ≤ p ≤1; rezultă 0 ≤ u(Vi) = p ≤ 1. II. (ViPV1PV0); în această situaţie se calculează probabilitatea q pentru care

V1I[qVi+(1-q)V0], 0 ≤ q ≤1; rezultă ( ) 11 ≥=q

Vu i .

III. (V1PV0PVi); în acest caz se estimează probabilitatea r pentru care V0I[rVi+(1-r)Vi],

0 ≤ r ≤1; şi se va lua ( ) 01

≤−

=r

rVu i .

Pentru a se opera cu funcţia de utilitate trebuie să se exprime următoarele proprietăţi ale acesteia: 1. Două variante decizionale Vi şi Vj se află în relaţia de preferinţă (ViPVj) dacă şi numai dacă u(Vi) > u(Vj). 2. Utilitatea unui mix probabilistic de forma V’=[pVi+(1-p)Vj] este egală cu speranţa matematică a utilităţilor variantelor mixului:

u(V’) = pu (Vi) + (1-p) u (Vj) (6.7)

3. Proprietăţile anterioare permit o transformare liniară In funcţie de utilitatea de forma:

u (Vj) = a + b (Vi), a ≥ 0, b > 0 (6.8)

Dacă utilitatea evaluează gradul de satisfacţie după mai multe criterii (de exemplu, în cazul produselor – după calitate, după preţ, după serviciile postvânzare) trebuie ca fiecărei variante decizionale Vi să i se atribuie un indicator de utilitate de ansamblu Ui de forma:

njmikuUn

jjiji ,1,,1,

1=== �

=. (6.9)

în care uij este utilitatea corespunzătoare variantei i pentru criteriul Cj, iar kj – coeficientul de importanţă al criteriului Cj. Coeficientul de importanţă poate lua valori astfel:

�=

=≤≤n

jjj kk

11;10 (6.10)


119

Valorile acestor coeficienţi se pot stabili cu relaţia:

,,121;

2 2

2

21

21

1 njjja

akk

j jjj

jjj

jj ====��

� (6.11)

în care aj1j2 sunt elementele unei matrice pătrate, în care liniile sunt numerotate cu j1 şi coloanele cu j2, atât pe linii cât şi pe coloane figurând aceleaşi criterii Cj. Pentru a stabili elementele aj1j2 se poate utiliza relaţia:

��

��

�

=

restinCdecattimpormaiesteCdaca

CcatimpordefellaesteCdacaa jj

jj

jj

,0tan,2

tan,1

21

21

21 (6.12)

În unele cazuri funcţia utilităţii nu poate fi apreciată ca liniară, fiind considerată aşa cum rezultă din aprecierile subiective ale decidenţilor, în funcţie de factura lor psihică (optimişti, pesimişti) şi de impactul riscurilor. Exemplul 6.1: O firmă care fabrică ascensoare şi scări rulante trebuie să opteze pentru cea mai bună variantă de asimilare în fabricaţie din trei posibilităţi V1, V2 şi V3, caracterizate sumar prin datele din tab.6.1 unde V1 reprezintă asimilarea pe bază de componente din ţară, V2 – pe bază de elemente importate din Italia, iar V3 pe bază de import din Germania. Se iau în considerare trei criterii: C1 – costul, C2 – fiabilitatea, iar C3 – efortul valutar necesar. Tabelul 6.1

Criteriul / Varianta

C1 C2 C3

V1 1 2 scăzut V2 1,5 2,5 mediu V3 1,2 2,3 ridicat

Criteriului C3 i se asociază notele 10, 8, respectiv 5. Soluţia optimă se alege pe baza relaţiei 6.9. Pentru a determina coeficienţii de importanţă asociaţi criteriilor se alcătuieşte matricea A, ale cărei elemente se fixează de către un specialist (tab.6.2) Tabelul 6.2

01 220

10

21

A =

Rezultă coeficienţii de importanţă:

91;

95;

93

321 === kkk

Se determină utilităţile uij pentru fiecare variantă Vi şi criteriu Cj. Pentru criteriul cost, pe baza datelor din coloana 1 a matricei din tab.6.2, se poate scrie

relaţia:(V1PV3PV2)


120

Se atribuie valorile 1 şi 0 unităţii variantelor extreme din relaţia de preferinţă respectiv: u(V1)=1;u (V2) = 0

Se formează un mix probabilistic QV1 + (1-p)V2 şi se scrie relaţia de indiferenţă între V3 şi acest mix : V3I[pV1 + (1-p) V2] Aplicând proprietatea I a funcţiei de utilitate rezultă: u (V3)1 = p Valoarea lui p se calculează utilizând relaţia de liniaritate a funcţiei de utilitate, prin interpolare (fig.6.3)

minmax

max

XXXXp i

−−

=

în care Xmax = 1,5 şi Xmin = 1

( )1353

15,12,15,1 Vup ==

−−=

X

Xmax

1,2

0 3/5 1

Xmin

u(V)

Fig.6.3

Reprezentarea din fig.6.3 corespunde pentru criteriile la care utilitatea este invers proporţională cu valoarea lor numerică (exemplu – costul). Pentru criteriul efort valutar, rezultând:

( ) ( ) ( )52;0;1 323331 === VuVuVu

Pentru criteriul fiabilitate, care are valoarea direct proporţională cu utilitatea, se aplică formula de interpolare

min

min

max XXXX

p i

−−

=

Utilităţile variantelor sunt:

( ) ( ) ( )53;0;1 232122 === VuVuVu

Se calculează utilităţile globale Ui pe baza relaţiei

;1580

91

53

95

53

93

;53

52

911

950

93

;941

910

951

93

3

2

1

=⋅+⋅+⋅=

=⋅+⋅+⋅=

=⋅+⋅+⋅=

U

U

U

Pentru a le compara aducem la acelaşi numitor Ui şi avem relaţia de preferinţă pentru

cele trei variante este (V2 PV3 PV1). Rezultă că varianta optimă este V2, respectiv realizarea ascensorului importând elemente componente din Italia.


121

,454;

4527;

4520

321 === UUU

6.3. Optimizarea deciziilor în condiţii de certitudine

Situaţia de certitudine se caracterizează prin faptul că predomină variabilele controlabile, iar rezultatele obţinute pentru fiecare variantă se pot anticipa uşor.

Tabelul 6.3

Criterii / Variante

C1 ………. Cj ………. Cm

V1 R11 ………. R1j ………. R1m . .

.

. .

. Vi Ri1 ………. Rij ………. Rim . .

.

. .

. .

. Vn Rn1 ………. Rnj ………. Rnm

Matricea decizională din tabelul 6.3 corespunde unei probleme cu n variante decizionale ( )niVi ,1= , m criterii de decizie ( )mjC j ,1= şi conţine rezultatele sau consecinţele decizionale Rij. Se apelează la metode şi tehnici de optimizare a deciziilor multidimensionale care au la bază teoria utilităţii, care permite să se aducă la acelaşi numitor comun consecinţele decizionale exprimate diferit prin transformarea lor în unităţi (tab.6.4). Tabelul 6.4

Criterii / Variante

C1 ………. Cj ………. Cm

V1 u11 ………. u1j ………. u1m . .

.

. .

. Vi ui1 ………. uij ………. uim . .

.

. .

. .

. Vn un1 ………. unj ………. unm

Metoda aditivă Dacă coeficienţii de importanţă ai criteriilor decizionale sunt identici, stabilirea variantei optime, în ipoteza că criteriile sunt independente, se face pe baza relaţiei:

�=

=m

jijiopt uV

1max , (6.13)

respectiv varianta optimă este cea care are cel mai ridicat nivel al sumei unităţilor. 6.3.1. Metoda utilităţilor globale Criteriile de decizie pot să aibă coeficienţi de importanţă diferiţi, stabiliţi în funcţie de: - Situaţia economico–financiară a firmei; ��Specificul economic şi manageriala domeniului în care se integrează problema decizională; - Atitudinea decidentului�faţă de criteriile de decizie;


122

�� Amploarea şi complexitatea mediului înconjurător şi intensitatea influenţei exercitată de acesta asupra firmei şi asupra problemei care trebuie rezolvată.

În această situaţie se determină utilitatea globală pentru fiecare variantă decizională cu relaţia:

�=

=m

jijjgi ukU

1 (6.14)

în care: kj – coeficientul de importanţă al criteriului Cj; uij - utilitatea aferentă variantei i, determinată de criteriul j. Varianta optimă se stabileşte pe baza relaţiei..

giiopt UV max= (6.15)

Metoda are avantaje, legate de simplitatea în utilizare şi alegerea relativ rapidă a variantei optime, dar şi limite, generate de subiectivismul stabilirii coeficienţilor de importanţă ai criteriilor decizionale. 6.3.2. Metoda ELECTRE

Metoda ELECTRE (Elimination et Choix Traduisant la Réalité – metodă de clasament şi alegere în prezenţa unor puncte de vedere multiple) a fost elaborată de Şcoala franceză de management. Ea foloseşte pentru rezolvarea unor probleme decizionale complexe. La baza utilizării acestei metode stă matricea utilităţilor. Etapa I. Se stabilesc indicatorii de concordanţă care evidenţiază măsura în care o variantă Vl surclasează, pe baza valorii criteriilor, o altă variantă Vk, după relaţia:

( ) mklk

kVVC m

jj

Jjj

klc ,1,;,

1

==�

�

=

∈ (6.16)

în care: kj – coeficientul de importanţă al criteriului Cj; Jc – mulţimea indicilor criteriilor concordante, respectiv al criteriilor cărora le corespunde (VlPVk), ul ≥ uk

0 ≤ C(Vl, Vk) ≤ 1 (6.17) Etapa II. Se calculează indicatorii de discordanţă, care arată depăşirea variantei Vl de către Vk utilizând formula:

( ) ( )��

��

�

<−

≥=

kllk

kl

kl uupentruuue

uudacaVVd

,max1,0

, (6.18)

în care e este marja maximă între utilităţile aceluiaşi criteriu; dacă [ ]1,0∈u , atunci e = 1.

( ) 1,0 ≤≤ kl VVd (6.18)


123

Din relaţiile (6.16) şi (6.18) se observă că indicatorii de concordanţă se determină în raport cu coeficienţii de importanţă ai criteriilor, iar indicatorii de discordanţă în raport de utilităţile variantelor care se compară, ceea ce reprezintă o limită a metodei ELECTRE. Etapa III. Determinarea variantei optime se face prin operaţii succesive de surclasare a variantelor cu ajutorul unor relaţii de forma:

( )( ) qVVd

pVVC

kl

kl

≤≥

,,

(6.19)

în care p şi q constituie o pereche de valori ( [ ]1,0, ∈qp ), cu condiţia ca p să fie cât mai apropiat de 1 şi q cât mai aproape de 0. Fiecărei perechi p, q i se asociază un graf G(p, q). Prin scăderea pragului p şi creşterea pragului q se obţin grafuri succesive având tot mai multe legături între variante, până ce se poate stabili care variantă le surclasează pe toate celelalte. Pentru a elimina volumul mare de muncă pe care îl presupune construirea grafurilor se poate folosi o metodă ELECTRE analitică ce permite stabilirea variantei optime pe baza relaţiei:

( ) ( ) ( ) optkljklj

kii

VVVdVVCP ��

�� − ,max,minmax (6.20)

6.3.3. Metoda LEADER-ului

Metoda LEADER-ului are la bază determinarea variantei dominante în ansamblul soluţiilor pe baza relaţiei:

( ) ( )

optk

iiji

kii

VPaP �= �−1maxmax (6.21)

în care ( )k

iP este puterea de ordinul k a liniei i, iar aij elementul din linia i şi coloana j a matricei M. Matricea M se construieşte pe baza grafurilor relaţiilor de dominanţă – în care variantele sunt noduri, iar arcurile cu săgeţi indică dominanţa şi a punctajului stabilit astfel: ��Dacă soluţia Vl domină varianta Vk, se acordă lui Vl 2 puncte şi lui Vk – 0;

�� Dacă două variante au aceeaşi influenţă una asupra celeilalte, se dă fiecăreia un punct; �� Se consideră că fiecare variantă se autodomină:

�=

=m

jCjMM

1 (6.22)

unde CjM este matricea corespunzătoare criteriului Cj.

Exemplul 6.2 Se analizează mai multe variante de procese tehnologice de obţinere a unui produs (V1, V2, V3, V4). Variantele sunt analizate în funcţie de următoarele criterii:


124

��1�– costul de implementarea a procesul tehnologic (unităţi monetare);

��2�– cheltuieli anuale de mentenanţă (unităţi monetare)

�3�– posibilitatea de automatizare a sistemului de producţie;

�4�– eficienţa de reducere a noncalităţii. În tabelul 6.5. se prezintă performanţele variantelor, corespunzătoare acestor criterii; se observă că unele sunt exprimate cantitativ, iar altele calitativ. Tabelul 6.5


C1 C2 C3 C4

V1 540 360 Medii Bună V2 540 150 Dificile F. bună V3 150 100 Bune Slabă V4 350 200 Dificile F. bună

Pentru stabilirea deciziei optime se utilizează conceptul de utilitate, admiţând o dependenţă liniară intre consecinţe şi utilităţi şi 0 ≤ u ≤ 1. Se alcătuieşte matricea unităţilor (tabelul 6.6) Tabelul 6.6


C1 C2 C3 C4 �

=

4

1jiju

V1 0 0 0,5 0,5 1 V2 0,077 0,807 0 1 1,884 V3 1 1 1 0 3 V4 0,487 0,615 0 1 2,02

Conform Metodei aditive sau Von Neumann – Morgenstern se aplică relaţia 6.14 şi

rezultă:

3max4

1=�

=jiji

u

Varianta optimă este V3. Pentru a aplica Metoda utilităţii globale se acordă criteriilor coeficienţi de importanţă

diferiţi şi C4 va avea coeficientul de importanţă maxim pentru că obiectivul urmărit îl constituie creşterea eficienţei în reducerea noncalităţii. Valorile acestor coeficienţi sunt:

k1 = 3; k2 = 3; k3 = 2; k4 = 7.

În acest caz se aplică relaţiile 6.15 şi 6.16 pe baza datelor din tabelul 6.7 care

constituie utilităţile globale. Tabelul 6.7

Vj / Cj C1 C2 C3 C4 �

=

4

1jijjuk

V1 0 0 1 3,5 4,5 V2 0,231 2,421 0 7 9,652 V3 3 3 2 0 8 V4 1,461 1,845 0 7 10,306


125

306,10max4

1=�

=jijji

uk

Rezultă ca varianta optimă este V4. Pentru a aplica Metoda ELECTRE se calculează indicatorii de concordanţă (tabelul

6.8) şi indicatorii de discordanţă (tabelul 6.9) utilizând relaţiile (6.16), respectiv (6.18) şi utilităţile din tabelul 6.6.

Tabelul 6.8

V1 V 2 V 3 V4

V1

V2

V3

V 4

0,133 0,133

0,867

0,867

0,533 0,533 0,533

0,463 0,8

0 ,467

0,4670,8

C (V L,Vk)

Tabelul 6.9

V 1 V 2 V 3 V 4

V 1

V 2

V 3

V4

0,807 0,615

0,5

0,5

0,5 1

1 0,41

1

10,192

d(V L,Vk)

Stabilirea variantei optime aplicând Metoda LEADER-ului se face pe baza grafurilor

relaţiilor de dominanţă între variante şi a matricei M, care însumând matricele asociate grafurilor corespunzătoare celor patru criterii decizionale considerate. Pe baza relaţiei (6.21), admiţând puterea de ordinul 0 egală cu 1, se calculează pentru fiecare linie puterea de ordinul 1. Dacă apare o situaţie de indecidabilitate, se stabileşte puterea de ordinul 2 ş.a.m.d., până se depărtează varianta optimă. Dacă soluţia dominantă nu se poate determina, se acceptă oricare dintre variante. ( ) ( ) ( ) ( ) 16;22;16;10 1

41

31

21

1 ==== PPPP Se alege varianta optimă V3.

În urma aplicării celor patru metode rezultă ca optimă decizia privind varianta V3.


126

Grafurile relaţiilor de dominanţă Matricile asociate între variante fiecărui graf

V1 V2

V4 V3

12

0

22

0 0

0

122

01

021

MC1 =

GC1

V1 V2

V4 V3

12

0

22

0 0

0

120

01

221

MC2 =

GC2

V1 V2

V4 V3

10

2

20

0 2

0

121

01

121

MC3 =

GC3

V1 V2

V4 V3

12

0

02

2 0

2

101

21

101

MC4 =

GC4

46

2

66

2 2

2

464

24

464

M =


127

6.4. Optimizarea deciziilor în condiţii de risc Existenţa mai multe stări de condiţii obiective pentru care se cunosc probabilităţile de realizare, procesul de decizie se desfăşoară în condiţii de risc. Asemenea probleme stohastice apar frecvent în anumite domenii de activitate: producţie, cercetare-dezvoltare, marketing ş.a. Stările de condiţii obiective nu sunt controlabile de către decident, dar acesta caută să aleagă căi cu evenimente care minimizează pericolele. Astfel, el minimizează riscul la care se poate expune, fără a-l elimina complet, dacă fenomenele sunt aleatoare. Pentru aceasta se procedează la o analiză probabilistică de evaluare şi selecţie decizională. Metodele cantitative întrebuinţate cel mai des în acest scop sunt metoda speranţei matematice şi tehnica arborelui decizional. Metoda speranţei matematice Metoda speranţei matematice foloseşte modelul aditiv pornind de la o matrice, cu cel puţin două stări de condiţii obiective, anumite stări ale naturii (care nu sunt controlabile de către decident), şi care cuprinde utilităţile consecinţelor (rezultatelor) pentru fiecare variantă, criteriu sau stare a naturii. Fie o mulţime de stări ale naturii (N1, …,Nk,…,Np) pentru care se cunosc probabilităţile pk care satisfac condiţiile (6.23).

�=

=≤≤p

kkk pp

11,10 (6.23)

Matricea utilităţilor corespunzătoare celor m variante, n criterii şi p stări ale naturii se prezintă în tabelul 6.10, care corespunde şi utilităţile sinteză. Tab.6.10

STĂRI ALE NATURII - PROBABILITĂŢI N1,p1 Np,pp

Criterii / Variante

X1 … Xn … U1 X1 … Xn … Up V1

Vi

Vm

u111 … u1n1

ui11 … uin1

um11 … umn1

U11

Ui1

Um1

…

…

…

u11p … u1np

ui1p … uinp

um1p … umnp

U1p

Uip

Ump

Utilitatea sinteză a variantei decizionale i în starea de condiţii obiective k se determină cu relaţia:

pkmiUUn

kijkki ,1,,1,

1=== �

= (6.24)

Speranţa matematică a rezultatelor în varianta Vi va fi:

( ) �=

=p

kkiki pUVE

1

(6.25)


128

Dacă rezultatele (consecinţele) sunt exprimate prin efecte economice, cum sunt: profitul, încasările din vânzări, productivitatea, varianta optimă va fi cea care satisface condiţia (6.26).

( ) optiiVVE �max (6.26)

Dacă rezultatele exprimă eforturi, de exemplu: investiţii, cheltuieli de exploatare, consumuri specifice, varianta optimă se determină din condiţia de minimizare a riscului.

( ) optiiVVE �min (6.27)

Exemplul 6.3

1. O instalaţie energetică compusă din două părţi A şi B se defectează aleatoriu. Există trei variante de mentenanţă corectivă pentru această instalaţie. V1 – Când se produce defectarea, să se abordeze mai întâi subsistemul A; dacă defectul este găsit în A costul mentenanţei se consideră nul, iar dacă defectul este în B mentenanţa va costa 2000 $. V2 – Când se produce defecţiunea se abordează la început partea B; dacă defectul se găseşte în B se consideră că mentenanţa are cost zero, iar dacă defectul este în A costul mentenanţei va fi 4000 $. V3 – Se apelează la o firmă de service specializată, costul fiind 1000 $. Se cere să se stabilească varianta optimă. Se calculează speranţele matematice ale costurilor pentru fiecare variantă, admiţând că:

�=

−=�=2

111

jABj ppp ,

în care pj este probabilitatea ca defectul să fie în partea j.

( ) �=

=2

1jjiji pMVE

în care E(Vi) este speranţa matematică a costurilor corespunzătoare variantei Vi; Mij-costul mentenanţei dacă se aplică varianta Vi şi defectul este în partea j.

( ) ( )( ) ( )( ) ;$1000

;4000104000;20002000120000

3

2

1

==−+⋅=

−=−+⋅=

VEpppVE

pppVE

AAA

AAA

Cele trei speranţe matematice se pot reprezenta grafic, în funcţie de pA (fig.)

E(V3)

E(V2)

E(V1)

0,25 0,5 0,75

1

234

103$

E(Vi)

pA0

Fig.6.3


129

Se observă că soluţia optimă se găseşte în trapezul haşurat, mărginit superior de costurile minime asociate celor trei variante. Se constată că la valori diferite ale lui pA corespunde decizii diferite, respectiv:

0 ≤ pA ≤ 0,25 – decizia optimă este V2; 0,25 < pA ≤ 0,5 – decizia optimă este V3; 0,25 < pA ≤ 1 – decizia optimă este V1.

Deci rezolvarea problemei depinde de valoarea probabilităţii pA. De exemplu, dacă s-a stabilit că pA = 0,3 atunci decizia optimă este să se încheie contract cu firma de service.

Modelul arborelui de decizie

Modelul arborelui de decizie se aplică în probleme de decizii în condiţii de risc, când abordarea chestiunii complexe se face pe un interval mai lung de timp, deci este necesară o succesiune de decizii.

Reprezentarea grafică a succesiunii proceselor decizionale se face printr-un arbore de decizie, în care ramurile reprezintă evenimente, iar nodurile sunt punctele în care apar diversele variante. Nodurile pot să fie de decizie (O) – în care decidentul efectuează alegerea - şi noduri ( ) în care responsabilitatea alegerii uneia dintre variantele posibile revine naturii, adică unor factori independenţi de cel care ia hotărârea. Principiile care stau la baza aplicării modelului arborelui decizional sunt: - Valoarea fiecărui nod în care natura efectuează alegerea depinde numai de evenimentele viitoare(nu şi de deciziile precedente); �� n nodurile în care alegerea revine decidentului este preferată acea decizie pentru care următorul nod la care se ajunge este cel mai avantajos; valoarea nodului actual se obţine scăzând costul deplasării din valoarea nodului următor; ��Din proprietăţile exprimate anterior rezultă că evaluarea întregului sistem şi determinarea deciziei optime se poate face începând cu nodurile finale şi efectuând deplasarea în sens invers celui urmat de procesul real, până se ajunge la nodul iniţial.

Acest procedeu de evaluare a consecinţelor fiecărei variante, cunoscut sub numele de „rollback” simplifică tratarea problemelor decizionale complexe, deoarece de fiecare dată se ia în considerare doar setul de factori sau evenimente implicate într-o singură fază a procesului decizional şi nu întreaga succesiune a acestora.

Avantajele folosirii acestui model în adoptarea deciziilor sunt: prevederea implicaţiilor unui set de decizii strategice succesive eşalonate de-a lungul unei perioade lungi de timp (uneori câţiva ani); probabilitatea sporită de a lua decizii fundamentale în condiţii deosebit de complexe.

Dezavantajele sunt legate de numărul relativ scăzut de variante care se pot lua în considerare şi de faptul că erori mici în determinarea probabilităţilor de producere a evenimentelor aleatoare pot să aibă mari repercursiuni asupra valorilor finale cu consecinţe asupra exactităţii anticipării rezultatelor economice. Pentru a micşora influenţa dezavantajelor prezentate se impune studierea aprofundată de către specialişti şi manageri a factorilor care condiţionează situaţia decizională.

Este necesar să se alcătuiască o echipă de folosire a arborelui decizional, dirijată de un manager de nivel superior şi formată din: specialişti în elaborarea strategiei şi politicii globale a firmei, economişti profilaţi pe studiul pieţei, specialişti în investiţii, tehnologi, economişti specializaţi în probleme de costuri şi preţuri, matematicieni şi informaticieni.

Modelul arborelui de decizie se utilizează în domenii ca: definirea deciziilor strategice ale firmei, stabilirea unui program de cercetare – dezvoltare, lansarea unui nou produs.


130


131

BIBLIOGRAFIE

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

Armeanu A. – Bazele ingineriei şi managementului sistemelor de producţie, Note

de curs, UPB, 1999

Bărbatu Gh.I., Ionescu V. – Cercetarea operaţională în întreprinderile industriale,

Ed.Tehnică, Bucureşti 1981;

Blajină Ovidiu. – Programarea liniară, Ed. Printech 1999;

Blajină Ovidiu. – Cercetări operaţionale, Ed.Printech 2001

Boldur-Lăţescu G., Săcuiu I., Ţigănescu E. – Cercetare operaţională cu aplicaţii în

economie, Ed. Didactică şi Pedagogică, Bucureşti, 1979;

Ciobanu Gh., Nica V., Mustaţă F., Mărăcine V.- Cercetări operaţionale cu aplicaţii

în economie, Ed. MatrixRom, Bucureşti, 1996;

Ciobanu Gh., Nica V., Mustaţă F., Mărăcine V., Mitruţ D. – Cercetări

Operaţionale, Ed. MatrixRom, Bucureşti, 2002;

Dumitrescu M., Niculescu C. – Teoria deciziei şi Cercetare Operaţională, Ed.

Niculescu, Bucureşti, 2001;

Dijmărescu I. – Bazele Managementului, Ed. Didactică şi Pedagogică, Bucureşti,

1995

Hillier F., Limberman G., Introduction to operational research, McGraw-Hill

Publishing Company, New-York, 1990

Ionescu H., Dinescu C., Săvulescu B. – Probleme ale cercetării operaţionale - Ed.

Didactică şi Pedagogică, Bucureşti, 1972;

Kaufmann A., Desbazeille G., Metoda Drumului Critic, Ed.Tehnică, Bucureşti

1971;

Kaufmann A, Metode şi modele ale cercetării operaţionale, Ed,Ştiinţifică,

Bucureşti, 1967

Neagu C. – Modele de programare şi conducere a proceselor economice – EDP-

RA, Bucureşti, 1995.

Neagu C., Melnic L., Roşu M. – Managementul operaţional al proiectelor – Ed

Bren, Bucureşti, 2002;

Nica V., Ciobanu Gh., Mustaţă F., Mărăcine V. - Cercetări Operaţionale, Ed.

MatrixRom, Bucureşti 1998;

Nădejde I., Zidăroiu C. – Probleme de cercetare operaţională – Ed. Academiei,

Bucureşti, 1971;

Rusu Elisabeta, Fundamentarea deciziilor în management , Ed.Junimea , Iaşi, 2000

Cercetari Operationale

Documents

Transcript of Cercetari Operationale