chapter 2 introduction to linear programming liniara.pdf · dantzig a pus bazele "metodei...

1

Capitolul 3

PROGRAMAREA LINIARĂ

Modelarea și optimizarea proceselor energetice industriale

Ce este programarea liniară?

“... determinarea valorii maxime sau minime a

unei funcții liniare, în care mai multe

variabilele de optimizare sunt supuse unor

restricţii.” (dictionary.com)

O problemă de programare liniară este o

“problemă care necesită minimizarea unei

funcţii ce are o expresie liniară în prezenţa

unor restricţii liniare...” (Dantzig)

3

Istoria Programării Liniare

• Totul a început în anul 1947, când GBDantzig a pus bazele "metodei simplex" folosită în rezolvarea problemelor de planificare din US Air Force, probleme care aveau o formă liniară.

• Ulterior, a devenit clar faptul că o gamă surprinzator de largă de probleme din diverse domenii pot fi aduse la o formă corespunzătoare programării liniare și rezolvate prin metoda simplex.

4

Importanţa PROGRAMĂRII LINIARE

Multe dintre problemele din lumea reală se pretează a fi rezolvate folosind programarea liniară.

– Inginerie ;

– Agricultură;

– Marketing ;

– Economie;

– Finanțe (investiții);

– Publicitate.

5

Ce este o problemă de programare liniară?

1. Se încearcă maximizarea (sau minimizarea) unei funcții

ce are o expresie liniară (numită funcția obiectiv)

dependentă de variabilele de optimizare;

2. Valorile variabilelor de optimizare trebuie să satisfacă o

mulţime de restriicţii;

3. Fiecare restricţie de egalitate sau inegalitate trebuie să

aibă o expresie liniară.

4. O restricție de semn este asociată fiecărei variabile de

optimizare. Pentru fiecare variabilă xi, avem (xi ≥ 0).

O problemă de programare liniară (PL) este o problemă de optimizare în care:

Descrierea problemei

max (min) c1x1 + c2x2 + ... + cnxn

în prezenţa restricţiilor:

a1,1x1 + ... a1,nxn b1

a2,1x1 + ... a2,nxn b2

: : :

am,1x1 + ... am,nxn bn

sau, într-o formă simplificată:

n

j

