Home

Federica EU

1/18

Antonio Sforza » 6.Ottimizzazione lineare: Algoritmo del Simplesso

Schema della lezione

In questa lezione si descrive la struttura fondamentale dell’algoritmo del simplesso, interpretato come algoritmo a direzione ammissibile e come procedura algebrica.

Si descrivono infine le relazioni algebriche fondamentali alla base dell’algoritmo.

Soluzione dei problemi di Programmazione Lineare

Per la soluzione dei problemi di Programmazione Lineare (PL) è possibile costruire un algoritmo molto semplificato rispetto al caso non lineare. L’algoritmo utilizzato per la soluzione dei problemi PL è l’algoritmo del simplesso. Questo algoritmo può essere interpretato come algoritmo a direzione ammissibile. Esso genera infatti, come gli algoritmi a direzione ammissibile, una successione di punti che rispetta la relazione ricorsiva x_k+1 = x_k + θ_k d_k. In pratica esso opera in termini algebrici, attraverso la trasformazione del sistema di vincoli, costituito da equazioni e disequazioni, in un sistema di equazioni, del quale è necessario trovare particolari soluzioni, soluzioni basiche ammissibili, corrispondenti ai vertici del dominio. Infatti, poiché il dominio di ammissibilità è convesso e la funzione obiettivo è lineare, il punto di ottimo non solo appartiene alla frontiera ma è sicuramente un vertice del dominio di ammissibilità. L’algoritmo del simplesso è dunque in pratica un generatore di soluzioni basiche ammissibili sempre migliori, sottoposte ad un test di ottimalità necessario per decidere se la soluzione corrente è ottima o meno.

Struttura dell’Algoritmo del Simplesso

L’algoritmo del Simplesso come algoritmo a direzione ammissibile

L’algoritmo del Simplesso come procedura algebrica

$\begin{array}{llllll}a_{11}x_1+a_{12}x_2 + \ldots + a_{1n}x_n\leq b_1 \\ a_{21}x_1+a_{22}x_2 + \ldots + a_{2n}x_n\leq b_2\\\ldots\hspace{1cm} \lodts\hspace{1cm} \ldots\hspace{1cm} \ldots\hspace{1cm} \\a_{i1}x_1+a_{i2}x_2 + \ldots + a_{in}x_n\geq b_i\\ \ldots\hspace{1cm} \lodts\hspace{1cm} \ldots\hspace{1cm} \ldots\hspace{1cm}\\a_{m1}x_1+a_{m2}x_2 + \ldots + a_{mn}x_n\geq b_m\end{array}$

L’algoritmo del Simplesso come procedura algebrica

$\begin{array}{llllll}a_{11}x_1+a_{12}x_2+\ldots+a_{1n}x_n+y_t&&&=&b_1\\a_{11}x_1+a_{12}x_2+\ldots+a_{1n}x_n+&y_2&&=&b_2\\ a_{i1}x_1+a_{i2}x_2+\ldots+a_{in}x_n+&-\;\;y_i&&=&b_i\\ a_{m1}x_1+a_{m2}x_2+\ldots+a_{mn}x_n&\;\;\;-y_m&&=&b_m\end{array}$

Soluzioni del sistema di disequazioni/equazioni

Soluzioni di un sistema di equazioni lineari

Dominio di ammissibilità e s.b.a.

Vertici del dominio e valori delle variabili

Schema: dal modello P.L. alla soluzione ottima

Struttura dell’Algoritmo del Simplesso

Sistemi in forma canonica e soluzioni basiche ammissibili

Una soluzione basica ammissibile può essere agevolmente determinata a partire da un sistema in forma canonica.
Si ricordi che un sistema di equazioni si dice in forma canonica quando nella matrice A dei coefficienti a_ij del sistema è individuabile una matrice identità.

A partire da un sistema in questa forma è molto facile determinare una soluzione basica ammissibile. Infatti se si pongono a zero le variabili rispetto alle quali il sistema non è in forma canonica (variabili non basiche) da ciascuna riga è possibile ricavare il valore di una delle variabili rispetto alle quali il sistema è in forma canonica (variabili basiche).

Quindi in ogni equazione è presente una variabile basica (quella corrispondente alla colonna nella quale c’è il termine 1 della forma canonica).

Sistemi in forma canonica e soluzioni basiche ammissibili

Il sistema di equazioni seguente, con 3 vincoli e 5 variabili è in forma canonica rispetto alle variabili x₁, x₂ ed x₃.

Pertanto, annullando x₁ e x₂, variabili rispetto alle quali il sistema non è in forma canonica, dalla prima equazione si ricava x₃ = b₁, dalla seconda x₄ = b, dalla terza x₅ = b₃.

La soluzione basica ammissibile determinata è quindi x₁ = x₂ = 0, x₃ = b₁, x₄ = b₂, x₅ = b₃.

Trasformazione di Ax=b in forma canonica

Se il sistema Ax = b non è in forma canonica esso può essere messo in questa forma con una semplice operazione di tipo algebrico. Sia x_b il vettore delle variabili rispetto alle quali si vuole il sistema in forma canonica e sia x_nb il vettore delle restanti variabili. Sia B (matrice di base) la matrice costituita dalle colonne iniziali di A relative alle variabili di x_b. Sia NB la matrice delle restanti colonne di A.

$x=\left[\begin{array}{lll}x_{xb}\\ \ldots\\x_b\end{array}\right]\hspace{1,5cm}A=[NB|B]$

Il sistema Ax = b si potrà scrivere come:

$[NB|B]\left[\begin{array}{lll}x_{xb}\\ \ldots\\ x_b\end{array}\right]=b\hspace{1cm}\text{cioe'}\hspace{1cm}NBx_{xb+Bx_b=b}$

Trasformazione di Ax=b in forma canonica

Se si premoltiplica il sistema per B^-1 si ottiene:

B^-1 NB x_nb + B^-1Bx_b = B^-1b

ponendo B^-1NB = C ed essendo B^-1B = I si ottiene: Cx_nb + Ix_b = B^-1b

Pertanto per mettere un sistema Ax = b in forma canonica rispetto a certe variabili e determinare una s.b.a. basta premoltiplicare il sistema stesso per la matrice B^-1, inversa della matrice B costituita dalle colonne iniziali di A relative alle variabili rispetto alle quali si vuole il sistema in forma canonica.

La matrice B prende il nome di “matrice di base” o “base”. Con il termine “base” si suole anche indicare l’insieme di variabili basiche le cui colonne in A costituiscono B. La matrice B^-1 si indica con il termine “inversa di base”.