Cercetari Operationale si Teoria Deciziei

Introducere

1. Originea si natura cercetarilor operationale (CO)
2. Impactul CO si algoritmi. Modelare prin CO.

1. Originea si natura cercetarilor operationale (CO)

CERCETAREA OPERATIONALA, definita pe scurt "pregatirea stiintifica a deciziilor", a aparut in perioada celui de-al doilea razboi mondial si se caracterizeaza prin procesul de elaborare a unor modele economico-matematice ce conduc la decizii optime sau aproape optime.

2.Impactul CO si algoritmi. Modelare prin CO.

Modelarea este o metoda de cunoastere, de reflectare a realitatii. Esenta modelarii consta in inlocuirea procesului real studiat printr-un model mai accesibil studiului. Modelul este o reprezentare simplificata a procesului real, prin descrierea comportamentului global al marimilor esentiale ce intervin in proces. Abstractia si simplificarea sunt pasi necesari in rezolvarea oricarei probleme umane. Un model matematic in inginerie va reprezenta fidel un anumit proces in masura in care se sprijina pe teoria generala care formuleaza categoriile, conceptele si legile obiective ale realitatii procesului considerat si are la baza o structura logica deductiva de la axiome si ipoteze simplificatoare asupra marimilor ce descriu fenomenul studiat, pana la determinarea unor legaturi si legitati intre aceste marimi.

Introducerea unui model matematic pentru descrierea unui proces presupune aparitia unor erori:

Clase de modele, in functie de domeniul de provenienta si conceptie:

a)     modele tehnico-economice (pentru evidentierea fenomenelor de reglare)

b)    modele econometrice (pentru determinarea unei tendinte sau a unei periodicitati)

c)     modele de cercetare operationala (pentru gasirea unor solutii optime sau apropiate de optim)

d)    modele de teoria deciziei (luand in considerare diverse criterii, factori de risc, de incertitudine)

e)     modele de simulare

Modelarea si simularea proceselor economice - disciplina economica de granita cu matematica si tehnica de calcul - se ocupa cu fundamentarea deciziilor manageriale in conditii de eficienta pentru producator, cu ajutorul unor modele economico-matematice flexibile si cu posibilitatea utilizarii tehnicilii simularii.

Modele de culegere si prelucrare a datelor folosite in modelarea matematica

Metode exacte permit obtinerea in cadrul unei probleme de decizie economica a unei solutii S care indeplineste, fara nici o eroare restrictiile impuse si/sau conditiile de optim, cerute prin criteriile de eficienta. Daca notam prin S vectorul solutiei adoptate, iar prin S* vectorul solutiei adevarate, atunci: S-S*=0.

Metode aproximative sunt acele metode care permit obtinerea unei solutii S, diferita de solutia adevarata S* printr-un vector e, dominat de un vactor e_a dinainte stabilit, adica: |S-S*|=|e e_a

Metodele euristice sunt metode prin care, chiar in cazul unei probleme complexe se obtine intr-un timp relevant scurt, comparativ cu alte metode, o solutie S, acceptabila din punct de vedere practic, fara a avea garantii asupra rigurozitatii rezolvarii.

Fazele unui studiu de cercetari operationale:

Definirea problemei de interes si determinarea datelor relevante.

Formularea unui model matematic ce descrie problema.

Dezvoltarea unei proceduri bazata pe calculator pentru determinarea solutiilor problemei folosind modelul.

Testarea modelui si rafinarea acestuia daca este necesar.

Pregatirea pentru descrierea unei aplicatii a modelului catre management.

Implementare.

Cap1. Probleme de programare liniara.

1.1. Probleme de programare liniara. Exemple

1.2. Forme ale problemelor de programare liniara. Algoritmul simplex.

1.3. Teoria dualitatii si analiza de sensitivitate

1.4. Alti algoritmi de programare liniara.

1.1. Probleme de programare liniara

Exemple: utilizarea optima a resurselor, alocarea optima a fondurilor financiare, gestionarea optima a unui depozit, problema dietei, problema de tip transport

I. Problema analizei activitatii

(a folosirii optime a resurselor sau a sortimentului optim)

Notatii:

resurse (materii prime) necesare unei unitati economice,

cantitati maxime ce pot fi folosite din resursele (),

produsele finale,

cantitatea din resursa consumata pentru a obtine cantitatea unitara de produs , profitul

, cantitatea din produsul , a.i. profitul sa fie maxim.

Modelul matematic:

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

III. Problema dietei

Notatii:

alimente,

substante nutritive,

cantitatea de substanta aflata in unitatea de aliment

costul unitar al alimentului ,

dieta, = cantitatea folosita din alimentul ,

cantitati de substanta , minime necesare la o dieta.

Modelul matematic:

(minimizarea costului dietei)

IV. Alocarea optima a fondurilor financiare

Notatii:

