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:

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

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 9000m³ din, 14000m³ din , cantitatile fiind nelimitate, cu conditia de a se utiliza cel putin 6000m³ din si 18000m³ din .

Stiind ca beneficiul pentru este de 6 u.m. pe m³ si la de 5 u.m. pe m³ 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

Solutie: maxim pentru x= 1.5000 1.5000 3.0000.

Dualitate simetrica

Dualitate nesimetrica