Cursul 1 1

Problematica optimizării

Dificultăţi de abordare şi/sau rezolvare

Planul de învăţământ (= 14 săptămâni)

Optimizare liniară

ANTON BĂTĂTORESCU

Cursul 1 2

Optimizare liniară

CURS = 2 ORE / SĂPTĂMÂNĂ

SEMINAR = 2 ORE / SĂPTĂMÂNĂ

FORMA DE EXAMINARE: verificare ! (scris)

• 2 subiecte de teorie: – enunţuri cu demonstraţii;

– enunţuri descriptive.

• 1 exerciţiu de seminar (cu subpuncte)

Cursul 1 3

Conţinutul cursului:

Teorema fundamentală a programării liniare.

Teoremele algoritmului simplex primal.

Algoritmul simplex. Formule de schimbarea bazei.

Determinarea unei baze primal admisibile. Metoda celor două faze.

Sisteme liniare de inegalităţi. Lema Farkaş-Minkowski.

Dualitate în programarea liniară. Teoreme de dualitate.

Algoritmul simplex dual.

Problema transporturilor.

Postoptimizare şi programare liniară parametrică.

Programare liniară în numere întregi.

Cursul 1 4

Bibliografie

A. Ştefănescu, C. Zidăroiu, "Cercetări Operaţionale",

Ed. Didactică şi Pedagogică, Bucureşti, 1981.

C. Zidăroiu, “Programare liniară", Ed. Tehnică, Bucureşti, 1984.

A. Bătătorescu, "Metode de optimizare liniară", Ed. Universităţii

din Bucureşti, 2003.

R.J. Vanderbei, ”Linear Programming: Foundations and

Extensions”, Springer, New York, 2008.

V. Preda, M. Bad, "Culegere de probleme de cercetări

operaţionale", Tipografia Universităţii din Bucureşti, 1978.

http://www.ilog.com/

http://www.maximalsoftware.com/

Cursul 1 5

Problema 1. Un complex de locuinţe trebuie să cuprindă cel puţin 900 garsoniere,

2100 apartamente cu două şi 1400 apartamente cu trei camere.

Să se stabilească câte blocuri de fiecare fel trebuie construite astfel

încât cheltuielile de construcţie să fie minime.

Bloc tip A

4 mil €

Bloc tip B

5 mil €

10

garsoniere

30

ap. 2 cam.

40

ap. 3 cam.

30

garsoniere

50

ap. 2 cam.

20

ap. 3 cam.

Cursul 1 6

Modelul matematic

Variabilele de decizie:

x = numărul de blocuri de tipul A

y = numărul de blocuri de tipul B

Funcţia obiectiv: Costul = 4 x + 5 y ;

trebuie minimizat !

Restricţiile:

garsoniere: 10 x + 30 y >= 900 ;

ap. cu 2 camere: 30 x + 50 y >= 2100 ;

ap. cu 3 camere: 40 x + 20 y >= 1400 ;

Condiţii implicite (naturale): x şi y >= 0 şi în plus, numere întregi.

Cursul 1 7

Problema 2. O secţie a unei fabrici produce două tipuri de aparate.

Pentru aceasta trebuie să comande zilnic piese din care s-ar putea face,

în combinaţie, cel puţin, 80 de aparate de primul tip sau 60 de

aparate de al doilea tip.

Capacitatea de montaj este de cel mult 100 de aparate pe zi din

ambele tipuri.

La vânzare sunt solicitate zilnic cel puţin 40 de aparate de primul tip şi

cel puţin 20 de aparate de al doilea tip.

Pentru realizarea unui aparat de primul tip se cheltuiesc 200 €, iar

pentru un aparat de al doilea tip, 400 €.

Să se stabilească planul de producţie zilnic care se realizează cu

minimum de cheltuieli.

Cursul 1 8

Modelul matematic

Variabilele de decizie:

x = numărul de aparate de primul tip

y = numărul de aparate de al doilea tip

Funcţia obiectiv: Costul = 200 x + 400 y ; să fie minim !

Restricţiile:

comanda: x/80 + y/60 >= 1 ; capacitate: x + y <= 100 ; limita inferioară x: 40 <= x ; limita inferioară y: 20 <= y ;

Condiţii implicite (naturale): x şi y să fie numere întregi.

Cursul 1 9

Problema 3. Se consideră un sistem comercial format din două uzine, patru depozite şi

şase clienţi.

Să se determine o distribuţie de cost minim a mărfurilor între uzine, depozite

şi clienţi cunoscând următoarele:

C1

C2

C4

C5

C6

C3

U2

U1

D2

D1

D3

D4

Cursul 1 10

Datele problemei:

Capacitatea de producţie a uzinelor este: u1 = 150, u2 = 200;

Capacitatea de stocare a depozitelor este: d1 = 70, d2 = 50, d3 = 100, d4 = 40;

Cererea clienţilor este: c1=50, c2=10, c3=40, c4=35, c5=60, c6=20;

Costul unitar de transport al mărfii de la uzine la depozite este: u1, d1, 0.5, u2, d2, 0.3, u1, d2, 0.5, u2, d3, 0.5, u1, d3, 1.0, u2, d4, 0.2, u1, d4, 0.2

Costul unitar de transport al mărfii de la uzine la clienţi este: u1, c1, 1.0, u1, c3, 1.5, u1, c4, 2.0, u1, c6, 1.0, u2, c1, 2.0

Costul unitar de transport al mărfii de la depozite la clienţi este: d1, c2, 1.5, d2, c1, 1.0, d3, c2, 1.5, d4, c3, 0.2, d1, c3, 0.5, d2, c2, 0.5, d3, c3, 2.0, d4, c4, 1.5, d1, c4, 1.5, d2, c3, 0.5, d3, c5, 0.5, d4, c5, 0.5, d1, c6, 1.0, d2, c4, 1.0, d3, c6, 1.5, d4, c6, 1.5, d2, c5, 0.5

Cursul 1 11

CERINŢE:

Să se afle costul de transport al mărfurilor între:

Uzine şi depozite:

Uzine şi clienţi;

Depozite şi clienţi.

Capacitatea de producţie a fiecărei uzine să nu fie depăşită;

Capacitatea de stocare a fiecărui depozit să nu fie depăşită;

Cantitatea de marfă ce intră în fiecare depozit (de la uzine) să fie egală

cu cea trimisă către clienţi;

Cantitatea solicitată de fiecare client să fie exact satisfăcută.

Modelarea matematică

Cursul 1 12

MPL (Mathematical Programming Language) este un sistem de

programare care permite descrierea într-un mod simplu şi eficient a

unor modele de optimizare complicate.

Programele realizate în MPL pot fi rezolvate cu diferite produse

software de optimizare (“solver”):

Solver Supported Algorithms

CPLEX LP, MIP, BAR, MIQP

XPRESS LP, MIP, BAR, MIQP

GUROBI LP, MIP

Lindo LP, MIP, BAR, NLP,

MIQP, MINLP

MOPS LP, MIP, BAR

FortMP LP, MIP, BAR, MIQP

Solver Supported Algorithms

CoinMP LP, MIP

GLPK LP, MIP, BAR

LPSolve LP, MIP

CONOPT LP, NLP

KNITRO LP, NLP

LGO NLP, Global

Cursul 1 13

Cursul 1 14

Cursul 1 15

Cursul 1 16

Cursul 1 17

Cursul 1 18

Cursul 1 19

Exemplu – optimizare neliniară 4 3 2: , 2 1 3 5 7 5 31 30f f x x x x x x x x x

Cursul 1 20

4 3 2: 0, 5.6 , 7 5 31 30f f x x x x x

Cursul 1 21

Exemplu – optimizare liniară

2 3 , unde min maxoptim x y optim

Cu îndeplinirea condiţiilor:

Să se determine:

4

8 2 3

5 3 15

2 10

2 16

x y

x y

x y

x y

x y

Cursul 1 22

Rezolvare grafică

107.552.50-2.5

10

7.5

5

2.5

0

-2.5

x

y

x

y

Cursul 1 23

Rezolvare grafică

107.552.50-2.5

10

7.5

5

2.5

0

-2.5

x

y

x

y

Cursul 1 24

Rezolvare grafică

107.552.50-2.5

10

7.5

5

2.5

0

-2.5

x

y

x

y

Cursul 1 25

Rezolvare grafică

107.552.50-2.5

10

7.5

