CERCETĂRI OPERAŢIONALE1. Etapele principale ale cercetării operaţionale. Obiectivele şi criteriile de

eficienţă a problemelor decizionale.Cercetarea operationala reprezinta ansamblul de principii, metode si mijloace destinate

elaborarii de modele matematice ale fenomenelor si proceselor manageriale, în vederea adoptarii unor decizii care sa contribuie la modificarea acestora în directia dorita de manager. Cercetarea operationala se bazeaza pe aplicarea combinata a principiilor analizei stiintifice, logicii si interpretarii în scopul solutionarii unor probleme cantitative care se pun la adoptarea deciziilor manageriale.Principalele obiective ale cercetarii operationale sunt urmatoarele: a) fundamentarea cantitativa a deciziilor; b) compararea variantelor decizionale posibile de organizare a operatiilor; c) evaluarea influentelor probabile ale diferi-tilor factori asupra rezultatelor societatii comerciale.Cercetarea operationala are urmatoarele etape: a) definirea problemei; b) conceperea modelului matematic al fenomenului sau operatiei; c) analiza modelului si formularea deciziei; d) verificarea adecvarii modelului la feno-men sau operatie si analiza calitatii deciziei; e) corectarea modelului si a deciziei; f) aplicarea deciziei si urmarirea realizarii ei.Printre cele mai frecvente si semnificative teme abordate de cercetarea operationala mentionam: a) alege-rea amplasamentului unei sectii, uzine sau fabrici; b) sta-bilirea metodelor optime de distributie-depozitare; c) operatii de echilibrare a liniilor de productie în flux; d) prognoze privind forta de munca si capacitatile de productie; e) proiectarea sistemelor financiar-contabile si de control financiar; f) alegerea tematicii de cercetare-dezvoltare si altele.

2. Clasificarea problemelor cercetării operaţionale: probleme decizionale în condiţii de certitudine, risc şi incertitudine. Regulile decizionale în condiţii de incertitudine şi risc.

Clasificarea problemelor cercetării operaţionale:1. După conţinut

Planul optim de producţie Problema de transport Problema stocurilor Planificarea şi gestiunea proiectelor Teoria grafurilor

2. După numărul de scopuri puse Cu un singur scop (unicriteriale) Cu mai multe scopuri (multicriteriale)

3. După informaţia disponibilă Probleme decizionale în condiţii de certitudine Probleme decizionale în condiţii de risc Probleme decizionale în condiţii de incertitudine

Regulile decizionale în condiţii de incertitudine:MaxMax

a.

b.

MaxMin

a.

1

b.

Hurwicz

a. 0≤α≤1

b.LaPlace

a.

b.Savage(MinMax)

a.

b.Regulile decizionale în condiţii de risc:

Regula maximizării profitului mediu sperat

a.

b.Regula minimizării regretului mediu

a.

b.3. Modele liniare ale problemelor de cercetare operaţională: exemple de

probleme, modele matematice ale lor.Structura modelului general de programare liniară se constituie în primul rând prin mulţimea de

activităţi {A1, A2, ... An} care compun sistemul economic analizat, mulţimea de resurse utilizate {R1, R2, ... Rm} precum şi prin relaţiile tehnico-economice dintre acestea. Legătura dintre activităţi şi resurse este determinată de tehnologia de fabricaţie corespunzătoare fiecărei activităţi A j (j=1,...,n) şi poate fi caracterizată numeric prin vectorul coloană a(j) de componente (a1j, a2j, ... amj). Elementele {aij, i = 1,...,m; j = 1,...,n} se numesc coeficienţi tehnici sau coeficienţi de consum specific şi arată ce cantitate din resursa Ri se consumă pentru producerea unei unităţi din produsul (serviciul) P j (ca rezultat al activităţii Aj). Toate "tehnologiile" de fabricaţie definite de vectorii coloană a (j) se pot organiza într-o matrice A cu m linii şi n coloane; fiecare linie se referă la o resursă Ri (i = 1,...,m) şi fiecare coloană se referă la o activitate Aj (j = 1,...,n).

Notând cu xj (j = 1,...,n) rezultatul activităţii Aj într-o perioadă dată şi cu bi (i = 1,...,m) cantităţile disponibile din resursele Ri (i = 1,...,m), se pot scrie matematic următoarele restricţii tehnico-economice:

