Il simplesso in forma tabellare
Cap 3.2.4 Fischetti pg 33-36
Il metodo del tableau
• E’ d’uso presentare l’algoritmo del simplesso
come una sequenza di operazioni algebriche su
una tabella che riporta la matrice dei vincoli, il
vettore b e, come riga aggiuntiva, il vettore dei
costi ridotti e il valore della funzione obiettivo
nella soluzione corrente
• Formato di riferimento forma standard
Min cx: Ax=b, x0
Formato iniziale del tableau
x1 x2 .. xm xm+1 … xn
Riga 0
Riga 1
..
..
Riga m
Vettore dei costi
z
b
-1
0
0
0
0
Matrice A
0
0
0
b
Formato del tableau al passo k
Riga 0
x1 x2 .. xm xm+1 … xn z
0 … 0 cN-cBAB-1AN -1
AB-1b
-cBAB-1b
Riga 0 = Vettore dei costi ridotti
Riga 1
..
..
Riga m
AB-1 AB= I
AB-1 AN
B
xB
Le colonne sono opportunamente riordinate per affiancare a sx le colonne della base
In rosso sono evidenziate le colonne in base ( B), in blu quelle fuori base ( N)
Si aggiunge una colonna ausiliaria che evidenzia le variabili in base, mentre alla riga 0
nella colonna del termine noto compare il valore corrente della funzione
obiettivo cambiato di segno, inteso come il vincolo cx –z = 0
esempio
•
•
•
•
•
Min -13 x1 – 10 x2:
3 x1 + 4 x2 + x3 = 24
x1 + 4 x2 + x4 = 20
3x1 + 2 x2 + x5 = 18
xi  0
Esempio: usiamo i colori
per denotare le variabili in B e in N
c. red.
Riga 1
Riga 2
Riga 3
x1
x2 x3
-13 -10 0
3 4 1
1
4 0
3
2 0
x4
0
0
1
0
x5
0
0
0
1
z AB-1b
-1
0
x3 24
x4 20
x5 18
La base corrente e’ data dagli indici {3,4,5} mentre sono fuori base x1 e x2.
La soluzione di base associata ha valore x =[0,0,24,20,18] con costo pari a 0.
La tabella e’ gia in forma canonica rispetto alla base corrente (premoltiplicata
per l’inversa della matrice di base, e il vettore dei costi azzerato nelle componenti in B)
Le operazioni utilizzabili sono quelle invarianti rispetto alle soluzioni.
Entrambe le variabili fuori base hanno costo ridotto <0,
scelgo la variabile con indice minore x1 (ininfluente)
c. red.
Riga 1
Riga 2
Riga 3
x1
x2 x3
-13 -10 0
3 4 1
1
4 0
3
2 0
x4
0
0
1
0
☹
x5
0
0
0
1
z AB-1b
-1
0
x3 24
x4 20
x5 18
Per determinare l’indice della variabile uscente devo calcolare il minimo rapporto
tra il valore corrente della variabile i-esima della base e la componente i-esima della
colonna della variabile entrante, per le sole componenti >0.
Minimo {24/3, 20/1, 18/3} = 6  esce x5. Devo fare pivot su a31 in modo tale che
la colonna entrante A1 prenda la forma della colonna uscente A5 (dividere la III riga per
3, poi sommarla alla II moltiplicata per -1, e sommarla alla riga I moltiplicata per -3)
e azzerare il costo ridotto (sommarla alla riga 0 moltiplicata per 13)
Base corrente B={1,3,4}
☹
c. red.
Riga 1
Riga 2
Riga 3
x1 x2 x3
0 -4/3 0
0 2 1
0 10/3 0
1 2/3 0
x4 x5
0 13/3
0 -1
1 -1/3
0 1/3
z AB-1b
-1 78
x3 6
x4 14
x1 6
Facendo pivot su a31 ho trasformato A1 nella colonna 3 della matrice identita’ e
azzerato il suo costo ridotto
Ora solo x2 ha costo ridotto <0: entra x2 e devo calcolare il minimo rapporto
per determinare la variabile uscente.
Min {6/2, 14.3/10, 6.3/2}=3, esce x3 e faro’ pivot sull’elemento a12.
Base corrente B={1,2,4}
c. red.
Riga 1
Riga 2
Riga 3
x1
0
0
0
1
x2 x3 x4 x5
0 4/6 0 11/3
1 1/2 0 -1/2
0 -10/6 1 8/6
0 -1/3 0 0
z AB-1b
-1 82
x2 3
x4 4
x1 4
Facendo pivot su a12 ho trasformato A2 nella colonna 1 della matrice identita’ e
azzerato il suo costo ridotto
Tutti i costi ridotti sono 0 la soluzione corrente x = [4,3,0, 4,0] e’ ottima, di costo -82.
Esercizi:
Risolvere con il metodo del tableau
i seguenti problemi di PL:
• Min - 5x1 - 7x2:
2x1 + x2  8
x1 + 2x2  9
x1 + x 2  5
x1,x2  0
• Max 2x1 + 5x2:
x1 - 4x2  8
-x1 + x2  6
-3x1 + 2x2  5
x1,x2  0
Analisi post ottimale
Compito
Obiettivo
Tecnica
Debugging del modello
Trovare errori, mancanze e punti
deboli del modello
Riottimizzazione
Validazione del modello
Dimostrarne la validita’
Allocazione ottima delle
risorse (vettore b)
Destinare il giusto quantitativo di
risorse a ciascuna attivita’
Soluzione di
successive varianti
Prezzi ombra
Individuare i parametri critici da
Valutare le stime dei
stimare con maggiore
parametri del modello
precisione
Definire i trade-off tra i
parametri del modello
Trovare il miglior trade-off
Analisi di sensisitivita’
Programmazione
lineare parametrica
riottimizzazione
• I problemi reali hanno dimensioni consistenti
(O(104) variabili e vincoli) di cui puo’ essere
necessario esaminare e risolvere diverse
varianti, in fase di messa a punto (debugging)
del modello.
• Durante la fase di validazione si eseguiranno
anche numerosi test su dati passati per
confrontare le soluzioni del modello con quelle
effettive, prese nella realta’
riottimizzazione
• Quando si devono risolvere numerose varianti di un
modello tra loro leggermente diverse, anziche’ ripartire
ogni volta da capo (from scratch), quando e’ possibile,
risulta + conveniente effettuare una ripartenza a caldo
(warm start), a partire dalla soluzione ottima del modello
precedente x*.
• se x* e’ ancora una soluzione di base ammissibile del
nuovo modello ma non piu’ ottima (ad esempio, per
l’introduzione di una nuova variabile) si applica il
simplesso primale, altrimenti, se e’ ancora di base ma
non ammissibile (ad esempio per l’introduzione di un
nuovo vincolo) si applica il simplesso duale
Introduzione di una nuova variabile xn+1:
cosa cambia?
• Aggiungo una colonna al tableau, la
soluzione corrente e’ ancora ammissibile
nel nuovo spazio Rn+1, intendendo la
nuova variabile fuori base a valore 0.
• Da x*  Rn passo a x’=[x*,0]  Rn+1
• Devo calcolare il costo ridotto di xn+1 per
verificare se x’ e’ ottima. Se no, applico il
simplesso primale
Base corrente B={1,2,4}
c. red.
Riga 1
Riga 2
Riga 3
x1
0
0
0
1
x2 x3 x4 x5
0 4/6 0 11/3
1 1/2 0 -1/2
0 -10/6 1 8/6
0 -1/3 0 0
z -cB AB-1b
-1 82
x2 3
x4 4
x1 4
la soluzione corrente x = [4,3,0, 4,0] in R5 e’ ottima, di costo -82.
Inserisco una nuova variabile x6, di cui e’ nota
la colonna A6 nella matrice originaria e il costo c6
c. red.
Riga 1
Riga 2
Riga 3
x1
0
0
0
1
x2 x3 x4 x5
0 4/6 0 11/3
1 1/2 0 -1/2
0 -10/6 1 8/6
0 -1/3 0 0
x6
_
c6
a16
a26
a36
z -cB AB-1b
-1 82
x2
x4
x1
3
4
4
la colonna A6 puo’ essere aggiunta al tableau e portata nella forma AB-1A6
tramite le consuete operazioni elementari.
il costo ridotto c6- cB AB-1A6 deve venire calcolato from scratch, e poi inserito
in tabella. Se risolta <0 allora x6 entra in base altrimenti la soluzione ottima
non cambia (x6=0)
Aggiungo un nuovo vincolo am+1x=bm+1:
cosa cambia?
Consideriamo nuovamente la rappresentazione della regione
ammissibile del problema della WinDoorGlass, con ottimo in x*.
Introduco il vincolo a4 : e’ rispettato da x* che resta ottimo
Se introduco il vincolo a5 poiche’ questo e’ violato da x*, allora
x* diventa NON AMMISSIBILE ☹  devo applicare un passo
del simplesso duale per determinare il nuovo vertice ottimo x’
x2
10
8
a5: x1 + 5/6x2  6
(x7=0)
6
a2: x2  6
(x4=0)
X*
x’
a1: x1  4
(x3=0)
a4: x1 - x2  3
(x6=0)
4
x1=0
a3: 3x1+2 x2  18
(x5=0)
2
x1
x2=0
0
1
2
4
5
6
8
Prezzi ombra
• Interpretazione del problema come allocazione ottima di
risorse limitate (1 vincolo   risorsa) in quantita’ b (rhs)
• Il livello disponibile bi puo’ essere una decisione
reversibile alla luce dell’impatto sulla soluzione ottima
• ? Quanto sarei disponibile a pagare per ottenere 1 unita’
supplementare per la risorsa i?
• In un sistema di equilibrio, il prezzo unitario e’ tanto
quanto permette di migliorare il valore ottimo della
funzione obiettivo 
prezzo ombra della risorsa = suo valore marginale
Primo caso:
Risorsa eccedente nel punto di ottimo:
valore marginale della risorsa NULLO
(il vincolo relativo alla specifica risorsa
non e’ aderente al punto di ottimo corrente):
xB
10
8
a2: xB  6
6
traslare l’iperpiano
associato al vincolo
xA  4 (diventa xA5)
non modifica
le coordinate di x*
a1: xA  4
4
C = [ 3, 5 ]
2
a3: 3xA+2 xB  18
0
1
2
4
5
6
8
xA
Secondo caso:
Risorsa esaurita nel punto di ottimo
• Se la slack della risorsa si annulla
nell’ottimo x*, il vincolo e’ aderente al
punto di ottimo.
• Sia x’ l’ottimo disponendo di 1 unita’
supplemetare della risorsa i (spostando il
vincolo i parallelo a se stesso, le
coordinate del punto di ottimo cambiano
da x* a x’).
Risorsa esaurita nel punto di ottimo:
(il vincolo della risorsa e’ aderente al punto di ottimo corrente):
xB
valore marginale della risorsa >0
10
8
x’
a2: xB  6
6
traslare l’iperpiano
associato al vincolo
xB  6 (diventa xB7)
modifica il punto di ottimo
da x* a x’
(ma non la base, in questo caso,
poiche’ restano attivi sia a2 che a3)
x*
a1: xA  4
4
a3: 3xA+2 xB  18
C = [ 3, 5 ]
2
0
1
2
4
5
6
8
xA
Valutazione dell’incremento  della funzione obiettivo
in seguito all’incremento unitario di una componente dei rhs
Hp: la base ottima B non cambia quidi xN resta a 0
(i vincoli attivi in x* e in x’ sono i medesimi)
il vettore dei rhs e’ cambiato da b a b’=(b+ei) quindi xB= AB-1 b’
La variazione della funzione obiettivo e’ data da
 = cx’-cx* = c (x’-x*) =
