Algoritmo del simplesso: differenze tra le versioni

Versione delle 19:31, 27 mar 2019

Versione attuale delle 18:36, 30 nov 2024

(17 versioni intermedie di 12 utenti non mostrate)

Riga 1:

{{nota disambigua|l'omonimo metodo di ottimizzazione non lineare|metodo di Nelder-Mead|Metodo del simplesso}}

L<nowiki>{{'</nowiki>}}'''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 [[algoritmo|algoritmi]] del secolo.<ref>Computing in Science and Engineering, volume 2, no. 1, 2000</ref>

Questo [[algoritmo]] fa uso del concetto di [[simplesso]], cioè un [[politopo]] di ''<math>N+1''</math> vertici in ''<math>N''</math> dimensioni:, ossia un [[segmento]] di retta in una dimensione, un [[triangolo]] in due dimensioni, un [[tetraedro]] in tre dimensioni.

== La programmazione lineare ==

Riga 8:

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

Per esempio il problema:<br />

:<math>\begin{cases} \max \quad x + 2y \\

x - y \le 4 \\

x, \ge 0 \\
y \ge 0 \end{cases} </math>

è 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).

Riga 29 ⟶ 32:

</math> ''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

<math> \boldsymbol{\gamma}^T \mathbf{x} </math>

tale che

s.t.

<math> \boldsymbol{\Alpha} \mathbf{x}\le\mathbf{b} </math> e

<math>x_i \ge 0</math>.

Riassumibile in un [[tableau]] del tipo

<math>\begin{pmatrix}\mathbf{A} \;\, \mathbf{b} \\ \boldsymbol{\gamma}^{T} \; 0 \end{pmatrix}</math>, l'algoritmo si articola nei seguenti passi applicati al tableau:

L'algoritmo si articola nei seguenti passi applicati al tableau:

# Verifica di ottimalità.: [[Condizionecondizione sufficiente]] perché la tabella sia ottima è che <math>\boldsymbol{\gamma}_i \le 0,</math> per ogni <math>i =1,\ldots,n</math> (se è un problema di massimo) o <math>\forallboldsymbol{\gamma}_i \ge 0,</math> per ogni <math>i =1,...\ldots,n</math> (se di minimo).

# Se non si ha ancora una tabella ottima, scelgosi sceglie una colonna <math>h</math> corrispondente al massimo fra i <math>\gamma_i \ge0</math> (costi ridotti positivi) (ve ne sarà almeno uno, altrimenti ci saremmo fermati al punto 1).

# Verifica di illimitatezza. Condizione sufficiente perché il problema sia illimitato è che nella colonna <math> h </math> individuata si abbiano solo valori negativi nella matrice, cioè <math> \mathbf{a}_{ih} < 0, \quad; \forall i =1,...\ldots,n</math>. Dunque il problema è illimitato lungo questa direzione.

# Se non siamo in presenza di un problema illimitato, scelgosi sceglie il pivot che genera il minimo rapporto tra il termine noto e il coefficiente della relativa variabile nella colonna <math>h</math> della matrice <math> \mathbf {A}</math>, cioè <math> i'=\min \left\{ \frac{\mathbf{b}_{i} }{ \mathbf{a}_{ih} } \; \mathbf{:} \; \mathbf{a}_{ih}>{0}, \; \forall i =1,...\ldots,n\right\}</math> e applicosi 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à. [[Condizione sufficiente]] perché la tabella sia ottima è che <math>\boldsymbol{\gamma}_i \le 0 </math> <math>\forall i =1,...,n</math>.

# Se non si ha ancora una tabella ottima scelgo una colonna <math>h</math> corrispondente al massimo fra i <math>\gamma_i \ge0</math> (costi ridotti positivi) (ve ne sarà almeno uno altrimenti ci saremmo fermati al punto 1).

# Verifica di illimitatezza. Condizione sufficiente perché il problema sia illimitato è che nella colonna <math> h </math> individuata si abbiano solo valori negativi nella matrice, cioè <math> \mathbf{a}_{ih} < 0 \quad \forall i =1,...,n</math>. Dunque il problema è illimitato lungo questa direzione.

# 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 <math>h</math> della matrice <math> \mathbf {A}</math>, cioè <math> i'=\min \left\{ \frac{\mathbf{b}_{i} }{ \mathbf{a}_{ih} } \; \mathbf{:} \; \mathbf{a}_{ih}>{0}, \; \forall i =1,...,n\right\}</math> 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 <math>\min \left\{ \gamma\left(\mathbf{x}\right):=\mathbf{c}^{T}\mathbf{x}:A\mathbf{x}=\mathbf{b},\mathbf{x}\geq\mathbf{0}\right\}</math>

si considera la [[Base (algebra lineare)|base]] ammissibile <math>B</math> contenente colonne linearmente indipendenti di <math>A</math>. Si può riscrivere la relazione <math>A\mathbf{x}=\mathbf{b}</math> come:

:<math>B\cdot\mathbf{x}_{B}+F\cdot\mathbf{x}_{F}=\mathbf{b}</math>

con <math>F</math> matrice contenente le colonne di <math>A</math> escluse dalla base ammissibile <math>B</math>.

Riga 53 ⟶ 56:

Ancora si può riscrivere la relazione precedente come:

:<math>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}</math>

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

:<math>\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</math>

:<math>\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</math>

:<math>\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{x}_{F}=\mathbf{c}^{T}\mathbf{x}+k</math>

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

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

== Prestazioni ==

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

== Tipi di simplesso ==

Riga 90 ⟶ 93:

* [[Programmazione matematica]]

* [[Ricerca operativa]]

== Altri progetti ==

{{interprogetto|preposizione=sull'}}

== Collegamenti esterni ==

* {{MathWorld|2=SimplexCollegamenti Methodesterni}}

* {{SpringerEOMFOLDOC|autore=E.G.simplex Gol'shteinmethod|titolo=Simplexsimplex method}}

* {{en}} [https://web.archive.org/web/20060518080331/http://www.egwald.com/operationsresearch/lpsimplex.php Algoritmo del simplesso], di Elmer G. Wiens. Dimostra l'algoritmo del dettaglio, usando la ''simplex tableau''.

* {{cita web|url=http://www.univ.trieste.it/~orts/didattica/LezioniRicercaOperativa/prog_lineare/simplesso/|titolo=Risoluzione di problemi di programmazione lineare mediante il metodo del simplesso|sito=Operations Research Group|editore=University of Trieste|urlarchivio=https://web.archive.org/web/20080225142205/http://www.univ.trieste.it/~orts/didattica/LezioniRicercaOperativa/prog_lineare/simplesso/|dataarchivio=25 febbraio 2008|urlmorto=sì}}