decision analysis

1Tema nr.1

Optimizri cu restricii alocarea de resurse limitate unor activiti

12TEMA 1 aMetoda programrii liniare Algoritmul Simplex23Introducere in Programarea LiniaraStructura modelului matematic al unei probleme PLTipuri de problemeProblema de maximMetoda grafica de rezolvare a problemei de maximProblema de minimMetoda grafica de rezolvare a problemei de minimCazuri speciale de probleme de P.L.Solutii ale unei probleme de PL

34Structura modelului matematic al problemei PLo funcie obiectiv, liniar, ce trebuie optimizat; ea poate avea sensul de maxim sau de minim, dup natura scopului urmrit;

un sistem de restricii, de asemenea liniare; restriciile pot fi inecuaii cu semnul , inecuaii cu semnul precum i ecuaii; aceste restrictii sunt impuse de cantitatile limitate in care se gasesc resursele;

un alt set de restricii care se refera la condiiile de nenegativitate ale variabilelor (in problemele manageriale, valorile negative pentru orice activitate (produs) nu sunt acceptabile).45Tipuri de probleme

1. Determinarea structurii optime a productiei

Se cunosc: cantitile disponibile din fiecare materie prim (resurs) {bi , i = 1,,m} coeficienii tehnologici {aij , i = 1,,m, j = 1,,n}, aij reprezentnd cantitatea din materia prim i necesar fabricrii unei uniti din produsul j ctigul (beneficiul) unitar adus ntreprinderii de fabricarea fiecrui produs {cj , j = 1,,n}. Se cere: determinarea acelor cantiti xj ce trebuie fabricate din fiecare tip de produs astfel nct s se obin beneficiul maxim, n condiiile nedepirii disponibilurilor din fiecare resurs.56Modelul matematic:

672. Programarea operativ a produciei Obiectivul problemei: productie maxima restriciile se refer la o serie de utilaje cu care se execut produsele, cunoscndu-se timpul disponibil al fiecrui utilaj, pe perioada de timp analizat, bi. Coeficienii tehnologici aij reprezint timpul necesar prelucrrii unui produs j pe utilajul i . Modelul matematic este:

78 Obiectivul problemei: cost minim al unui amestec format din m substante care se gasesc in n materii prime Restrictiile sunt impuse de cantitatile (cunoscute) in care fiecare substanta trebuie sa intre in amestec Se cunosc cantitile {aij , i = 1,,m, j = 1,,n} din fiecare substan pe care le conine o unitate din fiecare materie prim i costurile {cj , j = 1,,n} unei uniti din aceste materii prime. Se poate scrie modelul:3. Problema de amestec optim

89Exemplul 1. Problema de maximFie problema de P.L. al carui model matematic este:max f (x) = 5x1 + 7x2x1 62x1 + 3x2 19x1 + x2 8x1, x2 0

Sa se afle solutia optima utilizand metoda grafica.910Exemplul 1: Metoda graficaRestrictia (1): x1 6

x2x1x1 < 6(6, 0)8

7

6

5

4

3

2

1

1 2 3 4 5 6 7 8 9 10 1011Exemplul 1: Metoda graficaRestrictia (2): 2x1 + 3x2 19

2x1 + 3x2 < 19 x2x1(0, 6 1/3)(9 1/2, 0)8

7

6

5

4

3

2

1

1 2 3 4 5 6 7 8 9 10 1112Exemplul 1: Metoda graficaRestrictia (3): x1 + x2 8

x2x1x1 + x2 < 8(0, 8)(8, 0)8

7

6

5

4

3

2

1

1 2 3 4 5 6 7 8 9 10 1213Exemplul 1: Metoda graficaSistemul de restrictii2x1 + 3x2 < 19 x2x1x1 + x2 < 8x1 < 68

7

6

5

4

3

2

1

1 2 3 4 5 6 7 8 9 10 13148

7

6

5

4

3

2

1

1 2 3 4 5 6 7 8 9 10 Exemplul 1: Metoda graficaZona solutiilor admisibilex1FeasibleRegion x214158

7

6

5

4

3

2

1

1 2 3 4 5 6 7 8 9 10 Exemplul 1: Metoda graficaFunctia obiectiv: max f(x) = 5x1 + 7x2x1 x2(7, 0)(0, 5)Functia obiectiv5x1 + 7x2 = 3515168

7

6

5

4

3

2

1

1 2 3 4 5 6 7 8 9 10 Exemplul 1: Metoda graficaSolutia optimax1 x2Functia obiectiv5x1 + 7x2 = 46Solutia optima(x1 = 5, x2 = 3)1617Exemplul 2. Problema de minimSe da problema:min f (x) = 5x1 +2x22x1 + 5x2 104x1 x2 12x1 + x2 4x1, x2 0

Sa se afle solutia optima utilizand metoda grafica1718Exemplul 2: Metoda graficaReprezentarea grafica a restrictiilor5

4

3

2

1 1 2 3 4 5 6x24x1 - x2 > 12

x1 + x2 > 42x1 + 5x2 > 10x1Zona solutiiloradmisibile1819Exemplul 2: Metoda graficaSolutia optima5

4

3

2

1 1 2 3 4 5 6x2Functia obiectivMin z = 5x1 + 2x2

4x1 - x2 > 12

x1 + x2 > 42x1 + 5x2 > 10

Sol. optima: x1 = 16/5 x2 = 4/5x11920Exemplul 3: Problema de P.L. nu are solutie Sa se rezolve prin metoda grafica problema:

max f (x) = 2x1 + 6x2

4x1 + 3x2 < 12 2x1 + x2 > 8

x1, x2 > 02021Exemplul 3: Problema P.L. imposibilaDeoarece nu exista o zona a solutiilor admisibile, problema nu are solutiex2x14x1 + 3x2 < 122x1 + x2 > 834482122Exemplul 4: Problema P.L. cu solutie optima infinitaSa se rezolve prin metoda grafica problema:

max f (x) = 3x1 + 4x2 x1 + x2 > 5 3x1 + x2 > 8

x1, x2 > 02223Exemplul 4: Problema cu solutie optima infinitaLa deplasarea dreptei functie obiectiv in sensul cresterii operatorului , solutia optima tinde sa creasca spre infinit, deoarece zona solutiilor admisibile este nemarginita x2x13x1 + x2 > 8x1 + x2 > 5Max 3x1 + 4x25582.672324Tipuri de solutii ale unei probleme PL se numete soluie admisibil X un element al mulimii programelor (soluiilor) P, care verific sistemul de restricii i condiiile de negativitate:

se numete soluie optim soluia admisibil care optimizeaz funcia obiectiv:

pentru o problem de minim, sau: pentru o problem de maxim.

Dac mulimea soluiilor admisibile este convex, nchis i mrginit, punctele sale extremale se numesc soluii de baz admisibile

24258

7

6

5

4

3

2

1

1 2 3 4 5 6 7 8 9 10 Exemplul 1: Tipuri de solutii ale problemei de P.L.x1Zona solutiilor admisibile12345 x2Solutii admisibile de baza (puncte extremale)Solutie optima2526

26