Per la coincidenza tra vertici e soluzioni di base ammissibili, abbiamo visto che possiamo restringere la ricerca delle soluzioni ottime alle sole soluzioni di base ammissibili. Per questa ragione il metodo del simplesso procede pas-sando ad ogni iterazione da una base ammissibile ad una adiacente ancora ammissibile fino a quando ´e sodisfatta una qualche condizione di termina-zione. Il passaggio da una base all’altra viene fatto in modo intelligente: dal momento che vogliamo massimizzare il nostro obiettivo, desideriamo passare da una base ammissibile con una certa soluzione di base associata ad un’altra base ammissibile con una soluzione di base che ha valore dell’o-biettivo migliore (pi´u elevato) o quanto meno non peggiore rispetto a quella precedente.
Vedremo nel seguito come questo sia verificato. Supponiamo ora di avere una base ammissibile B con la relativa riformulazione (2.6). Si noti che pro-blemi non banali sono stabilire se esiste una base ammissibile (o, equivalen-temente, stabilire se Sa6= ∅) e, nel caso esista, determinarne una. Di questi problemi ci occuperemo in seguito. Per il momento supponiamo di avere gi´a a disposizione una base ammissibile B (ovvero βk ≥ 0, k = 1, . . . , m, in (2.6).
Verifica di ottimalit´a
La prima domanda che ci poniamo ´e la seguente: quando possiamo dire che la soluzione di base ammissibile associata a B ´e una soluzione ottima del nostro problema? A questo proposito una particolare rilevanza han-no i coefficienti delle variabili fuori base nell’obiettivo della riformulazione (2.6). Questi vengono detti anche coefficienti di costo ridotto delle variabili fuori base e sono interpretabili come indicazione della variazione
dell’obiet-tivo in corrispondenza dell’incremento di un’unit´a della variabile fuori ba-se corrispondente. Infatti, ba-se consideriamo l’obiettivo della riformulazione (2.6): γ0+ n−m X j=1 γjxim+j,
supponiamo di tenere a 0 il valore di tutte le variabili fuori base tranne la variabile xim+h il cui valore viene incrementato a 1. Il nuovo valore dell’obiettivo ´e γ0+ γh con una variazione rispetto al valore γ0pari proprio al valore γhdel coefficiente di costo ridotto γh. Ma in che modo i coefficienti di costo ridotto ci possono dire se la soluzione di base associata alla base B ´e una soluzione ottima? Una condizione sufficiente per garantire l’ottimalit´a ´e la seguente:
γj≤ 0 j = 1, . . . , n− m. (3.1)
Si richiede quindi che i coefficienti di costo ridotto delle variabili fuori base siano tutti non positivi. Ricordando che γj sono le componenti del vettore cN − cBA−1B AN (detto anche, per questa ragione, vettore dei coefficienti di costo ridotto), in forma vettoriale la condizone sufficiente di ottimalit´a (3.1) si esprime nel modo seguente:
cN− cBA−1B AN ≤ 0. (3.2)
Ma vediamo di capire perch´e la condizione (3.1) ci garantisce che la solu-zione di base associata a B ´e una solusolu-zione ottima del problema. Sappiamo che il valore dell’obiettivo in corrispondenza di questa soluzione di base ´e γ0. Notiamo inoltre che in Sa si ha xim+j ≥ 0, j = 1, . . . , n − m. Quindi per il valore dell’obiettivo in Sa si avr´a:
γ0+ n−m X j=1 γj |{z} ≤0 xim+j | {z } ≥0 ≤ γ0, (3.3)
ovvero in Sa il valore dell’obiettivo non pu´o mai superare il valore γ0. Es-sendo questo anche il valore dell’obiettivo per la nostra soluzione di base, tale soluzione di base ´e anche soluzione ottima del nostro problema. ´
E importante sottolineare che la condizione ´e solo sufficiente, cio´e pu´o suc-cedere che la soluzione di base sia gi´a una soluzione ottima ma la condi-zione (3.1) non sia soddisfatta. Ci´o per´o pu´o accadere solo nel caso di una soluzione di base degenere.
Esempio 6 Sia data la seguente riformulazione rispetto alla base{x3, x4} di un problema di PL:
x3= 1− x2
x4=−x1
x1, x2, x3, x4≥ 0 La soluzione di base corrispondente ´e:
x3= 1 x4= 0 x1= x2= 0.
Si noti che ´e degenere. La condizione (3.1) non ´e soddisfatta (il coefficiente di x1 nell’obiettivo ´e pari a 1). Ma passiamo ora, con l’operazione di car-dine, alla base adiacente{x1, x3}. La riformulazione rispetto a questa base ´e la seguente:
max −x4
x3= 1− x2
x1=−x4
x1, x2, x3, x4≥ 0
Ora la condizione sufficiente ´e soddisfatta e quindi la soluzione di base associata ´e ottima. Ma se osserviamo la soluzione di base associata, questa coincide esattamente con la precedente.
Si pu´o comunque dimostrare che data una soluzione di base ottima esiste sempre almeno una base corrispondente per la quale la condizione (3.1) ´e soddisfatta. Nell’esempio abbiamo visto come la stessa soluzione di base sia rappresentata sia dalla base{x3, x4} che dalla base {x1, x3}. La prima base non soddisfa la condizione (3.1), ma questa ´e soddisfatta dalla seconda base. Torneremo in seguito su un’altra questione e cio´e quando possiamo dire che il problema ammette un’unica soluzione ottima o pi´u soluzioni ottime. Verifica di illimitatezza
Supponiamo ora che la condizione di ottimalit´a (3.1) non sia soddisfatta. Un’altra domanda che possiamo porci ´e la seguente: quando il problema ha valore dell’obiettivo illimitato? Una condizione sufficiente perch´e questo si verifichi ´e la seguente:
∃ γh> 0 : αrh≥ 0 r = 1, . . . , m. (3.4)
Vediamo perch´e questa condizione ci garantisce che il problema ha obiettivo illimitato. Prendiamo la riformulazione (2.6) ed in essa poniamo a zero tutte
le variabili fuori base tranne la variabile xim+h. Ci´o che rimane ´e: max γ0+ γhxim+h xi1 = β1+ α1hxim+h · · · xim = βm+ αmhxim+h x1, . . . , xn≥ 0
Cosa succede se faccio crescere il valore della variabile xim+h? Si ha che per ogni r∈ {1, . . . , m}: xir = βr |{z} ≥0 + α1h |{z} ≥0 xim+h | {z } ≥0 ≥ 0,
quindi per ogni possibile valore non negativo di xim+h le variabili in base continuano ad avere valore non negativo e quindi rimaniamo all’interno di Sa. Ma vediamo ora cosa succede all’obiettivo:
γ0+ γh |{z} >0 xim+h |{z}→ xim+h→+∞ +∞,
e quindi facendo crescere xim+hall’infinito non si esce mai da Saed il valore dell’obiettivo cresce anch’esso all’infinito. Ne consegue che il problema ha Sott=∅ in quanto il valore dell’obiettivo ´e illimitato.
Esempio 7 Sia data la seguente riformulazione rispetto alla base{x1, x2} di un problema di PL:
max 2 + x3− x4
x1= 2 + x3+ x4
x2= 1 + 2x3+ x4
x1, x2, x3, x4≥ 0
Il coefficiente di x3 nell’obiettivo ´e positivo e non negativi sono anche i coefficienti di x3 nelle equazioni dei vincoli. Quindi la condizione (3.4) ´e soddisfatta e possiamo concludere che il problema ha obiettivo illimitato. Infatti, se poniamo x4= 0 il problema diventa:
max 2 + x3
x1= 2 + x3
x2= 1 + 2x3
da cui si nota che facendo crescere x3i valori di x1e x2continuano a man-tenersi positivi (e quindi non si esce da Sa), mentre il valore dell’obiettivo cresce a +∞.
Scelta della variabile da far entrare in base
Se, data la base ammissibile B, non possiamo concludere che la soluzione di base associata ´e ottima (cio´e non ´e soddisfatta la condizione (3.1)) e neppure che il problema ha obiettivo illimitato (cio´e non ´e soddisfatta la condizione (3.4)), come possiamo procedere? Passeremo dalla base ammissibile B ad una nuova base ammissibile B′ ma facendo in modo che la soluzione di base associata a B′ abbia valore dell’obiettivo migliore o quantomeno non peggiore rispetto al valore della soluzione di base associata a B. Per prima cosa individuiamo una regola per decidere come scegliere la variabile xim+h fuori base che dovr´a entrare nella nuova base. Ricordiamo la formula dell’obiettivo: γ0+ n−m X j=1 γjxim+j.
Nella soluzione di base associata a B tutte le variabili xim+j, j = 1, . . . , n− m, sono fissate a 0. Se vogliamo incrementare il valore dell’obiettivo, quali di queste variabili dovremo far crescere dal valore 0? Dovremo far crescere quelle con coefficiente di costo ridotto γj positivo (facendo crescere le altre il valore dell’obiettivo diminuisce oppure non cambia). Quindi dobbiamo restringere l’attenzione alle sole variabili xim+j tali che γj> 0. Qui adotte-remo la regola di scelta tra queste variabili che consiste nel scegliere quella che fa crescere pi´u rapidamente il valore dell’obiettivo e cio´e la variabile xim+h tale che:
γh= max
j=1,...,n−mγj, (3.5)
tenendo comunque presente che questa non ´e l’unica regola possibile. Nel caso il massimo sia raggiunto da pi´u variabili adottiamo (come pura conven-zione) la regola di selezionare la variabile con indice pi´u piccolo. Vediamo ora un esempio.
Esempio 8 Sia data la seguente riformulazione rispetto alla base{x1, x2} di un problema di PL:
max 2 + 2x3+ 2x4+ x5
x1= 1− x3+ x4+ x5
x2= 2− x3− x4− x5
In questo caso tutte le variabili fuori base hanno coefficiente di costo ridotto positivo. Tra queste considero quelle il cui coefficiente di costo ridotto ´e massimo (la x3e la x4). Tra le due scelgo quella con indice minore e quindi la x3. Quindi scegliamo la variabile fuori base x3 come nuova variabile da far entrare in base.
Scelta della variabile uscente dalla base
Una volta scelta la variabile xim+h che dovr´a entrare in base, dobbiamo stabilire quale variabile in base dovr´a farle posto, ovvero quale sar´a la va-riabile in base xik che dovr´a uscire dalla base. Se la scelta della variabile che entra in base ´e guidata dal desiderio di far crescere il valore dell’obiet-tivo, la scelta della variabile uscente dalla base sar´a motivata dal desiderio di non uscire dalla regione ammissibile. Supponiamo come in precedenza di fissare a 0 tutte le variabili fuori base tranne la xim+h. Si avr´a dunque:
max γ0+ γhxim+h
xi1 = β1+ α1hxim+h
· · ·
xim = βm+ αmhxim+h
x1, . . . , xn≥ 0
Fino a quando possiamo far crescere il valore di xim+h? Abbiamo due casi: Caso 1 Per tutti gli r∈ {1, . . . , m} tali che αrh≥ 0 vediamo che:
xir = βr+ αrh |{z} ≥0 xim+h | {z } ≥0 ≥ βr≥ 0.
Quindi in questo caso non abbiamo alcuna restrizione sulla crescita di xim+h.
Caso 2 Per gli r tali che αrh < 0, allora vediamo che il valore di xim+h
pu´o crescere al massimo fino a: −αβr
rh
e oltre questo valore la variabile xir assume valori negativi (si esce quindi dalla regione ammissibile Sa).
Se vogliamo rimanere in Sa, ci dovremo arrestare non appena una variabile xir con αrh< 0 si annulla al crescere di xim+h. Questa sar´a la variabile xik
tale che αkh< 0 e −αβk kh = min r: αrh<0 ½ −αβr rh ¾ . (3.6)
Nel caso il minimo sia raggiunto da pi´u variabili la scelta ricade, per con-venzione, su quella con indice pi´u piccolo. La variabile xik sar´a quella che uscir´a dalla base. Va ribadito come questa scelta garantisca che la nuova ba-se B′ ottenuta scambiando xik con xim+h sia ancora ammissibile. Vediamo ora quale sar´a la variabile uscente dalla base nell’esempio precedente. Esempio 9 Ricordiamo la riformulazione rispetto alla base {x1, x2} del problema di PL dell’esempio:
max 2 + 2x3+ 2x4+ x5
x1= 1− x3+ x4+ x5
x2= 2− x3− x4− x5
x1, x2, x3, x4, x5≥ 0
In precedenza abbiamo visto che la regola di scelta della variabile fuori base che dovr´a entrare in base ci porta a scegliere la x3. Quale variabile dovr´a uscire dalla base? Sia la x1 che la x2 sono candidate (per entrambe il coefficiente di x3 nelle rispettive equazioni ´e negativo). Andiamo ora a prendere i rapporti, cambiati di segno, tra i termini noti delle equazioni e i coefficienti della x3. Abbiamo:
x1→ − 1
−1 = 1 x2→ −
2 −1 = 2.
Il minimo dei rapporti (pari a 1) ´e raggiunto in corrispondenza della va-riabile x1 e quindi questa sar´a la variabile che dovr´a uscire dalla base. A conferma di ci´o notiamo che fissando a 0 tutte le variabili fuori base tranne la x3 si ottiene:
max 2 + 2x3
x1= 1− x3
x2= 2− x3
x1, x2, x3, x4, x5≥ 0
e si pu´o vedere che per mantenersi in Sa (cio´e per mantenere non negative le variabili in base x1 e x2) possiamo far crescere x3 al massimo fino al valore 1. In corrispondenza di tale valore si annulla la variabile x1 e tale variabile sar´a quella che dovr´a uscire di base.
A questo punto, una volta selezionata la variabile entrante in base (la xim+h) e quella uscente di base (la xik) con le regole viste, non resta che compiere l’operazione di cardine nel modo gi´a descritto in precedenza. Vediamo di illustrare tale operazione per il nostro esempio.
Esempio 10 Nell’esempio x3 deve entrare in base e deve uscire x1. L’o-perazione di cardine porta alla seguente riformulazione rispetto alla nuova base{x2, x3}:
max 4− 2x1+ 4x4+ 3x5
x3= 1− x1+ x4+ x5
x2= 3 + x1− 2x4− 2x5
x1, x2, x3, x4, x5≥ 0
Una volta eseguita l’operazione di cardine e passati alla nuova base B′
non si dovr´a fare altro che ripetere le operazioni viste sopra (verifica di ottimalit´a, verifica di illimitatezza, scelta della variabile entrante in base, scelta della variabile uscente dalla base, operazione di cardine) sulla nuova base B′. Possiamo quindi riassumere il metodo del simplesso attraverso il seguente schema.
METODO DEL SIMPLESSO
Inizializzazione Sia B0 una base ammissibile e k = 0.
Passo 1- verifica ottimalit´a Se ´e soddisfatta la condizione (3.1) , la so-luzione di base associata a Bk ´e una soluzione ottima del problema e ci si arresta. Altrimenti si vada al Passo 2.
Passo 2 - verifica di illimitatezza Se ´e soddisfatta la condizione (3.4), allora si ha Sott=∅ in quanto l’obiettivo del problema ´e illimitato e ci si arresta. Altrimenti si vada al Passo 3.
Passo 3 - scelta variabile entrante in base Si selezioni la variabile xim+h
che dovr´a entrare in base attraverso la regola (3.5).
Passo 4 - scelta variabile uscente dalla base Si selezioni la variabile xik che dovr´a uscire dalla base attraverso la regola (3.6).
Passo 5 - operazione di cardine Si generi la nuova base Bk+1 sosti-tuendo in Bk la variabile xik con la variabile xim+h e si esegua la corrispondente operazione di cardine. Quindi, si ponga k = k + 1 e si ritorni al Passo 1.
Come esercizio si proceda nella risoluzione del problema dell’esempio. Commenti sul metodo del simplesso
Per prima cosa va puntualizzato che, anche se ampiamente utilizzato, il metodo del simplesso non ´e l’unico metodo per risolvere problemi di PL. Qui ci limitiamo a citare altri metodi di risoluzione per i problemi di PL, gli algoritmi del punto interno.
Notiamo poi, come gi´a fatto in precedenza, che abbiamo bisogno di partire con una base ammissibile B0. Vedremo in seguito un metodo (il metodo due fasi) che ci permetter´a di stabilire se esiste una base ammissibile per il problema e, nel caso esista, come ottenerla.
Partendo da una base B, abbiamo visto che la riformulazione rispetto al-la base B′ ottenuta attraverso l’operazione di cardine ´e data in (2.8). Da questa si vede immediatamente che il valore dell’obiettivo nella soluzione di base associata alla nuova base B′ ´e
γ0− γh
βk
αkh
.
Quando applichiamo il metodo del simplesso abbiamo che:
• βk≥ 0 per l’ammissibilit´a della soluzione di base associata a B. • γh> 0 per la regola di scelta (3.5) della variabile entrante in base. • αkh< 0 per la regola di scelta (3.6) della variabile uscente dalla base. Quindi si ha: γ0− γh |{z} >0 ≥0 z}|{ βk αkh |{z} <0 ≥ γ0.
Questo ci conferma che il valore dell’obiettivo nella nuova soluzione di base associata a B′ ´e non peggiore rispetto al valore γ0 nella soluzione di base associata a B. Inoltre, nel caso βk> 0, il che si verifica sempre nel caso di soluzioni di base non degeneri, il nuovo valore dell’obiettivo ´e strettamente migliore rispetto al precedente. Nel caso degenere pu´o invece succedere che i due valori siano uguali. In questo caso si pu´o dimostrare che le due basi B e B′ rappresentano la stessa soluzione di base. Quanto visto ci dice qualcosa riguardo la finitezza del metodo del simplesso, come stabilito nella seguente osservazione.
Osservazione 10 Se tutte le soluzioni di base ammissibili in un problema di PL sono non degeneri, allora il metodo del simplesso termina in un numero finito di iterazioni.
Dimostrazione Come abbiamo visto nel caso non degenere ad ogni ite-razione la nuova soluzione di base ammissibile ha un valore strettamente migliore rispetto alla precedente e quindi ´e diversa da tutte quelle che la hanno preceduta, cio´e tutte le soluzioni di base ammissibili associate alle basi B0, B1, B2, . . . sono distinte tra loro. Essendo il numero di soluzioni di base ammissibili finito (si ricordi che queste coincidono con i vertici che sono in numero finito), il metodo dovr´a arrestarsi dopo un numero finito di iterazioni o restituendo una soluzione ottima oppure stabilendo che il problema ha obiettivo illimitato.
Ma cosa succede se ci sono delle soluzioni di base ammissibili degeneri? Nel caso ci siano vertici degeneri si pu`o verificare la situazione di ciclaggio. Trovandoci in un vertice degenere, l’algoritmo del simplesso pu`o generare la seguente sequenza di basi che rappresentano tutte questo stesso vertice degenere:
Bt→ Bt+1→ · · · → Bt+r−1 → Bt+r= Bt.
Una volta tornato nella base Bt questa sequenza di basi verr`a di nuovo ripetuta all’infinito senza che l’algoritmo termini. Anche se non le vedre-mo, esistono comunque delle regole particolari per la scelta delle variabili da far entrare e uscire di base, dette regole anticiclaggio, che consentono all’algoritmo di terminare in un numero finito di iterazioni.
Soluzioni ottime uniche e multiple
Sia data la solita base B con la riformulazione (2.6). Nel caso in cui valga una condizione pi´u forte rispetto alla condizione di ottimalit´a (3.1) e cio´e se vale:
γj< 0 j = 1, . . . , m,
allora possiamo dire con certezza che la soluzione di base associata a B non solo ´e soluzione ottima del problema ma ´e anche l’unica soluzione ottima del problema. Infatti, per il valore dell’obiettivo in Sa si avr´a:
γ0+ n−m X j=1 γj |{z} <0 xim+j | {z } ≥0 ≤ γ0,
ovvero in Sa il valore dell’obiettivo non pu´o mai superare il valore γ0e pu´o essere uguale a γ0 solo se tutte le variabili xim+j, j = 1, . . . , n− m, hanno valore nullo e cio´e in corrispondenza della nostra soluzione di base. Quindi tale soluzione di base ´e la sola soluzione ottima.
Ma cosa succede se esiste un qualche γh = 0? Non possiamo conclude-re immediatamente che esistono pi´u soluzioni ottime. Esistono diversi casi
possibili che ci apprestiamo a descrivere. Prima per´o riscriviamo la riformu-lazione rispetto alla base B tenendo a 0 tutte le variabili fuori base tranne la xim+h con γh= 0. Avremo: max γ0 xi1 = β1+ α1hxim+h · · · (3.7) xim = βm+ αmhxim+h x1, . . . , xn≥ 0 Vediamo ora quali sono i casi possibili. Caso 1 Se esiste h tale che γh= 0 e
αrh≥ 0 r = 1, . . . , m,
allora esiste certamente un insieme illimitato di soluzioni ottime. In-fatti, se in (3.7) facciamo crescere all’infinito xim+h, vediamo che il valore dell’obiettivo resta quello ottimo γ0, mentre le variabili xir
continuano a mantenersi non negative e quindi non si esce da Sa. Caso 2 Se esiste h tale che γh= 0 e
∀ r : αrh< 0 si ha che βr> 0,
allora esiste certamente un insieme limitato di soluzioni ottime. In-fatti, in (3.7) possiamo far crescere xim+h fino al valore positivo
−αβk kh = min r: αrh<0 ½ −αβr rh ¾
mantenendo il valore dell’obiettivo pari a quello ottimo γ0. Quindi, un’operazione di cardine che scambi la variabile xik con la variabile xim+h conduce in questo caso ad una nuova soluzione di base ammis-sibile ed anch’essa ottima. Risulteranno ottimi anche tutti i punti lungo il segmento che congiunge le due soluzioni di base ammissibili (o vertici) ottime.
Caso 3 Se per ogni h tale che γh= 0 si ha che: ∃ r : αrh< 0 e βr= 0,
allora non possiamo dire se esiste un’unica soluzione ottima o se vi sono soluzioni ottime multiple. In questo caso infatti, per poter re-stare in Sa in (3.7) possiamo solo mantenere il valore di xim+h pari a 0 e quindi rimanere nella soluzione di base corrente.
I diversi casi saranno ora illustrati attraverso alcuni esempi.
Esempio 11 Sia data la riformulazione rispetto alla base {x3, x4} di un problema di PL.
max 4− x1− x2
x3= 2 + x1− x2
x4= 1− 2x2
x1, x2, x3, x4≥ 0
In questo caso tutti i coefficienti di costo ridotto sono strettamente negativi, quindi la soluzione di base ´e ottima ed ´e l’unica soluzione ottima.
Sia data la riformulazione rispetto alla base{x3, x4} di un problema di PL.
max 4− x2
x3= 2 + x1− x2
x4= 1− 2x2
x1, x2, x3, x4≥ 0
Qui ci troviamo nel Caso 1: il coefficiente di costo ridotto di x1 ´e nullo e i coefficienti di x1 nelle equazioni sono tutti non negativi. Quindi tutti i punti del seguente insieme:
(t, 0, 2 + t, 1) ∀ t ≥ 0,
sono soluzioni ottime del problema (si noti che t = 0 coincide con la solu-zione di base associata a{x3, x4}).
Sia data la riformulazione rispetto alla base{x3, x4} di un problema di PL.
max 4− x2
x3= 2 + x1− x2
x4= 1− x1+ 2x2
x1, x2, x3, x4≥ 0
Qui ci troviamo nel Caso 2: il coefficiente di costo ridotto di x1 ´e nullo e nelle equazioni in cui il coefficiente di x1 ´e negativo, il termine noto ´e positivo. Quindi tutti i punti del seguente insieme:
(t, 0, 2 + t, 1− t) 0 ≤ t ≤ 1,
sono soluzioni ottime del problema (si noti che t = 0 coincide con la solu-zione di base associata a{x3, x4} e t = 1 con quella adiacente {x1, x3}).
Sia data la riformulazione rispetto alla base{x3, x4} di un problema di PL.
max 4− x2
x3= 2 + x1− x2
x4=−x1− x2
x1, x2, x3, x4≥ 0
Qui ci troviamo nel Caso 3: il coefficiente di costo ridotto di x1 ´e nullo e in una equazione in cui il coefficiente di x1 ´e negativo, il termine noto ´e nullo. In questo particolare esempio esiste una sola soluzione ottima. Pi´u precisamente esiste una sola soluzione ammissibile. Infatti, l’equazione
x4=−x1− x2
pu´o essere soddisfatta in Sa solo se le variabili x1e x2sono entrambe nulle, ovvero in corrispondenza della soluzione di base associata a{x3, x4}. Sia data la riformulazione rispetto alla base{x4, x5} di un problema di PL.
max 2− x3
x4= x1− x2− x3
x5=−x1+ x2+ x3
x1, x2, x3, x4, x5≥ 0
Qui ci troviamo ancora nel Caso 3: il coefficiente di costo ridotto di x1 e x2 ´e nullo, in almeno una equazione in cui il coefficiente di x1 ´e negativo si ha che il termine noto ´e nullo e lo stesso vale per x2. Si pu´o dimostrare per´o che in questo caso tutte le soluzioni:
x3= x4= x5= 0 x1= x2= α ∀ α ≥ 0,
sono ammissibili e ottime (il caso α = 0 coincide con la soluzione di base associata alla base{x4, x5}).
Come individuare la matrice A−1B
Come vedremo ´e importante conoscere, data una base B e la relativa ma-trice AB, l’inversa A−1B di tale matrice. Non ´e per´o sempre necessario calcolare da zero tale inversa. In alcuni casi la riformulazione rispetto alla base B ci fornisce gi´a la matrice A−1B .
Supponiamo che alcune colonne della matrice A formino la matrice