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:

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

3000

8

20

3.5

0

85

54

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.

3

4

0

5

2

0

3

0

1

3

0

3

3

1

4

1

         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)

,

,

,

      

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




loading...





.com Copyright © 2017 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Proiecte

vezi toate proiectele
 PROIECT DE LECTIE Clasa: I Matematica - Adunarea si scaderea numerelor naturale de la 0 la 30, fara trecere peste ordin
 Proiect didactic Grupa: mijlocie - Consolidarea mersului in echilibru pe o linie trasata pe sol (30 cm)
 Redresor electronic automat pentru incarcarea bateriilor auto - proiect atestat
 Proiectarea instalatiilor de alimentare ale motoarelor cu aprindere prin scanteie cu carburator

Lucrari de diploma

vezi toate lucrarile de diploma
 Lucrare de diploma - eritrodermia psoriazica
 ACTIUNEA DIPLOMATICA A ROMANIEI LA CONFERINTA DE PACE DE LA PARIS (1946-1947)
 Proiect diploma Finante Banci - REALIZAREA INSPECTIEI FISCALE LA O SOCIETATE COMERCIALA
 Lucrare de diploma managementul firmei “diagnosticul si evaluarea firmei”

Lucrari licenta

vezi toate lucrarile de licenta
 CONTABILITATEA FINANCIARA TESTE GRILA LICENTA
 LUCRARE DE LICENTA - FACULTATEA DE EDUCATIE FIZICA SI SPORT
 Lucrare de licenta stiintele naturii siecologie - 'surse de poluare a clisurii dunarii”
 LUCRARE DE LICENTA - Gestiunea stocurilor de materii prime si materiale

Lucrari doctorat

vezi toate lucrarile de doctorat
 Doctorat - Modele dinamice de simulare ale accidentelor rutiere produse intre autovehicul si pieton
 Diagnosticul ecografic in unele afectiuni gastroduodenale si hepatobiliare la animalele de companie - TEZA DE DOCTORAT
 LUCRARE DE DOCTORAT ZOOTEHNIE - AMELIORARE - Estimarea valorii economice a caracterelor din obiectivul ameliorarii intr-o linie materna de porcine

Proiecte de atestat

vezi toate proiectele de atestat
 Proiect atestat informatica- Tehnician operator tehnica de calcul - Unitati de Stocare
 LUCRARE DE ATESTAT ELECTRONIST - TEHNICA DE CALCUL - Placa de baza
 ATESTAT PROFESIONAL LA INFORMATICA - programare FoxPro for Windows
 Proiect atestat tehnician in turism - carnaval la venezia




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



loading...

Termeni si conditii
Contact
Creeaza si tu