Algoritmo del simplesso

algoritmo di ottimizzazione lineare
(Reindirizzamento da Metodo del simplesso)
Disambiguazione – "Metodo del simplesso" rimanda qui. Se stai cercando l'omonimo metodo di ottimizzazione non lineare, vedi metodo di Nelder-Mead.

L'algoritmo del simplesso, ideato dall'americano George Dantzig nel 1947, è un metodo numerico per risolvere problemi di programmazione lineare. È citato dalla rivista statunitense Computing in Science and Engineering come uno dei dieci migliori algoritmi del secolo.[1]

Questo algoritmo fa uso del concetto di simplesso, cioè un politopo di vertici in dimensioni, ossia un segmento di retta in una dimensione, un triangolo in due dimensioni, un tetraedro in tre dimensioni.

La programmazione lineare

modifica
  Lo stesso argomento in dettaglio: Programmazione lineare.

Un problema di programmazione lineare consiste nel massimizzare o minimizzare una funzione lineare definita sull'insieme delle soluzioni di un sistema di disequazioni lineari, dette vincoli.

Per esempio il problema:

 

è un problema di programmazione lineare.

I vincoli definiscono la regione ammissibile (cioè l'insieme dei punti che soddisfano tutti i vincoli del problema, in inglese "feasible region"). Nel caso della programmazione lineare la regione ammissibile è un poliedro che può essere vuoto, limitato o illimitato. La funzione che va minimizzata o massimizzata è la "funzione obiettivo": essa in pratica calcola il "costo" di ogni soluzione dei vincoli.

È quindi obiettivo della risoluzione di un tale problema trovare tra le soluzioni che soddisfino i vincoli, quella cui corrisponde il costo minimo (o massimo, se si tratta di un ricavo).

L'algoritmo

modifica
 
Un sistema di disequazioni lineari definisce come regione ammissibile un politopo. L'algoritmo del simplesso inizia da un vertice iniziale e si sposta lungo i lati del politopo fin quando non raggiunge il vertice della soluzione ottima.

L'algoritmo del simplesso è in grado di determinare di che tipo di poliedro si tratta e trova la soluzione ottima, che è, sotto opportune ipotesi, un vertice del poliedro, nel caso il problema abbia una soluzione ottimale finita.

L'algoritmo viene solitamente formulato su problemi posti nella cosiddetta forma standard dove si deve cioè massimizzare una funzione lineare sottoposta (in inglese "subject to" abbreviato s.t.) a vincoli di uguaglianza, e in cui le variabili siano positive o nulle:

Massimizzare   s.t.   e  , dove   è una matrice,   sono vettori colonna, le   sono le   componenti di   e la   ad esponente è l'operatore di trasposizione.

A tale formulazione si perviene facilmente, sommando o sottraendo, a seconda della necessità, una variabile chiamata "di slack" (se sommata) o "di surplus" (se sottratta) ad un problema formulato in forma canonica   tale che   e  . Riassumibile in un tableau del tipo  , l'algoritmo si articola nei seguenti passi applicati al tableau:

  1. Verifica di ottimalità: condizione sufficiente perché la tabella sia ottima è che   per ogni   (se è un problema di massimo) o   per ogni   (se di minimo).
  2. Se non si ha ancora una tabella ottima, si sceglie una colonna   corrispondente al massimo fra i   (costi ridotti positivi) (ve ne sarà almeno uno, altrimenti ci saremmo fermati al punto 1).
  3. Verifica di illimitatezza. Condizione sufficiente perché il problema sia illimitato è che nella colonna   individuata si abbiano solo valori negativi nella matrice, cioè  . Dunque il problema è illimitato lungo questa direzione.
  4. Se non siamo in presenza di un problema illimitato, si sceglie il pivot che genera il minimo rapporto tra il termine noto e il coefficiente della relativa variabile nella colonna   della matrice  , cioè   e si applica l'operazione di cardine.

L'operazione cardine è quella operazione che permette di spostarsi lungo una direzione ammissibile per un certo passo in modo che la nuova soluzione sia anch'essa ammissibile ma migliore di quella precedente di partenza.

Verifica di ottimalità / Criterio d'arresto

modifica

Dato il problema di programmazione lineare   si considera la base ammissibile   contenente colonne linearmente indipendenti di  . Si può riscrivere la relazione   come:

 

con   matrice contenente le colonne di   escluse dalla base ammissibile  .

Ancora si può riscrivere la relazione precedente come:

 

e, andando a sostituire la relazione nella funzione obiettivo relativa al problema iniziale, si ha:

 
 
 

con   valore costante e   vettore dei costi ridotti.

Sotto tali condizioni se il vettore dei costi ridotti risulta non negativo, la soluzione base ammissibile associata ad   risulta essere ottima. Ciò significa che il valore assunto dalla funzione obiettivo   è il minimo globale per la funzione nel dominio considerato.

Prestazioni

modifica

In pratica l'algoritmo funziona molto bene[senza fonte], ma in teoria non è polinomiale e si possono costruire speciali esempi in cui l'algoritmo richiede di visitare un numero di vertici esponenziale rispetto alle dimensioni del problema. Reali competitori del metodo del simplesso per problemi di grandi dimensioni sono i metodi a punti interni.

Tipi di simplesso

modifica

La descrizione data in precedenza è quantomai generica: l'idea generale di Dantzig è stata poi applicata a molti problemi pratici di ricerca operativa, quindi alla fine questo ha prodotto una lunga serie di algoritmi del simplesso, ognuno per uno specifico problema.

Citiamo in seguito alcuni dei principali metodi del simplesso:

  1. ^ Computing in Science and Engineering, volume 2, no. 1, 2000

Voci correlate

modifica

Altri progetti

modifica

Collegamenti esterni

modifica
Controllo di autoritàLCCN (ENsh85122745 · GND (DE4181488-5 · J9U (ENHE987007546249105171
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica