Homeworks proposti in data 10 Marzo 1998

Contenuto della lezione del 10 Marzo 1998

Nel 1977 R. G. Bland propose la regola dell'indice minimo per impedire al metodo del simplesso di ciclare.

REGOLA DELL'INDICE MINIMO: si consideri di aver introdotto un ordinamento totale sugli indici delle variabili.
Quando più variabili si presentano come candidate per entrare in base (costo ridotto positivo) allora scelgo la variabile di indice inferiore.
Quando più variabili (degenerazione) si presentano come candidate per uscire di base (valore nullo nella soluzione associata al prossimo dizionario o tableau) allora scelgo la variabile di indice inferiore.

Si noti come la regola di Bland, a differenza dei metodi antidegenerativi quali il metodo lessicografico e quello delle perturbazioni, determini non solo la variabile uscente ma anche la variabile che entra in base. Effettivamente questo inconveniente inibì (almeno in un primo momento) la sua adozione.

Abbiamo dedicato buona parte della lezione alla dimostrazione del seguente risultato:

Teorema 1 (R. G. Bland 1977)   Qualora la regola dell'indice minimo venga adottata, allora il metodo del simplesso non può ciclare e la sua terminazione è quindi garantita.

dimostrazione: Si assuma, per assurdo, che il metodo cicli producendo la sequenza di dizionari: $D_0, D_1, D_2, \ldots, D_k = D_0$. Una variabile sarà detta oscillante se in base per alcuni di questi dizionari ma fuori base per altri. Sia t il massimo indice per il quale x_t è oscillante. Nella sequenza $D_0, D_1, \ldots, D_k$ avremo pertanto un dizionario D che vede x_t come variabile uscente (in base per D ma fuori base nel dizionario seguente) e sia x_s la variabile entrante in base al posto di x_t. Ovviamente la sequenza $D_0, D_1, \ldots, D_k$ dovrà inoltre contenere un dizionario D^* con x_t rientrante in base. Se B è l'insieme degli indici delle variabili in base per D allora possiamo accennare la struttura di D:

$$\begin{array}{l} x_i = b_i - \sum_{j \notin B} a_{ij} x_j \m... ... \overline{z = v + \sum_{j \notin B} c_j x_j} \\ \end{array}$$

Naturalmente la funzione obiettivo z assumerà lo stesso valore nelle soluzioni di base associate a D e D^*. Pertanto l'ultima riga del dizionario D^*potrà essere scritta come:

$$z = v + \sum_{j=1}^{n+m} c^*_j x_j$$

dove c_j^* = 0 ogniqualvolta x_j è in base per D^*.   Poichè quest'ultima equazione è stata ottenuta dalle equazioni descriventi D tramite operazioni di pivot essa deve ammettere ogni soluzione ammessa da Ded in particolare deve risultare soddisfatta dalla scelta dei seguenti valori:

$$\begin{array}{l} x_s = y \mbox{\hspace{1cm} per qualsiasi va... ...mbox{\hspace{1cm}} (i\in B) \\ z = v + c_s y \\ \end{array}$$

Pertanto avremo $v + c_s y = v + c^*_s y + \sum_{i\in B} c^*_i (b_i - a_{is} y)$che convenientemente raccogliendo y diviene:

$$\left( c_s - c^*_s + \sum_{i \in B} c^*_i a_{is} \right)y = \sum_{i \in B} c^*_i b_i$$

E poichè il secondo termine di quest'equazione è una costante indipendente da ypossiamo concludere che $c_s - c^*_s + \sum_{i \in B} c^*_i a_{is} = 0$. D'altro canto c_s > 0 poichè x_s è entrante in D. Inoltre $c^*_s \leq 0$ poichè s < t e tuttavia x_t e non x_s è la variabile entrante in D^*. Possiamo pertanto concludere che

$$c^*_r a_{rs} < 0 \mbox{\hspace{1cm} per un qualche $r\in B$ }$$

Siccome $c^*_r \neq 0$ la variabile x_r non è in base per D^* ed è quindi oscillante. Tuttavia $r\neq t$ dato che c_t^* a_ts > 0: siccome x_t entra in D^* allora c_t^* > 0; siccome x_t esce da D allora a_ts > 0. Pertanto r < t e siccome x_r non entra in D^*al posto di x_t ne deduciamo che c_r^* non può essere positivo. Quindi

$$a_{rs} > 0 \mbox{\hspace{1cm} per un qualche $r\in B$\space diverso da $t$ }$$

Poichè tutte le iterazioni che compongono il ciclo sono degeneri, a D e D^* è di fatto associata la stessa soluzione. In particolare x_r, che è fuori base per D^*, avrà valore nullo anche nella soluzione associata a D e pertanto b_r = 0. Quindi x_r era candidata a lasciare la base in D e contrariamente alla regola dell'indice minimo le abbiamo preferito x_t.       Q.E.D.

Homeworks proposti

Il metodo del simplesso in due fasi, implementato utilizzando una qualsiasi strategia che ne garantisca la terminazione (come per esempio la regola di Bland), costituisce dimostrazione algoritmica del seguente risultato:

Teorema 2 (Teorema Fondamentale della Programmazione Lineare)   Ogni problema di PL in forma standard ha le seguenti tre proprietà:

(i)

Se non ha una soluzione ottimale allora è o inammissibile o illimitato.

(ii)

Se ha una soluzione ammissibile allora ha una soluzione ammissibile di base.

(iii)

Se ha una soluzione ottimale allora ha una soluzione ottimale di base.

Argomentare più precisamente il Teorema Fondamentale della Programmazione Lineare, sulla base del comportamento del metodo del simplesso in due fasi e dei suoi possibili esiti.

Buon Lavoro!