(1) sau Ax b

2

unde A = ; x = şi b =

Modelul matematic pentru problema linară.xj – cantitatea de producţie de tip j

3

P1 P2 … Pn Disp.R1 a11 a12 … a1n b1R2 a21 a22 … a2n b2… … … … … …Rm am1 am2 … amn bm

c1 c2 … cn

4. Probleme de programare liniară (PPL); formele de prezentare. Noţiune de soluţie (soluţie admisibilă; soluţie de bază; soluţie de reper şi soluţie optimă).

Dacă într-o problemă de programare matematică funcţia obiectiv f şi funcţiile gi, din restricţiile 1.2, sunt funcţii liniare atunci problema se numeşte problemă de programare liniară. O problemă de programare liniară este, deci, un caz particular al problemelor de programare matematică şi, ţinând cont de forma oricărei funcţii liniare, rezultă că forma generală a oricărei probleme de programare liniară este:Formele de prezentare:

1. Forma simetricăa) Pentru forma de maxim

4

b) Pentru forma de minim

2. Forma standard

3. Forma canonicăO ppl este în forma canonică dacă în fiecare restricţie a modelului din forma standard există cîte o variabilă cu coef. 1 iar în celelalte restricţii aceasta are coef. 0.

În teoria programării matematice se folosesc, pentru claritatea şi simplitatea expunerii, următoarele noţiuni:

soluţie a problemei de optimizare

= un vector x Rn care verifică restricţiile 1.2

soluţie admisibilă a problemei de optimizare

= un vector x Rn care verifică restricţiile 1.2 şi 1.3 o soluţie care verifică restricţiile 1.3

soluţie optimă a problemei de optimizare

= un vector x Rn care verifică restricţiile 1.2 şi 1.3 şi optimizează funcţia obiectiv pe mulţimea tuturor vectorilor cu această proprietate

o soluţie care verifică restricţiile 1.3 şi optimizează funcţia obiectiv pe mulţimea tuturor soluţiilor cu această proprietate

o soluţie admisibilă care optimizează funcţia obiectiv pe mulţimea soluţiilor admisibile

5

5. Proprietăţile fundamentale ale PPL( teoremele principale). Interpretarea geometrică a PPL. Metoda grafică de soluţionare a PPL.Greutatea găsirii soluţiei problemei constă în imensitatea numărului de soluţiilor posibile ale

sistemului şi în respectarea condiţiei de nenegativitate a celor printre care căutăm extremul dorit al funcţiei f. Este natural ca primele încercări în rezolvare să caute în primul rând o limitare cât mai puternică a locului în care căutăm. Pe baza unor reprezentări geometrice ale problemei au fost descoperite următoarele proprietăţi ale problemei, care poartă denumirea de teoreme fundamentale ale programării liniare:

Teorema 1. Dacă problema de programare liniară are soluţii admisibile atunci are şi soluţii de bază admisibile.

Teorema 2. Dacă problema de programare liniară are soluţii optime atunci are şi soluţii optime de bază.

Teorema 3. Mulţimea soluţiilor admisibile (optime) este închisă şi convexă. Dacă este şi mărginită atunci punctele extremale ale acesteia sunt chiar soluţiile admisibile (optime) de bază ale problemei.

Cele două teoreme realizează efectiv trecerea către o problemă rezolvabilă pe calculator. Într-adevăr, deoarece o bază este un minor de ordinul m al matricii A şi unei baze îi corespunde o unică soluţie de bază rezultă că sunt cel mult C soluţii de bază, adică un număr finit. În acest moment s-ar părea că nu avem decât să lăsăm calculatorul să calculeze toate soluţiile de bază şi valorile funcţiei obiectiv în cele admisibile găsind-o prin comparare pe cea care dă minimul sau maximul funcţiei printre acestea.

Ex:

Pas 1.

DVA: OABCD

6. Metoda simplex de soluţionare a PPL. Algoritmul simplex pleacă de la presupunerea că dispunem deja de o soluţie admisibilă de bază xB, corespunzătoare unei baze B. De asemenea, presupunem că am rezolvat sistemul A⋅x = b folosind această bază, rezultând astfel variabilele principale în funcţie de cele secundare:

