Algoritmo del simplesso

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.

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

La 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:

${\begin{cases}\max \quad x+2y\\x-y\leq 4\\x\geq 0\\y\geq 0\end{cases}}$

è 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

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 ${\boldsymbol {\gamma }}^{T}\mathbf {x}$ s.t. ${\boldsymbol {\mathrm {A} }}\mathbf {x} =\mathbf {b}$ e $x_{i}\geq 0$, dove $\mathbf {A}$ è una matrice, $\mathbf {b} ,\mathbf {x} ,{\boldsymbol {\gamma }}$ sono vettori colonna, le $x_{i}$ sono le $n$ componenti di $\mathbf {x}$ e la $T$ 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 ${\boldsymbol {\gamma }}^{T}\mathbf {x}$ tale che ${\boldsymbol {\mathrm {A} }}\mathbf {x} \leq \mathbf {b}$ e $x_{i}\geq 0$. Riassumibile in un tableau del tipo ${\begin{pmatrix}\mathbf {A} \;\,\mathbf {b} \\{\boldsymbol {\gamma }}^{T}\;0\end{pmatrix}}$ L'algoritmo si articola nei seguenti passi applicati al tableau:

1. Verifica di ottimalità. Condizione sufficiente perché la tabella sia ottima è che ${\boldsymbol {\gamma }}_{i}\leq 0,$ per ogni $i=1,\ldots ,n$ (se è un problema di massimo, e ${\boldsymbol {\gamma }}_{i}\geq 0,$ per ogni $i=1,\ldots ,n$ se di minimo).
2. Se non si ha ancora una tabella ottima scelgo una colonna $h$ corrispondente al massimo fra i $\gamma _{i}\geq 0$ (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 $h$ individuata si abbiano solo valori negativi nella matrice, cioè $\mathbf {a} _{ih}<0,\;\forall i=1,\ldots ,n$. Dunque il problema è illimitato lungo questa direzione.
4. Se non siamo in presenza di un problema illimitato, scelgo il pivot che genera il minimo rapporto tra il termine noto e il coefficiente della relativa variabile nella colonna $h$ della matrice $\mathbf {A}$, cioè $i'=\min \left\{{\frac {\mathbf {b} _{i}}{\mathbf {a} _{ih}}}\;\mathbf {:} \;\mathbf {a} _{ih}>{0},\;\forall i=1,\ldots ,n\right\}$ e applico 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

Dato il problema di programmazione lineare $\min \left\{\gamma \left(\mathbf {x} \right):=\mathbf {c} ^{T}\mathbf {x} :A\mathbf {x} =\mathbf {b} ,\mathbf {x} \geq \mathbf {0} \right\}$ si considera la base ammissibile $B$ contenente colonne linearmente indipendenti di $A$. Si può riscrivere la relazione $A\mathbf {x} =\mathbf {b}$ come:

$B\mathbf {x} _{B}+F\mathbf {x} _{F}=\mathbf {b}$

con $F$ matrice contenente le colonne di $A$ escluse dalla base ammissibile $B$.

Ancora si può riscrivere la relazione precedente come:

$B\mathbf {x} _{B}=\mathbf {b} -F\mathbf {x} _{F}\Rightarrow \mathbf {x} _{B}=B^{-1}\mathbf {b} -B^{-1}F\mathbf {x} _{F}$

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

$\mathbf {c} ^{T}\mathbf {x} =\left[{\begin{bmatrix}\mathbf {c} _{B}^{T}&\mathbf {c} _{F}^{T}\end{bmatrix}}\right]\left[{\begin{bmatrix}\mathbf {x} _{B}\\\mathbf {x} _{F}\end{bmatrix}}\right]\Rightarrow$

$\mathbf {c} ^{T}\mathbf {x} =\left[{\begin{bmatrix}\mathbf {c} _{B}^{T}&\mathbf {c} _{F}^{T}\end{bmatrix}}\right]\left[{\begin{bmatrix}B^{-1}\mathbf {b} -B^{-1}F\mathbf {x} _{F}\\\mathbf {x} _{F}\end{bmatrix}}\right]\Rightarrow$

$\mathbf {c} ^{T}\mathbf {x} =\mathbf {c} _{B}^{T}B^{-1}\mathbf {b} +\left(\mathbf {c} _{F}^{T}-\mathbf {c} _{B}^{T}B^{-1}F\right)\mathbf {x} _{F}=\mathbf {c} ^{T}\mathbf {x} +k$

con $k$ valore costante e $\mathbf {c} ^{T}:=\mathbf {c} _{F}^{T}-\mathbf {c} _{B}^{T}B^{-1}A$ vettore dei costi ridotti.

Sotto tali condizioni se il vettore dei costi ridotti risulta non negativo, la soluzione base ammissibile associata ad $A$ risulta essere ottima. Ciò significa che il valore assunto dalla funzione obiettivo $\gamma \left(\mathbf {x} \right)$ è il minimo globale per la funzione nel dominio considerato.

Prestazioni

In pratica l'algoritmo funziona molto bene, 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

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:

• Simplesso primale standard
• Simplesso duale standard
• Simplesso per flussi

Voci correlate

• Programmazione matematica
• Ricerca operativa

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sull'algoritmo del simplesso

Collegamenti esterni

• Angelo Guerraggio, Metodo del simplesso, in Enciclopedia della scienza e della tecnica, Istituto dell'Enciclopedia Italiana, 2007-2008.
• Simplesso, metodo del, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) Stephen J. Wright, simplex method, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Simplex Method, su MathWorld, Wolfram Research.
• (EN) Simplex method, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
• (EN) Denis Howe, simplex method, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
• (EN) Algoritmo del simplesso, di Elmer G. Wiens. Dimostra l'algoritmo del dettaglio, usando la simplex tableau.
• Risoluzione di problemi di programmazione lineare mediante il metodo del simplesso, su Operations Research Group, University of Trieste (archiviato dall'url originale il 25 febbraio 2008).