c3-4_aat- pl inainte de simplex

8/18/2019 C3-4_AAT- PL Inainte de Simplex

1/39

Programare liniara

An universitar 2015 - 2016

METODE DE OPTIMIZARE A PROCESELOR

DECIZIONALE

Conf. Dr. Cristinca FULGA

Academia de Studii Economice

Bucuresti, Romania


2/39

Programare liniara

Metode de Optimizare a Proceselor Decizionale

1 Programare liniara


3/39

Programare liniara

Forma generala a unei probleme de programare liniara

( PPL)

8>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>>>:

optim f ( x) =nX

j=1

c j x j

n

X j=1aij x j bi ; i 2 f1;:::; l g

nX j=1

aij x j = bi ; i 2 fl + 1;:::; pg

n

X j=1 aij x j bi ; i 2 f p + 1;:::; mg x j 0; 8 j cu 1 j k ; x j 2 R; 8 j cu k + 1 j s; x j 0; 8 j cu s + 1 j n:


4/39

Programare liniara

Forma generala a unei probleme de programare liniara

Matricea sistemului restrictiilor (numita si matricea tehnologica)

A = (aij)1im1 jn

;

m = numar de restrictii,

n = numar de necunoscute.

Ipoteza: rangA = m < n:

P li i


5/39

Programare liniara

Forma canonica a unei probleme de programare liniara

Forma canonica a unui model de maxim

8>>>>>><

>>>>>>:

max f ( x) =

n

X j=1

c j x j

nX j=1

aij x j bi ; i = 1; m

x j 0; j = 1; n

P li i


6/39

Programare liniara

Forma canonica a unei probleme de programare liniara

Forma canonica a unui model de minim

8>>>>>><>>>>>>:

min f ( x) =nX

j=1

c j x j

n

X j=1aij x j bi ; i = 1; m

x j 0; j = 1; n

Programare liniara


7/39

Programare liniara

Forma standard a unei probleme de programare liniara

Forma standard

8>>>>>><>>>>>>:

opt f ( x) =nX

j=1

c j x j

n

X j=1aij x j = bi ; i = 1; m

x j 0; j = 1; n

Programare liniara


8/39

Programare liniara


Transformarea problemei de programare liniara data in forma

generala in una din formele canonica sau standard se face astfel:

introducand variabile de compensare (pentru forma standard)

ex: 1) 2 x1 3 x2 + x3 2 =) 2 x1 3 x2 + x3 + u = 2 , u 02) 5 x1 + x2 7 x3 3 =) 5 x1 + x2 7 x3 u = 3 , u 0:

scriind ecare ecuatie ca 2 inecuatii de sens contrar (pentru una

dintre formele canonice).

ex: 2 x1 3 x2 + x3 = 4 ()

2 x1 3 x2 + x3 42 x1 3 x2 + x3 4

Programare liniara


9/39

Programare liniara


pentru a obtine variabile nenegative

daca xi 0; se face substitutia x0

i = xi cu x0

i 0

daca xi 2 R se face substitutia xi = x0

i x00

i cu x0

j ; x00

i 0:

o inecuatie cu se inmulteste cu (1) si devine (pentruforma canonica).

un model matematic de min se transforma in model de max

astfel:

min f ( x) () max ( f ( x)) :

Programare liniara


10/39

Programare liniara

Solutiile unei PPL

Fie modelul matematic standard al unei PPL:

( PPL)

8


11/39

g

Solutiile unei PPL

DEFINITIE X 0 2 Rn s.n. solutie realizabila (solutie posibila sau

admisibila) a ( PPL) daca verica sistemul restrictiilor Ax = b x 0:

Programare liniara


12/39

g

Solutiile unei PPL

DEFINITIE X 0 2 Rn s.n. solutie de baza daca

verica Ax = b;

are cel mult m componente diferite de 0si

coloanele matricei A ce corespund componentelor diferite de 0

sunt vectori liniari independenti.

Programare liniara


13/39

Solutiile unei PPL

DEFINITIE

Daca solutia de baza X 0 are exact m componente diferite de 0

atunci s.n. solutie nedegenerata.

Daca are mai putin de m componente diferite de 0 s.n.

degenerata.

Programare liniara


14/39

Solutiile unei PPL

DEFINITIE Fie X 1; X 2 solutii realizabile ale (PPL).Spunem ca ” X 1 este mai buna decat X 2” daca

pentru problema de minim: f ( X 1

) f ( X 2

) ;

pentru problema de maxim: f ( X 1) f ( X 2) :

DEFINITIE O solutie realizabila pentru care este atins optimul

functiei obiectiv s.n. solutie optima.

Programare liniara


15/39

Solutiile unei PPL

Notatie: < = multimea solutiilor realizabile ale ( PPL) adusa la forma

standard


16/39

Solutiile unei PPL

PROPRIETATE Multimea solutiilor realizabile < ale unei ( PPL)este multime convexa.

DEMONSTRATIE Fie x1; x2 2


17/39

Solutiile unei PPL

Fie 2 [0; 1]. Atunci

0 =) Ax1 = b; x1 01 0 =)

(1 ) Ax2 = (1 ) b;(1 ) x2 0

Programare liniara


18/39

Solutiile unei PPL

Adunand relatiile corespunzatoare, obtinem

Ax1 + (1 ) Ax2 = b + (1 ) b () A [ x1 + (1 ) x2] =b ( + 1 ) si deci

A [ x1 + (1 ) x2] = b;

x1 + (1 ) x2 0

ceea ce inseamna ca x1 + (1 ) x2 2


19/39

Solutiile unei PPL

Vom studia relatia dintre solutiile realizabile de baza x 2 < sivârfurile multimii


20/39

Solutiile unei PPL

OBSERVATIE

Cum un sistem cu m linii si n coloane are cel mult C mn solutii de baza

=) < va avea cel mult C mn varfuri.

Programare liniara


21/39

Solutiile unei PPL

PROPRIETATE x solutie realizabila de baza =) x vârf al


22/39

Solutiile unei PPL

Fie xi1 ; :::; xik componentele nenule ale solutiei de baza x; undek m:

Fie ai1 ;:::; aik coloanele ce corespund componentelor nenule;fai1 ;:::; aik g sunt vectori liniari independenti.

Programare liniara

l iil i


23/39

Solutiile unei PPL

Demonstram prin Reducere la Absurd (R.A.):

Presupunem prin R.A. ca x nu este varf al< ()

9 y; z 2 Rn; y 6= z ;9 2 (0; 1)

a.i. x = y + (1 ) z :

Programare liniara

S l iil i PPL


24/39

Solutiile unei PPL

pentru componentele nebazice j 2 f1; 2; :::; ng n fi1;:::; ik g sestie ca x j = 0:

Dar ( > 0; y j 0 =) y j 0

(1 ) > 0; z j 0 =) (1 ) z j 0

Rezulta ca, din ecare ecuatie x j

|{z} 0= y j + (1 ) z j

va rezulta y j = z j = 0; 8 j indice nebazic.

Programare liniara

S l iil i PPL


25/39

Solutiile unei PPL

pentru componentele bazice i1;:::; ik , yi j si z i j pot 6= 0;8 j = 1; k :

Dar y; z 2 < =)

Ay = b; Az = b

=) A ( y z ) = 0:

( y z )T A = 0 ()

() ( yi1 z i1 ) ai1 + ::: + ( yik z ik ) aik = 0:

Dar fai1 ;:::; aik g sunt vectori liniari independenti )

yi j z i j = 0; 8 j = 1; k :

Programare liniara

S l tiil i PPL


26/39

Solutiile unei PPL

Concluzie:

y j z j = 0; 8 j indice nebazic yi j z i j = 0; 8i j indice bazic

=) y = z CONTRADICTIE cu ipoteza R.A. ) x este vârf al


27/39

Solutiile unei PPL

PROPRIETATE Fie x varf al < =) x solutie realizabila de baza.

Programare liniara

Sol tiile nei PPL


28/39

Solutiile unei PPL

EXEMPLU

8>>>:max f ( x) = 2 x1 + 5 x2

