![]() | Afaceri | Agricultura | Economie | Management | Marketing | Protectia muncii |
Transporturi |
Cercetari Operationale si Teoria Deciziei
Introducere
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:
erori ce apar prin omiterea unor variabile importante in model,
erori ce apar in definirea relatiilor dintre variabile,
erori de calcul al variabilelor cantitative,
erori de masurare (de determinare a variabilelor exogene).
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.
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 ea dinainte stabilit, adica: |S-S*|=|e ea
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.
;
.
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.
;
.
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:
,
. (1.2.1)
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.:
Baza B |
|
|
|
|
|
|
aleg min |
||||||
CVB |
VB |
VVB |
|
|
|
|
|
|
|
||||
|
|
|
|
|
| ||||||||
|
|
|
|
|
|
|
|
| |||||
|
|
|
|
|
| ||||||||
|
|
|
|
|
|
|
|
| |||||
|
|
|
|
|
| ||||||||
Valoarea functiei obiec-tiv |
|
|
aleg max |
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.:
Masina Produsul |
|
|
| ||
| ||
|
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:
Baza B |
alegem minim |
||||||||
CVB |
VB |
VVB |
|
|
|
|
|
|
|
|
|
||||||||
|
|
||||||||
|
|
||||||||
valoarea functiei obiectiv |
|
alegem min |
Tabel 1.3.
|
|
alegem minim |
|||||||
CVB |
VB |
VVB |
|
|
|
|
|
|
|
|
|
||||||||
|
|
||||||||
|
|
||||||||
valoarea functiei obiectiv |
|
alegem min |
Tabel 1.4.
|
alegem minim |
|||||||
CVB |
VB |
VVB |
|
|
|
|
|
|
| ||||||||
| ||||||||
| ||||||||
valoarea functiei obiectiv |
alegem min |
Tabel 1.5.
Maximul
functiei se obtine pentru realizat pentru
si
(
,
si
). Astfel:
,
,
.
Pentru masinile M1 si M3 timpul este folosit integral. Pentru masina M2 nu este utilizat timpul integral.
Rezolvarea problemei folosind pachetul de programe MatLab. Fisierul prob1.m contine urmatoarele comenzi:
function [f,g]=prob1(x);
f=-4*x(1)-3*x(2);
g=[2*x(1)+x(2)-8,3*x(1)+2*x(2)-24,x(1)+3*x(2)-18];
Fisierul simplex.m contine comenzile:
options(1)=1;
VMI=zeros(1,3);
VMS=[];
x0=[0 0 0];
[x, options]=constr('prob1',x0, options,VMI,VMS);x
options
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)).
Copyright © 2025 - Toate drepturile rezervate