In questo capitolo presenteremo un algoritmo per la risoluzione dei problemi di PL, l’algoritmo del simplesso. Pi`u precisamente vedremo una variante di tale algoritmo (un’altra la vedremo nel Capitolo 5).
4.1 I passi dell’algoritmo
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 l’algoritmo del simplesso procede passando a ogni iterazione da una base ammissibile a una adiacente ancora ammissibile fino a quando `e sodisfatta una qualche condizione di terminazione. 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’obiettivo 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 (3.6). Si noti che problemi non banali sono stabilire se esiste una base ammissibile (o, equivalentemente, stabilire se Sa 6= ∅) 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 (3.6)).
4.1.1 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 nos-tro problema? A questo proposito una particolare rilevanza hanno i coefficienti delle variabili fuori base nell’obiettivo della riformulazione (3.6). Questi ven-gono detti anche coefficienti di costo ridotto delle variabili fuori base e sono
interpretabili come indicazione della variazione dell’obiettivo in corrispondenza dell’incremento di un’unit`a della variabile fuori base corrispondente. Infatti, se consideriamo l’obiettivo della riformulazione (3.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+hil cui valore viene incrementato a 1. Il nuovo valore dell’obiettivo `e γ0+ γh con una variazione rispetto al valore γ0 pari proprio al valore γh del 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. (4.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 condizione sufficiente di ottimalit`a (4.1) si esprime nel modo seguente:
cN − cBA−1B AN ≤ 0. (4.2) Ma vediamo di capire perch´e la condizione (4.1) ci garantisce che la soluzione di base associata a B `e una soluzione 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, (4.3)
ovvero in Sa il valore dell’obiettivo non pu`o mai superare il valore γ0. Essendo 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 succedere che la soluzione di base sia gi`a una soluzione ottima ma la condizione (4.1) non sia soddisfatta. Ci`o per`o pu`o accadere solo nel caso di una soluzione di base degenere.
Esempio 16 Sia data la seguente riformulazione rispetto alla base {x3, x4} di un problema di PL:
max x1
x3= 1− x2
x4=−x1
La soluzione di base corrispondente `e:
x3= 1 x4= 0 x1= x2= 0.
Si noti che `e degenere. La condizione (4.1) non `e soddisfatta (il coefficiente di x1 nell’obiettivo `e pari a 1). Ma passiamo ora, con l’operazione di cardine, 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 (4.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 (4.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.
4.1.2 Verifica di illimitatezza
Supponiamo ora che la condizione di ottimalit`a (4.1) non sia soddisfatta. Un’al-tra 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. (4.4) Vediamo perch´e questa condizione ci garantisce che il problema ha obiettivo illimitato. Prendiamo la riformulazione (3.6) e 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 + αrh |{z} ≥0 xim+h | {z } ≥0 ≥ 0,
quindi per ogni possibile valore non negativo di xim+h le variabili in base con-tinuano 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+h all’infinito non si esce mai da Sa e 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 17 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 coeffici-enti di x3 nelle equazioni dei vincoli. Quindi la condizione (4.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
x1, x2, x3, x4≥ 0
da cui si nota che facendo crescere x3i valori di x1e x2continuano a mantenersi positivi (e quindi non si esce da Sa), mentre il valore dell’obiettivo cresce a +∞.
4.1.3 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 (4.1)) e neppure che il problema ha obiettivo illimitato (cio`e non `e soddisfatta la condizione (4.4)), come possiamo procedere? Passeremo dalla base ammissibile B a 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
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 co-efficiente di costo ridotto γjpositivo (facendo crescere le altre il valore dell’obiet-tivo diminuisce oppure non cambia). Quindi dobbiamo restringere l’attenzione alle sole variabili xim+j tali che γj > 0. Qui adotteremo 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, (4.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 convenzione) la regola di selezionare la variabile con indice pi`u piccolo. Vediamo ora un esempio. Esempio 18 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
x1, x2, x3, x4, x5≥ 0
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.
4.1.4 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 variabile 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’obiettivo, la scelta della vari-abile 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 che deve entrare in base. Si avr`a dunque:
max γ0+ γhxim+h
xi1 = β1+ α1hxim+h
· · ·
xim = βm+ αmhxim+h
x1, . . . , xn≥ 0
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 . (4.6)
Nel caso il minimo sia raggiunto da pi`u variabili la scelta ricade, per convenzione, 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 base B′ ottenuta scambiando xik con xim+h sia ancora ammissibile. Vediamo ora quale sar`a la variabile uscente dalla base nell’esempio precedente.
Esempio 19 Ricordiamo la riformulazione rispetto alla base{x1, x2} del prob-lema 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 variabile 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’op-erazione di cardine nel modo gi`a descritto in precedenza. Vediamo di illustrare tale operazione per il nostro esempio.
Esempio 20 Nell’esempio x3 deve entrare in base e deve uscire x1. L’oper-azione di cardine porta alla seguente riformulL’oper-azione rispetto alla nuova base {x3, x2}:
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, ver-ifica di illimitatezza, scelta della variabile entrante in base, scelta della variabile uscente dalla base, operazione di cardine) sulla nuova base B′.
4.1.5 Lo schema dell’algoritmo
A questo punto possiamo dare lo schema dell’algoritmo del simplesso mettendo assieme i pezzi studiati in precedenza.
ALGORITMO DEL SIMPLESSO
Inizializzazione Sia B0 una base ammissibile e k = 0.
Passo 1- verifica ottimalit`a Se `e soddisfatta la condizione (4.1) , la soluzione 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 (4.4), al-lora 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 (4.5).
Passo 4 - scelta variabile uscente dalla base Si selezioni la variabile xik
che dovr`a uscire dalla base attraverso la regola (4.6).
Passo 5 - operazione di cardine Si generi la nuova base Bk+1 sostituendo 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.
4.1.6 Commenti sul metodo del simplesso
Vediamo ora di fare alcuni commenti sul metodo del simplesso.
Finitezza dell’algoritmo
Partendo da una base B, abbiamo visto che la riformulazione rispetto alla base B′ (in cui xim+h sostituisce xik) ottenuta attraverso l’operazione di cardine `e data in (3.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 (4.5) della variabile entrante in base. • αkh< 0 per la regola di scelta (4.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 as-sociata a B′`e non peggiore rispetto al valore γ0nella 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 13 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 iterazione la nuova soluzione di base ammissibile ha un valore strettamente migliore rispet-to 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 dis-tinte 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. Trovan-doci 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 Btquesta sequenza di basi verr`a di nuovo ripetuta all’infinito senza che l’algoritmo termini. Anche se non le vedremo, esistono co-munque 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 anche in presenza di soluzioni di base ammissibili degeneri.
Soluzioni ottime uniche e multiple
Sia data la solita base B con la riformulazione (3.6). Nel caso in cui valga una condizione pi`u forte rispetto alla condizione di ottimalit`a (4.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 Sail 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 concludere imme-diatamente che esistono pi`u soluzioni ottime. Esistono diversi casi possibili che
ci apprestiamo a descrivere. Prima per`o riscriviamo la riformulazione 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 · · · (4.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. Infatti, se in (4.7) facciamo crescere all’infinito xim+h, vediamo che il valore del-l’obiettivo resta quello ottimo γ0, mentre le variabili xir, r = 1, . . . , m, 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. Infatti, in (4.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 ammissibile ed an-ch’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 senza fare ulteriori considerazioni. In questo caso infatti, per poter restare in Sa in (4.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 21 Sia data la riformulazione rispetto alla base {x3, x4} di un prob-lema 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 x1nelle 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 soluzione 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 soluzione 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
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 x1 e x2 sono 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 matrice 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, la matrice originale dei vincoli di uguaglianza del problema, formino la matrice identica I, ovvero che esistano m variabili [xt1, . . . , xtm] le cui corrispondenti colonne nella matrice A formino la matrice identica di ordine m×m. Queste variabili rappresentano una base per il problema di PL (la matrice identica `e ovviamente invertibile) e in particolare una base ammissibile se tutti i termini noti delle equazioni sono non negativi.