x1 + 2 x2 23 x1 + x2 3

x1; x2 0


29/39

Programare liniara

Solutiile unei PPL


30/39

Solutiile unei PPL

Fie

( PPL) opt f ( x) = cT x x 2 < ;unde


31/39

Solutiile unei PPL

Cazuri posibile:

1


32/39

Solutiile unei PPL

2.1. f nemarginita pe


33/39

Rezolvarea graca a problemelor de programare liniara

EXEMPLU Pentru a asigura hrana animalelor din ferma sa, unfermier poate cumpara doua tipuri de alimente: F 1 si F 2. Pentru a le

asigura o dieta corecta, fermierul a calculat ca este nevoie zilnic de

60, 84 si 72 de unitati din elementele nutritionale notate A; B; C .Continutul de elemente nutritionale si costul ecarui kilogram ale

celor doua tipuri de alimente sunt date in tabel:

Elemente nutritionale (unitati=kg ) A B C Cost ( RON =kg )

F 1 3 7 3 10

F 2 2 2 6 4

Sa se determine planul optim de achizitii.

Programare liniara

Programare liniara


34/39

Programare liniara

Notatii: x = nr. de kg din F 1 ce urmeaza a cumparate y = nr. de kg din F 2 ce urmeaza a cumparate

Functia obiectiv: functia cost total f ( x; y) = 10 x + 4 y

Restrictiile modelului relative la ecare dintre elementele

nutritionale A; B; C :

pentru A, 3 x + 2 y 60

pentru B, 7 x + 2 y 84 pentru C , 3 x + 6 y 72:

Programare liniara

Programare liniara


35/39

Programare liniara

Modelul matematic asociat problemei este:

8>>>>>>>:

min f ( x; y) = 10 x + 4 y

3 x + 2 y 607 x + 2 y 843 x + 6 y 72

x; y 0:

Programare liniara

Programare liniara


36/39

Programare liniara

Etapele rezolvarii grace a problemelor de programare liniara

1) Se reprezinta grac ecare restrictie in parte.

1a) Pentru restrictiile de tip egalitate ax + by = c: se traseaza dreapta

corespunzatoare in sistemul de axe xOy.

1b) Pentru restrictiile de tip inegalitate ax + by c sau ax + by c:

(i) inegalitatii i se asociaza ecuatia corespunzatoare ax + by = c si setraseaza dreapta de ecuatie ax + by = c in sistemul de axe xOy;

(ii) se determina semi-planul corespunzator restrictiei in forma initiala( sub forma de inegalitate).

Programare liniara

Programare liniara


37/39

Programare liniara

2) Se determina multimea solutiilor admisibile < ca intersectie atuturor semi-planelor corespunzatoare restrictiilor modelului.

3) Pentru functia obiectiv f ( x; y) = x + y:

3a) Se traseaza dreapta de ecuatie x + y = , unde 2 R, insistemul de axe xOy;

3b) Se calculeaza gradientul functiei obiectiv:

gradf = 0@@ f

@ x

@ f

@ y

1A = :

Programare liniara

Programare liniara


38/39

g

Gradientul gradf indica directia de crestere a functiei obiectiv

f ( x; y) = x + y: Pentru rezolvarea modelului, ne intereseazadirectia in care trebuie deplasata dreapta

x + y =

a.i. sa e obtinuta o cat mai buna valoare pentru functia obiectiv, i.e.

o cat mai mare valoare pentru problemele de maxim (deplasarea

se face pe directia gradientului)

respectiv,

o cat mai mica valoare pentru problemele de minim (deplasarea

se face pe directia opusa directiei gradientului).

Programare liniara

Programare liniara


39/39

g

Se obisnuieste ca dreapta de ecuatie x + y = sa e numita

dreapta de isocost daca modelul este de minimizare a costului,

respectiv,

dreapta de isoprot daca modelul este de maximizare a

protului.

Prexul "iso" indica faptul ca de-a lungul dreptei y = x + y;valoarea x + y este constanta (si anume, este egala cu in scrierea x + y = ).

c3-4_aat- pl inainte de simplex

Documents