6

DO 94

2

6

x2

x1

B

C

A

Exemplu: Fie problema de programare liniară:

pentru care ştim că baza formată din coloanele a1, a2, a3 este admisibilă. Pentru rezolvare vom aduce problema la forma standard de maxim introducând variabilele de abatere x7, x8, x9 obţinând:

Vom aşeza în tabelul simplex variabilele în ordinea indicilor şi vom avea:

c = , A = , B = , cB =

7

vom calcula matricea B-1 = şi pe baza acesteia soluţia de bază

xB = B-1 * b = şi

matricea B-1A = care se trec în tabelul

simplex:

3 2 1 4 3 5 0 0 0

cB xB xB x1 x2 x3 x4 x5 x6 x7 x8 x9

3

2

1

x1

x2

x3

1

2

3

şi în final se vor calcula valoarea funcţiei obiectiv în această soluţie, zj şi j:

3 2 1 4 3 5 0 0 0

cB xB xB x1 x2 x3 x4 x5 x6 x7 x8 x9

3

2

1

x1

x2

x3

1

2

3

10

Din tabel se observă că există j < 0, aceştia fiind 4, 5, 6, 8 iar minimul lor este 6.

8

Observaţie Dacă vom căuta acel j care dă cea mai bună îmbunătăţire vom avea de găsit acel j dintre cei

negativi pentru care se obţine şi deci de calculat:

= =

= =

= =

= =

şi în final max ( , , , ) = şi corespunde tot lui 6.

În concluzie, soluţia actuală nu este optimă şi soluţia cea mai bună dintre cele posibile ca succesoare va avea variabila x6 printre cele principale.

Analizând coloana a6 observăm că există componente strict pozitive (de fapt, în acest caz sunt chiar toate) şi calculăm pentru acestea rapoartele i obţinând:

1 = = , 2 = = 14, 3 = =

deci minimul corespunde variabilei x1 şi aceasta este cea care va ieşi din bază. În cest moment cunoaştem noua bază şi vom construi tabelul simplex pe baza regulilor de calcul de la pasul 4:

1. pivotul este a16 =

4. de exemplu, pentru elementul de pe poziţia a34 avem dreptunghiul:

şi noua valoare de pe această poziţie va fi: = –1

În final, tabelul corespunzător noii baze va fi:

3 2 1 4 3 5 0 0 0

cB xB xB x1 x2 x3 x4 x5 x6 x7 x8 x9

9

5

2

1

x6

x2

x3

Continuând algoritmul vom găsi tabelele:

3 2 1 4 3 5 0 0 0

cB xB xB x1 x2 x3 x4 x5 x6 x7 x8 x9

5

2

0

x6

x2

x8

3 2 1 4 3 5 0 0 0

cB xB xB x1 x2 x3 x4 x5 x6 x7 x8 x9

5

3

0

x6

x5

x8

5

1

2

28

Ultimul tabel conţine soluţia optimă, deoarece toţi j 0. Deoarece nu mai există nici un j = 0 în afara celor din bază rezultă că soluţia optimă este unică.

7. Dualitatea în programarea liniară. Teoremele fundamentale ale teoriei dualităţii.

În principiu, oricărei probleme de programare liniară i se asociază o alta, numită duala sa şi în esenţă teoria dualităţii constă în studiul relaţiilor dintre cele două probleme. Fireşte, construcţia problemei duale depinde nemijlocit de structura problemei iniţiale denumită şi problema primală. Întotdeauna sensul optimizării în cele două probleme este diferit: dacă în primală funcţia obiectiv se maximizează (se minimizează) în duală funcţia obiectiv se minimizează (se maximizează). Studiul şi interpretarea economică a problemei duale aduc informaţii suplimentare în analiza proceselor economice şi în fundamentarea deciziilor.

10

