seconda parte

23
3.5. BASI DEGENERI E TERMINAZIONE
3.5
Basi degeneri e terminazione
La descrizione del metodo del simplesso data finora lascia aperte due questioni
fondamentali:
1. Il metodo del simplesso giunge sempre a terminazione?
2. Com’`e possibile determinare una base ammissibile da cui partire? (Si
noti infatti che finora abbiamo assunto di conoscere una base ammissibile
iniziale B.)
Osserviamo innanzitutto che, affinch´e il metodo del simplesso possa essere considerato un vero e proprio algoritmo, `e necessario specificare con quale
criterio vengono scelte la variabile uscente dalla base e quella entrante quando
pi`
u variabili soddisfano le condizioni dell’algoritmo. In altre parole, l’indice k
scelto al Passo 3 e l’indice h selezionato al Passo 5 potrebbero non essere univocamente determinati. Una regola di scelta di questi due indici `e detta una
regola di pivot, in quanto ci dice senza ambiguit`a su quale elemento effettuare il
pivot. In questa sezione mostreremo che, per un’opportuna scelta della regola
di pivot, la risposta alla prima domanda `e affermativa. Rinviamo alla sezione
successiva l’analisi della seconda questione.
Dati un problema di programmazione lineare (3.1)–(3.4) ed una base ammissibile da cui partire, diciamo che il metodo del simplesso (con una data
regola di pivot) cicla su tale problema se c’`e una base che viene visitata in due
iterazioni distinte.
Lemma 3.2 Se l’algoritmo del simplesso applicato ad un dato programma lineare non giunge a terminazione, allora cicla.
Dimostrazione. Il numero di basi della matrice A ∈ Rm×n `e al massimo il numero
n
).
di sottoinsiemi di cardinalit`a m di un insieme universo con n elementi, cio`e (m
In particolare, il numero di basi ammissibili di A `e finito. Allora, se il metodo
del simplesso non giunge a terminazione, deve necessariamente visitare la stessa
base pi`
u di una volta.
◻
Si ricordi che ad ogni iterazione del metodo del simplesso si costruisce una
nuova soluzione di base a partire dalla soluzione di base corrente aumentando
il valore di una variabile non in base ad un certo valore t¯ (e modificando di
conseguenza il valore delle variabili in base). Precisamente, si sceglie
t¯ =
min
i∈{1,...,m} ∶ a
¯ik >0
{
¯bi
}.
a
¯ik
(3.22)
Si noti che t¯ = 0 se e solo se esiste un indice i tale che ¯bi = 0 e a
¯ik > 0; in tal caso,
x
¯B[i] = 0. Una soluzione di base con quest’ultima propriet`a `e detta degenere;
diamo ora la definizione precisa.
Una base ammissibile B si dice non degenere se la soluzione di base x
¯ relativa
−1
¯
a B soddisfa x
¯i > 0 per ogni i ∈ B, cio`e se b = AB b > 0. In caso contrario, la
base `e detta degenere.
24
CAPITOLO 3. IL METODO DEL SIMPLESSO
Lemma 3.3 Se l’algoritmo del simplesso applicato ad un dato programma lineare cicla, allora ad una certa iterazione si ha t¯ = 0 e l’algoritmo visita una
base degenere. Inoltre, tale iterazione non cambia la soluzione di base (ed il suo
valore).
Dimostrazione. Se t¯ fosse positivo ad ogni iterazione, allora per la (3.17) il valore
della funzione obiettivo aumenterebbe strettamente ad ogni iterazione. Ne segue
che ogni soluzione di base (e, per l’Osservazione 2.5, ogni base) verrebbe visitata
al massimo una volta, quindi l’algoritmo non ciclerebbe. Concludiamo dunque
che t¯ = 0 in qualche iterazione.
Come osservato sopra, se t¯ = 0 allora x
¯B[i] = 0 per qualche i ∈ {1, . . . , m},
dunque la base corrente `e degenere. Ricordando che la nuova soluzione di base
`e data dal vettore x(t¯) = x(0) (dove x(t) `e stato definito nella Sezione 3.2),
si verifica immediatamente che la soluzione di base relativa alla nuova base
coincide con la soluzione precedente (nonostante le basi siano distinte).
◻
Un’iterazione del metodo del simplesso che non modifica la soluzione di base
(cio`e un’iterazione in cui t¯ = 0) `e detta pivot degenere.
Dunque, se durante l’esecuzione del metodo del simplesso vengono visitate
solo basi non degeneri (cio`e se effettuiamo sempre pivot non degeneri), allora
tale metodo termina dopo un numero finito di iterazioni. Tuttavia questo in
generale non accade ed `e effettivamente possibile che il metodo cicli. Fortunatamente esistono regole di pivot che garantiscono che il metodo del simplesso
termini in tempo finito. Ad esempio, una tale regola `e la cosiddetta regola di
Bland, in cui si sceglie come variabile entrante la variabile di indice minimo tra
quelle di costo ridotto positivo e come variabile uscente la variabile di indice
minimo tra quelle che minimizzano il rapporto in (3.22). Di seguito riportiamo
una definizione formale di tale regola di pivot.
Regola di Bland Ad ogni iterazione dell’algoritmo del simplesso, relativa ad
una base ammissibile B = {B[1], . . . , B[m]}:
tra tutte le variabili di costo ridotto positivo, si faccia entrare in base la
variabile xk per cui l’indice k `e minimo;
definito t¯ come in (3.22), si faccia uscire dalla base la variabile xB[h] che
ha indice B[h] minimo tra quelle che soddisfano a
¯hk > 0 e ¯bh /¯
ahk = t¯.
Esempio. Si consideri il seguente problema in forma tableau, relativo a qualche
iterazione dell’algoritmo del simplesso:
z
−
x1 +
3x2
3
2 x2
0.4x2
1
3 x2
−
7x3
2
+
3 x3
− 0.2x3
+ x5
2
−
3 x3 + x4
=
=
=
=
26
18
3.6
3
Le variabili di costo ridotto positivo sono x2 e x3 , con costi ridotti 3 e 7.
Applicando la regola di Bland, selezioniamo come variabile entrante quella di
indice minimo tra le due, cio`e x2 .
25
3.5. BASI DEGENERI E TERMINAZIONE
Per scegliere la variabile uscente, dobbiamo applicare il criterio del minimo
18 3.6 3
rapporto. Si noti che min { 3/2
, 0.4 , 1/3 } = 9 e che tale valore `e ottenuto su
due righe del tableau: quella in cui `e in base x4 e quella in cui `e in base x5 .
Selezioniamo come variabile uscente quella di indice minimo tra le due, cio`e x4 .
Teorema 3.4 Il metodo del simplesso con la regola di Bland termina per ogni
A ∈ Rm×n , b ∈ Rm , c ∈ Rn e per ogni base ammissibile iniziale.
Dimostrazione. Per contraddizione, supponiamo che esistano A ∈ Rm×n , b ∈ Rm ,
c ∈ Rn ed una base ammissibile B = {B[1], . . . , B[m]} tali che il metodo del
simplesso con la regola di Bland applicato al programma lineare (3.1)–(3.4) a
partire dalla base B non termini. Scegliamo A, b, c e B in modo tale che il
problema abbia il minimo numero possibile di variabili (cio`e n `e il pi`
u piccolo
possibile). Chiamiamo tale problema un controesempio minimo.
Il problema in forma tableau rispetto alla base B `e
max z
(3.23)
− ∑ c¯j xj = z¯
s.a z
(3.24)
j∈N
xB[i] + ∑ a
¯ij xj = ¯bi ,
i = 1, . . . , m
(3.25)
j = 1, . . . , n.
(3.26)
j∈N
xj ≥ 0,
Estendiamo il vettore c¯N ad un vettore c¯ ∈ Rn ponendo c¯j = 0 per j ∈ B, e la
matrice A¯N ad una matrice A¯ ∈ Rm×n ponendo, per i = 1, . . . , m e j ∈ B,
⎧
⎪
⎪1, j = B[i]
a
¯ij = ⎨
⎪
⎪
⎩0, j ≠ B[i].
I vincoli (3.24)–(3.25) possono pertanto essere riscritti cos`ı:
n
z − ∑ c¯j xj = z¯
j=1
n
¯ij xj = ¯bi ,
∑a
i = 1, . . . , m.
j=1
La dimostrazione consiste nel provare una serie di propriet`a del controesempio minimo, fino ad ottenere una contraddizione.
Fatto 1 Durante l’esecuzione del metodo del simplesso con la regola di Bland
applicato al controesempio minimo, ogni variabile entra ed esce di base un
numero infinito di volte.
Dimostrazione. Supponiamo per assurdo che da una certa iterazione p in poi
la variabile xℓ rimanga sempre in base oppure sempre fuori base. Possiamo
26
CAPITOLO 3. IL METODO DEL SIMPLESSO
assumere senza perdita di generalit`a p = 0, dunque la base corrente durante tale
iterazione `e proprio la base iniziale B.
Supponiamo prima che xℓ sia sempre fuori base e consideriamo il problema ottenuto da (3.23)–(3.26) eliminando la colonna del tableau relativa alla
variabile xℓ . Tale problema ha una variabile in meno di prima ed `e ancora in
forma tableau rispetto alla base B. Inoltre, anche per questo nuovo problema il
metodo del simplesso con la regola di Bland non termina, perch´e i passi eseguiti
dall’algoritmo saranno esattamente gli stessi, dato che nessuno di essi dipende dalla colonna del tableau relativa ad xℓ (stiamo infatti assumendo che xℓ
non venga mai selezionata come variabile entrante). Poich´e avevamo scelto un
controesempio con il minimo numero di variabili, otteniamo una contraddizione.
Supponiamo ora che xℓ sia sempre in base, diciamo ℓ = B[i], e consideriamo
il problema ottenuto da (3.23)–(3.26) eliminando la colonna del tableau relativa
ad xℓ ed il vincolo xℓ + ∑j∈N a
¯ij xj = ¯bi . Tale problema ha una variabile ed un
vincolo in meno dell’originale ed `e in forma tableau rispetto alla base B ∖ {ℓ}.
Inoltre, anche per questo nuovo problema il metodo del simplesso con la regola
di Bland non termina, perch´e i passi eseguiti dall’algoritmo saranno gli stessi,
dato che nessuno di essi dipende dalla colonna del tableau relativa a xℓ n´e dalla
riga del tableau relativa a xℓ (stiamo infatti assumendo che xℓ non venga mai selezionata come variabile uscente). Poich´e avevamo scelto un controesempio con
il minimo numero di variabili, otteniamo di nuovo una contraddizione. Dunque
il Fatto 1 `e vero.
◇
Fatto 2 Durante l’esecuzione del metodo del simplesso con la regola di Bland
applicato al controesempio minimo, da una certa iterazione in poi la soluzione
di base corrente resta invariata.
Dimostrazione. Poich´e l’algoritmo non termina, da una certa iterazione in poi
tutti i pivot devono essere degeneri, dato che i pivot non degeneri aumentano
il valore della funzione obiettivo della soluzione di base corrente. Allora, per il
Lemma 3.3, la soluzione di base corrente non cambia mai durante l’esecuzione
delle iterazioni successive dell’algoritmo.
◇
D’ora in avanti assumeremo senza perdita di generalit`a che la soluzione
di base resti invariata durante tutta l’esecuzione dell’algoritmo (cio`e sin dalla
prima iterazione).
Fatto 3 ¯b = 0 e z¯ = 0.
Dimostrazione. Supponiamo per assurdo che esista un indice h ∈ {1, . . . , m} tale
che ¯bh > 0. Allora x
¯B[h] = ¯bh > 0. Per il Fatto 1, esiste un’iterazione durante
la quale xB[h] esce di base. All’iterazione successiva, il valore di xB[h] sar`a 0,
dunque la soluzione sar`a diversa dalla precedente, contraddicendo il Fatto 2.
Quindi ¯b = 0. Da questo segue immediatamente che z¯ = c⊺B ¯b = 0 (si veda la
definizione (3.8)) e dunque il Fatto 3 `e verificato.
◇
Per il Fatto 1, a qualche iterazione p la variabile xn sar`a in base e sar`a scelta
come variabile uscente. Possiamo assumere senza perdita di generalit`a p = 0,
27
3.5. BASI DEGENERI E TERMINAZIONE
dunque la base corrente durante tale iterazione `e B. Sia h l’indice di riga tale
che n = B[h] e sia xk la variabile entrante durante tale iterazione.
Fatto 4 a
¯hk > 0 e a
¯ik ≤ 0 per i = 1, . . . , m, i ≠ h.
Dimostrazione. Poich´e xn `e la variabile di indice massimo e viene scelta come
variabile uscente, per la regola di Bland xn deve essere l’unica candidata ad
uscire di base, cio`e il valore del rapporto ¯bh /¯
ahk deve essere l’unico minimo
dell’insieme
¯bi
{
∶ i ∈ {1, . . . , m}, a
¯ik > 0} .
a
¯ik
Siccome, per il Fatto 3, tutti gli elementi di tale insieme valgono zero, affinch´e
¯bh /¯
ahk sia l’unico minimo dell’insieme `e necessario che h sia l’unico indice tale
che a
¯hk > 0, mentre a
¯ik ≤ 0 per i ≠ h.
◇
Per il Fatto 1, a qualche iterazione p˜ > 0 la variabile xn non sar`a in base e
˜ = {B[1],
˜
˜
sar`
a scelta come variabile entrante. Sia B
. . . , B[m]}
la base corrente
˜
˜
durante tale iterazione e definiamo N = {1, . . . , n} ∖ B. Il problema in forma
˜ avr`a la forma seguente:
tableau rispetto a B
max z
s.a z
(3.27)
− ∑ c˜j xj = 0
(3.28)
j∈N
xB[i]
+∑a
˜ij xj = 0,
˜
i = 1, . . . , m
(3.29)
j = 1, . . . , n.
(3.30)
j∈N
xj ≥ 0,
˜ l’equazione (3.28) pu`o essere scritta
Come prima, se definiamo c˜j = 0 per j ∈ B,
n
nella forma z − ∑j=1 c˜j xj = 0.
Fatto 5 c˜n > 0 e c˜j ≤ 0 per j = 1, . . . , n − 1.
Dimostrazione. Poich´e, all’iterazione p˜, xn `e la variabile di indice massimo e
viene scelta come variabile entrante, per la regola di Bland xn deve essere l’unica
˜ ∖{n}. Inoltre,
candidata ad entrare in base, dunque c˜n > 0 e c˜j ≤ 0 per ogni j ∈ N
˜
per j ∈ B vale per definizione c˜j = 0. Dunque il Fatto 5 `e vero.
◇
˜ij .
Fatto 6 Esistono µ1 , . . . , µm tali che, per ogni j = 1, . . . , n, c˜j = c¯j + ∑m
i=1 µi a
Dimostrazione. Poich´e il problema (3.27)–(3.30) `e stato ricavato dal problema
(3.23)–(3.26) attraverso operazioni di pivot, il vincolo z − ∑nj=1 c˜j xj = 0 `e stato
¯ij xj = 0, i =
ottenuto sommando a z − ∑nj=1 c¯j xj = 0 multipli dei vincoli ∑nj=1 a
1, . . . , m. In altre parole, esistono µ1 , . . . , µm ∈ R tali che, per ogni j = 1, . . . , n,
c˜j = c¯j + ∑m
˜ij .
◇
i=1 µi a
Fatto 7 µh > 0 e µi ≤ 0 per i = 1, . . . , m, i ≠ h.
28
CAPITOLO 3. IL METODO DEL SIMPLESSO
Dimostrazione. Grazie al Fatto 6, per ogni ℓ = 1, . . . , m fissato e per j = B[ℓ]
abbiamo
m
¯iB[ℓ] = 0 + µℓ .
c˜B[ℓ] = c¯B[ℓ] + ∑ µi a
i=1
Utilizzando quest’ultima relazione ed il Fatto 5, ricordando che B[h] = n,
otteniamo µh = c˜B[h] > 0 e µℓ = c˜B[ℓ] ≤ 0 per ℓ = 1, . . . , m, ℓ ≠ h.
◇
Ora, poich´e durante l’iterazione iniziale p = 0 (relativa alla base B) xk era
stata selezionata come variabile entrante in base e xn come variabile uscente,
abbiamo necessariamente k < n e c¯k > 0. Pertanto, utilizzando i Fatti 4, 6 e 7,
otteniamo
m
m
¯hk > 0.
¯ik + µh a
¯ik = c¯k + ∑ µi a
c˜k = c¯k + ∑ µi a
® i=1,i≠h ² ²
i=1
>0
≥0
>0
Dunque c˜k > 0 e k < n, il che contraddice il Fatto 5. Poich´e siamo giunti ad un
assurdo, questo conclude la dimostrazione del teorema.
◻
3.6
Determinare una base ammissibile: il metodo
delle due fasi
Come abbiamo visto, il metodo del simplesso richiede che venga specificata una
base ammissibile da cui partire. In questa sezione mostriamo una procedura per
trovare una tale base, sempre che ne esista una, oppure per stabilire con certezza
che una tale base non esiste (in tal caso il problema `e inammissibile, grazie al
Corollario 2.7). Curiosamente, il problema di determinare la base iniziale per
il metodo del simplesso viene risolto attraverso il metodo del simplesso stesso,
applicato per`o ad un problema ausiliario per il quale una base ammissibile
iniziale sia immediatamente disponibile.
Dato un programma lineare in forma standard
max c⊺ x
s.a Ax = b
x ≥ 0,
(3.31)
(3.32)
(3.33)
dove A ∈ Rm×n , b ∈ Rm e c ∈ Rn , abbiamo gi`a discusso all’inizio del capitolo
come sia possibile verificare se il sistema Ax = b ammetta soluzioni e, in caso
affermativo, ridursi ad avere rk(A) = m. Possiamo inoltre assumere b ≥ 0,
perch´e in caso contrario `e sufficiente cambiare il segno a tutti i coefficienti che
appaiono nei vincoli in cui bi < 0.
Sotto queste ipotesi, per determinare se il programma lineare ha soluzioni
ammissibili costruiamo un problema ausiliario. Il problema ausiliario ha n + m
variabili: le variabili x1 , . . . , xn del problema (3.31)–(3.33), dette variabili originali, e m variabili xn+1 , . . . , xn+m , dette variabili ausiliarie, una per ciascun
vincolo di uguaglianza. Indichiamo con xA il vettore (xn+1 , . . . , xn+m )⊺ delle variabili ausiliarie (mentre continuiamo ad indicare con x il vettore delle variabili
originali) e con e il vettore (1, . . . , 1)⊺ di dimensione m.
3.6. IL METODO DELLE DUE FASI
29
Il problema ausiliario `e il seguente:
max
−e⊺ xA
s.a Ax + IxA = b
x ≥ 0, xA ≥ 0,
(3.34)
(3.35)
(3.36)
dove I `e la matrice identica m × m. Indichiamo con w la funzione obiettivo del
n+m
xj . Inoltre, definiamo w∗ come il
problema ausiliario: w = −e⊺ xA = − ∑j=n+1
valore ottimo del problema ausiliario (vedremo tra un attimo che in effetti tale
problema ammette ottimo).
Si noti che il problema ausiliario `e in forma standard. Inoltre, valgono le
seguenti propriet`a.
(a) Il problema ausiliario `e sempre ammissibile, poich´e ponendo x
¯=0 e x
¯A = b
si ottiene una soluzione ammissibile (si ricordi che b ≥ 0). Inoltre, tale
˜ = {n + 1, . . . , n + m}
soluzione `e una soluzione di base rispetto alla base B
di (A ∣ I).
(b) Il problema ausiliario non `e mai illimitato, perch´e w ≤ 0 per ogni xA ≥ 0.
In particolare, w∗ ≤ 0.
(c) Un vettore x
¯ ∈ Rn `e una soluzione ammissibile per il programma lineare
x
¯
(3.31)–(3.33) se e solo se il vettore ( ) `e una soluzione ammissibile per il
0
problema ausiliario (3.34)–(3.36).
(d) Una soluzione ammissibile del problema ausiliario soddisfa w = 0 se e solo se
x
¯
¯ ∈ Rn che sia soluzione ammissibile del problema
`e del tipo ( ) per qualche x
0
iniziale.
La cosiddetta Fase I del metodo del simplesso consiste nel risolvere il problema ausiliario applicando il metodo del simplesso (cos`ı come presentato nelle
˜ definita
sezioni precedenti). Come base iniziale si utilizza la base ammissibile B
nel punto (a). Per il Teorema 3.4, il metodo del simplesso con la regola di Bland
termina sempre; dunque, poich´e per il punto (b) il problema ausiliario non `e
x∗
illimitato, determineremo necessariamente una soluzione di base ottima ( ∗ )
xA
∗
relativa ad una qualche base B ⊆ {1, . . . , n + m}. Ancora per il punto (b), il
valore w∗ della soluzione ottima soddisfer`a w∗ ≤ 0.
Distinguiamo ora due casi.
(1) Supponiamo prima che w∗ = 0. Per il punto (d), questo avviene se e solo se
x∗A = 0, cio`e (per il punto (c)) se e solo se x∗ `e ammissibile per il problema
originale.
(2) Supponiamo ora w∗ < 0. In tal caso possiamo concludere che il problema
originale `e inammissibile. Infatti, se per assurdo esistesse una soluzione
x
¯
ammissibile x
¯ per tale problema, allora ( ) sarebbe ammissibile per il
0
30
CAPITOLO 3. IL METODO DEL SIMPLESSO
problema ausiliario ed il suo valore rispetto a quest’ultimo problema sarebbe
0 > w∗ , contraddicendo il fatto che w∗ `e il valore ottimo del problema
ausiliario.
Nel caso (2) abbiamo dimostrato che il problema originale `e inammissibile
e abbiamo dunque terminato. Nel caso (1), invece, non abbiamo ancora finito
perch´e, sebbene x∗ sia una soluzione ammissibile per il problema originale, non
`e chiaro che x∗ sia una soluzione di base per tale problema (B ∗ `e s`ı una base
ammissibile, ma del problema ausiliario, non di quello originale). Siccome il metodo del simplesso necessita di una base ammmissibile per poter essere avviato,
dobbiamo capire come ricavare una tale base. A questo scopo, distinguiamo
due sottocasi.
(1a) Supponiamo prima che B ∗ ⊆ {1, . . . , n}. In questo caso `e immediato verificare che B ∗ `e una base ammissibile anche per il problema originale;
inoltre, la soluzione di base associata `e x∗ .
(1b) Supponiamo ora che esista un indice j ∈ {n + 1, . . . , n + m} tale che j ∈ B ∗ .
Si noti che, poich´e x∗A = 0, si ha x∗j = 0 e la base `e quindi degenere. Sia i
l’indice della riga del tableau finale in cui appare la variabile xj (in altre parole, B ∗ [i] = j). Per ℓ = 1, . . . , n, indichiamo con a
¯iℓ l’elemento che appare
nella riga i del tableau finale in corrispondenza della variabile xℓ . Poich´e
x∗j = 0, l’ultima colonna del tableau contiene uno zero in corrispondenza
dell’i-esima riga.
Ora affermiamo che esiste almeno un indice ℓ ∈ {1, . . . , n} tale che a
¯iℓ ≠ 0.
Per verificarlo, si ricordi che le operazioni effettuate per ottenere il tableau
finale a partire dalla matrice iniziale (A ∣ I) sono operazioni elementari
sulle righe, che dunque non cambiano il rango della matrice. Se quindi si
avesse a
¯iℓ = 0 per ogni ℓ ∈ {1, . . . , n}, allora l’i–esima riga della sottomatrice
del tableau relativa alle prime n colonne sarebbe il vettore riga nullo,
contraddicendo l’ipotesi che A ha rango m. Allora esiste almeno un indice
ℓ ∈ {1, . . . , n} tale che a
¯iℓ ≠ 0, come preannunciato.
Facendo uscire dalla base xj e facendo entrare xℓ , otteniamo una base ammissibile B ′ per il problema ausiliario, associata alla medesima soluzione
di base x∗ , in quanto il pivot `e degenere. (Sottolineiamo che non `e necessario avere a
¯iℓ > 0 per effettuare un cambio di base.) Inoltre, B ′ contiene
` semplice osservare che,
una variabile ausiliaria in meno rispetto a B ∗ . E
iterando questa procedura fino a quando si ottiene una base contenuta in
{1, . . . , n}, si trova una base ammissibile per il problema originale, ancora
associata alla soluzione x∗ .
In entrambi i sottocasi, dunque, si ottiene una base ammissibile per il problema originale. A questo punto `e possibile utilizzare tale base come base iniziale
per l’algoritmo del simplesso descritto nelle sezioni precedenti: questa `e detta
la Fase II del metodo del simplesso. L’applicazione in sequenza del simplesso
sul problema ausiliario e quindi sul problema originale `e detta metodo delle due
fasi. Riportiamo qui sotto la descrizione del metodo delle due fasi.
31
3.6. IL METODO DELLE DUE FASI
Metodo delle due fasi
Input: A ∈ Rm×n , b ∈ Rm , c ∈ Rn .
Output: Una delle seguenti:
una soluzione di base ottima per (3.31)–(3.33);
l’informazione che il problema `e inammissibile;
l’informazione che il problema `e illimitato.
1. Si cambino di segno eventuali equazioni con termine noto negativo in
(3.31)–(3.33), si costruisca il problema ausiliario (3.34)–(3.36) e lo si
risolva con il metodo del simplesso a partire dalla base {n+1, . . . , n+m}
(Fase I).
2. Se la soluzione ottima ha valore w∗ < 0, allora il problema (3.31)–
(3.33) `e inammissibile; STOP.
3. Se la soluzione ottima ha valore w∗ = 0, si determini una base ammissibile B per (3.31)–(3.33) effettuando, se necessario, pivot (degeneri)
che sostituiscano una per volta in B le eventuali variabili ausiliarie
con variabili originali.
4. Si applichi il metodo del simplesso al problema originale (3.31)–(3.33)
a partire dalla base B (Fase II).
Poich´e il metodo del simplesso con la regola di Bland giunge sempre a terminazione, il metodo delle due fasi termina sempre con la conclusione (e la prova)
che il problema `e inammissibile, `e illimitato, oppure ha soluzione ottima. Dunque la correttezza del metodo delle due fasi prova il Teorema Fondamentale
della Programmazione Lineare (Teorema 1.1).
3.6.1
Esempio
Applichiamo la Fase I del metodo del simplesso al programma lineare seguente,
gi`
a in forma standard:
max
x1 + x2 + 4x3
s.a − x1 + x2 + x3 = −2
x1 − x2 − 2x3 = 2
x1 , x2 ,
x3 ≥ 0
Come prima cosa bisogna cambiare tutti i segni della prima equazione, perch´e il
termine noto `e negativo. Successivamente vanno introdotte le variabili ausiliare
32
CAPITOLO 3. IL METODO DEL SIMPLESSO
x4 e x5 .1 Il problema ausiliario cos`ı ottenuto `e il seguente:
− x4 − x5
max
s.a x1 − x2 − x3 + x4
x1 − x2 − 2x3
x1 , x2 ,
=2
+ x5 = 2
x3 , x4 , x5 ≥ 0
Il problema `e quasi in forma tableau rispetto alla base {4, 5}, eccetto che per
la funzione obiettivo w = −x4 − x5 , che non `e espressa in funzione della variabile
fuori base. Facili conti ci portano al seguente tableau:
w x1 x2 x3 x4 x5
2
3 0 0 −4
1 −2
0
1 −1 −1 1 0 2
1 −1 −2 0 1 2
0
Applicando un’iterazione del metodo del simplesso con la regola di Bland, entra
in base x1 al posto di x4 . Il nuovo tableau, relativo alla base B ∗ = {1, 5}, `e il
seguente:
w x1 x2 x3 x4 x5
1
0
0
1
2 0 0
0
1 −1 −1
1 0 2
0
0 −1 −1 1 0
0
Si noti che questo tableau `e ottimale, perch´e non vi sono costi ridotti positivi.
Il valore ottimo, leggibile dalla posizione in alto a destra, `e zero; dunque il
problema originale `e ammissibile. Tuttavia, la base B ∗ contiene variabili ausiliarie, dunque dobbiamo eseguire qualche pivot (degenere) per ottenere una
base ammissibile per il problema originale. Scegliamo una qualunque variabile
ausiliaria in base: in questo caso l’unica possibilit`a `e x5 . La teoria garantisce
che la riga del tableau relativa alla variabile x5 (cio`e l’ultima riga) contenga un
elemento diverso da zero in corrispondenza di almeno una variabile originale:
in effetti, in corrispondenza di x3 c’`e un −1. Eseguiamo dunque il pivot rispetto
a tale elemento, ottenendo il seguente tableau:
w x1 x2 x3 x4 x5
0
0 0 1
1 0
1
0
1 −1 0 2 −1 2
0
0 1 1 −1 0
0
`
Come previsto, il pivot `e degenere: la soluzione di base non `e cambiata. E
ovviamente cambiata la base, che ora `e {1, 3} e contiene dunque solo variabili
originali: questa base pu`o allora essere utilizzata per avviare la Fase II del
metodo del simplesso. Il tableau iniziale per la Fase II `e costituito dalle colonne
del tableau precedente relative alle variabili originali, eccetto che per la funzione
1
Se il problema dato non fosse in forma standard, bisognerebbe prima introdurre le
eventuali variabili di scarto e successivamente quelle ausiliarie.
3.6. IL METODO DELLE DUE FASI
33
obiettivo, che ora `e z = x1 + x2 + 4x3 e deve essere espressa in funzione delle
variabili in non-base (nel nostro caso, in funzione di x2 ). Si ottiene
z x1 x2 x3
1 0 −2 0 2
0 1 −1 0 2
0 1 0
0 0
Questo tableau consente di avviare la Fase II (non riportata qui).

Download Report