jj xc1

)...,,2,1(0

)...,,2,1(1

njx

mibxa

j

i

n

j

jij

max (min)

în prezenţa restricţiilor:

7

Exemplu :

Max 5x1 + 7x2

s.t. x1 < 6

2x1 + 3x2 < 19

x1 + x2 < 8

x1 > 0 and x2 > 0

Funcţia obiectiv

Restricţii

Restricţii de non-negativitate

Incercaţi şi imaginaţi-vă…

Un poliedru foarte mare, convex;

Un plan care intersectează această poliedru;

Interpretarea reprezentării grafice

Poliedrul reprezintă mulţimea de restricţii

de inegalitate.

Planul reprezintă funcția obiectiv liniară

care trebuie maximizată.

Important

Programarea liniară solicită numai expresii

liniare.

Expresie corectă: ax + by + cz < 3

Expresie incorectă: ax2 + log2y > 7

10

Proporţionalitate şi ipoteze suplimentare

Funcția obiectiv corespunzătoare unei probleme de

programare liniară trebuie să fie o funcție lineară

dependentă de variabilele de decizie, ceea ce

presupune următoarele două implicații:

1. Contribuția fiecărei variabile de optimizare la valoarea

funcției obiectiv este proporțională cu valoarea variabilei

de optimizare.

2. Contribuția la valoarea funcției obiectiv a fiecărei

variabile de optimizare este independentă de celelalte

variabile de optimizare.

11

Proporţionalitate şi ipoteze suplimentare - continuare

1. Contribuția fiecărei variabile de optimizare la expresia

fiecărei restricţii este proporțională cu valoarea

variabilei.

2.Contribuția unei variabile de optimizare din cadrul

expresiei fiecărei restricţii este independentă de valorile

variabilei.

Fiecare restricţie trebuie să fie o inegalitate liniară

sau o ecuație liniară, ceea ce presupune

următoarele două implicații:

12

Ipoteza divizibilităţii

Presupunerea divizibilităţii necesită ca fiecarevariabilă de optimizare să poată lua valorifracționare.

Ipoteza certitudinii

Presupunerea certitudinii necesită ca fiecare componentă din modelul matematic corespunzător unei probleme de programare liniară (coeficiențiifuncției obiective, termenii liberi din restricţii și coeficienţii din expresiile restricţiilor) să fie cunoscută cu certitudine.

Proporţionalitate şi ipoteze suplimentare -

continuare

1. Forma generală

Forma matematică a problemelor PL

2. Forma standard

Forma în care toate restricţiile sunt exprimate prin

egalităţi şi toate variabilele sunt supuse condiţiei de

nonnegativitate.

Forma matematică a problemelor PL

Variabile suplimentare de eliminare/adăugare

• Forma standard este obținută prin adăugarea de

variabile pentru forma inegalitaţilor “≤”, și prin

eliminarea de variabile forma inegalitaţilor “≥”.

• Variabilele suplimentare de eliminare/adăugare

reprezintă diferența dintre partea stânga și cea

dreaptă a restricţiilor.

• In expresia funcţiei obiectiv, aceste variabile

suplimenare au coeficienți egali cu 0.

max 5x1 + 7x2 + 0s1 + 0s2 + 0s3

în prezenţa restricţiilor:

x1 + s1 = 6

2x1 + 3x2 + s2 = 19

x1 + x2+ s3 = 8

x1, x2 , s1 , s2 , s3 > 0

Examplul 1 in Forma Standard

s1 , s2 , şi s3 sunt variabile auxiliare de adaugare

3. Forma matriceala

Forma matematică a problemelor PL

A – matricea coeficienţilor sistemului de restricţii;

b – vectorul coloană al termenilor liberi;

X – vectorul coloană al celor n necunoscute;

C – vectorul coeficienţilor funcţiei obiectiv F(X).

4. Forma vectorială

Se obţine prin partiţionarea matricei A după coloanele sale, a1,

a2, …an.

Forma matematică a problemelor PL

a – coloanele matricei A corespunzătoare sistemului de restricţii;

b – vectorul coloană al termenilor liberi;

x – cele n necunoscute;

C – vectorul coeficienţilor funcţiei obiectiv F(X).

5. Forma canonică

Forma în care restricţiile sunt concordante şi toate variabilele sunt

supuse condiţiei de nenegativitate.

O restricţie corespunzătoare unei probleme de programare liniară

spunem că este concordantă dacă este o inegalitate de tipul " ≥ ",

când funcţia obiectiv trebuie minimizată, respectiv este o egalitate

de tipul " ≤ ", când se cere maximizarea funcţiei obiectiv.

Forma matematică a problemelor PL

sau

20

Definiţii în Programarea Liniară

O soluţie admisibilă a problemei de programare liniară este un

vector X = [x1, x2, ..., xn]t care satisface sistemul de ecuaţii al

restricţiilor, respectiv condiţia de nenegativitate.

O soluţie admisibilă de bază este o soluţie admisibilă care conţine

cel puţin (n – m) componente xj care au valoarea zero, în care m

este numărul restricţiilor iar n reprezintă numărul variabilelor

de optimizare.

O soluţie admisibilă de bază nedegenerată are exact m necunoscute

xj cu valoare pozitivă (> 0).

O soluţie optimală este o soluţie admisibilă care extremizează

funcţia obiectiv.

21

Teoreme în Programarea Liniară

Teorema 1

Funcţia obiectiv îşi realizează optimul într-un punct extrem al

mulţimii restricţiilor. Dacă îşi realizează optimul în mai mult

decât un punct extrem, atunci funcţia obiectiv ia aceeaşi valoare

în fiecare punct de pe segmentul de dreaptă care uneşte oricare

două puncte optimale.

Teorema 2

Un vector X = [x1, x2, ..., xn]t este un punct extrem al mulţimii

restricţiilor unei probleme de programare liniară dacă şi numai

dacă X este o soluţie admisibilă de bază.

22

Analiza grafică în

Programarea Liniară

Mulţimea tuturor punctelor care îndeplinesc toate restricţiile

modelului matematic se numeşte

MULŢIME ADMISIBILĂ

Mulţimi admisibile

1. Mărginite

2. Nemărginite

3. Vide (Goale)

Paşii Algoritmului

• Reprezentarea grafică a inegalităților și

identificarea vârfurilor poligonului format.

• Înlocuirea coordonatelor nodurile în funcția

obiectiv

• Determinarea valorilor minimă şi maximă.

Să se determine minimul funcţiei

F(x, y) = 3x - 2y.

în prezenţa restricţiilor:

y ≥ 2

1 ≤ x ≤5

y ≤ x + 3

Exemplul 1.

6

4

2

2 3 4

3

1

1

5

5

7

8

y ≤ x + 3

y ≥ 2

1 ≤ x ≤5

• Vârfurile poligonului format sunt:

(1, 2) (1, 4) (5, 2) (5, 8)

• Coordonatele determinate în pasul

anterior sunt introduse succesiv în

fucţia obiectiv:

F(x, y) = 3x - 2y

F(x, y) = 3x - 2y

• F(1, 2) = 3(1) - 2(2) = 3 - 4 = -1

• F(1, 4) = 3(1) - 2(4) = 3 - 8 = -5

• F(5, 2) = 3(5) - 2(2) = 15 - 4 = 11

• F(5, 8) = 3(5) - 2(8) = 15 - 16 = -1

• f(1, 4) = -5 minimum

• f(5, 2) = 11 maximum

29

max 8X1 + 5X2 funcţia obiectiv

2X1 + 1X2 1000

3X1 + 4X2 2400

X1 + X2 700 restricţii de inegalitate

X1 - X2 350

Xj> = 0, j = 1,2 restricţii de

nonnegativitate

Exemplul 2

30

Restricţiile de nonnegativitate

X2

X1

Analiza grafică – Mulţimea admisibilă

31

1000

500

Admisibil

X2

Imposibil

3X1+4X2 2400

X1+X2 700 (restricţie redundantă)

500

700

2X1+X2 1000

X1

700

Analiza grafică – Mulţimea admisibilă

32

1000

500

Feasible

X2

Infeasible

3X1+4X22400

X1+X2 700 (redundantă)

500

700

X1-X2 350

2X1+X2 1000

X1

700

Analiza grafică – Mulţimea admisibilă

• Există trei tipuri de puncte admisibilePuncte interioare Puncte de frontieră Puncte extreme

33

Determinarea soluţiei optime

Start într-un punct ales arbitrar...

Apoi se creşte valoarea, dacă este posibil...

... și continuă până când devine imposibilă.

Soluţia = 4360

500

700

1000

500

X2

X1

X1 = 320

X2= 360

F(X) = 4360

Determinaţi valoarea minimă şi maximă a funţiei

F(x, y) = 4x + 3y

în prezenţa restricţiilor

y ≥ -x + 2

y ≤ x + 2

y ≥ 2x -5

1

4

Exemplul 3

6

4

2

53 4

5

1

1

2

3

y ≥ -x + 2

y ≥ 2x -5

y x 1

24

Vârfurile poliedrului convex:

F(x, y) = 4x + 3y

F(0, 2) = 4(0) + 3(2) = 6

F(4, 3) = 4(4) + 3(3) = 25

F( , - ) = 4( ) + 3(- ) = -1 = 7

3

1

3

1

3

7

3

28

3

25

3

f(0, 2) = 6 minimum

f(4, 3) = 25 maximum

37

Metoda simplex primal

Metoda geometrică nu poate fi extinsă la probleme PL

pentru care numărul de variabile de decizie este mai

mare de 3.

Această metodă reprezintă una dintre cele mai folosite

metode e rezolvare a problemelor de programare liniară.

• mulţimea soluţiilor admisibile este un poliedru convex;

• orice punct de extrem local este un punct de extrem global,

funcţia obiectiv fiind liniară;

• funcţia obiectiv fiind liniară, extremul se atinge într-unul

din vârfurile poliedrului soluţiilor admisibile.

Algoritmul metodei Simpex primal

Etapele principale ale metodei simplex sunt următoarele

Etapa 1. Calculul matricei G:

Etapa 2. Calculul diferenţelor Fj - Cj:

Etapa 3. Se analizează semnele diferenţelor Fj - Cj:

- dacă ( Fj – Cj ) > 0, atunci XB este o soluţie optimală;

- dacă ( Fj – Cj ) < 0, se trece la punctul următor.

Etapa 5. Se găseşte variabila k ce părăseşte baza cu relaţia:

Etapa 4. Se alege variabila de intrare în bază :

Etapa 6. Se formează o altă bază şi se reia calculul de la pasul

1, criteriul de oprire fiind cel specificat la pasul 3.