c ([AB-1 b’,0]T - [AB-1b,0]T) = cBAB-1(b’-b) =
cBAB-1(b+ei-b) = cBAB-1ei = yi  0
Il prezzo ombra della risorsa e’ la componente i-esima del
prodotto cBAB-1 (comando getdual(vincolo) in Mosel)
Vedremo nel seguito come a questa quantita’
corrisponda una precisa variabile nello spazio duale
Esercizio
Calcolare i prezzi ombra y delle 3 risorse del problema della
WindorGlass, verificando che sono nulli per le risorse che
non si esauriscono nella soluzione ottima
• Oss:
– dato il sistema Ax=b, x0 portato in forma canonica
Axb premoltiplicando per AB-1, dove B e’ la base
ottima e x* la soluzione ottima associata,
– dato y il vettore dei prezzi ombra delle risorse rispetto
a B,
ALLORA vale che
(b-Ax*)y=0
Questo risultato nella teoria della dualita’ va sotto il nome di
teorema degli SCARTI COMPLEMENTARI
Analisi di sensitivita’
• I parametri del modello sono frutto di una stima
• Vogliamo testare quanto la soluzione ottima sia robusta rispetto a
tali stime
• I parametri per cui si registra una maggiore variazione della
soluzione ottima sono da stimare con maggiore accuratezza in fase
di messa a punto del modello, e da monitorare attentamente durante
il periodo di applicazione dei risultati, per verificare se i valori stimati
si mantengono stabili.
• I sw commerciali offrono strumenti per l’analisi di sensitivita’ per i
singoli parametri (bi, cj principalmente) che rispondono alla
domanda “entro quale range bi, cj puo’ variare mantenendo x* (o la
base associata) come ottimo corrente?”
• Comandi MOSEL:
– XPRSrhssa fornisce lower e upper bound dell’intervallo in cui
puo’ variare il singolo elemento del vettore dei termini noti
mantenendo la stessa base nel punto di ottimo
– XPRSobjsa fornisce lower e upper bound dell’intervallo in cui
puo’ variare il singolo elemento del vettore dei costi mantenendo
la stessa base nel punto di ottimo
Programmazione lineare
parametrica
• Estende il concetto di analisi di sensitivita’
• Permette di stimare come varia la soluzione
ottima quando + parametri variano
simultaneamente all’interno di un intervallo, data
una correlazione fra i parametri, per effetto di un
unico fattore che ne governa il cambiamento
(es. il tasso di crescita, l’euribor, etc. puo’ far
cambiare insieme un costo di produzione e
beneficio atteso)
DUALITA’
HL cap 6
Risolvere il problema P:Min cx Ax=b, x0, vuol anche dire
cercare la stima w il piu’ possibile esatta del valore ottimo cx*,
vale a dire
cercare w*, ovverosia il massimo valore w che sia non superiore a cx, xP
Possiamo quindi definire il problema equivalente
D: Max w: wcx, xP, wR.
NB
• Se P ha ottimo finito, l’ottimo di D non puo’ che avere uguale valore
• D ha un numero infinito di vincoli del tipo wcx (dovendo limitare
superiormente il costo di ogni soluzione x ammissibile di P) e assume
valore in R,
• cerchiamone formulazioni equivalenti + trattabili
• Poiche’ l’ottimo di P sta su un vertice del politopo P,
allora possiamo trasformare il sistema formato
dall’insieme infinito di vincoli wcx, xP in un sistema
equivalente formato da un numero finito per i soli x
vertici del politopo P, passando alla forma
wcxv, vV(P)
• Se P ha ottimo finito (z*=cx* > -) allora esiste una base
ottima B tale che
– c – cBAB-1A  0 (costi ridotti non negativi)
– z* = cBAB-1b
per cui posso riformulare il problema come:
Max w: w cBAB-1b, cBAB-1A  c per ogni base B
• Introduco yRm come la soluzione di base duale
associata alla base B, y = cBAB-1, e riformulo il problema
come determinare la y tale che
• w  yb
• yA  c
Teorema (dell’alternativa o lemma di Farkas):
dato un problema di programmazione lineare
z* = min {cx: xP} dove P={x: Ax=b, x0}
allora vale che
 y  Rm:
