Creeaza.com - informatii profesionale despre


Cunostinta va deschide lumea intelepciunii - Referate profesionale unice
Acasa » referate » matematica
Cercetari Operationale si Teoria Deciziei - Probleme de programare liniara

Cercetari Operationale si Teoria Deciziei - Probleme de programare liniara




Cercetari Operationale si Teoria Deciziei

Probleme de programare liniara.

Probleme de programare liniara. Exemple. Algoritmul simplex.

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.

; .

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:

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 .

Probleme de programare liniara cu optim infinit

Aplicatie 2:

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

Probleme propuse

max (maximizarea functiei obiectiv)

,

,

,

max (maximizarea functiei obiectiv)

,

,

,

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

Pret

Tabel 1.

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

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.

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

max (maximizarea functiei obiectiv)

,

,

,

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.

Dualitate simetrica

Dualitate nesimetrica







Politica de confidentialitate







creeaza logo.com Copyright © 2024 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Comentarii literare

ALEXANDRU LAPUSNEANUL COMENTARIUL NUVELEI
Amintiri din copilarie de Ion Creanga comentariu
Baltagul - Mihail Sadoveanu - comentariu
BASMUL POPULAR PRASLEA CEL VOINIC SI MERELE DE AUR - comentariu

Personaje din literatura

Baltagul – caracterizarea personajelor
Caracterizare Alexandru Lapusneanul
Caracterizarea lui Gavilescu
Caracterizarea personajelor negative din basmul

Tehnica si mecanica

Cuplaje - definitii. notatii. exemple. repere istorice.
Actionare macara
Reprezentarea si cotarea filetelor

Economie

Criza financiara forteaza grupurile din industria siderurgica sa-si reduca productia si sa amane investitii
Metode de evaluare bazate pe venituri (metode de evaluare financiare)
Indicatori Macroeconomici

Geografie

Turismul pe terra
Vulcanii Și mediul
Padurile pe terra si industrializarea lemnului



CONCEPTE PROBABILISTICE DE BAZA ALE SECURITATII SISTEMELOR
Reducerea formei patratice la expresia canonica
INDICATORI DE POZITIE
TRANSFORMATA LAPLACE
Vectori proprii. Valori proprii. Definitii. Proprietati
Subspatiu vectorial
Subspatii invariante ale unui endomorfism
Ecuatii diferentiale de ordinal intai



Termeni si conditii
Contact
Creeaza si tu