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
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Paola Festa » 5.Algoritmo del Simplesso


Metodo del Simplesso, 1

Nella trattazione del Metodo del Simplesso supporremo di dover risolvere il seguente generico problema di PL formulato in forma standard:

\[  \begin{array}{llll} \mbox{{\rm (Pr)}} & \mbox{{\rm min}} & c'x\\ & \mbox{{\rm s.a}} \\ &                  &Ax  & = b\\ &                  &x    & \geq 0, \end{array} \]

dove A\in {\mathbb R}^{m\times n} ha rango pari ad m.

Con A_i indicheremo l’i.ma colonna di A, mentre con a'_i ne indicheremo l’i.ma riga.

Suppurremo, inoltre, che P sia la regione ammissibile corrispondente al problema.

Metodo del Simplesso, 2

Come già sottolineato, il Metodo del Simplesso passa da una soluzione ammissibile di base ad una soluzione ammissibile di base adiacente e termina quando non esiste una soluzione ammissibile di base adiacente migliore.

Infatti, esso può essere interpretato come algoritmo di ricerca locale. Si noti che sfortunatamente in generale una soluzione ottima localmente non è necessariamente ottima globalmente.

Fortunatamente, però, nel caso di problemi di PL, dal momento che si tratta di ottimizzare una funzione obiettivo convessa su una regione ammissibile convessa, si è certi che l’ottimo locale restituito in output dal metodo del simplesso è ottimo anche globalmente.

Metodo del Simplesso, 3

Supponiamo che ad una generica iterazione, il Metodo del Simplesso abbia calcolato la soluzione ammissibile di base x in P.

Come individuare una direzione lungo la quale si verifica un decremento del valore corrente della funzione obiettivo a partire da x?

In altri termini, data la soluzione ammissibile di base corrente x in P a partire dalla quale vogliamo muoverci lungo la direzione di un certo vettore d\in {\mathbb R}^n , come va scelto detto vettore d?

Innanzitutto, dobbiamo limitare la scelta di d a quei vettori che non ci conducano fuori dalla regione ammissibile P. Tale osservazione porta immediatamente alla seguente definizione di direzione ammissibile.

Definizione: Sia x\in P\subset {\mathbb R}^n .

Un vettore d\in {\mathbb R}^n è detto direzione ammissibile a partire da x se esiste uno scalare \theta>0 tale che

\[ x+\theta d\in P. \]

Metodo del Simplesso, 4

Dunque, dalla soluzione ammissibile di base corrente x tale che

\[B=\left[A_{B(1)}\ A_{B(2)}\ \ldots\ A_{B(m)}\right];\qquadx_B=\left(x_{B(1)}\ x_{B(2)}\ \ldots\ x_{B(m)}\right)=B^{-1}b;\qquad x_N=0.\]
si vuole passare alla soluzione adiacente

\[\bar x=x+\theta d\in P\]

\bar x può essere ottenuta selezionando una variabile non di base x_j,\ j\not= B(1),B(2),\ldots,B(m) ed incrementando il suo valore di una quantità positiva \theta , mantenendo nulle le restanti n-m-1 variabili non di base.

Metodo del Simplesso, 5

Algebricamente ciò equivale a porre
<br />
\[<br />
d_j=1,\quad  d_i=0 \ \ \forall i\not=j,B(1),B(2),\ldots,B(m).<br />
\]<br />

Al contempo, anche il vettore di base x_B dovrà cambiare in x_B+\theta d_B , dove d_B=\left(d_{B(1)}\ d_{B(2)}\ \ldots\ d_{B(m)}\right) è il vettore le cui componenti sono le componenti di d corrispondenti alle variabili di base.

Come determinare d_B ? Basta osservare che si vuole che

</p>
<p>\[</p>
<p>\bar x\in P\qquad \mbox{e}\qquad c'\bar x<c'x.</p>
<p>\]</p>
<p>

Metodo del Simplesso, 6

</p>
<p>\[</p>
<p>\bar x\in P \Longleftrightarrow \left\{</p>
<p>\begin{array}{ll}</p>
<p>\mbox{(a)} & A\bar x=b;\\ \mbox{(b)} & \bar x\geq 0.</p>
<p>\end{array} \right .</p>
<p>\]</p>
<p>

Ricordando che d_j=1,\  d_i=0\ \ \forall i\not=j,B(1),B(2),\ldots,B(m)

\[ \begin{array}{llll} (a)\qquad  b=A\bar x  =  Ax + \theta Ad \stackrel{Ax=b}{\Longrightarrow} & 0 & = & Ad=\displaystyle{\sum_{i=1}^m A_{B(i)}d_{B(i)}+\sum_{l\not=B(1),\ldots,B(m)}A_ld_l} \\ &  & = & \displaystyle{\sum_{i=1}^m A_{B(i)}d_{B(i)}+A_j} \\ &  & = & Bd_B+A_j\Longrightarrow d_B=-B^{-1}A_j. \end{array} \]

Metodo del Simplesso, 7

Ma come scegliere j fra le variabili non di base? Ricordando che vogliamo spostarci lungo una direzione ammissibile di miglioramento del valore corrente di funzione obiettivo:

\[ c'x>c'\bar x=c'x+\theta c'd\stackrel{\theta>0\ \mbox{\tiny per ip.}}{\Longrightarrow} 0>c'd=c'_Bd_B+c_j=c_j-c'_B B^{-1}A_j={\bar c}_j. \]<br />

Definizione: Sia x una soluzione di base, B la matrice di base ad essa associata e sia c_B il vettore dei costi associati alle variabili di base. Per ogni j=1,\ldots,n,\ {\bar c}_j si definisce costo ridotto della variabile x_j.

Dunque, j è un indice di variabile non di base cui corrisponde un costo ridotto negativo.

Nota: per ogni variabile di base x_{B(i)}, i=1,2,\ldots,m, si ha che

\[ \bar c_{B(i)}=c_{B(i)}-c'_B B^{-1} A_{B(i)}=c_{B(i)}-c'_B e_i=c_{B(i)}-c_{B(i)}=0. \]

Metodo del Simplesso, 8

Teorema

Sia x una soluzione ammissibile di base, B la matrice di base ad essa associata e sia \bar c il corrispondente vettore dei costi ridotti.

Se \bar c\geq 0 , allora x è ottima.

Se x è ottima e non degenere, allora \bar c\geq 0 .

Dunque, per essere sicuri che la corrente soluzione ammissibile di base non degenere sia ottima, è sufficiente controllare che tutti i costi ridotti delle variabili correntemente non in base siano non negativi.

Tale controllo equivale ad esaminare tutte le n-m direzioni di base.

Se, invece, la corrente soluzione è degenere, non è purtroppo disponibile un test altrettanto semplice. Fortunatamente, come vedremo di qui a poco, esiste una “regola” (Regola di Bland) che consente di ovviare a tali difficoltà in maniera efficiente.

Metodo del Simplesso, 9

In quanto segue supporremo per il momento di trattare soluzioni ammissibili di base non degeneri.

Se esiste un costo ridotto \bar c_j<0 con j indice di variabile non di base, allora la j.ma direzione di base d (d_j=1,\  d_i=0\ \ \forall i\not=j,B(1),\ldots,B(m) e d_B=-B^{-1}A_j ) è una direzione di base ammissibile che porta ad un decremento del valore della funzione obiettivo.

Muovendosi lungo la direzione di d, il valore della variabile non di base di indice j passa da 0 ad un valore \theta , mentre il valore delle altre variabili non di base rimane nullo.

Si fa riferimento a tale cambiamento dicendo che la variabile x_j (o la colonna A_j ) entra in base.

Metodo del Simplesso, 10

Muoversi lungo la direzione d vuol dire muoversi toccando punti del tipo x+\theta d,\  \theta>0 , ottenendo decrementi del valore della funzione obiettivo.

E’ banale osservare che vorremmo raggiungere il punto cui corrisponde il massimo di tali decrementi, sempre però rimanendo all’interno della regione ammissibile P, e cioè il punto x+\theta^* d , dove

\[ \theta^*=\max\{\theta>0\ \vert\ x+\theta d\in P\}. \]<br />

La risultante variazione del valore della funzione obiettivo sarà pari a:

\[ \theta^*c'd=\theta^*\bar c_j. \]<br />

Metodo del Simplesso, 11

Ma quanto vale \theta^* ?

Osserviamo che

\[ Ad=0 \Longrightarrow A(x+\theta d)=Ax=b\ \ \forall\ \theta, \]
per cui i vincoli di uguaglianza che descrivono P non possono essere mai violati.

Così, \bar x=x+\theta d può essere non ammissibile solo se una delle sue componenti diventa negativa.

A tal proposito osserviamo che le variabili fuori base in x rimangono non nulle. Infatti:

\[ \bar x_k \stackrel{\mbox{\tiny def.}}{=} x_k+\theta^* d_k = \left\{ \begin{array}{ll} \theta^*, & k=j;\\ x_k=0,    & \mbox{\small altrimenti}. \end{array} \right . \]

Metodo del Simplesso, 12

Dunque, per stabilire il valore da assegnare a \theta^* occorre preservare la nonnegatività delle sole variabili che in x sono in base.

A tal proposito distinguiamo due casi:

d_B\geq 0 .

In questa caso, dato che per ogni \theta>0 il vettore x+\theta d\geq 0 non può mai diventare non ammissibile, poniamo \theta^*=+\infty .

d_{B(i)}<0 per qualche i=1,\ldots,m .

In questo caso, occorre porre

\[ \theta^*=\displaystyle{\min_{\{i=1,2,\ldots,m \vert d_{B(i)}<0\}} \left\{\frac{x_{B(i)}}{d_{B(i)}}\right\}}. \] Nota: \theta^*>0 , dato che x_{B(i)}>0 per ogni i (ipotesi di soluzioni non degeneri).

Metodo del Simplesso, 13

Supponiamo di aver calcolato \theta^*<\infty . A questo punto, ci spostiamo da x a \bar x=x+\theta^* d .

Sia l l’indice di variabile tale che

\[ -\frac{x_{B(l)}}{d_{B(l)}}=\min_{\{i=1,2,\ldots,m \vert d_{B(i)}<0\}}\left\{ \frac{x_{B(i)}}{d_{B(i)}}\right\}=\theta^*, \]<br />

allora

\[  d_{B(l)}<0\  \mbox{e}\  x_{B(l)}+\theta^*d_{B(l)}=0. \]<br />

Dunque, la variabile di base x_{B(l)} è diventata nulla, mentre la variabile non di base x_j è diventata positiva e sostituisce x_{B(l)} in base.

Si fa riferimento a tale cambiamento dicendo che

  • la variabile x_j (o la colonna A_j ) entra in base;
  • la variabile x_{B(l)} (o la colonna A_{B(l)} ) esce dalla base.

Metodo del Simplesso, 14

Coerentemente, per ottenere la matrice di base \bar B associata alla nuova base, sostituiamo la colonna A_{B(l)} con la colonna A_j , cioè

<br />
\begin{displaymath}<br />
\bar B = \left[<br />
\begin{array}{ccccccc}<br />
A_{B(1)} & \ldots & A_{B(l-1)} & A_j & A_{B(l+1)} & \ldots &<br />
A_{B(m)}<br />
\end{array}<br />
\right].<br />
\end{displaymath}<br />

Teorema
Valgono le seguenti proprietà:

  • le colonne A_{B(i)},\  i\not= l , e A_j sono linearmente indipendenti, per cui \bar B è una base;
  • il punto \bar x=x+\theta^* d è una soluzione di base ammissibile associata alla matrice di base \bar B .

Metodo del Simplesso, 15

Si noti che,

  • dal momento che \theta^*>0,\ \bar x\not= x ;
  • d è una direzione ammissibile che porta ad un decremento del valore della funzione obiettivo.

Dunque, abbiamo raggiunto il nostro scopo: passare da una soluzione ammissibile di base (che è un vertice del poliedro descritto dall’insieme dei vincoli) ad una adiacente (vertice adiacente) cui corrisponde un valore della funzione obiettivo inferiore.

Abbiamo, cioè, effettuato un’iterazione dell’algoritmo del simplesso, che viene di solito chiamata operazione di pivot, formalmente descritta nella slide successiva.

Metodo del Simplesso, 16

Generica iterazione del Metodo del Simplesso.

Generica iterazione del Metodo del Simplesso.


Metodo del Simplesso, 17

Teorema
Sia dato un problema di PL avente regione ammissibile P non vuota.
Si supponga che ogni soluzione di base ammissibile al problema sia non degenere, allora il Metodo del Simplesso termina dopo un numero finito di iterazioni.

Al termine dell’esecuzione, possono verificarsi due possibilità:

  1. è stata ottenuta una base ottima B ed una soluzione ottima ad essa associata;
  2. è stato individuato un vettore d tale che

\[ Ad=0,\quad d\geq 0\quad \mbox{e}\quad c'd<0, \]<br />
per cui il valore ottimo della funzione obiettivo è -\infty .

Che succede in caso di soluzioni degeneri?
Può accadere che l’algoritmo cicli indefinitamente.

Rimedio: semplice regola (Regola di Bland) nello scegliere le variabili che escono dalla base e quelle che entrano in caso di ex equo, cioè nel caso in cui a più di una variabile di base corrisponda il minimo valore per \theta^* e nel caso in cui più di una variabile non di base abbia un costo ridotto negativo.

Metodo del Simplesso: regola di Bland

Regola di Bland

Caso A: \bar c_{j_1}<0,\cdots,\bar c_{j_k}<0,\quad j_1,\ldots,j_k\notin \{B(1),\ldots,B(m)\}.

Si decide di far entrare in base la variabile

\[ j=\min\{j_h\ \vert\ \bar c_{j_h}<0\}; \]<br />

Caso B: B(l_1),\cdots,B(l_k)\in \{B(1),\ldots,B(m)\}\ \mbox{t.c.}\  \frac{x_{B(l_h)}}{d_{B(l_h)}}=\theta^*,\ h=1,\ldots,k.

Si decide di far uscire dalla base la variabile

\[ B(l)=\min\left\{l_h\ \vert\ -\frac{x_{B(l_h)}}{d_{B(l_h)}}=\theta^*\right\}. \]<br />

Metodo del Simplesso: complessità computazionale

L’algoritmo del Simplesso con regola di Bland termina in al più \left(\begin{array}{c} n\\ m \end{array} \right) iterazioni (# vertici _ # finito di pivoting).
Per ciascuna iterazione:

  • risolvere il sistema p'B=c'_BB\qquad \left[O(m^3)\right]
  • per ogni variabile non di base x_j calcolare \bar c_j=c_j-p'A_j\qquad \left[O(mn)\right]
  • se esiste j t.c. \bar c_j<0 ,
  • risolvere Bu=A_j\qquad \left[O(m^3)\right]
  • se esiste almeno un indice i t.c. u_i>0 ,
    • calcolare \theta^*=\displaystyle{\min_{\{i=1,2,\ldots,m \vert u_i>0\}}\frac{x_{B(i)}}{u_i}} \qquad \left[O(m)\right]
    • calcolare \bar x\qquad \left[O(m)\right]
    • aggiornare \bar B\qquad \left[O(1)\right]
    • calcolare \bar B^{-1}\qquad \left[O(m^3)\right]

I materiali di supporto della lezione

D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008.

M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova, 1999.

S. Martello, Fondamenti di Ricerca Operativa L-A, Bologna, Società Editrice Esculapio, 2004.

S. Martello, Ricerca Operativa LS, Bologna, Società Editrice Esculapio, 2004.

Dispense ed Appunti del Corso.

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