programmazione lineare: un esempio

Mix produttivo ottimo

con risorse vincolate

2 modelli in produzione

Modello A Modello B

Disponibilita’ dei componenti

10 MODULI DISPLAY

18 MODULI di MEMORIA

12 MODULI di TRASMISSIONE

21 TASTIERINE

9 TASTIERE di NAVIGAZIONE

10 MICROCAMERE

Utilizzo dei componenti

Modello A

1

1

2

1

2

1

3

Modello B

2

-

3

3

2

-

8

Componenti

Display

Tast navigazione

Tastiere a 6 tasti

Trasmissione

Memoria

MicroCamera

GUADAGNO

Modello di PLMax 3 xA + 8 xB:

xA + 2 xB 10 a1

2 xA + 2 xB 18 a2

xA + 3 xB 12 a3

2 xA + 3 xB 21 a4

xA 9 a5

xA 10 a6

xA, xB 0

In formamatriciale compatta

Max cx:Ax bx 0

Rappresentazione geometrica della regione ammissibile

xA

xB

1

2

3

4

5

01 2 3 4 5 6 7 8 9

a1: xA+2 xB 10

a3: xA+3 xB 12

a2: 2xA+2xB 18

10

xA0

xB0

a5: xA9

a6: xA10a4: 2xA+3 xB 21

Curve di iso-costo

xA

xB

1

2

3

4

5

01 2 3 4 5 6 7 8 9

A1: xA+2 xB 10

A3: xA+3 xB 12

A2: 2xA+2xB 18

10

c

3,3

cx=0

cx=16

cx=24

cx=32

cx=33

cx=34

• Gradiente: vettore ortogonale all’iperpiano tangente alla curva di livello (se la funzione c(x) e’ lineare coincide con il vettore dei coefficienti non dipende dal punto in cui viene calcolato).

• Curva di isocosto: insieme dei punti che hanno lo stesso valore della funzione obiettivo (se la funzione c(x) e’ lineare, la curva di isocosto e’ un iperpiano)

Condizione di ottimo: c = y1a1+y3a3, y0

xA

xB

1

2

3

4

5

01 2 3 4 5 6 7 8 9

a1: xA+2 xB 10

a3: xA+3 xB 12

10

C = [ 3, 8 ]

c appartiene al cono generato dai gradienti dei vincoli a1 e a3

y R2, y0, tale che cT = yT

dove a1=[1, 2], a3=[1,3]

y risolve il sistema 1 1 y1 3

con y0 2 3 y2 8

y = a1 a2 -1 c = =

a1

a3

=

1

2

3 -1

-2 1

3

8

Vertici (punti estremi) del politopo

xA

xB

1

2

3

4

5

01 2 3 4 5 6 7 8 9

a1: xA+2 xB 10

a3: xA+3 xB 12

a2: 2xA+2xB 18

10

(0,0)

(0,4)

(0,5)

(6,3)

(6,2)

(8,1)

(9,1)

0

(9,0)

(9,½)

(7.5, 1.5)

Idee base dell’algoritmo• L’ottimo (se esiste finito) coincide con (almeno)

un vertice del politopo

• Possiamo definire delle condizioni di ottimalita’ in base alla geometria dei vettori

• Per implementare un algoritmo dobbiamo fornire una descrizione algebrica dei vertici.

Forniamo un supporto teorico a queste intuizioniForniamo un supporto teorico a queste intuizioni

Combinazione convessa di due punti x, y

z=x + (1-)y, con [0,..1]

combinazione convessa stretta per (0,..,1)

Programmazione convessaProgrammazione convessarichiami di

Generalizzando a n punti

Dati k punti x1,..,xk Rn, il punto z in Rn e’ combinazione convessa di x1,..,xk se esistono k scalari 0, 1,..,k tali che i=1,k i xi = z

Altri tipi di combinazioni

• Combinazione affine (+,R)

• Combinazione conica (,0, in R)

• Combinazione lineare (,R)

Un insieme si dice convesso

se contiene tutte le combinazioni convesse dei propri punti

xy

xy

di insiemi convessi e’ convessa

Una funzione f:X→R si dice convessa se

x,yX, [0,1],

chiamando z = x + (1-)y

la combinazione convessa di x e y,

allora

f (z) f(x) +(1-) f(y)

Le funzioni lineari Le funzioni lineari sono funzioni convesse sono funzioni convesse

x z y

f(y)

f(x)

f(z)

f(x) + (1-)f(y)

risultati• TH:

Sia X = {x Rn: gi(x) 0, i=1,..,m} e gi(x) sia convessa i, allora l’insieme X e’ convesso(la regione ammissibile definita dalle soluzioni di un sistema di funzioni convesse e’ convessa)

• Def: problema di programmazione convessa

min {f(x) : xX} dove XRn

e’ convesso, f:X→R e’ convessa

• TH: Dato un problema di programmazione convessa, ogni punto di ottimo locale e’ un punto di ottimo globale

• Dato un vettore aRn e uno scalare a0R, si dice – semispazio affine indotto da (a,a0) l’insieme X={xRn :

axa0}– iperpiano indotto da (a,a0) l’insieme X={xRn : ax=a0}

• Poliedro PRn: di semispazi e iperpiani (politopo se limitato)

• Un punto xP si dice vertice o punto estremo di P se non e’ esprimibile come combinazione convessa stretta di nessuna coppia di punti di P.

Richiami di algebra lineare

• Faccia: HPP dove HP e’ un iperpiano tangente a P e PRn.

• Faccetta: faccia di dimensione n-1.

• Spigolo (lato): faccia di dimensione 1.

• Vertice (punto estremo): faccia di dimensione 0

Facce, vertici e spigoli di un politopo

Si puo’ dimostrare che …

• Th di Minkowski-Weyl:Un politopo P e’ esprimibile come combinazione convessa dei suoi vertici(+ la combinazione conica dei suoi raggi estremi per poliedri non limitati)

• Se P e’ limitato, allora esiste almeno un vertice di P che e’ soluzione ottima del problema di programmazione lineare min {cx : xP} / max {cx : xP}

In breve

• P e’ un insieme convesso, esprimibile come combinazione convessa dei suoi vertici

• Th: il problema min {cx : xP} ha ottimo (se esiste finito) su di un vertice

• Th: e’ sufficiente l’ottimalita’ locale del punto per dimostrarne l’ottimalita’ globale

Per implementare un algoritmoalgoritmo occorre fornire

– una caratterizzazione algebrica dei vertici – delle condizioni di ottimalita’– una regola per spostarsi su un vertice

(adiacente) con miglior valore della funzione obiettivo