Lezioni di Ricerca Operativa
Corso di Laurea in Informatica ed Informatica Applicata
Università di Salerno
Lezione n° 11: 20-21 Aprile 2009
Algoritmo del Simplesso:
- Metodo delle 2 Fasi
- Esempio
Anno accademico 2008/2009
Prof. Cerulli – Dott.ssa Gentili
Metodo Delle Due Fasi
Dato il seguente problema di PL in forma STANDARD:
min
zc x
Ax  b
x0
T
(1)
(2)
x  Rn
con A(m.n) e b ≥ 0. Supponiamo di volerlo risolvere
utilizzando l’algoritmo del simplesso.
Ci occorre una base iniziale
Metodo Delle Due Fasi
Se tra le colonne di A non è presente la matrice Identità
non è facile individuare m colonne di A linearmente
indipendenti.
Si modifica allora artificialmente il sistema dei vincoli:
T
min c x
Ax  b  Ax  I y  b
x0
 x  0, y  0
con l’aggiunta di una variabile artificiale yi ad ogni
vincolo del sistema. Nel nuovo sistema è presente una
matrice identità (associata alle variabili y).
Metodo Delle Due Fasi
Una soluzione (x’,y’) del nuovo sistema sarà soluzione
anche del sistema di partenza se e solo se y’=0.
Per ottenere una tale soluzione (se esiste) risolviamo il
seguente problema di PL.
min
y
i
i
Ax  I y  b
x  0, y  0
Metodo Delle Due Fasi
Per risolvere tale problema possiamo utilizzare
il simplesso utilizzando come base iniziale le colonne
della matrice (A,I) associate alle variabili artificiali y.
Quindi nella prima fase si risolve il problema:
min g   yi
i
Ax  I y  b
x  0, y  0
Inizialmente tutte le variab. y sono
in base mentre tutte le variabili x
sono fuori base.
Metodo Delle Due Fasi
Alla fine della prima fase possono verificarsi due casi,
l’ottimo della F.O:
1) g* >0  Ax=b non ammette soluzione. Non si
passa alla seconda fase
2) g* =0  Ax=b ammette soluzione (a meno di
soluzioni degeneri).
Si passa alla seconda fase: si risolve il problema
iniziale utilizzando la base ottima della prima fase
come base iniziale della seconda fase.
Metodo Delle Due Fasi: Esempio
min z   x1  2 x2
min z   x1  2 x2
x1  x2  1
x1  x2  x3
x1  2 x2  4
x1  2 x2
x0
1
 x4  4
x0
min g  y1
Problema della
Prima fase
x1  x2  x3  y1  1
x1  2 x2
 x4
x  0, y  0
4
Metodo Delle Due Fasi: Esempio
min g  x5
Per uniformità poniamo
y1=x5.
x1  x2  x3
x1  2 x2
 x5  1
 x4
4
x0
x1 x 2 x 3 x 4 x 5
1 1 - 1
A
1 2 0
0
1
1  B  5,4 N  1,2,3

0 
Matr. Identità
Base Iniziale
Metodo Delle Due Fasi: Esempio
1 0 
AB  

0 1 
x B  A B1 b  x B  Ib  x B  b
 x5 
1 0
-1
 x   b  A B b  0 1
 
 4
1  1 
 4    4
   
x5  1, x4  4
Test di Ottimalità: calcolo di zj – cj per j N
B  5,4 N  1,2,3
1
( z1  c1 )  1 0 I    0  1
1
1 
( z2  c2 )  1 0 I    0  1
 2
 1
( z3  c3 )  1 0 I    0  1
 0
Metodo Delle Due Fasi: Esempio
x2 entra in base
Quale variabile esce dalla base?
Regola del minimo rapporto:
 x5 
1 
 x   b   4
 
 4
y2  A a
-1
B 2
1  1 
I   
2 2
 b j

b1
x2 
 min 
: y jk  0  x2  1  min 1,2
jB  y
y1k

 jk
x5 esce dalla base; x2 entra in base con valore 1
Nuova base:
Possiamo ignorare la var. x5:
B  2,4
B  2,4
N  1,5,3
N  1,3
Metodo Delle Due Fasi: Esempio
1 0
AB  

2
1


 1 0
A 

- 2 1
1
B
 x2 
 1 0
-1
 x   b  A B b  - 2 1


 4
1  1 
 4   2
   
Test di Ottimalità: calcolo di zj – cj per j N
B  2,4 N  1,3
-1 1
( z1  c1 )  0 0 A B    0  0
1
 1
( z3  c3 )  0 0 A    0  0
 0
-1
B
Metodo Delle Due Fasi: Esempio
Soluzione Ottima della Prima fase
1
B
g*  c B b  c B A b
 1 0 1 
g*  0 0 
0



- 2 1 4
Si risolve il problema iniziale:
utilizzando come base di
partenza:
B  2,4 N  1,3
Si può passare
alla seconda fase
min z   x1  2 x2
x1  x2  x3
x1  2 x2
x0
1
 x4  4
Metodo Delle Due Fasi: Esempio
1 0
AB  

2
1


 1 0
A 

- 2 1
1
B
 x2 
 1 0
-1
 x   b  A B b  - 2 1


 4
1  1 
 4   2
   
Test di Ottimalità: calcolo di zj – cj per j N
B  2,4 N  1,3
 1 0 1
( z1  c1 )  - 2 0 
 (1)  1



- 2 1 1
 1 0  1
( z3  c3 )  - 2 0 
0  2



- 2 1  0 
Metodo Delle Due Fasi: Esempio
x3 entra in base
Quale variabile esce dalla base?
Regola del minimo rapporto:
 x2 
1 
 x   b   2
 
 4
 1 0 - 1  - 1
y3  A a3  
 



- 2 1  0  2 
-1
B
 b j

b2
x3 
 min 
: y jk  0  x3  1  min 1
jB  y
y2 k

 jk
x4 esce dalla base; x3 entra in base con valore 1
Nuova base:
B  2,3 N  1,4
Metodo Delle Due Fasi: Esempio
1 - 1 
AB  

2
0


 0 1/2 
A 

- 1 1/2 
1
B
 x2 
 0 1/2  1  2
-1
 x   b  A B b  - 1 1/2  4  1 

    
 3
Test di Ottimalità: calcolo di zj – cj per j N
B  2,3 N  1,4
 0 1/2  1
( z1  c1 )  - 2 0 
 (1)  1  1  0



- 1 1/2  1
 0 1/2  0
( z4  c4 )  - 2 0 
 0  1



- 1 1/2  1 