w  cx,  xP

yAc
w  yb
• Cercare
• Equivale a cercare
w* = max w :
w  cx,  xP,
wR
w* = max w :
w  yb
y A  c,
y Rm
• Sono equivalenti i due problemi, P e D
z* = min cx :
Ax = b
x0, xRn
w* = max yb :
y A  c,
y Rm
Coppie di problemi primale-duale
• Pillole per polli: l’allevatore
• Ha a disposizione 2 tipi di mangimi, A,B di costo
cA,cB, di cui conosce i valori nutrizionali di
proteine, carboidrati e vitamine
• Sono noti gli apporti nutrizionali minimi di una
dieta per essere un “super=pollo”
• L’allevatore vuole la dieta super-pollo di costo
minimo
Formalizzazione algebrica del problema
• Variabili: xA, xB 0
• Vincoli: per ogni principio nutritivo, occorre
raggiungere la soglia minima
carbA xA +
carbB xB
 mincarb
protA xA +
protB xB
 minprot
vitA xA
+
vitB xB
 minvit
• Funzione obiettivo: minimizzare la spesa
– Min cAxA + cBxB
Esercizio: formulare il problema con i dati seguenti
Mangime A Mangime B Minimo
Giornaliero
Carboidrati 2
2
14
Proteine
4
2
20
Vitamine
1
3
9
Costo
unitario
1200
1600
?
Il cugino chimico dell’allevatore …..
Sintetizza in garage pillole per polli di
vitamine carboidrati e proteine…
Che vuole vendere all’allevatore
al massimo prezzo possibile
Il cugino risolve un problema di equilibrio…
Massimizzare il profitto restando sul mercato
= essendo competitivo con i mangimi
Il cugino chimico risolve il problema
• Max mincarb yc + minprot yp + minvit yv :
carbA yc + protA yp + vitA yv  cA
carbB yc + protB yp + vitB yv  cB
yc yp yv 0
Il vincolo 1 garantisce la concorrenza con il mangime A
Il vincolo 2 garantisce la concorrenza con il mangime B
I due problemi P, D sono EQUIVALENTI
(Fischetti 4.2-4.4)
ma lavorano in spazi decisionali diversi
x  R2, y  R3
Relazioni:
• A R3x2 e’ la matrice dei vincoli di P
• AT R2x3 e’ la matrice dei vincoli di D
• b e’ il rhs di P, e il vettore dei costi di D
• c e’ il vettore dei costi di P e il rhs di D
Tabella generale delle corrispondenze
(duale in modo automatico)
• P (min cx)
•
•
•
•
•
•
a i x  bi
a i x  bi
ai x = bi
xj  0
xj  0
xj libera
• D (max yb)
•
•
•
•
•
•
yi  0
yi  0
yi libera
yAj  cj
yAj  cj
yAj = cj
Una variabile D per ogni vincolo P e una variabile P per ogni vincolo D
esercizio
• Costruire il duale del problema della
WindoorGlass in base alla tabella.
• Riusciamo a darne una interpretazione?
WindoorGlass, primale e duale
DUALE
Max 4y1 + 12y2 + 18y3
PRIMALE
Min -3 xA -5 xB:
xA
2 xB
3 xA + 2 xB
+ xC
= 4
+ xD
= 12
+ xE = 18
xA, xB, xC, xD, xE  0
(a1
(a2
(a3
y1
+ 3y3
2 y2 + 2y3
y1
y2
y3
≤ -3
≤ -5
≤ 0
≤ 0
≤ 0
(a1
(a2
(a3
(a4
(a5
Ma anche….
PRIMALE
Min 4y1 + 12y2 + 18y3
DUALE
Max 3 xA + 5 xB:
xA
2 xB
3 xA + 2 xB
≤4
≤ 12
≤ 18
(a1
(a2
(a3
y1
+ 3y3
2 y2 + 2y3
= 3
= 5
(a1
(a2
y1 , y2 , y3  0
Attraverso passaggi equivalenti si trasforma la coppia di problemi in una coppia
in cui riconosciamo un nuovo primale e un nuovo duale.
Possiamo interpretare il problema di dx come l’acquisizione da parte di un soggetto
esterno delle ore disponibili dei 3 impianti (4 del primo, 12 del secondo, 18 del terzo),
a fronte della spesa minima che garantisce uguale reddito al produttore, affinche’
l’offerta del soggetto esterno sia competitiva con quanto il produttore guadagnerebbe
se utilizzazze le ore disponibili per realizzare la propria produzione (equilibrio).
Th: idempotenza
il duale del duale e’ il primale
• Banalmente segue dalla tabella
Th dualita’ debole:
xP, yD
cxyb
Per P= min {cx: Ax=b, x0}, D= max {yb: yAc}
yb = yAx  cx
Max yb 

Min cx
Th: dualita’ forte
dati P= min {cx: Ax=b, x0}, D= max {yb: yAc}
con ottimo finito, allora
Min cx = Max yb
Corollario:
sia x ammissibile per P, y ammissibile per D,
Se vale che cx=yb  x e’ ottima per P, y e’ ottima per D.
Oss
il costo di una soluzione ammissibile a uno dei due problemi
fornisce una STIMA ottimistica del valore OTTIMO dell’altro
Max yb 
cx*=y*b 
Min cx
Casi possibili
P/D
Ottimo
finito cx*
FP = 
Illimitato
(-)
Ottimo
finito y*b
cx* = y*b
NO
NO
FD = 
NO
SI
SI
Illimitato
(+)
NO
SI
NO
Th scarti complementari:
anche detti “ condizioni di ortogonalita’ ”
dati, xP, yD
P= min {cx: Ax=b, x0}, D= max {yb: yAc}
se (c-ya)x=0  x e y sono ottime
generalizzando date x,y ammissibili per
P= min {cx: Ax  b, x0}, D= max {yb: yAc, y0}
(c-ya)x=0 e y(Ax-b)=0  x e y sono ottime
Possiamo vedere in questa ottica il fatto che i prezzi ombra
(variabili duali) delle risorse non esaurite all’ottimo siano 0
Simplesso duale (cenni) (Fischetti 4.7)
• Consideriamo la coppia di problemi P e D
P: Min cx : Ax=b, x0
D: Max yb : yAc
P: min
D: max
c
y
b
x
Tale che:
Tale che:
n
m
=
A
b
x
x0
AT
y

c
Ammissibilita’ e ottimalita’ duale
•
Data una base B posso calcolare y = cB AB-1 la soluzione di base duale 
analizzo la soluzione di base complementare associata nello spazio primale
x= [AB-1b, 0])
•
Per costruzione y soddisfa gli m vincoli in B (detti vincoli attivi) yAB cB, come =

infatti i costi ridotti delle componenti in base della soluzione primale complementare x sono
nulli per costruzione (cB - cB AB-1AB = 0)
•
y e’ duale ammissibile se sono soddisfatti anche i vincoli in N, AN y  cN 
corrisponde a chiedere costi ridotti 0 nel primale per la soluzione di base complementare
associata, x= [AB-1b, 0], quindi anche per le componenti xN
Quindi l’ammissibilita’ duale di una soluzione di base yB equivale a chiedere la primale
ottimalita’ della soluzione primale associata alla stessa base B
•
Condizione di ottimalita’ duale nello spazio duale (posso immaginare il politopo):
secondo la geometria, la soluzione duale e’ ottima se il gradiente della funzione obiettivo
duale (b)  cono dei gradienti dei vincoli attivi (cioe’ le righe in base) 
 x0, x  Rm, tale che AB x = b 
da x posso costruire una soluzione
primale ammissibile ponendo xB= x e
completando il vettore nello spazio Rn
con n-m elementi nulli (xN=0)
Ammissibilita’ duale  ottimalita’ primale,
Ammissibilita’ primale  ottimalita’ duale
• Data una soluzione di base del duale y=cBAB-1 i
gradienti dei vincoli non attivi hanno moltiplicatore 0 
• posso costruire un vettore x = [x, 0] in Rn,
che soddisfa A x = b, x 0.
 ammissibilita’ primale
• se y= cB AB-1 e’ duale ammissibile, significa:
_
T
-1
A y c

c  cB AB A 
c0 
condizione di ottimalita’ primale sui costi ridotti
Allora posso costruire un metodo che esplora le basi,
mantiene la duale ammissibilita’ cercando la duale ottimalita’
e interpretarlo nello spazio primale
Questo metodo si chiama SIMPLESSO DUALE
Interpretazione del Simplesso duale
nello spazio primale di Ax=b, x0
Data una soluzione di base corrente alla iterazione k, x(k)=
[xB,0] dove xN=0 e xB= AB-1b tale che:
- soddisfa i criteri di ottimalita’ primale (ammissibilita’ duale):
ha costi ridotti non negativi: c  cBAB-1A
- non e’ primale ammissibile nei soli vincoli di segno x  0 (non
e’ ottimo duale):
per costruzione x(k) soddisfa Ax=b,
ma  almeno un vincolo i1..m tale che AB-1ai x(k) = (AB-1b ei) <0
Si danno 2 casi
• L’intera riga i di AB-1A ha componenti 0, per cui nessun
vettore x 0 potra’ mai soddisfare contemporaneamente i
vincoli Ax=b e x0  primale inammissibile e duale illimitato
•  un componente j di AB-1ai di segno negativo (a’ij= AB-1aiej<0):
utilizzando tale elemento a’ij come pivot posso moltiplicare per
-1 il vincolo e eliminare la negativita’ della componente j in
soluzione
MA
devo mantenere l’ottimalita’ primale: la scelta della
componente i tra gli elementi negativi della riga AB-1aj deve
minimizzare il valore assoluto del rapporto tra il costo ridotto
di i e l’elemento selezionato a’ij :
i = ArgMini=1..n { (ci-cBAB-1Ai) / |AB-1ai ej| tale che AB-1ai ej<0}
Rappresentiamo la regione ammissibile del primale come il politopo P.
Il simplesso duale si muove sui punti di intersezione di m vincoli, tali per cui c sta nel cono dei
gradienti dei vincoli attivi (ottimalita’ primale = ammissibilita’ duale). Si muove su basi
adiacenti cercando di soddisfare l’ammissibilita’ primale, che e’ la condizione di ottimalita’ del
problema duale.
In BLU le soluz di base DUALI ammissibili (costi ridotti 0)
In ROSSO le soluz di base che NON sono DUALI ammissibili
8
Ad ogni step
- l’algoritmo seleziona un
vincolo non soddisfatto,
- si muove su di vertice
adiacente con un cambio di
base verso l’ammissibilita’
primale, mantenedo l’ottimalita’
primale = tenendo c nel cono
dei gradienti dei vincoli attivi
6
4
2
0
1
2
4
5
6
8
x1
Soluzioni di base complementari
• Data una base B (AB ha rango pieno)
si dicono soluzioni di base complementari
x = [AB-1b, 0] e y = [cB AB-1]T
NB
una coppia di soluzioni complementari, per definizione soddisfa gli
scarti complementari (e’ nullo il prodotto scalare del vettore delle
slack dei vincoli per il vettore delle variabili associate ai vincoli nel
problema complementare)
 idea per un 3 algoritmo:
il Simplesso primale-duale:
conserva la complementarieta’ delle due soluzioni di base e ricerca
la simultanea ammissibilita’ di entrambe, passando a basi adiacenti
con le consuete operazioni di scambio di indici
Data la coppia di problemi
P: min cx: Ax=b, x0,
D: max yb: yAc
per ogni base B si ha la coppia di soluzioni
x=[AB-1b, 0] e y=cBAB-1
• Ax=b, x0
Ammissibilita’ primale
Ottimalita’ duale
• c  yA
Ammissibilita’ duale
Ottimalita’ primale
• (c-yA) x = 0
complementarieta’
(ortogonalita’)
• Il simplesso primale mantiene
l’ammissiblita’ primale di x e cerca
l’ammissibilita’ duale della soluzione
complementare duale y(B) = [cB AB-1]
• Il simplesso duale mantiene l’ammissibilita’
duale di y e cerca l’ammissibilita’ primale
della soluzione complementare x(B) = [AB1b,0]
• I solver permettono la scelta di quale
simplesso usare
Esercizi: utilizzando gli scarti complementari
verificare se
la soluzione
x1=8, x2=3,
e’ ottima per il problema
max 4x1 + 2x2:
2x1  16,
x1 + 3x2  17,
x2  5,
x1,x20
la soluzione
x1=2, x2= -4,
e’ ottima per il problema
max x1 - x2:
x2  1,
2x1 + x2  5,
x1 + 3x2  -10,
-x1 -x2  2,
x10, x2 libera
Soluzione: si determina a quale base B e’ associata la soluzione x,
si formula il problema duale, si calcola la soluzione di base complementare y
associata a B,e se ne verifica l’ammissibilita’ duale
Il problema duale: un’ulteriore riflessione (1)
Dato un problema primale nella consueta forma, Min cx: Ax=b, x  0, il problema duale nasce
dall’analisi delle soluzioni di base primali che soddisfano alle condizioni di ottimalita’ primale
ma non necessariamente a quelle di ammissibilita’ sul segno delle variabili x: sono soluzioni
di base che non sono anche vertici del politopo P.
Ricordiamo che P e’ la rappresentazione delle soluzioni ammissibili del problema primale
nello spazio di n-m variabili, ottenuto portando il sistema in forma di disuguaglianza
premoltiplicando Ax=b per l’inversa della sottomatrice di base rispetto alle altre m colonne.
Cosi’ possiamo interpretare ciascuna variabile primale xi come la slack del vincolo
corrispondente alla riga di AB-1A in cui la colonna i-esima ha la forma della i-esima colonna
della matrice identita’ (versore ei). Se xi <0 significa che il vincolo suddetto e’ violato.
Consideriamo una base B tale che c  0, quindi c  cBAB-1A, ma B non e’ necessariamente una
base primale ammissibile, nel senso che la soluzione di base associata puo’ violare x0.
Introduciamo il vettore y∊Rm = cBAB-1 come la soluzione di base duale rispetto alla base B,
osservando che, per costruzione, y costituisce una soluzione ammissibile del sistema yAc,
e interroghiamoci sul valore di yb.
Se B e’ anche primale ammissibile allora la soluzione di base primale associata
x(B)=[xB,xN]=[AB-1b,0] e’ anche ottima con costo
cx(B) = cBAB-1b = z*
ottimo del problema.
In tal caso yb = cBAB-1b = z* ha lo stesso valore.
Il problema duale: un’ulteriore riflessione (2)
Sotto tali condizioni, y e’ anche l’ottimo del problema duale, da
cui si deriva il seguente
TH: la primale ammissibilita’ di una base duale ammissibile, ne
implica la duale ottimalita’.
DIM:
Le componenti di xB=AB-1b forniscono le coordinate di una
combinazione conica delle colonne in base di A che
generano b. Essendo tali vettori pari ai gradienti dei vincoli
attivi nella base B per il problema duale, e b il gradiente della
funzione obiettivo del duale, tale condizione e’ condizione di
ottimo per un problema di massimo.
Contrariamente, se B non e’ primale ammissibile, z*
rappresenta un upper bound al valore di yb per ogni y
ammissibile per yAc. Infatti un’altra base primale ottima ma
non primale ammissibile non rispetta le condizioni di ottimo
duale yb ≤ z*
Esempio numerico di simplesso duale sul tableau:
rappresento le iterazioni nello spazio delle variabili primali x1,x2.
x2
10
La base iniziale B1={1,2,5,6} (N1={3,4}) individua il vertice v1,
posto all’ dei vincoli a1 e a2 ove sia annullano le scarto x3 e x4.
v1 e’ duale ammissibile in quanto il vettore c=[3,5] e’
compreso nel cono dei gradienti dei vincoli attivi a1 e a2.
8
v1
6
a2: x2  6
La soluzione primale associata a B1
non e’ primale ammissibile essendo
x5<0, x6<0 (x5= -6, x6= -3)
a1: x1  4
4
a4: x1+ x2  7
a3: 3x1+2 x2  18
Su ogni vincolo sono
evidenziati i gradienti
C = [ 3, 5 ]
2
0
1
2
4
5
6
8
x1
Svolgiamo un passo di simplesso duale sul tableau:
(Fischetti 4.7)
inseriamo in tabella i dati secondo la forma primale del problema
x1
-3
1
0
3
1
x2
-5
0
1
2
1
x3
0
1
0
0
0
x4
0
0
1
0
0
x5
0
0
0
1
0
x6
0
0
0
0
1
z
-1
b
4
6
18
7
La tabella va portata in forma canonica rispetto alla base B1={1,2,5,6}
premoltiplicandola per l’inversa della matrice di base, e
azzerando il vettore dei costi ridotti nelle componenti in B.
Avendo premoltiplicato per
l’inversa di AB={A1,A2,A5,A6}
otteniamo la tabella seguente
x1
0
1
0
0
0
x2
0
0
1
0
0
x3
3
1
0
-3
-1
x4
5
0
1
-2
-1
x5
0
0
0
1
0
AB-1=
x6
0
0
0
0
1
z
-1
b
x1
x2
x5
x6
4
6
-6
-3
1 0 00
0 1 00
-3-2 1 0
-1-1 0 1
La base corrente e’ data dagli indici {1,2,5,6} di valore x =[4,6,0,0,-6,-3]
con costo della soluzione pari a 3*4+5*6=42.
x non e’ primale ammissibile quindi occorre portare a 0 x5 o x6 muovendosi verso
il vincolo su cui una delle due si azzera, senza perdere la duale ammissibilita’.
(Continuare per esercizio)
Quando e’ corretto addottare un modello di PL
per descrivere e risolvere
un problema di ottimizzazione?
La scelta di un modello di PL e’ appropriata solo se
sono soddisfatte le seguenti condizioni:
•
•
•
•
Proporzionalitá
Additivitá
Divisibilitá
Certezza
PL: indicazioni per l’uso (1)
Proporzionalitá
• Nella LP sia la funzione obiettivo che i vincoli sono funzioni lineari, che
presuppongono un tasso costante di crescita tra variabili indipendenti e
dipendenti (es. costi marginali costanti).
• Scegliendo funzioni lineari non sono correttamente rappresentate
economie di scala, punti di saturazione, costi fissi, e ogni altra relazione
non lineare tra variabili indipendenti e dipendenti.
• Nel breve periodo e per intervalli di variazione limitati, una funzione
lineare puo’ fornire una buona approssimazione della funzione vera
• .
• Si possono costruire funzioni lineari a tratti e con costi fissi in modelli +
complessi di MILP.
• Altrimenti occorre adottare modelli non lineari (NLP)
PL: indicazioni per l’uso (2)
Additivitá
• Ogni funzione e’ data dalla somma dei contributi delle
singole variabili
• Non presuppone alcuna interazione e sinergia fra le
variabili.
• L’effetto della singola variabile dipende solo dal valore
della stessa e non e’ condizionato dal valore che
assumono contemporaneamente le altre variabili.
• Molti fenomeni reali non soddisfano questo requisito
(fenomeni fisici) e richiedono modelli non-lineari (NLP)
PL: indicazioni per l’uso (3)
Divisibilitá
• Eventuali valori frazionari delle variabili decisionali
devono avere una corretta interpretazione nel problema
reale.
• Ad esempio possono rappresentare un tasso di
funzionamento di una attivita’ che andra’ ripetuta in tutti i
periodi temporali, (es. quantitativo prodotto per unita’ di
tempo).
• Se l’ipotesi non e’ verificata occorrono variabili a valori
interi (ILP)
PL: indicazioni per l’uso (4)
Certezza
• i valori assegnati a ogni parametro del modello devono
essere delle costanti note.
• spesso sono frutto di un processo di stima per cui
possono contenere delle inesattezze rispetto a quanto si
verifichera’.
• occorre effettuare a posteriori l’analisi di sensitivita’, cioe’
verificare la robustezza della soluzione ottima al variare
dei singoli parametri: per quale range di variazione del
parametro ci (bj, aij) la soluzione ottima corrente rimane
tale?
PL: indicazioni per l’uso (5)
Oltre la PL  la PLI
• Quando le suddette condizioni non sono verificate spesso e’
possibile dare un modello matematico del problema in esame che
mantenga sia vincoli che funzione obiettivo lineari, utilizzando
variabili intere.
• Questo ci porta a una nuova classe di problemi, dalla
Programazione Lineare alla Programmazione Lineare Intera (o
mista) (ILP o MILP).
• Passare da LP a ILP fa passare da un problema nella classe P a un
problema di tipo NP-Hard, a meno di particolari proprieta’ del
problema in esame.
• Algoritmo per la PLI: Branch and Bound, con worst case complexity
esponenziale  importanza di una buona modellazione per la
performance media