Metodo del Simplesso

Preliminari al Metodo del Simplesso

Schema Generale

1. Si sceglie un vertice
2. Se Test Ottimalità
3. Se Test Illimitatezza
4. Si cambia vertice altrimenti

Forma Canonica

Sia dato un problema di PL in forma standard, e sia B una base, il problema si dice in forma canonica se tutte le variabili di base e la funzione obiettivo son espresse in funzione delle variabili fuori base.

Costi Ridotti

Dato un problema di PL in forma canonica (o anche standard) rispetto alla base B, i coefficienti delle variabili nella f.o. si dicono costi ridotti delle variabili rispetto alla base B

Considerando un problema in FS: 

Forma Canonica

(cioè tutto espresso in funzione di )

• La f.o. diventa quindi:
• • = f.o in forma canonica  

Perciò, il vettore dei costi ridotti:

• Si partiziona in:
• tutte le variabili di base, con costi ridotti nulli
• costi ridotti delle variabili fuori base

Test di Ottimalità

Si basa sul segno dei costi ridotti. Se i costi ridotti sono tutti , la soluzione di base corrente è ottima.

Sia la soluzione di base corrente. 

Sappiamo che i costi ridotti delle variabili fuori base sono , idem per

Quindi se la f.o in base qualunque f.o nella soluzione di base corrente la soluzione di base corrente è ottima.  

Se non vale il test di ottimalità si è costretti a cambiare vertice, passando ad un vertice adiacente. Cioè si passa a un’altra base .

deve:

• essere adiacente (cioè differisce da per una sola colonna);
• migliorare la funzione obiettivo;
• essere tale che è una soluzione ammissibile

In termini di matrici si scambia una colonna fuori base con una colonna di base.

In termini di vettori entra in base ed esce

Criterio di Entrata

Criterio di Entrata

Entra in base una variabile con costo ridotto negativo.

Supponiamo che entri in base una variabile , allora la f.o. diventa:

Dove è il costo ridotto della variabile entrata. Se la variabile entra in base, questa passa da un valore zero (dato che era fuori base) ad un valore positivo. Le altre variabili fuori base restano sempre a zero. Però ha effetto sulle variabili di base:

Le componenti di base dunque diventano:

• Se tutti gli sono , allora può aumentare senza limiti e le sono ancora ammissibili;
• Se aumenta all’infinito la f.o. va a , cioè:

Stabiliamo quindi il test di limitatezza:

Test di Limitatezza

Se c’è un costo ridotto e gli elementi della colonna sono allora il problema non è limitato. 

Se non è valido il test di illimitatezza bisogna cambiare vertice. Occorre scegliere quale variabile fare uscire dalla base.

Riferendoci al sistema delle componenti di base definito prima, vogliamo che

Otteniamo dunque:

Che significa?

Tutto questo significa che può crescere fino al raggiungere il minimo tra tutti i rapporti. O, in altre parole:

Criterio di Uscita (del Rapporto)

Criterio di Uscita

Esce dalla base la variabile dove è l’indice cui corrisponde il minimo dei rapporti.

La funzione migliora del valore , e la variabile entra con valore .

Questo valore è infatti il valore additivo , visto nel criterio di entrata.

Schema del Metodo del Simplesso

Preparati, da qui in poi partono gli esempi grafici.

Innanzitutto, si considera la Forma Standard del problema:

1. Si sceglie una base B (matrice con Det. ), e si calcola la soluzione di base
2. Se i costi ridotti delle variabili fuori base sono , la soluzione è ottima (Test di Ottimalità)
3. Se c’è un costo ridotto , quindi negativo (per il criterio di entrata), e gli elementi della colonna della matrice sono , il problema non è limitato (Test di Illimitatezza)
4. Si calcola:
   • e sia raggiunto per (Criterio di uscita)
5. Si cambia base:

Cambio Base: Operazione Pivotale

Adottiamo la forma Tableau del metodo del simplesso:

Tableau simplesso

Soluzione Base Ammissibile (SAB) corrente:

• Se entra la variabile ,
• Se il criterio di uscita ha indicato l’indice , esce la variabile

Dunque la colonna entra nella matrice di Base al posto della colonna .

L’elemento si chiama o perno della trasformazione, e deve essere sempre . 

La colonna h-esima si trasforma nella colonna k-esima con le seguenti operazioni:

Operazioni di trasformazione colonna

1. La riga si divide per il perno (motivo della condizione );
2. Alle altre righe si aggiunge un opportuno multiplo della riga del perno modificata in modo da annullare tutti gli elementi

Esempio in LateX

Si porta il problema in forma standard

Abbiamo aggiunto una base B con le variabili di scarto: sono variabili di base, e la matrice B in questo caso è una matrice identità. 

Questo perché se i vincoli sono tutti le variabili scarto diventano variabili di base.

La SAB Corrente sarà:

• Ricordiamo che , in notazione vettoriale, dove vettore delle componenti in base, mentre sarebbe il vettore delle componenti fuori base
• Se le componenti di base della SAB sono i termini noti.

Inoltre, se i vincoli sono tutti di tipo i costi ridotti coincidono con i coefficienti delle variabili della f.o. 

• Notiamo che ci sono 2 costi ridotti negativi. In questo caso, il criterio d’entrata sceglie quello con indice minore (cioè quello trovato prima). Questa scelta è definita dalla Regola di Bland.
• Per la variabile uscente, usiamo il criterio del rapporto. In questo caso calcoliamo:
• Il rapporto minimo è pertanto in corrispondenza della seconda riga, cioè della variabile , la variabile uscente.
• In sunto: Entra , Esce , l’incrocio tra la colonna della variabile entrante e la riga di quella uscente

Operazioni sulle righe

La colonna 2 deve dividere la colonna 5.

Procedura

1. Il perno vale 1, quindi non ci sono modifiche da fare.
   1. Se fosse , bisognerebbe dividere tutta la riga del perno per il perno stesso.
2. Operiamo sull’ultima riga, generiamo una nuova riga

3. Il costo ridotto della nuova variabile di base deve fare zero:

La nuova tabella, con relativa nuova SAB, sarà quindi:

Dato che abbiamo ancora un costo ridotto negativo (), si continua con l’algoritmo.

• Entra , ed esce
• Si hanno le seguenti trasformazioni:

Otteniamo un’altra tabella e nuova SAB:

Purtroppo dai calcoli abbiamo un nuovo costo negativo in , per cui:

• Entra , ed esce , perché ha il rapporto minimo rispetto alla riga
• E si hanno le seguenti trasformazioni:
• Reminder: finora non è stato necessario toccare la riga del pivot perché abbiamo avuto fortuna e tutti i pivot sono , altrimenti avremmo dovuto dividere per il pivot.

Otteniamo la tabella finale con SAB ottima:

• Questa è la tabella finale perché tutti i costi ridotti sono , quindi ci fermiamo per il Test di Ottimalità.
• Il valore ottimo della funzione obiettivo è dunque .

Questo conclude l’esempio.

• Nel caso in cui i costi ridotti siano tutti strettamente positivi (), allora per Unicità della soluzione, la SAB corrente sarebbe l’unica soluzione ottima.

Convergenza del Metodo

Continua in:

Convergenza del Metodo