Analisi di sensitivitá
Analisi di sensitivitá
Ci porremo ora la seguente domanda:
dato un problema di PL di cui ho giá determinato una
soluzione ottima, che cosa succede se modifico il valore di un coefficiente di una variabile (nell’obiettivo o nei vincoli) o il valore di un termine noto?
ovvero: come cambiano il valore ottimo e la soluzione
ottima del problema in corrispondenza di queste modifiche?
Analisi di sensitivit ´a – p. 2/48
Problema degli aiuti umanitari
max 14x1 + 5x2 + 4x3
10x1 + 30x2 + 20x3 ≤ 5100 10x1 + 20x2 + 40x3 ≤ 8000 30x1 + 10x2 + 5x3 ≤ 1805
x1, x2, x3 ≥ 0
Perché questa domanda?
In alcuni casi nei problemi di PL compaiono dati stimati e non dati oggettivi. Per tali dati é importante stabilire quanto é sensibile il risultato ottenuto a perturbazioni di tali dati:
Nel problema degli aiuti umanitari i valori di utilitá (coefficienti nell’obiettivo) sono valori stimati.
Inoltre, in alcuni casi dopo aver risolto il problema
intervengono fattori esterni che modificano alcuni dati originari del problema.
Nel problema degli aiuti umanitari qualcuno puó procurare, ad esempio, 1000 sacchi di farina in piú.
Analisi di sensitivit ´a – p. 4/48
Problema di PL
max cx Ax = b
x ≥ 0
Ipotesi : esiste base ottima del problema B∗. max cB∗A−1
B∗b + (cN∗ − cB∗A−1
B∗AN∗)xN∗ xB∗ = A−1B∗b − A−1B∗AN∗xN∗
xB∗, xN∗ ≥ 0
Continua
Soluzione ottima del primale:
xB∗ = A−1B∗b xN∗ = 0, Soluzione ottima del duale:
uB∗ = cB∗A−1
B∗.
Valore ottimo per il primale e per il duale:
cB∗A−1
B∗b.
Analisi di sensitivit ´a – p. 6/48
Problema degli aiuti umanitari
In forma standard:
max 14x1 + 5x2 + 4x3
10x1 + 30x2 + 20x3 + y1 = 5100 10x1 + 20x2 + 40x3 + y2 = 8000 30x1 + 10x2 + 5x3 + y3 = 1805
x1, x2, x3, y1, y2, y3 ≥ 0 Qual é il significato delle variabili y1, y2, y3?
Continua
Base ottima B∗ = {y1, x3, x1}:
max 1164 − 231 y2 − 11552 y3 − 239 x2
y1 = 960 + 234 y3 + 1123y2 − 43023 x2
x3 = 193 + 1151 y3 − 1153 y2 − 1023x2
x1 = 28 − 1154 y3 + 2301 y2 − 236 x2
x1, x2, x3, y1, y2, y3 ≥ 0
Analisi di sensitivit ´a – p. 8/48
Continua
Soluzione ottima del primale:
y1∗ = 960 x∗3 = 193 x∗1 = 28 x∗2 = y2∗ = y3∗ = 0.
Matrice A−1B∗:
A−1
B∗ =
1 −1123 −234 0 1153 −1151 0 −2301 1154
Continua
Soluzione ottima del duale uB∗: uB∗ = cB∗A−1
B∗ = (0 4 14)A−1B∗ =
0 1 23
52 115
Valore ottimo del primale e del duale: 1164
Analisi di sensitivit ´a – p. 10/48
Modifica di un termine noto
b → b
con
bi = bi ∀ i 6= r br = br + ∆br
Riformulazione rispetto a B∗ dopo la modifica:
max cB∗A−1
B∗b + (cN∗ − cB∗A−1
B∗AN∗)xN∗ xB∗ = A−1B∗b − A−1B∗AN∗xN∗
xB∗, xN∗ ≥ 0
Continua
Quando la base B∗ resta ottima?
B∗ continua ad essere ammissibile per il duale (non cambiano i coefficienti di costo ridotto) e quindi rimane ottima se continua ad essere anche ammissibile per il primale, ovvero se
A−1
B∗b ≥ 0 Variazione del valore ottimo:
cB∗A−1
B∗b−cB∗A−1
B∗b = uB∗(b−b) =
m
X
i=1
uBi ∗(bi−bi) = uBr ∗∆br. Quindi il valore di una variabile duale nella soluzione ottima del duale misura la rapiditá con cui cambia il valore ottimo del problema al variare del termine noto del vincolo
corrispondente nel primale. Analisi di sensitivit ´a – p. 12/48
Continua
Nuova soluzione ottima del primale
xB∗ = A−1B∗b xN∗ = 0,
Nuovo valore ottimo per il primale e per il duale:
cB∗A−1
B∗b.
La soluzione ottima del duale:
uB∗ = cB∗A−1
B∗.
non cambia (non dipende dai termini noti del problema primale).
Calcolo di A −1 B∗b
b =
b1
... br
... bm
+
0 ...
∆br ... 0
= b + ∆br
0 ... 1 ... 0
Analisi di sensitivit ´a – p. 14/48
Quindi ...
A−1
B∗b = A−1B∗b + ∆brA−1
B∗
0 ... 1 ... 0
A−1
B∗b giá noto (termini noti nella riformulazione rispetto a B∗)
Continua
∆brA−1
B∗
0 ... 1 ... 0
é pari a ∆br moltiplicato per la colonna r-esima di A−1B∗.
Analisi di sensitivit ´a – p. 16/48
E se B ∗ non é piú ottima?
Se con la modifica B∗ non é piú base ottima, ovvero:
A−1
B∗b 6≥ 0
B∗ continua a rimanere ammissibile per il duale e quindi posso utilizzare B∗ come base iniziale per il simplesso duale senza dover risolvere di nuovo tutto il problema da capo.
Nell’esempio
Modifica ∆b2 del secondo termine noto. Nuovo vettore di termini noti:
b = (5100 (8000 + ∆b2) 1805).
Modifica nella riformulazione dell’obiettivo:
1164 + u∗2∆b2 − 1
23y2 − 52
115y3 − 9 23x2
Modifica termini noti dei vincoli:
(960 193 28) + ∆b2
−11 23
3
115 − 1 230
Analisi di sensitivit ´a – p. 18/48
Continua
∆b2 = 1150:
max 1214 − 231 y2 − 11552 y3 − 239 x2
y1 = 410 + 234 y3 + 1123y2 − 43023 x2
x3 = 223 + 1151 y3 − 1153 y2 − 1023x2
x1 = 23 − 1154 y3 + 2301 y2 − 236 x2
x1, x2, x3, y1, y2, y3 ≥ 0 Nuova soluzione ottima:
y1 = 410 x3 = 223 x1 = 23 y2 = y3 = x2 = 0 Nuovo valore ottimo: 1214
Continua
∆b2 = 2300
max 1264 − 231 y2 − 11552 y3 − 239 x2
y1 = −140 + 234 y3 + 1123y2 − 43023 x2
x3 = 253 + 1151 y3 − 1153 y2 − 1023x2
x1 = 18 − 1154 y3 + 2301 y2 − 236 x2
x1, x2, x3, y1, y2, y3 ≥ 0
B∗ non é piú base ottima. Si parte da B∗ con il simplesso duale.
Analisi di sensitivit ´a – p. 20/48
Continua
Intervallo in cui posso variare ∆b2 mantenendo B∗ base ottima:
(960 193 28) + ∆b2
−11 23
3
115 − 1 230
=
960 − 11∆b2
23 193 + 3∆b2
115 28 − ∆b2 230
≥ 0
960 − 11∆b23 2 ≥ 0 193 + 3∆b1152 ≥ 0 28 − ∆b2302 ≥ 0
Ancora nell’esempio
Modifica ∆b1 del primo termine noto. Nuovo vettore di termini noti:
b = ((5100 + ∆b1) 8000 1805).
Modifica nella riformulazione dell’obiettivo:
1164 + u∗1∆b1 − 1
23y2 − 52
115y3 − 9 23x2
Modifica termini noti dei vincoli:
(960 193 28) + ∆b1 (1 0 0)
Analisi di sensitivit ´a – p. 22/48
Continua
∆b1 = 100:
max 1164 − 231 y2 − 11552 y3 − 239 x2
y1 = 1060 + 234 y3 + 1123y2 − 43023 x2
x3 = 193 + 1151 y3 − 1153 y2 − 1023x2
x1 = 28 − 1154 y3 + 2301 y2 − 236 x2
x1, x2, x3, y1, y2, y3 ≥ 0 Nuova soluzione ottima:
y1 = 1060 x3 = 193 x1 = 28 y2 = y3 = x2 = 0 Valore ottimo invariato! É sorprendente?
Modifica nell’obiettivo
cN∗ → cN∗ Riformulazione rispetto a B∗:
max cB∗A−1
B∗b + (cN∗ − cB∗A−1
B∗AN∗)xN∗ xB∗ = A−1B∗b − A−1B∗AN∗xN∗
xB∗, xN∗ ≥ 0
Analisi di sensitivit ´a – p. 24/48
Quando B ∗ rimane base ottima?
Questo accade se i coefficienti di costo ridotto restano tutti
≤ 0, ovvero
cN∗ − cB∗A−1
B∗AN∗ ≤ 0
In tal caso soluzione ottima del primale e del duale e valore ottimo del problema restano invariati.
E se B ∗ non é piú ottima?
Ovvero: se
cN∗ − cB∗A−1
B∗AN∗ 6≤ 0
In tal caso B∗ non é piú ammissibile per il duale ma lo é per il primale e quindi si puó ripartire da essa con il simplesso primale.
Analisi di sensitivit ´a – p. 26/48
Nell’esempio
Modifica del coefficiente di x2: da 5 a 5 + ∆cx2
Modifica nella riformulazione dell’obiettivo:
1164 − 1
23y2 − 52
115y3 − 9
23x2 + ∆cx2x2
Continua
∆cx2 = −1
max 1164 − 231 y2 − 11552 y3 − 3223x2
y1 = 960 + 234 y3 + 1123y2 − 43023 x2
x3 = 193 + 1151 y3 − 1153 y2 − 1023x2
x1 = 28 − 1154 y3 + 2301 y2 − 236 x2
x1, x2, x3, y1, y2, y3 ≥ 0
Analisi di sensitivit ´a – p. 28/48
Continua
∆cx2 = 1
max 1164 − 231 y2 − 11552 y3 + 1423x2
y1 = 960 + 234 y3 + 1123y2 − 43023 x2
x3 = 193 + 1151 y3 − 1153 y2 − 1023x2
x1 = 28 − 1154 y3 + 2301 y2 − 236 x2
x1, x2, x3, y1, y2, y3 ≥ 0
Continua
Intervallo in cui può variare ∆cx2 senza cambiare la base ottima
− 9
23 + ∆cx2 ≤ 0
Analisi di sensitivit ´a – p. 30/48
Modifica nell’obiettivo
cB∗ → cB∗
Riformulazione rispetto a B∗: max cB∗A−1
B∗b + (cN∗ − cB∗A−1
B∗AN∗)xN∗ xB∗ = A−1B∗b − A−1B∗AN∗xN∗
xB∗, xN∗ ≥ 0
Quando B ∗ rimane base ottima?
Questo accade se i coefficienti di costo ridotto restano tutti
≤ 0, ovvero
cN∗ − cB∗A−1
B∗AN∗ ≤ 0
In tal caso soluzione ottima del primale non cambia, quella del duale diventa cB∗A−1B∗ mentre il valore ottimo cambia di una quantitá pari alla variazione del coefficiente moltiplicata per il valore della variabile di cui si é modificato il
coefficiente nella soluzione ottima del primale (vedi esempi).
Analisi di sensitivit ´a – p. 32/48
E se B ∗ non é piú ottima?
Ovvero: se
cN∗ − cB∗A−1
B∗AN∗ 6≤ 0
In tal caso B∗ non é piú ammissibile per il duale ma lo é per il primale e quindi si puó ripartire da essa con il simplesso primale.
Nell’esempio
Modifica del coefficiente di x1: da 14 a 14 + ∆cx1 Modifica nella riformulazione dell’obiettivo:
1164 − 1
23y2 − 52
115y3 − 9
23x2 + ∆cx1x1 = 1164 − 1
23y2 − 52
115y3 − 9
23x2+ +∆cx1(28 − 4
115y3 + 1
230y2 − 6
23x2) = 1164 + 28∆cx1 + y2
− 1
23 + ∆cx1 230
+ +y3
− 52
115 − 4∆cx1 115
+ x2
− 9
23 − 6∆cx1 23
Analisi di sensitivit ´a – p. 34/48
Continua
∆cx1 = 1
max 1192 − 2309 y2 − 11556 y3 − 1523x2
y1 = 960 + 234 y3 + 1123y2 − 43023 x2
x3 = 193 + 1151 y3 − 1153 y2 − 1023x2
x1 = 28 − 1154 y3 + 2301 y2 − 236 x2
x1, x2, x3, y1, y2, y3 ≥ 0
B∗ rimane base ottima ed il valore ottimo varia della quantitá
∆cx1x∗1 = 1 ∗ 28 = 28
Continua
∆cx1 = −2
max 1108 − 23012 y2 − 11544 y3 + 233 x2
y1 = 960 + 234 y3 + 1123y2 − 43023 x2
x3 = 193 + 1151 y3 − 1153 y2 − 1023x2
x1 = 28 − 1154 y3 + 2301 y2 − 236 x2
x1, x2, x3, y1, y2, y3 ≥ 0
La base B∗ non é piú ottima ma é ancora ammissibile per il primale. Posso ripartire da essa con il simplesso primale.
Analisi di sensitivit ´a – p. 36/48
Continua
Intervallo in cui può variare ∆cx1 senza cambiare la base ottima
−231 + ∆c230x1 ≤ 0
−11552 − 4∆c115x1 ≤ 0
−239 − 6∆c23x1 ≤ 0
In tale intervallo il valore ottimo varia della quantitá
∆cx1x∗1 = 28∆cx1
Modifica nei vincoli
AN∗ → AN∗ Riformulazione rispetto a B∗:
max cB∗A−1
B∗b + (cN∗ − cB∗A−1
B∗AN∗)xN∗ xB∗ = A−1B∗b − A−1B∗AN∗xN∗
xB∗, xN∗ ≥ 0
Analisi di sensitivit ´a – p. 38/48
Quando B ∗ rimane base ottima?
Questo accade se i coefficienti di costo ridotto restano tutti
≤ 0, ovvero
cN∗ − cB∗A−1
B∗AN∗ ≤ 0
In tal caso soluzione ottima del primale e del duale e valore ottimo del problema restano invariati.
E se B ∗ non é piú ottima?
Ovvero: se
cN∗ − cB∗A−1
B∗AN∗ 6≤ 0
In tal caso B∗ non é piú ammissibile per il duale ma lo é per il primale e quindi si puó ripartire da essa con il simplesso primale.
Analisi di sensitivit ´a – p. 40/48
Nell’esempio
Modifica ∆a22 del coefficiente di x2 nel secondo vincolo:
da 20 a 20 + ∆a22
Modifica nella riformulazione dell’obiettivo:
1164 − 1
23y2 − 52
115y3 − 9
23x2 − u∗2∆a22x2
Continua
Modifica coefficienti di x2 nei vincoli:
−430
23 − 10
23 − 6 23
− ∆a22
−11 23
3
115 − 1 230
ovvero: il vettore dei coefficienti originari di x2 nei vincoli della riformulazione a cui sottraggo la modifica ∆a22
moltiplicata per la colonna di A−1B∗ corrispondente al vincolo in cui ho introdotto la modifica (in tal caso la seconda).
Analisi di sensitivit ´a – p. 42/48
Continua
∆a22 = 10:
max 1164 − 231 y2 − 11552 y3 − 1923x2
y1 = 960 + 234 y3 + 1123y2 − 32023 x2
x3 = 193 + 1151 y3 − 1153 y2 − 1623x2
x1 = 28 − 1154 y3 + 2301 y2 − 235 x2
x1, x2, x3, y1, y2, y3 ≥ 0
B∗ rimane ottima, le soluzioni ottime del primale e del duale e il valore ottimo non cambiano.
Continua
∆a22 = −10
max 1164 − 231 y2 − 11552 y3 + 231 x2
y1 = 960 + 234 y3 + 1123y2 − 54023 x2
x3 = 193 + 1151 y3 − 1153 y2 − 234 x2
x1 = 28 − 1154 y3 + 2301 y2 − 237 x2
x1, x2, x3, y1, y2, y3 ≥ 0
B∗ non é piú ottima ma continua ad essere ammissibile per il primale. Posso ripartire da B∗ con il simplesso primale.
Analisi di sensitivit ´a – p. 44/48
Continua
Intervallo in cui può variare ∆a22 senza cambiare la base ottima:
− 9
23 − u∗2∆a22 = − 9
23 − ∆a22
23 ≤ 0
Domanda
Secondo voi il problema é molto sensibile a modifiche ∆a12 del coefficiente di x2 nel primo vincolo del problema?
Analisi di sensitivit ´a – p. 46/48
Continua
AB∗ → AB∗
Nel caso peggiore si ha che B∗ non é piú neppure una base!
AB∗ =
"
2 1 1 0
#
AB∗ =
"
2 0 1 0
#
Inoltre ...
... anche se B∗ rimane una base abbiamo la seguente riformulazione rispetto a B∗:
max cB∗A−1B∗b + (cN∗ − cB∗A−1B∗AN∗)xN∗ xB∗ = A−1B∗b − A−1B∗AN∗xN∗
xB∗, xN∗ ≥ 0
Da cui si nota che si puó perdere sia l’ammissibilitá del primale che quella del duale per B∗ e quindi non si puó utilizzare B∗ né come base di partenza del simplesso primale né del simplesso duale.
Analisi di sensitivit ´a – p. 48/48
