Algoritmo del simplesso: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
mNessun oggetto della modifica |
|||
Riga 2:
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
== 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:
:<math>\begin{cases} \max \quad x + 2y \\
x - y \le 4 \\
x
y \ge 0 \end{cases} </math> è un problema di programmazione lineare.
Riga 42 ⟶ 45:
# 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 ⟶ 57:
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{c}^{T}\mathbf{x}+k</math>
con <math>k</math> valore costante e <math>{c}^{T}:=\mathbf{c}_{F}^{T}-\mathbf{c}_{B}^{T}B^{-1}A</math> vettore dei costi ridotti.
Riga 74 ⟶ 78:
== Prestazioni ==
{{senza fonte|In pratica l'algoritmo funziona molto bene}}, ma in teoria non è polinomiale e si possono costruire speciali
== Tipi di simplesso ==
| |||