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ă 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.

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).

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;- î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”.

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.

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.

Probleme de programare liniara. Exemple. Algoritmul simplex.

 Problema planului optim de productie

Notatii:

•      produsele care se fabrica sau se consuma in ateliere,

•     atelierele de productie pentru produsele  ,

•     cantitatea produsa in unitatea de timp, din produsul   in atelierul  ,

astfel:   produce in unitatea de timp cantitatea   din produsul 

;   nu produce si nu consuma produsul  ;     consuma in

unitatea de timp cantitatea (- ) din produsul  ,

•     restrictii de resurse: productia minima  , (daca  ), respectiv

consumul maxim   (daca  ),

•     timpul de functionare al atelierului  ,

•     beneficiul obtinut prin functionarea lui   in unitatea de timp.

Modelul matematic: (pentru determinarea planului optim de productie)

 ;  .

Notatii:

 costul functionarii atelierului   in unitatea de timp.

;  .

Algoritmul simplex: enunt algoritm simplex, tabel simplex si transformarea sa

Notatii:

 sistem de ecuatii liniare,  , 

           =  matrice patratica nesingulara extrasa din A

           = vectorul variabilelor corespunzatoare coloanelor lui B

         S = partea din matricea A ce mai ramane dupa extragerea lui B,  ,

    ,      = functia obiectiv .

Definitii:

1. Numim problema de programare liniara sub forma standard problema:

 ,  .                                                                                     (1.2)

2.   se numeste solutie de baza daca  ,  .

3.   se numeste solutie nedegenerata daca

 solutie de baza si   are   componente nenule.

4.   se numeste solutie degenerata daca

 solutie de baza si   are si componente nule.

5.   se numeste solutie admisibila sau program daca   si  .

6.   se numeste program de baza daca   este solutie de baza si   este program (pentru problema de programare liniara sub forma standard).

7.   se numeste solutie optima sau program optim  daca:   finit,  .

 

Notatii:

          ,  .

           ( ,  problema are optim infinit).

        

Teorema 1:

i)      Daca problema de programare liniara sub forma standard are un program atunci are cel putin un program de baza.

ii)     Daca problema de programare liniara sub forma standard are un program optim, atunci are un program de baza optim.

 

Observatii:

1.      Se poate determina solutia problemei de programare liniara sub forma standard astfel:

- pentru toate bazele B din matricea A calculam solutia  ;

- se retin programele de baza  ;

- se alege programul de baza care conduce la valoarea optima a functiei obiectiv.

 

Notatii

         B baza formata cu coloane   ale matricei A cu  ; S a.i.  ,

         B multimea indicilor variabilelor de baza;

         S multimea indicilor variabilelor secundare; 

           vectorul unitate (avand componenta j egala cu 1)

          ,  ,   coloana j a matricei A

          ,  

           numiti  coeficienti de cost redus (coeficienti de cost relativ).

         Daca alegem baza B astfel incat  , sistemul de ecuatii   se

scrie  , iar     .

Daca   atunci   si  .

2.      Teorema 2:

i)      Daca   ( ) programul de baza corespunzator bazei B (

, ) este optim.

ii)     Daca   astfel incat  (adica  ) atunci programul asociat bazei B nu este optim (cu exceptia cazului in care programul este degenerat) si poate fi imbunatatit

daca  .

iii)    Daca   astfel incat  si daca   atunci problema are optim infinit.

iv)    Daca   astfel incat   si   atunci  poate creste pana la

valoarea:   pentru care se obtine un nou program de baza, asociat bazei 

, dedusa din B prin inlocuirea coloanei   cu  .

3.      Daca exista mai multi indici k pentru care  (adica  )  se alege acel

indice pentru care    are valoarea cea mai mare, ceea ce asigura, in general, o scadere mai rapida a functiei obiectiv, si conduce la un numar mai mic de iteratii (o iteratie o reprezinta trecerea de la un program de baza  la altul).

         Criteriu de intrare in baza: alege k astfel incat  .

         Criteriu de iesire din baza:   nu este minim pentru  .

Enuntul algoritmului simplex

         Consideram problema de programare liniara sub forma standard (1.2).

