Algoritmo del simplesso

Da Wikipedia, l'enciclopedia libera.

L'algoritmo del simplesso, ideato dall'americano George Dantzig nel 1947, è un metodo numerico per risolvere problemi di programmazione lineare. È citato dalla rivista americana 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 N+1 vertici in N dimensioni: un segmento di retta in una dimensione, un triangolo in due dimensioni, un tetraedro in tre dimensioni.

La programmazione lineare[modifica | modifica sorgente]

Exquisite-kfind.png Per approfondire, vedi 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 \le 4 \\
x,y \ge 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[modifica | modifica sorgente]

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 così detta 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{\Alpha}  \mathbf{x}=\mathbf{b} e x_i \ge 0.

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} s.t.  \boldsymbol{\Alpha}  \mathbf{x}\le\mathbf{b} e x_i \ge 0. Riassumibile in un tableau del tipo \begin{vmatrix}\mathbf{A}  & \mathbf{b} \\ \boldsymbol{\gamma}^t & 0 \end{vmatrix} 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 \le 0  \forall i .
  2. Se non si ha ancora una tabella ottima scelgo una colonna h corrispondente al massimo fra i \gamma_i \ge0 (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 \quad \forall i . 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è  \min \left\{  \frac{\mathbf{b}_{ih} }{ \mathbf{a}_{ih} }  \; \mathbf{:} \; \mathbf{a}_{ih}>{0}, \; \forall i \right\} e applico l'operazione di cardine.


Verifica di ottimalità[modifica | modifica sorgente]

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\cdot\mathbf{x}_{B}+F\cdot\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\cdot\mathbf{x}_{B}=\mathbf{b}-F\cdot\mathbf{x}_{F}\Rightarrow\mathbf{x}_{B}=B^{-1}\cdot\mathbf{b}-B^{-1}\cdot F\cdot\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]\cdot\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]\cdot\left[\begin{bmatrix}
B^{-1}\cdot\mathbf{b}-B^{-1}\cdot F\cdot\mathbf{x}_{F}\\
\mathbf{x}_{F}\end{bmatrix}\right]\Rightarrow

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

con k valore costante e {c}^{T}:=\mathbf{c}^{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[modifica | modifica sorgente]

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

Tipi di simplesso[modifica | modifica sorgente]

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:

Note[modifica | modifica sorgente]

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

Voci correlate[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]


matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica