Lezioni di Ricerca Operativa
Corso di Laurea in Informatica ed Informatica Applicata
Università di Salerno
Lezione n° 10: 6-7 Aprile 2009
Algoritmo del Simplesso:
- Passi fondamentali
- Esempio
Anno accademico 2008/2009
Prof. Cerulli – Dott.ssa Gentili
Scelta della variabile entrante.
Quando la condizione di ottimalità non è verificata è
sempre possibile scegliere una variabile fuori base xk
da portare in base per migliorare l’obiettivo.
Quando esistono più alternative la scelta non preclude
il raggiungimento della soluzione ottima, ma può al
peggio aumentare il tempo necessario per la sua
ricerca.
Scelta della variabile entrante.
Il metodo del gradiente
Sceglie la variabile che localmente fa aumentare più
rapidamente l’obiettivo:
z k  ck  max z j  c j 
jN
Scelta della variabile uscente.
Determinata la variabile fuori base xk da portare in
base, si deve scegliere la variabile uscente.
Esistono due situazioni alternative:
a) yrk>0 per almeno un r
Allora si può aggiornare la base come visto.
Scelta della variabile uscente.
Determinata la variabile fuori base xk da portare in
base, si deve scegliere la variabile uscente.
Esistono due situazioni alternative:
b) yik0 "i=1,...m
Allora la soluzione del problema è illimitata
(non esiste ottimo finito).
In questo caso facendo aumentare xk il valore di
nessuna variabile di base diminuisce:
z  z 0  ( z k  ck ) xk  z 0
Per qualsiasi valore di xk
Nota

Se per una variabile di base i si ha che yik>0 e br=0
(soluzione degenere), xk entra in base con valore
nullo.

In questo caso la soluzione non cambia, ed in
particolare rimane degenere.

Per questa ragione la ricerca della soluzione
potrebbe rimanere bloccata generando sempre la
medesima soluzione (cycling).

Il cycling è piuttosto raro e comunque esistono
strategie per evitalo.
L’algoritmo del Simplesso
1. Inizializzazione.
Determinare una soluzione di base ammissibile.
2. Test di ottimalità.
Se zj-cj≤0 "jN allora la soluzione corrente è
ottima e l’algoritmo termina.
Altrimenti andare al passo 3.
3. Scelta della variabile entrante in base.
Scegliere una variabile fuori base xk tale che zk-ck>0
ed andare al passo 4.
L’algoritmo del Simplesso
4. Test di illimitatezza:
Se yik0 "i=1,...m, allora la soluzione del problema
è illimitata (non esiste ottimo finito), e l’algoritmo
termina. Altrimenti vai al Passo 5.
5. Scelta della variabile uscente dalla base: Test
dei minimi Rapporti
Scegliere la variabile xBr tale che
 b j

br
xk 
 min 
: y jk  0
jN  y
y rk

 jk
L’algoritmo del Simplesso
6. Aggiornamento della base:
Aggiornare gli indici delle variabili in base (B) e
quelli delle variabili fuori base (N).
Andare al passo 2.
Esempio: Applicazione del Simplesso
min z   x1  2 x2
 2 x1  x2  1
x1  x2  2
x1  x2  5
x0
  2 1 1 0 0
A  - 1 1 0 1 0 
 1 1 0 0 1 
min z   x1  2 x2
 2 x1  x2  x3  1
 x1  x2  x4  2
x1  x2  x5  5
x  0 x3  0, x4  0, x5  0
B  3,4,5
N  1,2
Esempio: Applicazione del Simplesso (Cont.)
 1 0 0
AB   0 1 0 
 0 0 1 
x B  A B1 b  x B  Ib  x B  b
 x3 
1 0 0  1 
 x   A-1 b  0 1 0  2
B
 4

  
 x5 
0 0 1 5 
z0  c B AB1 b
x3  1, x4  2, x5  5
1 


z 0  0 0 0 2  0
5 
Esempio: Applicazione del Simplesso (Cont.)
Test di Ottimalità: calcolo di zj – cj per j N
B  3,4,5
N  1,2
( z j  c j )  ( c B AB1 a j  c j )  ( c B y j  c j )
  2
( z1  c1 )  0 0 0 I  1   (1)  0  1  1
 1 
1




( z 2  c2 )  0 0 0 I 1  (2)  0  2  2
1
"j  N
Esempio: Applicazione del Simplesso (Cont.)
( z 2  c2 )  max z j  c j   max ( z1  c1 ), ( z 2  c2 )
jN
j1, 2
( z 2  c2 )  max 1,2  2
x2 entra in base
Quale variabile esce dalla base?
Regola del minimo rapporto:
 b j

br
xk 
 min 
: y jk  0
jB  y
yrk

 jk
1
B
yj  A aj
1
B
b A b
Esempio: Applicazione del Simplesso (Cont.)
y2  A a
-1
B 2
1 1
 I 1  1
   
1 1
 x3  b1  1 
 x   b   2
 4  2  
 x5  b 3  5 
 
 b j

b1
1 2 5 
x2 
 min 
: y jk  0  x2  1  min  , , 
jB  y
y12

1 1 1 
 jk
x3 esce dalla base; x2 entra in base con valore 1
Nuova base:
B  2,4,5
N  1,3
Esempio: Applicazione del Simplesso (Cont.)
 1 0 0
AB   1 1 0 
 1 0 1 
Calcoliamo
1
B
xB  A b
1
B
A
 1 0 0  1 0 0
 1 0 0  1 0 0
 1 0 0
 1 1 0   0 1 0   0 1 0 - 1 1 0   A 1  - 1 1 0 
B








 1 0 1   0 0 1
 0 0 1 - 1 0 1 
- 1 0 1 
Esempio: Applicazione del Simplesso (Cont.)
1
B
xB  A b
 x2 
 1 0 0 1  1 
 x   A 1 b  - 1 1 0  2  1 
B
 4

   
 x5 
- 1 0 1  5  4
z0  c B b  c B AB1 b
 1 0 0 1 
1 
z0  - 2 0 0 - 1 1 0  2  - 2 0 0 1   2
- 1 0 1  5 
4
Esempio: Applicazione del Simplesso (Cont.)
Test di Ottimalità: calcolo di zj – cj per j N
B  2,4,5
N  1,3
( z j  c j )  ( c B AB1 a j  c j )  ( c B y j  c j )
"j  N
 1 0 0   2
  2
( z1  c1 )  - 2 0 0 - 1 1 0   1   (1)  - 2 0 0  1   1  5
- 1 0 1   1 
 3 
 1 0 0 1 
1
( z 3  c3 )  - 2 0 0  - 1 1 0  0  0  - 2 0 0  - 1   0  2
 - 1 0 1 0
 1
Esempio: Applicazione del Simplesso (Cont.)
zj – cj > 0 per j=1
x1 entra in base
Quale variabile esce dalla base?
Regola del minimo rapporto:
 b j

br
xk 
 min 
: y jk  0
jB  y
yrk

 jk
1
B
yj  A aj
1
B
b A b
Esempio: Applicazione del Simplesso (Cont.)
1 0 0 
y1  A-1B a1  -1 1 0


 -1 0 1
-2 -2
 -1   1 
   
 1   3 
 x 2  b1  1 
 x   b   1 
 4  2  
 x5  b 3  4
 
 b j

b2
1 4 
x1 
 min 
: y jk  0  x1  1  min  , 
jB  y
y21

1 3 
 jk
x4 esce dalla base; x1 entra in base con valore 1
Nuova base:
B  1,2,5
N  3,4
Esempio: Applicazione del Simplesso (Cont.)
- 2 1 0
AB  - 1 1 0 
 1 1 1 
1
B
xB  A b
Calcoliamo
1
B
A
- 2 1 0  1 0 0
 1 - 1 2 0 - 1 2 0 0
 - 1 1 0   0 1 0   - 1 1 0   0 1 0





 1 1 1   0 0 1
 1 1 1   0 0 1




1 - 1 2 0 - 1 2 0 0
 1 - 1 2 0 - 1 2 0 0
 0 1 2 0  -1 2 1 0    0 1 0  -1 2 0





 0 3 2 1   1 2 0 1 
 0 3 2 1   1 2 0 1




Esempio: Applicazione del Simplesso (Cont.)
- 2 1 0
AB  - 1 1 0 
 1 1 1 
1
B
xB  A b
Calcoliamo
1
B
A
1 0 0  - 1 1 0 
 -1 1 0 
0 1 0  - 1 2 0  A 1   - 1 2 0
B





0 0 1  2 - 3 1
 2 - 3 1
Esempio: Applicazione del Simplesso (Cont.)
1
B
xB  A b
 x1 
 - 1 1 0  1  1 
 x   A1 b  - 1 2 0 2  3
