0 ¯a1
hk ? . . . ? 1 ? . . . ? ¯a¯bh
hk
⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
0 −¯a¯amk
hk 1 ? . . . ? 0 ? . . . ? ¯bm−¯a¯amk
hk ¯bh che `e precisamente il tableau rispetto alla nuova base B′.
Quest’operazione `e detta pivot rispetto alla posizione o all’elemento(h,k). Una scrittura del tutto equivalente delle operazioni di pivot, leggermente pi`u pratica da usare nel caso di conti manuali, `e la seguente:
rigah(T′) = 1
¯
ahkrigah(T)
rigai(T′) = rigai(T) − ¯aikrigah(T′), i = 1,... ,m, i ≠ h riga0(T′) = riga0(T) + ¯ckrigah(T′).
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.
3.5. BASI DEGENERI E TERMINAZIONE 23 Dimostrazione. Il numero di basi della matrice A ∈ Rm×n`e al massimo il numero di sottoinsie-mi di cardinalit`a m di un insieme universo con n elementi, cio`e(mn). 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} ∶ ¯aik>0{¯bi
¯
aik} . (3.23)
Si noti che ¯t =0 se e solo se esiste un indice i tale che ¯bi =0 e ¯aik >0; in tal caso, ¯xB[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 ¯xrelativa a B soddisfa
¯
xi>0 per ogni i ∈ B, cio`e se ¯b = A−1Bb >0. In caso contrario, la base `e detta degenere.
Lemma 3.3 Se l’algoritmo del simplesso applicato ad un dato programma lineare cicla, al-lora 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 relazione (3.18) 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 ¯xB[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’ite-razione 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 giungeremo a terminazione 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.23). Di seguito riportiamo una definizione formale di questa 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 ¯tcome in (3.23), si faccia uscire dalla base la variabile xB[h] che ha indice B[h]
minimo tra quelle che soddisfano ¯ahk>0 e ¯bh/¯ahk= ¯t.
Esempio. Si consideri il seguente problema in forma tableau, relativo a qualche iterazione del metodo del simplesso:
Dal tableau si evince che la base corrente `e{1,5,4}. 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.
Per scegliere la variabile uscente, dobbiamo applicare il criterio del minimo rapporto. Si noti che min{318/2,30.6.4,13
/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 ∈ Rned 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.24)
I vincoli (3.25)–(3.26) possono ora essere riscritti cos`ı:
z−
3.5. BASI DEGENERI E TERMINAZIONE 25 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 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.24)–(3.27) 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.24)–(3.27) eliminando la colonna del tableau relativa ad xℓ ed il vincolo xℓ+
∑j∈N¯aijxj = ¯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. Quando viene eseguito un pivot non degenere, il valore della funzione obiettivo aumenta strettamente e quindi le basi finora incontrate non saranno pi`u visitate. Allora, poich´e nel nostro caso l’algoritmo non termina, da una certa iterazione in poi tutti i pivot devono essere degeneri. Inoltre, per il Lemma 3.3, da questa iterazione in poi la soluzione di
base corrente non cambia pi`u. ◇
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.
Dimostrazione. Supponiamo per assurdo che esista un indice h ∈{1,... ,m} tale che ¯bh >0.
Allora ¯xB[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. Concludiamo quindi che ¯b = 0. ◇ Per il Fatto 1, a qualche iterazione p la variabile xnsar`a in base e sar`a scelta come variabile uscente. Senza perdita di generalit`a assumiamo p = 0, dunque la base corrente durante tale iterazione `e B. Sia h l’indice di riga tale che B[h] = n e sia xk la variabile entrante.
Fatto 4 ¯ahk>0 e ¯aik≤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
¯
aik ∶ i ∈{1,... ,m}, ¯aik >0} .
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 ¯ahk > 0, mentre
¯
aik≤0 per i ≠ h. ◇
Per il Fatto 1, a qualche iterazione ˜p > 0 la variabile xn non sar`a in base e sar`a scelta come variabile entrante. Sia ˜B = { ˜B[1],... , ˜B[m]} la base corrente durante tale iterazione e definiamo ˜N = {1,... ,n} ∖ ˜B. Il problema in forma tableau rispetto a ˜B avr`a la forma seguente:
max z (3.29)
s.a z −∑
j∈ ˜N
˜
cjxj=0 (3.30)
xB˜[i]+ ∑
j∈ ˜N
˜
aijxj=0, i =1, . . . , m (3.31) xj≥0, j =1, . . . , n. (3.32) Come prima, se definiamo ˜cj =0 per j ∈ ˜B, l’equazione (3.30) pu`o essere scritta nella forma z−∑nj=1˜cjxj=0.
Fatto 5 ˜cn>0 e ˜cj≤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 candidata ad entrare in base, dunque ˜cn > 0 e ˜cj ≤0 per ogni j ∈ ˜N∖{n}. Inoltre, per j ∈ ˜B vale per definizione ˜cj =0.
Dunque il Fatto 5 `e vero. ◇
Fatto 6 Esistono µ1, . . . , µm∈R tali che, per ogni j = 1, . . . , n, ˜cj =¯cj+∑mi=1µi¯aij.
Dimostrazione. Poich´e il problema (3.29)–(3.32) `e stato ricavato dal problema (3.24)–(3.27) attraverso operazioni di pivot, il vincolo z −∑nj=1c˜jxj = 0 `e stato ottenuto sommando a z−∑nj=1¯cjxj = 0 multipli dei vincoli ∑nj=1a¯ijxj = 0, i = 1, . . . , m. In altre parole, esistono µ1, . . . , µm∈R tali che, per ogni j = 1, . . . , n, ˜cj=¯cj+∑mi=1µi¯aij. ◇ Fatto 7 µh >0 e µi≤0 per i = 1, . . . , m, i ≠ h.
Dimostrazione. Grazie al Fatto 6, per ogni ℓ = 1, . . . , m fissato e per j = B[ℓ] abbiamo
˜
cB[ℓ]=¯cB[ℓ]+
∑m i=1
µi¯aiB[ℓ]=0 + µℓ,
dove `e stata usata la definizione (3.28). Dalla relazione appena ottenuta e dal Fatto 5, ricordando che B[h] = n, otteniamo µh =c˜B[h]>0 e µℓ=˜cB[ℓ]≤0 per ℓ = 1, . . . , m, ℓ ≠ h. ◇
3.6. IL METODO DELLE DUE FASI 27