Programmazione Lineare

Il Metodo del Simplesso

Convergenza del Simplesso: Casi Degeneri

Consideriamo l'esempio:

Semplificando si ha:

Il terzo vincolo e' ridondante, infatti, ponendo x2 = 0, il secondo vincolo e' identico al terzo; vediamo cosa succede se si continua con il metodo del simplesso:

Per il pivot, si puo' sciegliere indifferentemente la seconda o la terza riga; consideriamo la terza:

La soluzione di base relativa alla matrice trovata sara':

La variabile x2 ha per termine noto uno zero, pur essendo in base: e' uno zero inatteso; siamo di frone ad un caso degenere

La soluzione di base e' identica alla precedente, a causa dello zero inatteso: x2 entra in base e prende come termine noto proprio lo zero inatteso; lo zero inatteso fa sì che venga scelta sempre la riga dove e' comparso come riga del pivot, in questo modo lo zero riappare dopo ogni iterazione

L'apparizione di uno zero inatteso tra i termini noti mette in discussione la convergenza del metodo del simplesso:

in casi normali, quando cioe' non si e' in presenza di zeri inattesi, il simplesso e' tale da fer migliorare il valore della funzione obiettivo dopo ogni iterazione: si esplorano tutte le soluzioni di base possibili (che possono essere moltepoici ma in numero finito) e non si ripresenta mai una soluzione trovata in precedenza Þ il simplesso converge

in casi degeneri, quando cioe' si hanno zeri inattesi, una forma canonica trovata precedentemente si ripresenta dopo varie iterazioni e, quando cio' avviene, l'algoritmo inizia a ciclare attormo ad essa proponendo sempre il medesimo valore per la funzione obiettivo; in questo modo la funzione obiettivo mantiene costante il suo valore e non e' piu' possibile arrivare alla soluzione ottima in un numero finito di passi Þ il simplesso non converge

Il presupposto per il verificarsi del caso degenere e' la  comparsa di due valori uguali, nella colonna dei termini noti, per la scelta del pivot; questa situazione si verifica frequentemente quando si lavora con problemi che hanno dimensione elevata

Graficamente si ha:

Le soluzioni di base coincidono con i vertici dell'area ammissibile, che sono il risultato dell'intersezione dei vincoli; nel vertice C, convergono ben te vincoli ed e' proprio questa particolarita' a rendere il simplesso ciclico: C puo' essere espresso attraverso una qualunque coppia dei tre vincoli, percio' puo capitare che il simplesso rimanga a ciclare sullo stesso punto, descritto in tre modi diversi

Quando si inizia a ciclare, il caso e' sicuramente degenere, ma si possono verificare dei casi in cui, anche se degeneri, il ciclo non si manifesta; ritornando all'esempio, si ha:

Si fa entrare x5 in base e si sceglie come pivot la prima riga (la seconda avrebbe pivot negativo e non e' ammissibile); si ottiene:

Ora la soluzione di base e' diversa dalla precedente e non si e' manifestato lo zero inatteso; inoltre quella trovata e' la soluzione ottima (tutti costi ridotti nulli o negativi):

In questo caso il caso degenere si e' risolto da solo ed e' cio' che accade nella maggior parte dei casi; i problemi di programmazione lineare che ciclano non si verificano praticamente mai

Esistono due metodi per evitare che il sistema inizi a ciclare attorno ad una forma canonica:

Primo metodo: Si perturbano lievemente tutti i termini noti con valori diversi tra loro: in questo miodo la tripla intersezione non e' piu' tale e si trasforma in tre combinazioni diverse di due vincoli ciascuna; non si aggiunge la stessa quantita' ai vincoli per evitare che l'intersezione tripla si verifichi in un altro punto del piano; il problema diventa:

Secondo metodo: Regola di Blade Quando ci si trova di fronte ad una incertezza, non si sa cioe' quale riga (due termini noti sono uguali) o quale colonna (due costi ridotti sono uguali) scegliere per il pivot, basta scegliere la riga o la colonna con l'indice piu' basso; si puo' dimostrare che questo e' sufficiente ad evitare il ciclo