B
 2

   
 x5 
2 - 3 1 5 1 
z0  c B b  c B AB1 b
 - 1 1 0 1 
1
z0  - 1 - 2 0  - 1 2 0  2  - 1 - 2 0 3  7

 
 
 2 - 3 1 5
1
Esempio: Applicazione del Simplesso (Cont.)
Test di Ottimalità: calcolo di zj – cj per j N
B  1,2,5
N  3,4
( z j  c j )  ( c B AB1 a j  c j )  ( c B y j  c j )
"j  N
 - 1 1 0  1 
 1
( z3  c3 )  - 1 - 2 0 - 1 2 0 0  0  - 1 - 2 0  1  0  3

 
 
2 - 3 1 0
 2 
 - 1 1 0  0
1
( z4  c4 )  - 1 - 2 0 - 1 2 0 1   0  - 1 - 2 0  2   0  5

 
 
2 - 3 1 0
 3
Esempio: Applicazione del Simplesso (Cont.)
zj – cj > 0 per j=3
x3 entra in base
Quale variabile esce dalla base?
Regola del minimo rapporto:
 b j

br
xk 
 min 
: y jk  0
jB  y
yrk

 jk
1
B
yj  A aj
1
B
bA b
Esempio: Applicazione del Simplesso (Cont.)
 - 1 1 0  1 - 1
y3  A -B1a 1  - 1 2 0 0  - 1
 2 - 3 1 0  2 
 x 2  b1  1 
 x   b   3
 1   2  
 x5  b 3  1 
 
 b j

b3
1
1 
x3 
 min 
: y jk  0   x3   min  
jB
y33
2
2
 y jk

x5 esce dalla base; x3 entra in base con valore 1/2
Nuova base:
B  1,2,3
N  4,5
Esempio: Applicazione del Simplesso (Cont.)
 - 2 1 1
AB  - 1 1 0 
 1 1 0 
1
B
xB  A b
Calcoliamo
1
B
A
- 2 1 1  1 0 0
 1 - 1 2 - 1 2  - 1 2 0 0
 - 1 1 0   0 1 0  


-1 1 0  0 1 0




 1 1 0   0 0 1

1 1 0   0 0 1




1 - 1 2 - 1 2 - 1 2 0 0
 1 - 1 2 0  - 1 2 0 0
 0 1 2 -1 2  -1 2 1 0    0 1 -1  -1 2 0





 0 3 2 1 2   1 2 0 1 
 0 3 2 1 2  1 2 0 1




Esempio: Applicazione del Simplesso (Cont.)
 - 2 1 1
AB  - 1 1 0 
 1 1 0 
1
B
xB  A b
Calcoliamo
1
B
A
1 0 - 1  - 1 1 0  1 0 - 1  - 1 1 0 
0 1 - 1  - 1 2 0  0 1 - 1  - 1 2 0 


 


 0 0 2   2 - 3 1  0 0 1   1 - 3 2 1 2
1 0 0  0 - 1 2 1 2
 0 - 1 2 1 2
0 1 0  0 1 2 1 2   A 1   0 1 2 1 2 
B





0 0 1  1 - 3 2 1 2
 1 - 3 2 1 2
Esempio: Applicazione del Simplesso (Cont.)
1
B
xB  A b
 x2 
0 - 1 2 1 2 1  3 2 
 x   A 1 b   0 1 2 1 2  2  7 2
B
 1

   
 x3 
1 - 3 2 1 2 5  1 2 
z0  c B b  c B AB1 b
 0 - 1 2 1 2 1 
3 2 
17






z0  - 1 - 2 0 0 1 2 1 2 2  - 1 - 2 0 7 2  

 
 
2
 1 - 3 2 1 2  5
1 2 
Esempio: Applicazione del Simplesso (Cont.)
Test di Ottimalità: calcolo di zj – cj per j N
B  1,2,3
N  4,5
( z j  c j )  ( c B AB1 a j  c j )  ( c B y j  c j )
"j  N
0 - 1 2 1 2 0
 12
1
( z4  c4 )  - 1 - 2 0 0 1 2 1 2 1   0  - 1 - 2 0  1 2   0  

 


2
1 - 3 2 1 2  0
 - 3 2
0 - 1 2 1 2 0
1 2 
3
( z5  c5 )  - 1 - 2 0 0 1 2 1 2 0  0  - 1 - 2 0  1 2   0  

 
 
2
1 - 3 2 1 2  1 
 1 2