Algoritmo del simplesso

Da Wikipedia, l'enciclopedia libera.

L'Algoritmo del simplesso, ideato da G.B. Dantzig, è un metodo per risolvere problemi di programmazione lineare. Si vuole massimizzare o minimizzare una funzione lineare con delle restrizioni (vincoli) anch'esse lineari per i valori delle variabili, che possono assumere valori positivi.

Per esempio il problema:

max $\,x + 2y$

con

$x - y \le 4$

$x,y \ge 0$

è 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 insieme poliedrale o poliedro, il quale può essere vuoto, limitato o illimitato. L'algorimo 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 aggiungendo variabili di eccesso (slack) 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} & 0 \end{vmatrix}$ L'algoritmo si articola nei seguenti passi applicati al tableau:

Verifica di ottimalità.Condizione sufficiente perché la tabella sia ottima è che $\boldsymbol{\gamma}_i \le 0$ $\forall i$ .
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.
Verifica di illimitatezza. Condizione sufficiente se cioè nella colonna h individuata abbiamo tutti valori negativi l’obiettivo è illimitato lungo questa direzione.
Se non siamo in presenza di una sol. illimitata scelgo il pivot tra gli quello che da vita al minimo rapporto e applico l’operazione di cardine.

[modifica] Verifica di ottimalità

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}$

ed andando a sostiture 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.

[modifica] Prestazioni

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.