Home

Federica EU

1/19

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
$ \[ d_j=1,\quad d_i=0 \ \ \forall i\not=j,B(1),B(2),\ldots,B(m). \] $

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

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

Metodo del Simplesso, 6

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

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. \] $

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\}. \] $

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

$\[ \theta^*c'd=\theta^*\bar c_j. \] $

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^*, \] $

allora

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

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è

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

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.

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à:

è stata ottenuta una base ottima B ed una soluzione ottima ad essa associata;

è stato individuato un vettore d tale che

$\[ Ad=0,\quad d\geq 0\quad \mbox{e}\quad c'd<0, \] $
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\}; \] $

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\}. \] $

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]$

Le lezioni del Corso

1. Presentazione del Corso ed Introduzione alla Programmazione Mat...
2. Introduzione ai Problemi di PL
3. Problemi di PL
4. Geometria della PL
5. Algoritmo del Simplesso
6. Algoritmo del Simplesso Revisionato
7. Algoritmo del Simplesso Tabellare
8. Metodo delle Due Fasi
9. Metodo del Big-M
10. Soluzione di Problemi di PL tramite Algoritmo del Simplesso
11. Problemi di Programmazione Lineare Intera
12. PLI con matrice dei vincoli unimodulare
13. Problemi di PLI: Branch & Bound
14. Il Problema dello Zaino 0/1 e il Problema dello Zaino Frazionar...
15. Il Problema dello Zaino 0/1: un algoritmo B&B
16. Il Problema dello Zaino 0/1: un algoritmo di Programmazione Din...
17. Richiami di Teoria dei Grafi: definizioni e notazioni
18. Il Problema del Vertex Cover Minimo di un Grafo
19. Il Problema dell'Albero di Copertura Minimo (MST)
20. Il Problema dell'Albero di Copertura Minimo (MST): esempio
21. Problemi di Cammino Minimo
22. Problemi di Cammino Minimo: algoritmo di Dijkstra
23. Problemi di Cammino Minimo: esempio
24. Il Problema della Pianificazione di un Progetto

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.

Chi siamo | Friendly | Mobile e-Learning | Policy | Email | Facebook | YouTube | Twitter | Pinterest | Flickr