Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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 xk+1 = xk + θk dk. 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 algoritmo a direzione ammissibile


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 aij 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 x1, x2 ed x3.

Pertanto, annullando x1 e x2, variabili rispetto alle quali il sistema non è in forma canonica, dalla prima equazione si ricava x3 = b1, dalla seconda x4 = b, dalla terza x5 = b3.

La soluzione basica ammissibile determinata è quindi x1 = x2 = 0, x3 = b1, x4 = b2, x5 = b3.

 


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 xb il vettore delle variabili rispetto alle quali si vuole il sistema in forma canonica e sia xnb il vettore delle restanti variabili. Sia B (matrice di base) la matrice costituita dalle colonne iniziali di A relative alle variabili di xb. 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 xnb + B-1Bxb = B-1b

ponendo B-1NB = C ed essendo B-1B = I si ottiene: Cxnb + Ixb = 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”.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion