programmazione lineare:
un esempio
Mix produttivo ottimo
con risorse vincolate
Materiale di studio:
M. Fischetti, Lezioni di RO, Cap. 3. Libreria Progetto PD
D. Bertsimas, Introduction to linear optimization, Cap 2. MIT Athena Scientific
Modello A
Modello B
2 modelli in produzione
10 MODULI
DISPLAY
9 TASTIERE di
NAVIGAZIONE
21
TASTIERINE
18 MODULI di
MEMORIA
12 MODULI di
TRASMISSIONE
10
MICROCAMERE
Disponibilita’ dei componenti
Utilizzo dei componenti
Componenti
Modello A
Modello B
Display
Tast navigazione
Tastiere a 6 tasti
Trasmissione
Memoria
MicroCamera
1
1
2
1
2
1
2
3
3
2
-
GUADAGNO
3
8
Modello di PL
Max 3 xA + 8 xB:
xA + 2 xB  10
2 xA + 2 xB  18
xA + 3 xB  12
2 xA + 3 xB  21a4
xA
 9
xA
 10
xA, xB  0
a1
a2
a3
a5
a6
In forma
matriciale
compatta
Max cx:
Ax  b
x0
xB
5
Rappresentazione geometrica della
regione ammissibile
a1: xA+2 xB 10
a6: xA10
a4: 2xA+3 xB 21
4
3
a5: xA9
a3: xA+3 xB 12
2
1
xA0
xB0
a2: 2xA+2xB  18
0
1
2
3
4
5
xA
6
7
8
9 10
Curve di iso-costo
xB
A1: xA+2 xB  10
5
A3: xA+3 xB  12
4
A2: 2xA+2xB  18
cx=33
3
3,3
cx=34
cx=24
2
cx=16
1
cx=32
c
0
cx=0
1
2
3
4
5
6
7
8
xA
9 10
• 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, y0
5
xB
a1: xA+2 xB  10
4
3
a3: xA+3 xB  12
2
1
C = [ 3, 8 ]
0
1
2
3
4
5
6
7
8
xA
9 10
Condizione di ottimalita’: c appartiene al cono
generato dai gradienti dei vincoli (attivi) a1 e a3
 y R2, y0, tale che cT = yT a1
dove a1=[1, 2], a3=[1,3]
a3
y risolve il sistema
con y0
y = a1 a2
-1
c =
1
2
1
3
y1
y2
3 -1
3
-2 1
8
=
vettori riga
della matrice A
=
3
8
1
2
L’unica soluzione del sistema si ottiene invertendo la sotto-matrice dei vincoli
xB
Vertici (punti estremi) del politopo
Sono un sottonsieme dei punti di intersezione dei vincoli, alcuni
dei quali si trovano al di fuori della regione ammissibile (politopo)
(0,5)
5
a1: xA+2 xB  10
a2: 2xA+2xB  18
4
(0,4)
(6,3)
3
a3: xA+3 xB  12
2
(6,2)
(7.5, 1.5)
(9,1)
1
(8,1)
(0,0)
(9,0)
0
0
(9,½)
1
2
3
4
5
6
7
8
xA
9 10
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.
• Abbiamo osservato che siano i punti di intersezione dei vincoli che
si trovano sulla frontiera del politopo.
Forniamo un supporto teorico a queste intuizioni
Prima occorre fare alcuni richiami per contestualizzare la
programmazione lineare come caso particolare della
programmazione convessa, di cui eredita tutte le proprieta’
Programmazione convessa
richiami di
Combinazione convessa di due punti x, y
z=lx + (1-l)y, con l[0,..1]
combinazione convessa stretta per l(0,..,1)
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, l1,..,lk tali che i=1,k li xi = z
Altri tipi di combinazioni
• Combinazione affine (l1+l2=1, l1,l2R)
• Combinazione conica (l1,l20, in R)
• Combinazione lineare (l1,l2R)
Un insieme si dice convesso
se contiene tutte le combinazioni
convesse dei propri punti
x
y
 di insiemi convessi e’ convessa
x
y
Una funzione f:X→R si dice convessa se
x,yX, l[0,1],
chiamando z = lx + (1-l)y
la combinazione convessa di x e y,
allora
f (z)  l f(x) +(1-l) f(y)
lf(x) + (1-l)f(y)
f(y)
f(x)
f(z)
x
z
y
Le funzioni lineari
sono funzioni convesse
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) : xX} dove
XRn 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
Richiami di algebra lineare
• Dato un vettore aRn e uno scalare a0R, si
dice
– semispazio affine indotto da (a,a0) l’insieme X={xRn
: axa0}
– iperpiano indotto da (a,a0) l’insieme X={xRn : ax=a0}
• Poliedro PRn:  di semispazi e iperpiani
(politopo se limitato)
• Un punto xP si dice vertice o punto estremo di
P se non e’ esprimibile come combinazione
convessa stretta di nessuna coppia di punti di P.
• Faccia: HPP dove HP e’ un iperpiano
tangente a P e PRn.
• 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 : xP} / max {cx : xP}
In breve
• P e’ un insieme convesso, esprimibile come
combinazione convessa dei suoi vertici
• Th:
il problema min {cx : xP} 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 algoritmo occorre fornire
– una caratterizzazione algebrica dei vertici del politopo
– delle condizioni di ottimalita’ per certificare di avere determinato
una soluzione ottima
– una regola per spostarsi su un vertice (adiacente) con miglior
valore della funzione obiettivo (una mossa) se le condizioni di
ottimalita’ non sono soddisfatte
– un test per verificare che esista un ottimo finito