Pas0 Se determina o baza B in matricea A, se calculeaza:

          ,  ,  ,   coloana j a matricei A,   .

Pas1 a) Criteriu de intrare in baza:

            1) daca toti   programul este optim. Stop.

            2) daca  , se determina k astfel incat  .

         b) Criteriu de iesire din baza:

            1) daca toti   problema are optim infinit.

            2) daca  , se determina l astfel incat  .

Pas2 Se inlocuieste in baza B vectorul   cu  vectorul  , obtinandu-se baza  . Se

calculeaza  ,  ,  ,   . Se trece la Pas1 inlocuind baza B cu baza  .

 

Observatie:

         Pentru o problema de maximizare:

         

 ,  .

se modifica criteriul de intrare in baza:

            1) daca toti   programul este optim. Stop.

            2) daca  astfel ca , se determina k astfel incat  .

Probleme de programare liniara cu optim infinit

Aplicatie 2:

Observatie: S-a notat cu   cantitatile din produsul  ,  ,  , ,  ce trebuiesc fabricate.

Probleme propuse

1.     max   (maximizarea functiei obiectiv)

,

,

,

   

2.

max   (maximizarea functiei obiectiv)

,

,

,

   

3. Un meniu trebuie sa asigure necesarul de substante   (calorii, proteine, glucide),

cu ajutorul alimentelor   (paine, carne vita, lapte, mere). Cantitatile de

substante   ce se afla la 100g aliment, cantitatile minime necesare organismului din cele trei substante, precum si preturile celor patru alimente sunt trecute in Tabelul 1.:

Necesar

260 170 70 60 30008 20 3.5 0 8554 0 5 14 400

Pret 0.2 1.4 0.25 3

Tabel 1.

        

         Sa se determine cantitatile ce trebuiesc incluse in meniu din cele patru alimente astfel incat costul total a meniului sa fie minim.

4. Substantele   contin in cantitati diferite elementele  . Din cele patru substante trebuie facut un amestec care sa contina cel putin 28, 30, 25 si respectiv 25 unitati din cele patru elemente. Cate o unitate din fiecare tip de substanta costa 6, 3, 4 ti respectiv 5 u.m. Continutul unei unitati din fiecare substanta in cele patru elemente este dat in Tabelul 2:

Tabel 2.

         Amestecul trebuie sa contina cel putin

3 unitati din substanta   si cel putin 2 unitati din  . Sa se determine cantitatile ce trebuie amestecate din cele patru elemente astfel incat sa fie indeplinite conditiile impuse iar costul total al amestecului sa fie minim.

5. O rafinarie prepara doi carburanti auto   si   din patru componente de benzina 

,   in compozitie volumetrica de 20%, 30%, 30%, respectiv 20% pentru   si de 10%,

10%, 60%, 20% pentru  . Rafinaria dispune de 9000m3 din , 14000m3 din ,

cantitatile   fiind nelimitate, cu conditia de a se utiliza cel putin 6000m3 din   si

18000m3 din  .

         Stiind ca beneficiul pentru   este de 6 u.m. pe m3 si la   de 5 u.m. pe m3 sa se realizeze un amestec astfel ca beneficiul global sa fie maxim.

Solutii de PL folosind tratarea geometrica

1.     max   (maximizarea functiei obiectiv)

,

,

,

      

3 4 0 5

2 0 3 0

1 3 0 3

3 1 4 1

Solutie de optim: 

Programe MATLAB pentru problema 1 propusa: simplex3.m si simplex3_geom.m

function simplex3

x0=[0 0 0];

A=[1 3 2;4 2 2;1 1 3];

b=[12 15 12]';

[x,feval]=fmincon(@prob,x0,A,b);

disp(x)

disp(feval)

function f=prob(x)

f=-4*x(1)-3*x(2)-5*x(3);

syms x y z positive

z1=(x+3*y)/2-6;

z2=2*x+y-7.5;

z3=(x+y)/3-4;

figure(1)

hold on;

grid on;

axis([0,8,0,6,0,3]);

ezsurf(x,y,z1);

ezsurf(x,y,z2);

ezsurf(x,y,z3);

Solutie: maxim pentru  x= 1.5000    1.5000    3.0000.