5

2.5

0

-2.5

x

y

x

y

Cursul 1 26

Rezolvare grafică

107.552.50-2.5

10

7.5

5

2.5

0

-2.5

x

y

x

y

Cursul 1 27

Rezolvare grafică

Cursul 1 28

Rezolvare grafică

Cursul 1 29

Rezolvare grafică

Cursul 1 30

Notaţii şi câteva definiţii

Vom nota cu o matrice cu m linii şi n coloane: m nA

11 12 1

21 22 2

11

1 2

n

n

i mijj n

m m mn

a a a

a a aA a

a a a

, 1 ,1 ,ija i m j n unde,

Transpusa matricei A o vom nota cu .n mA f

Mulţimea matricelor de aceeaşi dimensiune formează un spaţiu

vectorial peste corpul numerelor reale.

1 11 1

, , , ,m n

i m i mij ij ijj n j n

A B A B a b B b

Cursul 1 31

Produsul matricelor: este matricea: ,m k k nA B

1

1 , 1, , .k

m n

ij il lj

l

i m j nA B C c a b

Determinantul unei matrice pătratice este numărul n nA

1 1 2 2det

n

n nA a a a

S

Dacă matricea A se numeşte nesingulară, iar în acest

caz, există o unică matrice A-1 numită matrice inversă:

det 0,A

1 1

1 0 0

0 1 0

0 0 1

n n

nA A A A

I

Cursul 1 32

Un vector coloana este considerat ca fiind o matrice

iar transpusa acesteia este un vector linie.

nv 1,nv

1

2

1 2, , , , n

n

v

vv v v v v

v

f

Produsul scalar a doi vectori

1

, , .n

n

i i

i

x y x y x y y x

f f

pentru orice

pentru orice

1, ,

1,

i i

i

n

i

x y x y i n

x y x y i n y x

Definim relaţiile:

În particular, 0, 1, .n

ix x i n 0

Cursul 1 33

Sisteme de ecuaţii liniare

11 1 12 2 1 1

21 1 22 2 2 2

1 1 2 2

n n

n n

m m mn n m

a x a x a x b

a x a x a x bA x b

a x a x a x b

Fie: şi considerăm sistemul de ecuaţii liniare: ,m n mA b

nxunde reprezintă vectorul necunoscutelor.

Notăm:

1 2

1 2

, , , linia '' '' a matricei ;

, , , coloana '' '' a matricei .

i i i in

j

j j mj

A a a a i A

A a a a j A

f

1

, 1, .n

j

i i j

j

A x b A x b i m A x b

Cursul 1 34

Teorema Kronecker-Capelli :

Ecuaţii principale, respectiv variabile principale.

Ecuaţii secundare, respectiv variabile secundare.

Prin eliminarea ecuaţiilor secundare, considerăm:

Pentru m = n, avem soluţia unică:

Pentru m < n, avem o infinitate de soluţii.

Există m coloane liniar independente ale matricei A, care formează

o matrice de bază:

Restul coloanelor formează matricea R.

min ,rang A rang A b r m n

.rang A m n

1 .x A b

1 2 ... .mss sB A A A

Cursul 1 35

Partiţionarea matricei: .A B R

Notăm mulţimea de indici corespunzătoare coloanelor lui B cu

1 2, ,..., ,ms s sB

iar mulţimea de indici corespunzătoare coloanelor lui R cu

1,2,..., \ .nR B

Partiţionarea variabilei în care, , ,nx

x xx

B

R

1 2, ,...,

m

m

i s s six x x x x

B B

f

variabile de bază (principale)

n m

j jx x

R R variabile secundare

Cursul 1 36

1 1A x b B x R x b x B b B R x B R B R

Vectorul se numeşte soluţie a sistemului dacă nv .A v b

O soluţie a sistemului este numită soluţie de bază, dacă

componentele ei diferite de zero corespund unor coloane liniar

independente ale matricei A.

Deoarece rang(A) = m, cel mult m componente ale unei soluţii de

bază pot fi nenule. Dacă soluţia de bază are exact m componente

nenule, ea se numeşte nedegenerată; în caz contrar ea se numeşte

degenerată.

Pentru orice bază B, se poate obţine o soluţie de bază:

1B bvv

v

0

B B

R R