Forme equivalenti di problemi di PL
Ricordiamo che
max cx  - min –cx
ax  b  ax + s = b, s0 (slack di deficit)
ax  b  ax - s = b, s0 (slack di surplus)
x = (x+ - x-), x+ x- 0
ax = b  ax  b, ax  b
da max a min
da  a =
da  a =
da libera a vincolata 0
da = a  e 
Ogni risultato ottenuto per una forma particolare
ha validita’ generale, fatte le opportune variazioni
– Forma standard
Min cx : Ax=b, x0, xRn, ARmxn, m<n
– Forma canonica
Max cx: Axb, xRn, ARmxn, m>n
Si passa da un problema in forma canonica ad uno in forma standard
aggiungendo le variabili slack e
sostituendo x+,x- a ogni variabile x non vincolata in segno
 Sviluppiamo l’algoritmo per la forma standard senza perdita di generalita’
Ex portare in forma standard il modello dei telefonini
I telefonini in forma canonica
Max 3 x1 + 8 x2:
x1 + 2 x2  10
2 x1 + 2 x2  18
x1 + 3 x2  12
x 1, x 2  0
Il vettore c ∈ R2 e’ [ +3 +8]
a1
a2
a3
La matrice A ∈ R3x2
e’ cosi’ composta
1 2
2 2
1 3
I telefonini in forma standard
- Min - 3 x1 - 8 x2:
Il vettore c ∈ R5 e’ [ -3 -8 0 0 0 ]
x1 + 2 x2 + x 3
= 10
2 x 1 + 2 x2
+ x4
= 18
x1 + 3 x2
+ x5 = 12
x 1, x 2, x 3, x 4, x 5  0
a1
a2
a3
La matrice A ∈ R3x5
e’ cosi’ composta
1 2 1 0 0
2 2 0 1 0
1 3 0 0 1
Vertici del politopo
In R5 e’ [0,5,0,8,-3]
5
(0,5)
I vertici di P sono un sottoinsieme dei punti di intersezione dei vincoli.
Di questi, alcuni si trovano al di fuori della regione ammissibile, come i punti
(0,5) e (7.5, 1.5), mentre gli altri sono posizionati sulla frontiera del politopo.
Se calcoliamo il valore delle variabili slack nei punti (0,5) e (7.5, 1.5), alcune
risultano negative: ecco come distinguere i vertici del politopo tra i punti che
si trovano nell’intersezione dei vincoli, usando criteri algebrici.
a1: x1+2 x2  10
4
Ma cosa significa dal punto di vista algebrico
“stare sull’intersezione dei vincoli”?
(0,4)
3
a2: 2x1+2 x2  18
a3: x1+3 x2  12
In R5 e’ [7.5,1.5,0,0,-0.5]
2
(6,2)
(7.5, 1.5)
1
(8,1)
x2
(0,0)
(9,0)
0
0
x1
1
2
3
4
5
6
7
8
9 10
Il sistema Ax=b, x0 (forma standard) ha n-m gradi di liberta’
(hp A ha rango pieno, m righe e n colonne, n>m)
Osservazione:
Cosa significa?
Posso dare valore a piacere a n-m variabili e determinare l’unico valore delle restanti m
in modo tale che soddisfino i vincoli del sistema Ax=b
E’ una conseguenza
del teorema
di Rouche’ Capelli
m
Th Rouche’ Capelli:
{x: Ax=b}  r(A)=r(A|b)=r, con O(n-r) soluzioni
n-m
A
m
AB
AN
n
xB
=
b
xN
Stare sull’intersezione dei vincoli significa porre a 0 (n-m) variabili tali che le colonne delle restanti m siano
Linearmente Indipendenti (base per Rm), interpretarle come variabili di slack, e risolvere il restante sistema mxm
Ricordiamo che
al sistema Ax=b
possiamo applicare
le seguenti
trasformazioni…
•
•
•
•
Le operazioni precedenti sono possibili operando
trasformazioni equivalenti
per sistemi di equazioni lineari
che lasciano invariato l’insieme delle soluzioni ottime
Moltiplicare una riga ai per uno scalare a
Sommare alla riga aj la riga ai moltiplicata per uno scalare a
Scambiare di posto (permutare) le righe
Premoltiplicare per la stessa matrice entrambi i membri del sistema
Tali operazioni sono alla base del Metodo di Gauss-Jordan per
risolvere il sistema Ax=b:
trasformare il sistema in un sistema equivalente in cui la nuova matrice A
contiene le colonne della matrice identita’ Ir (dove r e’ il rango di A)
NB equivale a premoltiplicare entrambi i membri del sistema (Ax e b) per la
matrice AB-1, dove AB e’ composta dalle colonne di A che compongono la
matrice identita’ dopo la trasformazione di Gauss-Jordan.
Possiamo applicare tali trasformazioni anche per rappresentare le soluzioni di Ax=b
come i punti di un politopo P={xN: ANxN b } (il cui ottimo sappiamo essere in un vertice)
Rappresentazione delle soluzioni del sistema Ax=b
nello spazio delle variabili “fuori base”
Data la base B, rappresento le soluzioni del sistema {Ax=b, x0, xRn} nello spazio Rn-m
delle variabili fuori base N, come il politopo P = {xN: AB-1ANxN  AB-1b, xN0, xNRn-m }
Ax=b  ABxB + ANxN = b  AB-1ABxB + AB-1ANxN = AB-1b 
_
_
AB-1ANxN + xB = AB-1b  (vedo le xB come slack) AB-1ANxN  AB-1b  ANxN b
xN
AB-1AB = I
xB
+
AB-1AN

