I coefficienti cha appaiono in un problema di PL non sono sempre dei va-lori esatti ma piuttosto delle stime. Inoltre, anche quando si tratta di dati esatti succede spesso che dopo aver ottenuto la soluzione ottima del pro-blema ci si chiede che cosa succederebbe modificando un qualche dato del problema. Questo ci spinge a porci la seguente domanda: se i coefficienti vengono modificati, come cambiano la soluzione ottima e il valore ottimo del nostro problema? In altre parole, la soluzione ottima e il valore ottimo del nostro problema quanto sono sensibili a modifiche dei valori dei coef-ficienti? L’analisi di sensitivit´a si occupa della risposta a tali domande. Supponiamo di avere il nostro problema di PL in forma standard:
max cx
Ax= b
x≥ 0
e di aver stabilito che una base ottima del problema ´e B∗. Avremo quindi la seguente riformulazione rispetto alla base B∗:
max cB∗A−1B∗b+ (cN∗− cB∗A−1B∗AN∗)xN∗
xB∗ = A−1B∗b− A−1B∗AN∗xN∗ (5.1) xB∗, xN∗ ≥ 0
Avremo inoltre che una soluzione ottima del primale ´e: xB∗ = A−1B∗b xN∗ = 0, mentre per il duale si ha la soluzione ottima:
Entrambi i problemi hanno valore ottimo: cB∗A−1B∗b.
A questo punto vediamo cosa succede modificando diversi tipi di coefficien-ti. Ci limiteremo ad analizzare l’effetto di modifiche di singoli coefficienti ma l’analisi pu´o essere estesa anche alla modifica in contemporanea di pi´u coefficienti.
5.1 Modifica di un termine noto
Supponiamo che il termine noto br di un dato vincolo venga modificato in br+ ∆br, dove ∆br ´e un certo valore reale (pu´o essere sia positivo che negativo). Avremo quindi al posto del vettore b il vettore b le cui compo-nenti sono tutte uguali a quelle del vettore b, tranne la r-esima che diventa br+ ∆br. Andando a sostituire nella riformulazione (5.1), si ottiene:
max cB∗A−1B∗b+ (cN∗− cB∗A−1B∗AN∗)xN∗
xB∗ = A−1B∗b− A−1B∗AN∗xN∗
xB∗, xN∗ ≥ 0 Si possono avere due casi:
Caso 1 Il vettore A−1B∗bha delle componenti negative. Ci´o vuol dire che la modifica del termine noto ha reso la soluzione di base del primale associata a B∗non ammissibile. Tuttavia, la condizione
cN∗ − cB∗A−1B∗AN∗ ≤ 0,
che non dipende dai termini noti, continua ad essere soddisfatta e quindi la soluzione di base del duale associata a B∗ continua ad es-sere ammissibile. ´E importante sottolineare come non sia necessario risolvere il nuovo problema da zero, visto che, sfruttando l’ammis-sibilit´a della soluzione di base del duale associata a B∗, possiamo applicare il simplesso duale con base iniziale proprio B∗. In questo modo si arriva tipicamente ad una soluzione del problema modificato in tempi molto pi´u rapidi che non risolvendolo da zero.
Caso 2 Si ha che:
A−1B∗b≥ 0.
Quindi la soluzione di base del primale associata a B∗ continua ad essere ammissibile. Come nel Caso 1, la soluzione di base del duale
associata a B∗ resta ammissibile. Poich´e entrambe le soluzioni di base sono ammissibili, si ha che la base B∗ ´e ancora ottima. La nuova soluzione ottima del primale diventa
xB∗ = A−1B∗b xN∗ = 0,
mentre quella del duale resta invariata e cio`e pari a cB∗A−1B∗. Vediamo ora come cambia il valore ottimo rispetto a prima. Il nuovo valore ottimo ´e cB∗A−1B∗be quindi la differenza rispetto al precedente ´e pari a: cB∗A−1B∗b− cB∗A−1B∗b= uB∗(b− b) = m X i=1 uBi ∗(bi− bi). Poich´e: bi= bi ∀ i 6= r br= br+ ∆br, avremo: cB∗A−1B∗b− cB∗A−1B∗ = uBr∗(br− br) = uBr∗∆br.
Questo ci d´a una interpretazione della soluzione ottima del duale: il valore della r-esima variabile nella soluzione ottima del duale misura la rapidit´a con cui cambia il valore ottimo del problema al variare del termine noto br del vincolo r-esimo del primale. Se il valore di uB∗
r
´e elevato, anche piccole modifiche di brpossono portare a consistenti variazioni del valore ottimo. Se invece il valore di uB∗
r ´e piccolo, il valore ottimo del problema non ´e molto sensibile a variazioni del termine noto br.
5.2 Modifica del coefficiente di costo di una
variabile al di fuori della base ottima
Supponiamo che venga modificato il coefficiente di costo di una delle va-riabili fuori base xim+j, j = 1, . . . , n− m, ad esempio la variabile xim+t. Avremo quindi al posto del vettore cN∗ il vettore cN∗ le cui componen-ti sono tutte uguali a quelle del vettore cN∗, tranne quella relativa alla variabile xim+t. Andando a sostituire nella riformulazione (5.1), si ottiene:
max cB∗A−1B∗b+ (cN∗− cB∗A−1B∗AN∗)xN∗
xB∗ = A−1B∗b− A−1B∗AN∗xN∗
xB∗, xN∗ ≥ 0 Si possono avere ancora due casi:
Caso 1 Il vettore
cN∗− cB∗A−1B∗AN∗,
ha delle componenti positive. Questo vuol dire che la soluzione di base del duale associata a B∗ non ´e pi´u ammissibile. Resta invece ammissibile la soluzione di base del primale associata a B∗
xB∗ = A−1B∗b, xN∗ = 0,
che non ´e influenzata dalla modifica introdotta. Quindi, anche qui non ´e necessario risolvere il nuovo problema da zero, ma, sfruttando l’ammissibilit´a della soluzione di base del primale associata a B∗, possiamo applicare questa volta il simplesso primale con base iniziale proprio B∗. Si pu´o anche dimostrare che la prima variabile che entrer´a in base sar´a proprio la variabile xim+t. Perch´e?
Caso 2 Si ha che:
cN∗ − cB∗A−1B∗AN∗ ≤ 0,
Quindi la soluzione di base del duale associata a B∗ continua ad essere ammissibile. Come nel Caso 1, la soluzione di base del primale associata a B∗ resta ammissibile. Poich´e entrambe le soluzioni di base sono ammissibili, si ha che la base B∗ ´e ancora ottima. Le soluzioni ottime del primale e del duale restano invariate in quanto non dipendono dalla modifica introdotta. Lo stesso vale per il valore ottimo comune dei due problemi.
5.3 Modifica del coefficiente di costo di una
variabile appartenente alla base ottima
Supponiamo che venga modificato il coefficiente di costo di una delle va-riabili in base xir, r = 1, . . . , m, ad esempio la variabile xis, che passa da cis a cis+ ∆cis . Avremo quindi al posto del vettore cB∗ il vettore cB∗
le cui componenti sono tutte uguali a quelle del vettore cB∗, tranne quella relativa alla variabile xis. Andando a sostituire nella riformulazione (5.1), si ottiene:
max cB∗A−1B∗b+ (cN∗− cB∗A−1B∗AN∗)xN∗
xB∗ = A−1B∗b− A−1B∗AN∗xN∗
xB∗, xN∗ ≥ 0 Si possono avere ancora due casi:
Caso 1 Il vettore
cN∗− cB∗A−1B∗AN∗,
ha delle componenti positive. Questo vuol dire che la soluzione di base del duale associata a B∗ non ´e pi´u ammissibile. Resta invece ammissibile la soluzione di base del primale associata a B∗
xB∗ = A−1B∗b, xN∗ = 0,
che non ´e influenzata dalla modifica introdotta. Quindi, al solito, non ´e necessario risolvere il nuovo problema da zero, ma, sfruttando l’ammissibilit´a della soluzione di base del primale associata a B∗, possiamo applicare il simplesso primale con base iniziale proprio B∗. Caso 2 Si ha che:
cN∗ − cB∗A−1B∗AN∗ ≤ 0,
Quindi la soluzione di base del duale associata a B∗ continua ad essere ammissibile. Come nel Caso 1, la soluzione di base del primale associata a B∗resta ammissibile. Poich´e entrambe le soluzioni di base sono ammissibili, si ha che la base B∗´e ancora ottima. La soluzione ottima del primale, che non dipende dalla modifica introdotta, resta invariata, mentre la nuova soluzione ottima del duale ´e
uB∗ = cB∗A−1B∗.
Vediamo anche come cambia il valore ottimo comune dei due proble-mi.
cB∗A−1B∗b−cB∗A−1B∗b= (cB∗−cB∗)A−1B∗b= (cB∗−cB∗)xB∗ = ∆cisx∗ is. Quindi la variazione ´e data dal prodotto tra la perturbazione ∆cis del coefficiente di costo della variabile xised il valore della stessa variabile xis in corrispondenza della soluzione ottima del primale.
5.4 Modifica di un coefficiente della matrice
AN∗
Supponiamo ora che venga modificato un coefficiente della matrice AN∗, la matrice ottenuta da A considerando le sole colonne relative a variabili fuori base. Sia AN∗ la nuova matrice ottenuta dopo la modifica. Andando a sostituire nella riformulazione (5.1), si ottiene:
max cB∗A−1B∗b+ (cN∗− cB∗A−1B∗AN∗)xN∗
xB∗ = A−1B∗b− A−1
B∗AN∗xN∗
Si possono avere ancora due casi: Caso 1 Il vettore
cN∗− cB∗A−1B∗AN∗,
ha delle componenti positive. Questo vuol dire che la soluzione di base del duale associata a B∗ non ´e pi´u ammissibile. Resta invece ammissibile la soluzione di base del primale associata a B∗
xB∗ = A−1B∗b, xN∗ = 0,
che non ´e influenzata dalla modifica introdotta. Quindi, anche qui non ´e necessario risolvere il nuovo problema da zero, ma, sfruttando l’ammissibilit´a della soluzione di base del primale associata a B∗, possiamo applicare il simplesso primale con base iniziale proprio B∗. Caso 2 Si ha che:
cN∗ − cB∗A−1B∗AN∗ ≤ 0,
Quindi la soluzione di base del duale associata a B∗ continua ad essere ammissibile. Come nel Caso 1, la soluzione di base del primale associata a B∗ resta ammissibile. Poich´e entrambe le soluzioni di base sono ammissibili, si ha che la base B∗ ´e ancora ottima. Le soluzioni ottime del primale e del duale restano invariate in quanto non dipendono dalla modifica introdotta. Lo stesso vale per il valore ottimo comune dei due problemi.
5.5 Modifica di un coefficiente della matrice
AB∗
Supponiamo ora che venga modificato un coefficiente della matrice AB∗, la matrice ottenuta da A considerando le sole colonne relative a variabili nella base B∗. A questo caso accenniamo solo brevemente solo per far notare che ´e il pi´u complicato tra quelli visti. Sia AB∗ la nuova matrice ottenuta dopo la modifica. Il primo inconveniente che si pu´o verificare ´e che AB∗ non sia invertibile. A questo punto B∗ non ´e pi´u neppure una base. Ma vediamo cosa pu´o succedere anche nel caso fortunato in cui AB∗
sia invertibile. Andando a sostituire nella riformulazione (5.1), si ottiene: max cB∗A−1B∗b+ (cN∗− cB∗A−1B∗AN∗)xN∗
xB∗ = A−1B∗b− A−1B∗AN∗xN∗
Si pu´o avere che il vettore:
A−1B∗b ha componenti negative, mentre il vettore
cN∗ − cB∗A−1B∗AN∗
ha componenti positive. In altre parole, n´e la soluzione di base del primale associata a B∗, n´e quella del duale sono ammissibili. Di conseguenza, non possiamo applicare n´e il simplesso duale n´e quello primale con base iniziale B∗. 5.6 Un esempio Si consideri il problema di PL max −x1− x2+ 2x3+ 3x4 2x1+ x2+ 2x3= 1 x1+ 2x2+ x3+ x4= 1 x1, x2, x3, x4≥ 0
Si pu´o vedere che la base ottima ´e B∗ ={x3, x4}. Quindi avremo N∗ = {x1, x2}, AB∗ = · 2 0 1 1 ¸ A−1B∗ = · 1/2 0 −1/2 1 ¸ AN∗ = · 2 1 1 2 ¸ cB∗ = (2 3) cN∗ = (−1 − 1) b = (1 1). La soluzione ottima del primale ´e:
(x∗3 x∗4) = A−1B∗b= (1/2 1/2) (x∗1 x∗2) = (0 0).
Quella del duale ´e:
(u∗1 u∗2) = cB∗A−1B∗ = (−1/2 3). Il valore ottimo comune dei due problemi ´e
cB∗A−1B∗b= 5/2.
Vediamo ora di apportare alcune modifiche nei coefficienti del problema e di studiare gli effetti di queste modifiche.
Modifica di un termine noto
Introduciamo la perturbazione ∆b2=−3/4 del termine noto della seconda equazione. Quindi il valore b2 diventa pari a 1/4 e il nuovo vettore dei termini noti ´e:
b= (1 1/4). Si ha che:
A−1B∗b= (1/2 − 1/4)
e quindi la soluzione di base del primale associata a B∗non ´e pi´u ammissi-bile. Ma la soluzione di base del duale uB∗
associata a B∗ resta invariata e continua ad essere ammissibile. Quindi possiamo applicare il simplesso duale con base iniziale B∗.
Introduciamo ora la perturbazione ∆b2 = 1/4 del termine noto della se-conda equazione. Quindi il valore b2 diventa pari a 5/4 e il nuovo vettore dei termini noti ´e:
b= (1 5/4). Si ha che:
A−1B∗b= (1/2 3/4).
La soluzione di base del primale associata a B∗´e ancora ammissibile. Resta invariata la soluzione di base del duale uB∗
associata a B∗e quindi continua ad essere ammissibile. Quindi le due soluzioni sono ottime per i rispettivi problemi. La nuova soluzione ottima del primale ´e:
x∗3= 1/2 x∗4= 3/4 x∗1= x∗2= 0.
Il valore ottimo dei due problemi viene modificato della quantit´a: u∗2∆b2= 3× 1/4 = 3/4,
e quindi il valore ottimo passa da 5/2 a 13/4.
Modifica del coefficiente di costo di una variabile fuori base Introduciamo la perturbazione ∆c1 = 4 del coefficiente di costo della va-riabile fuori base x1. Quindi il valore c1 diventa pari a 3 e il nuovo vettore dei costi delle variabili fuori base ´e:
cN∗ = (3 − 1). Si ha che:
e quindi la soluzione di base del duale associata a B∗non ´e pi´u ammissibile. Ma la soluzione di base del primale associata a B∗resta invariata e continua ad essere ammissibile. Quindi possiamo applicare il simplesso primale con base iniziale B∗. Possiamo anche dire che la prima variabile ad entrare in base sar´a certamente la x1. Perch´e?
Introduciamo ora la perturbazione ∆c1 = 2 del coefficiente di costo del-la variabile fuori base x1. Quindi il valore c1 diventa pari a 1 e il nuovo vettore dei costi delle variabili fuori base ´e:
cN∗ = (1 − 1). Si ha che:
cN∗− cB∗A−1B∗AN∗ = (1 − 1) − (2 11/2) = (−1 − 13/2). La soluzione di base del duale associata a B∗ ´e ancora ammissibile. Resta invariata la soluzione di base del primale associata a B∗ e quindi continua ad essere ammissibile. Quindi le due soluzioni sono ottime per i rispet-tivi problemi. Le due soluzioni ottime ed il valore ottimo non subiscono modifiche.
Modifica del coefficiente di costo di una variabile appartenente alla base
Introduciamo la perturbazione ∆c3 = −4 del coefficiente di costo della variabile in base x3. Quindi il valore c3diventa pari a−2 e il nuovo vettore dei costi delle variabili in base ´e:
cB∗ = (−2 3). Si ha che:
cN∗− cB∗A−1B∗AN∗ = (−1 − 1) − (−2 7/2) = (1 − 9/2). e quindi la soluzione di base del duale associata a B∗non ´e pi´u ammissibile. Ma la soluzione di base del primale associata a B∗resta invariata e continua ad essere ammissibile. Quindi possiamo applicare il simplesso primale con base iniziale B∗.
Introduciamo ora la perturbazione ∆c3=−1 del coefficiente di costo della variabile in base x3. Quindi il valore c3 diventa pari a 1 e il nuovo vettore dei costi delle variabili in base ´e:
Si ha che:
cN∗− cB∗A−1B∗AN∗ = (−1 − 1) − (1 5) = (−2 − 6).
La soluzione di base del duale associata a B∗ ´e ancora ammissibile. Resta invariata la soluzione di base del primale associata a B∗ e quindi continua ad essere ammissibile. Quindi le due soluzioni sono ottime per i rispettivi problemi. Le nuova soluzione ottima del duale ´e:
uB∗ = cB∗A−1B∗ = (−1 3).
Il valore ottimo dei due problemi viene modificato della quantit´a: x∗3∆c3= 1/2(−1) = −1/2,
e quindi il valore ottimo passa da 5/2 a 2.
Modifica di un coefficiente della matrice AN∗
Introduciamo la perturbazione ∆a11= 8 del coefficiente associato alla va-riabile fuori base x1 nel primo vincolo. Quindi il valore a11 diventa pari a 10 ed avremo la seguente nuova matrice:
AN∗ = · 10 1 1 2 ¸ Si ha che: cN∗− cB∗A−1B∗AN∗ = (−1 − 1) − (−2 11/2) = (1 − 13/2). e quindi la soluzione di base del duale associata a B∗non ´e pi´u ammissibile. Ma la soluzione di base del primale associata a B∗resta invariata e continua ad essere ammissibile. Quindi possiamo applicare il simplesso primale con base iniziale B∗.
Introduciamo ora la perturbazione ∆a11= 2 del coefficiente associato alla variabile fuori base x1 nel primo vincolo. Quindi il valore a11diventa pari a 4 ed avremo la seguente nuova matrice:
AN∗ = · 4 1 1 2 ¸ Si ha che: cN∗− cB∗A−1B∗AN∗ = (−1 − 1) − (1 11/2) = (−2 − 13/2).
La soluzione di base del duale associata a B∗ ´e ancora ammissibile. Resta invariata la soluzione di base del primale associata a B∗ e quindi continua ad essere ammissibile. Quindi le due soluzioni sono ottime per i rispet-tivi problemi. Le due soluzioni ottime ed il valore ottimo non subiscono modifiche.
Modifica di un coefficiente della matrice AB∗
Introduciamo la perturbazione ∆a24 = −1 del coefficiente associato alla variabile in base x4 nel secondo vincolo. Quindi il valore a24diventa pari a 0 ed avremo la seguente nuova matrice:
AB∗ = ·
2 0 1 0
¸
Come si vede la nuova matrice non ´e invertibile e quindi B∗ non ´e pi´u una base.
5.7 L’esempio del problema degli aiuti
uma-nitari
Nelle prime lezioni abbaimo introdotto il problema degli aiuti umanitari, che ha la seguente formulazione come problema di PL:
max 14x1+ 5x2+ 4x3
10x1+ 30x2+ 20x3≤ 5100 10x1+ 20x2+ 40x3≤ 8000 30x1+ 10x2+ 5x3≤ 1805
x1, x2, x3≥ 0
Il problema `e in forma canonica ma con l’aggiunta delle variabili non negative y1, y2, y3lo si pu`o ricondurre alla forma standard:
max 14x1+ 5x2+ 4x3
10x1+ 30x2+ 20x3+ y1= 5100
10x1+ 20x2+ 40x3+ y2= 8000 (5.2)
30x1+ 10x2+ 5x3+ y3= 1805 x1, x2, x3, y1, y2, y3≥ 0
Partendo dalla base ammissibile B0={y1, y2, y3} si pu`o applicare il metodo del simplesso e si giunge alla base ottima B∗={y1, x3, x1} con la seguente
riformulazione rispetto ad essa: max 1164− 1 23y2− 52 115y3− 9 23x2 y1= 960 +234y3+1123y2−430 23x2 x3= 193 + 1151 y3−1153 y2−1023x2 (5.3) x1= 28− 4 115y3+ 1 230y2− 6 23x2 x1, x2, x3, y1, y2, y3≥ 0
Da qui si vede immediatamente che la soluzione ottima (unica) del primale `e:
y1∗= 960 x∗3= 193 x∗1= 28 x∗2= y2∗= y3∗= 0.
Essendo partiti con la base B0 le cui variabili formano la matrice identica nella formulazione originaria (5.2), posso, con il metodo visto in precedenza, leggere la matrice A−1B∗ dalla riformulazione (5.3):
A−1B∗ = 1 −11 23 −4 23 0 3 115 − 1 115 0 − 1 230 4 115
La soluzione di base del duale uB∗
associata a B∗sar`a soluzione ottima del duale: uB∗ = cB∗A−1B∗ = (0 4 14)A−1B∗ = µ 0 1 23 52 115 ¶
(per esercizio si ricavi la stessa soluzione anche attraverso le condizioni di complementarit`a).
5.7.1 Modifiche nei dati del problema
Tra i dati del problema degli aiuti umanitari alcuni sono esatti mentre altri sono delle stime. In particolare, la disponibilit`a di farina, acqua e medici-nali e i contenuti di ciascun tipo di pacco sono dati esatti, mentre i valori di utilit`a sono stime. Ora, se ho a che fare con dati stimati `e importante chiedersi quanto la mia soluzione sia sensibile al valore di tali dati. Per esempio, il valore stimato dell’utilit`a del pacco di tipo I `e 14 ma mi posso chiedere come cambiano la soluzione ottima e il valore ottimo del problema se il valore di utilit`a passa da 14 a 13 oppure a 15. Se queste modifiche lasciano sostanzialmente invariata la soluzione ottima del mio problema, allora vuol dire che questa `e poco sensibile a modifiche del dato stimato e di conseguenza possiamo aspettarci conclusioni corrette anche usando una stima non troppo precisa. Viceversa, se le modifiche comportano notevo-li cambiamenti nella soluzione ottima, allora vuol dire che questa `e molto
sensibile a modifiche del dato ed in tal caso per avere conclusioni corrette occorre avere una stima molto precisa del dato. Quindi, in presenza di dati stimati `e importante riuscire a capire che cosa succede quando apporto ad essi delle modifiche.
Ma non `e questo l’unico caso in cui voglio sapere cosa succede se modi-fico un qualche dato. Nel nostro esempio degli aiuti umanitari posso, dopo aver risolto il problema, chiedermi cosa succede se riesco a procurarmi, ad esempio, altri 100 sacchi di farina portando quindi la disponibilit`a di questa da 5100 a 5200 sacchi. Anche in questo caso vogliamo vedere quale impatto avrebbe sulla soluzione ottima del nostro problema la modifica di un dato del problema stesso.
L’analisi di sensitivit`a si occupa proprio di studiare gli effetti di modifiche nei dati del problema e vedremo ora come funziona modificando singolar-mente alcuni dati del nostro problema.
Modifica di un termine noto
Vediamo cosa succede se modifico la disponibilit`a di acqua (che attualmen-te `e b2= 8000) prima incrementandola di 1150 unit`a (∆b2= 1150) e poi di 2300 unit`a (∆b2= 2300).
∆b2= 1150 Il nuovo vettore di termini noti sar`a: b= (5100 9150 1805).
Nella riformulazione rispetto a B∗ le uniche parti che vengono modificate sono i termini noti dei vincoli che diventeranno:
A−1B∗b= (410 223 23)
e il valore dell’obiettivo, che viene modificato della quantit´a: u∗2∆b2= 1
231150 = 50,
e quindi passa da 1164 a 1214. La soluzione di base del primale associata a B∗ ´e ancora ammissibile. Resta invariata la soluzione di base del duale uB∗
associata a B∗e quindi continua ad essere ammissibile. Quindi le due soluzioni sono ottime per i rispettivi problemi. La nuova soluzione ottima del primale ´e:
Il valore ottimo dei due problemi `e ora 1214. ∆b2= 2300 Il nuovo vettore di termini noti sar`a:
b= (5100 10300 1805).
Nella riformulazione rispetto a B∗ le uniche parti che vengono modificate sono i termini noti dei vincoli che diventeranno:
A−1B∗b= (−140 253 18)
e il valore dell’obiettivo, che viene modificato della quantit´a: u∗2∆b2= 1
232300 = 100,
e quindi passa da 1164 a 1264. La riformulazione rispetto a tale base sar`a la seguente: max 1264−231y2−11552y3−239x2 y1=−140 + 4 23y3+11 23y2−430 23x2 x3= 253 + 1151 y3−1153 y2−1023x2 x1= 18− 4 115y3+ 1 230y2− 6 23x2 x1, x2, x3, y1, y2, y3≥ 0
La soluzione di base del primale associata a B∗ non ´e pi´u ammissibile. Ma la soluzione di base del duale uB∗
associata a B∗resta invariata e continua ad essere ammissibile. Quindi possiamo applicare il simplesso duale con base iniziale B∗.
Vediamo anche che cosa succede se apporto la modifica ∆b1 = 100, ov-vero incremento di 100 unit`a la disponibilit`a di sacchi di farina. Si pu`o verificare che il nuovo vettore di termini noti sar`a:
b= (5200 8000 1805).
Nella riformulazione rispetto a B∗ le uniche parti che vengono modificate sono i termini noti dei vincoli che diventeranno:
A−1B∗b= (1060 193 28)
Quindi la base B∗`e ancora ottima. Il valore dell’obiettivo viene modificato della quantit´a:
e quindi resta invariato. Ci`o ci dice che avere 100 sacchi di farina in pi`u non migliora le cose. Questo lo si poteva intuire anche analizzando quello che succedeva in corrispondenza della soluzione ottima trovata. Mentre in tale soluzione acqua e medicinali venivano usati in modo completo, restavano invece inutilizzati 960 sacchi di farina. Ne consegue che, se gi`a con 5100 sacchi di farina si avevano delle eccedenze, non `e aumentando il numero di tali sacchi che possiamo sperare di migliorare il valore ottimo, ma piuttso-sto dovremo incrementare il numero di bottiglie d’acqua e/o di scatole di medicinali.
Modifica del coefficiente di costo di una variabile fuori base Vediamo cosa succede se modifico delle quantit`a ∆cx2 =−1 e ∆cx2 = 1 il valore di utilit`a della variabile fuori base x2 (e quindi dei pacchi di tipo II). La nuova riformulazione rispetto a B∗ `e identica a (5.3) con la sola differenza che nell’obiettivo si deve aggiungere il termine ∆cx2x2.
∆cx2=−1 La nuova riformulazione rispetto a B∗`e la seguente:
max 1164− 1 23y2− 52 115y3−¡9 23+ 1¢x2 y1= 960 + 4 23y3+11 23y2−430 23x2 x3= 193 + 1151 y3−1153 y2−1023x2 x1= 28− 4 115y3+ 1 230y2− 6 23x2 x1, x2, x3, y1, y2, y3≥ 0
La soluzione di base del duale associata a B∗ ´e ancora ammissibile. Resta invariata la soluzione di base del primale associata a B∗ e quindi continua ad essere ammissibile. Quindi le due soluzioni sono ottime per i rispettivi problemi. Le due soluzioni ottime ed il valore ottimo non subiscono modi-fiche.
∆cx2= 1 La nuova riformulazione rispetto a B∗ `e la seguente:
max 1164− 1 23y2− 52 115y3+¡1− 9 23 ¢ x2 y1= 960 + 4 23y3+11 23y2−430 23x2 x3= 193 + 1151 y3− 3 115y2−10 23x2 x1= 28−1154 y3+2301 y2−236x2 x1, x2, x3, y1, y2, y3≥ 0
La soluzione di base del duale associata a B∗non ´e pi´u ammissibile. Ma la soluzione di base del primale associata a B∗ resta invariata e continua ad
essere ammissibile. Quindi possiamo applicare il simplesso primale con base iniziale B∗. Possiamo anche dire che la prima variabile ad entrare in base sar´a certamente la x2(`e l’unica con coefficiente di costo ridotto positivo). Modifica del coefficiente di costo di una variabile appartenente alla base
Vediamo cosa succede se modifico delle quantit`a ∆cx1 = 1 e ∆cx1 =−2 il valore di utilit`a della variabile in base x1(e quindi dei pacchi di tipo I). La nuova riformulazione rispetto a B∗ `e identica a (5.3) con la sola differenza che nell’obiettivo si deve aggiungere il termine
∆cx1x1= ∆cx1 µ 28−1154 y3+ 1 230y2−236 x2 ¶ .
∆cx1= 1 La nuova riformulazione rispetto a B∗ `e la seguente:
max 1192− 9 230y2− 56 115y3−15 23x2 y1= 960 +234y3+1123y2−43023x2 x3= 193 + 1 115y3− 3 115y2−10 23x2 x1= 28− 4 115y3+2301 y2− 6 23x2 x1, x2, x3, y1, y2, y3≥ 0
La soluzione di base del duale associata a B∗ ´e ancora ammissibile. Resta invariata la soluzione di base del primale associata a B∗ e quindi continua ad essere ottima. Il nuovo valore dell’obiettivo varia rispetto al precedente della quantit`a ∆cx1x∗
1= 1∗ 28 = 28. La nuova soluzione ottima del duale sar`a data da cB∗A−1B∗ = µ 0 9 230 56 115 ¶
∆cx1=−2 La nuova riformulazione rispetto a B∗`e la seguente:
max 1108− 12 230y2− 44 115y3+ 3 23x2 y1= 960 +234y3+1123y2−430 23x2 x3= 193 + 1 115y3− 3 115y2−10 23x2 x1= 28− 4 115y3+2301 y2− 6 23x2 x1, x2, x3, y1, y2, y3≥ 0
In tal caso B∗ non ´e pi´u ammissibile per il duale. Ma la soluzione di base