S o suma totala care poate fi investita in diverse activitati j,

profit unitar obtinut din investitia in activitatea ,

suma ce va fi investita in activitatea pentru a obtine profit maxim.

Modelul matematic:

Observatie: Se pot impune reguli suplimentare in legatura cu posibilitatea de investitie, cu existenta unui risc al investitiilor si natura neliniara a profitului total.

V. Problema de tip transport

Notatii:

m numarul de centre de aprovizionare (depozite) ,,

n numarul de centre de consum (puncte de lucru, magazine) ,,

cantitatea de produs omogen care se afla la depozitul

cantitatea ceruta la centrul de consum ,

cantitatea necunoscuta de produs ce va fi transportata de la depozitul la centrul de consum (cantitate pozitiva),

costul transportului unei unitati din produsul considerat de la depozitul la centrul de consum (se face ipoteza ca acest cost nu depinde de cantitatea transportata pe ruta respectiva).

Observatii:

cantitatea aflata la depozitul ,

necesarul la centrul de consum ,

este costul transportului de la depozitul i la centrul j, iar este costul total de transport,

Se impune conditia de balansare sau de echilibru .

Modelul matematic: (program de transport)

Observatie:

Problema se poate pune in felul urmator: trebuie aprovizionat un grup de uzine de un centru comun, avand la dispozitie m centre de aprovizionare si n puncte de consum.

Modelul matematic:

cu conditia de a avea solutii si cu notatiile:= capacitatile centrelor de depozitare, = cantitatile necesare uzinelor, iar = costul unitar de transport.

1 Forme ale problemelor de programare liniara. Algoritmul simplex

(fundamentele algoritmului, enuntul algoritmului simplex, tabelul 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:

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:

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 .

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 .

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

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 .

Tabelul simplex si transformarea sa

Notatii:

CVB = prima coloana a tabelului, contine coeficientii din functia obiectiv

VB = a doua coloana a tabelului, contine valorile variabilele de baza

VVB= a treia coloana din tabel, contine valorile variabilelor de baza, ultima linie fiind valoarea functiei obiectiv.

Tabelul simplex corespunzator bazei B este dat de Tabelul 2.1.:

Tabel 2.1.

Elementele noului tablou, corespunzator noii baze:

Elementele liniei k se impart la pivot: , .

Elementele celorlalte linii se calculeaza dupa regula dreptunghiului cu diagonala principala cea a pivotului: , , .

Modificarea functiei obiectiv: .

Aplicatie:

S-a observat ca in fiecare luna masinile ce lucreaza intr-o sectie a unei intreprinderi nu sunt folosite 8, 24 si respectiv 18 ore. Se ia hotararea sa se foloseasca si acest timp, punandu-le sa lucreze la fabricarea a doua produse suplimentare si , ca produse anexe ale sectiei, aducand un profit la unitatea de produs fabricat de 4 si respectiv 3 u.m. Timpul necesar de lucru la fiecare masina este descris in Tabelul 2.2.:

Tabel 2.2.

Sa se determine planul de productie al sectiei pentru produsele si care sa conduca la un profit maxim. (vezi R. Trandafir, 2002)

Rezolvare:

Fie cantitatile din produsul , ce trebuiesc fabricate. Modelarea problemei conduce la:

max (maximizarea functiei obiectiv)

Adaugand variabilele de compensare se obtine problema de programare liniara sub forma standard:

max

Matricea sistemului: . Alegem corespunzator variabilelor . Avem ca: . Tabelul simplex:

Tabel 1.3.

Tabel 1.4.

Tabel 1.5.

Maximul functiei se obtine pentru realizat pentru si (,si ). Astfel:

Pentru masinile M₁ si M₃ timpul este folosit integral. Pentru masina M₂ nu este utilizat timpul integral.

Rezolvarea problemei folosind pachetul de programe MatLab. Fisierul prob1.m contine urmatoarele comenzi:

Fisierul simplex.m contine comenzile:

La rularea programului simplex.m obtinem:

f-COUNT FUNCTION MAX STEP Procedures

4 0 -8 1

8 -18.4 -1.64543e-007 1 Hessian modified twice

12 -19.2292 0 1 Hessian modified

16 -21.6 1.41306e-007 1 Hessian modified

17 -21.6 -1.77636e-015 1 Hessian modified

Optimization Converged Successfully

Active Constraints:

1

3

x = 1.2000 5.6000 0

options(1)=1, options(2)=0.0001, options(3)=0.0001, options(4)=0.0000, options(5)=0, options(6)=0, options(7)=0, options(8)=-21.6000, options(9)=0, options(10)=5.0000, options(11)=5.0000, options(12)=0, options(13)=0, options(14)=300.0000, options(15)=0, options(16)=0.0000, options(17) =0.1000, options(18)=1.0000

Astfel si iar (= options(8)).