=
AB-1b
B e’ un insieme di indici di colonne di A che sono tra loro linearmente
indipendenti ( la sottomatrice AB e’ invertibile) e si dice una BASE
Come caratterizzare algebricamente i vertici del politopo P?
Abbiamo visto che sono punti in cui si azzerano n-m variabili, ma per essere
anche sulla frontiera di P occorre che l’unico valore delle restanti variabili sia 0.
La frontiera di P, per ogni vincolo di disuguaglianza,
e’ data dalle soluzioni del vincolo inteso come =, quindi
si puo’ interpretare come il luogo in cui
si azzera una variabile xi intesa come la variabile slack di quel vincolo
analogamente,
ogni vincolo di non-negativita’ xi0
gioca tale ruolo per la rispettiva variabile xi
Th:
ad ogni vertice del politopo P corrisponde una soluzione di base ammissibile
del sistema Ax=b nello spazio delle soluzioni Rn ottenuta uguagliando a 0
n-m variabili.
Equivale, nello spazio Rn-m, a porsi all’intersezione di n-m vincoli, inclusi
quelli di segno.
Perche’ e’ possibile fare questo?
Il prodotto matrice per vettore Ax equivale a fare
la combinazione lineare delle colonne di A
utilizzando come coefficienti moltiplicativi gli elementi del vettore x:
Ax = iAixi
Risolvere Ax=b equivale a cercare i coefficienti di una combinazione lineare
delle colonna di A che generino b nello spazio Rm.
Poiche’ A ha rango pieno, qualsiasi sottoinsieme di colonne Lin Indip di A
e’ sufficiente a generare b (i moltiplicatori delle restanti colonne sono 0)
xN
AB-1AB = I
xB
+
=
AB-1AN
AB-1b
xN=0
B e’ un insieme di indici di colonne di A che sono tra loro linearmente
indipendenti ( la sottomatrice AB e’ invertibile) e si dice una BASE
L’ammissibilita’ del problema in forma standard Ax=b, x0 richiede anche la condizione di
non negativita’ x0  non tutte le basi B corrispondono a una soluzione ammissibile ma
solo quelle per cui la combinazione lienare con cui generano b e’ anche una combinazione
CONICA (moltiplicatori x0)
Possiamo concludere che………
• Le soluzioni ammissibili di un problema di PL in forma standard
min {cx: Ax=b, x0} con A∊Rnxm, n>m,
sono i punti di un politopo P in Rn-m.
• Ogni politopo P e’ ottenibile come combinazione convessa dei suoi
vertici P={x: x=i xili, con ili=1, 0li 1}
• I punti di minimo(massimo) di una funzione lineare definita su un
politopo includono almeno uno dei vertici
Dim per assurdo (richiamo, gia vista)
– Ricordiamo la def di vertice (non essere esprimibile come combinazione
convessa di nessun altro punto)
– x* e’ ottimo ma non e’ vertice   dei moltiplicatori l per cui
x* =i xili, con ili=1 e 0li<1  i.
– Per la linearita’di cx, vale
cx* = c i xili, = i cxili, = i li (cxi) = i lici dove ci e’ il costo del vertice iesimo.
Allora o tutti i vertici con li>0 hanno lo stesso costo cx* oppure uno dei vertici
ha valore inferiore a cx* per cui x* non puo’ essere il punto di minimo.
• Per risolvere min {cx: Ax=b, x0} esamino solo i vertici del politopo
Caratterizzazione algebrica dei vertici di P
• I vertici di P sono posizionati all’  di n-m vincoli
vincoli attivi  soddisfatti come uguaglianza nel vertice
• Ogni vincolo di P e’ il luogo in cui si azzera la rispettiva variabile di
slack.
All’ di n-m vincoli si azzerano le slack corrispondenti (le n-m variabili
fuori base xN) mentre le variabili in base hanno un unico valore dato
dalla soluzione del sistema
AB xB = b  xB = AB-1b
dove AB e’ la sottomatrice di A data dalle colonne delle variabili in B
xB, unica soluzione al sistema, e’ soluzione ammissibile al problema e
vertice di P  sono verificati ANCHE i vincoli di non negativita’
xB = AB-1b  0
• QUINDI  non ogni base (subset di n-m colonne LI della matrice A)
indentifica un vertice di P ma solo le basi ammissibili  Occorre
verificare il requisito di non-negativita’ del vettore xB = AB-1b
In sintesi:
• La matrice dei vincoli A viene partizionata
A = AB, AN
(con AB invertibile )
AB si dice matrice di base, AN matrice fuori base,
• Ponendo a 0 le n-m variabili in N, si ottiene il sistema ABxB=b
che ammette come unica soluzione il vettore xB= AB-1 b
• Il vettore x= xB,xN con xN=0, xB= AB-1 b si dice soluzione di
base associata alla base B
• xB,xN e’ una soluzione di base ammissibile se xB0.
Caratterizzazione algebrica dei
vertici del politopo
esempio di
vertice
degenere
A meno di degenerazione
esiste una corrispondenza biunivoca
tra vertici del politopo P e
soluzioni di base ammissibili del sistema
Ogni vertice e’ determinato:
ponendo a 0 le variabili slack dei vincoli attivi (var. fuori base xN= 0)
risolvendo il sistema risultante xB= AB-1 b.
Enumerare i vertici  enumerare le basi ammissibili
Il problema della WyndorGlass
stessa struttura del problema dei telefonini..
Allocazione ottima di risorse limitate
in attivita’ concorrenti
3 reparti
• Produzione di telai in alluminio e
serramenta in metallo
• Telai in legno
• Vetro e assemblaggio
2 prodotti
• Porta in vetro con intelaiatura in alluminio
• Finestra con telaio di legno
Monte Ore
disponibile
4
12
18
Profitto
3
5
Tasso di impiego
(ore per lotto di prodotto)
stabilimento
p1
p2
1
2
1
0
0
2
3
3
2
Modello matematico di PL
Max 3 x1 + 5 x2:
 4