Pentru a conferi construcţiei problemei duale maxima generalitate vom slăbi condiţia de nenegativitate impusă tuturor variabilelor , admiţând căunele din ele nu pot lua decât valori nepozitive (≤ 0) în timp ce altele pot lua orice valoare reală.Cu această observaţie duala unei probleme de programare liniară cu m restricţii şi n variabile se construieşte după următoarele reguli:1) Dacă în primală funcţia obiectiv se maximizează (respectiv se minimizează) în problema duală funcţia obiectiv se minimizează (respectiv se maximizează).2) Restricţiei de rang i , i=1,...,m din primală îi corespunde în duală o variabilă ui; dacă restricţia primală este o inegalitate concordantă (respectiv neconcordantă, respectiv o egalitate) variabila duală asociată este nenegativă (≥0), ( respectiv nepozitivă (≤0), respectiv fără restricţie de semn).3) Variabilei xj , j=1,...,n din problema primală îi corespunde în duală restricţia de rang j. Membrul stâng al acestei restricţii este o combinaţie liniară a variabilelor duale ui realizată cu coeficienţii variabilei xj din toate restricţiile primalei (aceştia sunt aij, i=1,...,m). Termenul său liber este coeficientul cj al lui xj din funcţia obiectiv primală. În fine, dacă variabila primală xj este nenegativă (respectiv nepozitivă, respectiv fără restricţie de semn) restricţia duală asociată va fi o inegalitate concordantă (respectiv neconcordantă, respectiv o egalitate).4) Coeficienţii funcţiei obiectiv ai problemei duale sunt termenii liberi bi ai restricţiilor problemei primale.Teorema (Teorema fundamentală a dualităţii) Pentru un cuplu de probleme în dualitate una şi numai una din următoarele situaţii este posibilă:1) Ambele probleme au soluţii admisibile; atunci ambele au soluţii optime şi valorile optime ale funcţiilor obiectiv coincid.2) Numai una din probleme are soluţii admisibile, iar cealaltă nu are; atunci problema compatibilă are optim infinit.3) Nici una din probleme nu are soluţii admisibile.

8. Interpretarea economică a dualităţii în programarea liniară. Preţurile umbră ale factorilor de producţie şi rolul lor în analiza modelelor liniare.

Considerăm o întreprindere care produce bunurile G1,G2,...,Gm la preţurile c1,c2,...,cn folosind pentru aceasta mai multe resurse R1,R2,...,Rm disponibile în cantităţile limitate b1,b2,...,bm. Consumurile specifice de resurse pentru unul sau altul din bunurile realizabile de către firmă sunt specificate în matricea:

Obiectivul firmei este maximizarea veniturilor rezultate din vânzarea bunurilor produse. În ipotezele de liniaritate uzuale, programul liniar pentru determinarea combinaţiei optime de bunuri este:

11

Să notăm cu combinaţia de bunuri care aduce firmei venitul maxim : Dacă admitem că singura posibilitate a firmei de a obţine venitul V* constă în transformarea resurselor disponibile în bunuri conform programului x* şi vânzarea acestora este natural să ne întrebăm care este contribuţia fiecărei resurse în parte la formarea acestui venit.La baza discuţiei vom pune aceleaşi ipoteze de liniaritate care ne-au condus la modelul matematic (P) şi anume:• contribuţia unei resurse la venitul maxim al firmei este - pînă la o anumită limită - direct proporţională cu cantitatea disponibilă;• nivelul contribuţiei unei resurse nu este condiţionat de celelalte resurse , ci numai de cantitatea în care ea se află disponibilă.

12

2) Relaţia (2.4.1) rescrisă în forma f(x*) = g(u*), coroborată cu teorema de dualitate 2.3.1, ne arată că u* este chiar soluţia optimă a problemei duale Q.Astfel, am găsit un conţinut economic coerent variabilelor duale u1, u2,..., um din problema duală (Q). Ele reprezintă nişte valori băneşti asociate la câte o unitate din fiecare resursă disponibilă a firmei şi exprimă aportul unitar al fiecărei resurse la formarea venitului maxim. Strict dimensional, variabilele u1, u2,..., um au semnificaţia unor preţuri ataşate resurselor. Totuşi aceste preţuri nu au nimic comun cu valoarea intrinsecă a resurselor ci - aşa cum a rezultat din interpretarea dată - reflectă numai măsura participării lor la formarea venituluimaxim. Tocmai pentru a preveni identificarea lor cu preţurile reale ale resurselor, în literatura de specialitate, aceste entităţi au fost denumite preţuri umbră (shadow prices).

13