2 x2  12
3 x1 + 2 x2  18
x1
x 1, x 2  0
Forma compatta
max cx: Axb, x0
(a1
(a2
(a3
matrice A
1
0
3
0
2
2
vettore b
4
12
18
Rappresentazione geometrica
del politopo in R2.
m=3, n=5, n-m=2
x2
10
8
a2: x2  6
6
a1: x1  4
4
a3: 3x1+2 x2  18
C = [ 3, 5 ]
2
x1
0
1
2
4
5
6
8
in forma standard
Min – (3 x1 + 5 x2 + 0 x3 + 0 x4 +0 x5)
A1 A2 A3 A4
A5 (colonne)
x1
+ x3
= 4
2 x2
+ x4
= 12
3 x1 + 2 x2
+ x5
= 18
a1
a2
a3
xi  0  i=1,..,5
La matrice A ha rango pieno, e’ =
10100
02010
32001
Le basi sono sottomatrici 3x3 invertibili, ma non tutte sono ammissibili
100
010
001
associata
alle slack,
(sono a 0 x1 e x2)
ma non solo..
100
010
301
x2=x3=0
010
200
201
x1=x4=0
100
020
321
x3=x4=0
(x1=0)
10
Evidenziamo su quale vincolo
si annulla ciascuna variabile
8
a2: x2  6 (x4=0)
6
a1: x1  4 (x3=0)
4
Sui vertici si annullano
coppie di variabili (n-m)
a3: 3x1+2 x2  18 (x5=0)
2
0
1
2
4
5
6
8
(x2=0)
Vertici e basi per il problema WyndorGlass:
enumeriamo le basi su base combinatoria
e verifichiamo la corrispondenza con i vertici
A1
A2
A3
A4
A5
Punto x
Vertice
B
B
B
N
N
(2,6,2,0,0)
d
B
B
N
B
N
(4,3,0,6,0)
c
B
B
N
N
B
(4,6,0,0,-6)
g*
B
N
B
B
N
(6,0,-2,12,0)
h*
B
N
N
B
B
(4,0,0,12,6)
b
B
N
B
N
B
Rango 2
N
B
B
B
N
(0,9,4,-6,0)
f*
N
B
B
N
B
(0,6,4,0,6)
e
N
B
N
B
B
Rango 2
N
N
B
B
B
(0,0,4,12,18)
(0,9) f
x2
(0,6) e
(4,3) c
(0,9) a
a
Ricordo, A =
(4,6) g
(2,6) d
(4,0) b
(6,0) h
x1
10100
02010
32001
e
b = 4
12
18
Esercizio per casa:
per ogni scelta di m=3 colonne sulle 5 colonne di A, valutare se la sottomatrice quadrata 3x3
corrispondente e’ una matrice di base, e, se ammissibile, quale sia il vertice del politopo
associato
Esempio sul caso 1:
x4,x5 in N (x4,x5=0), ottengo il sistema
x1
+ x3 = 4
2x2
= 12
3x1 + 2x2
= 18
che ha come unica soluzione x2=6, x1=2, x3=2.
Il corrispondente vettore in R5 e’ x=[2,6,2,0,0] 
xi0  i=1..5, quindi B e’ una base ammissibile.
Dall’esame della rappresentazione geometrica del politopo, osserviamo che il
punto deve trovarsi all’intersezione dei vincoli a2 e a3 le cui variabili di scarto
sono fuori base (in N) e quindi sono poste a 0
La base B={1,2,3} (N={4,5} ) corrisponde al vertice d del politopo

la base B e’ ammissibile
Vertici adiacenti in P
• Vertici adiacenti in uno spazio Rn: condividono n-1 vincoli
• Le matrici di base di vertici adiacenti differiscono per 1
colonna
• Due vertici adiacenti giacciono lungo il medesimo
spigolo.
• Tale spigolo rappresenta una direzione di spostamento
lungo la frontiera del politopo da un vertice v1 a un
vertice adicente v2.
vertici adiacenti su di un politopo
Il politopo in figura e’ in Rn-m = R7-4 = R3
v1 e’ all’ dei 3 vincoli x1=2 (x4=0), x2=0,
x1+x2+x3=4 (x7=0) da cui x5=3, x3=2, x6=1
v2 e’ all’ dei 3 vincoli x1=2 (x4=0), x3=0,
x1+x2+x3=4 (x7=0) da cui x6=3, x2=2, x5=1
x3
da v1 a v2 e’ cambiata
una delle variabili
fuori base
sono x2, x4, x7 in v1
sono x3, x4, x7 in v2
V1 = [2,0,2,0,3,1,0]
Iperpiano x1=2
x1
V2 = [2,2,0,0,1,3,0]
slack x4
x5
x6
x7
x2
vertici adiacenti su di un politopo
Spostamento da v1 a v2, cambio di base:
In v1, B={x1,x3,x5,x6} e N={x2,x4,x7}
In v2, B={x1,x2,x5,x6} e N={x3,x4,x7}
x3
In entrambi i vertici, sono fuori base x4 e x7
Quindi lo spostamento avviene lungo lo spigolo d
all’ degli iperpiani (x1=2) e (x1+x2+x3=4)
V1 = [2,0,2,0,3,1,0]
Iperpiano x1=2
x1
d
V2 = [2,2,0,0,1,3,0]
Allontanandosi da v1 lungo la direzione d
x2 cresce (lungo d mi allontano da x2=0 nella
direzione del gradiente infatti
il prodotto scalare dT(gradiente x2)>0
Lungo d mi avvicino a x3=0 in direzione opposta
al gradiente del vincolo x3=0 la variabile x3
diminuisce, devo fermarmi quando x3=0
slack x4
x5
x6
x7
x2
Schema dell’algoritmo
• Input: un vertice v (una base ammissibile B)
• While ! opt test (v) do
– Selezionare una direzione di spostamento d lungo uno
spigolo tale che sia una direzione di miglioramento
della funzione obiettivo
– Spostarsi lungo d fino a che si resta nella ammissibilita’
(nuovo vertice w)
– v := w
NB
Spostarsi lungo uno spigolo 
mantenere attivi n-m-1 vincoli degli n-m attivi nel vertice
Il simplesso come local search
per (F,c,min) con F = {vertici di P}
• Inizializzazione (xF)
– k:=0, x0:=x, x*:=x0. {una soluzione di base ammissibile}
• Repeat:
– Genera N(xk)
– Foreach xN(xk) do
{insieme dei vertici adiacenti a xk}
If c(x)c(x*) and (x F) then x*:=x
– If x*xk
then k:=k+1, {se un vertice sulla fontiera di P, adiacente a x*,
xk:= x* ha valore di funzione obiettivo migliore di x*}
else STOP:=True
return(xk)
• Until STOP
Componenti dell’algoritmo
1.
Calcolo di un vertice ammissibile di partenza
2.
Test di ottimalita’ (ottimalita’ locale  globale per le
proprieta’ della programmazione convessa)
3.
Calcolo di una direzione di miglioramento lungo uno
spigolo (vado direttamente verso un vertice adiacente
migliore anziche’ esplorare tutto l’intorno dei vertici
adiacenti alla ricerca di un punto migliore)
4.
Calcolo del passo lungo la direzione di spostamento
(di quanto mi posso muovere restando nella regione
ammissibile?)