Modelli e Algoritmi della Logistica
Metodo del Simplesso Dinamico
SARA MATTIA
Università di Roma“La Sapienza”
Dipartimento di Informatica e Sistemistica
Problema
Sia dato il grafo G(V,E), dove V rappresenta un insieme
di città, ed E rappresenta i collegamenti tra le città.
2
(6,3)
s
(2,8)
3
(6,2)
(5,5)
1
(2,6)
(5,4)
4
(3,5)
6 t
(4,4)
5
Ad ogni arco (u,v)E sono associati:
• un costo di utilizzo cuv
• un tempo di percorrenza tuv
Un corriere preleva un pacco in 1 e deve
consegnarlo in 6, decidendo quale percorso scegliere per:
• minimizzare il costo di trasporto
• impiegare un tempo minore di Tmax = 12
Formulazione
2
(6,3)
s
(2,8)
3
(6,2)
(5,5)
1
(2,6)
(5,4)
4
(3,5)
6 t
(4,4)
(cuv, tuv)
Tmax = 12
5
• insieme ammissibile S :
vettori di incidenza di cammini tra s e t con ritardo
minore di T
x uv
1 (u,v)  Pst

0 (u,v)  Pst
Formulazione
2
(6,3)
s
3
(6,2)
(5,5)
1
6 t
(2,6)
(5,4)

(2,8)
4
(3,5)
(4,4)
(cuv, tuv)
Tmax = 12
5
• formulazione P :
t
uv
( u ,v )E
x
( u ,v )K
x uv  T
uv
1
0  x uv  1
vincolo sul ritardo
K st  taglio
(u,v )  E
cammino st
vincoli di box
Formulazione
2
(6,3)
s
3
(6,2)
(5,5)
1
(2,6)
(5,4)

(2,8)
4
(3,5)
6 t
(4,4)
(cuv, tuv)
Tmax = 12
5
min (6x12  5x14  2x 23  5x 25  2x 43  3x 45  6x 36  4x 56 )
3x12  4x14  8x 23  5x 25  6x 43  5x 45  2x 36  4x 56  12
x
( u ,v )K
uv
1
0  x uv  1
K st  taglio
(u,v )  E
Metodo del Simplesso Dinamico
problema “core”
(PQ)
P=
min cTx
xQ = {Dx>d, 1n > x >0n }
Metodo del
Simplesso
Q=
x*
aggiungi a Q
il vincolo
x* P
aTx  b
Oracolo di
Separazione
x*P
x* ottima
Metodo del Simplesso Dinamico
problema “core”
(PQ)
2
t
s
min cTx
xQ = {Dx>d, 1n > x >0n }

3
6
1
4
5
min (6x12  5x14  2x 23  5x 25  2x 43  3x 45  6x 36  4x 56 )
3x12  4x14  8x 23  5x 25  6x 43  5x 45  2x 36  4x 56  12
x12  x14  1
x 36  x 56  1
0  x uv  1
(u,v )  E
Metodo del Simplesso Dinamico

min (6x12  5x14  2x 23  5x 25  2x 43  3x 45  6x 36  4x 56 )
3x12  4x14  8x 23  5x 25  6x 43  5x 45  2x 36  4x 56  12
x12  x14  1
x 36  x 56  1
0  x uv  1
(u,v )  E
min cTx
xQ = {Dx>d, 1n > x >0n }
2
Metodo del
Simplesso
3
t
s
6
1
4
5
z*  9
*
*
x14
 x 56
1
 *
*
*
*
x

x

x

x
 36
56
43
12 

*
*
*

x

x

x
25
45  0
 23
Metodo del Simplesso Dinamico
2
3
t
s
Cmin  0
6
1
4
x12  x 43  x 45  1
5
*
*
x14
 x 56
1
 *
*
*
*
x

x

x

x
 36
56
43
12 

*
*
*

x

x

x
25
45  0
 23
aggiungi a Q
il vincolo
z*  9
Metodo del
Simplesso
x*
x* P
aTx  b
Oracolo di
Separazione
Metodo del Simplesso Dinamico

min (6x12  5x14  2x 23  5x 25  2x 43  3x 45  6x 36  4x 56 )
3x12  4x14  8x 23  5x 25  6x 43  5x 45  2x 36  4x 56  12
x12  x14  1
x 36  x 56  1
Metodo del
x12  x 43  x 45  1
Simplesso
0  x uv  1 (u,v )  E
x*
*
x  x  1
 *
*
*
*
x

x

x

x
 36
56
43
14 

*
*
*

x

x

x
25
45  0
 23
*
12
*
56
z  10
2
3
t
s
6
1
4
5
Metodo del Simplesso Dinamico
2
3
Cmin  0
t
s
6
1
4
x 23  x 25  x 43  x 45  1
5
*
*
x12
*
 x 56
1
z

10
 *
*
*
x

x

x
 36
56
43 

*
*
*
*

x

x

x

x
23
25
45  0
 14
aggiungi a Q
il vincolo
x* P
aTx  b
Metodo del
Simplesso
x*
Oracolo di
Separazione
Metodo del Simplesso Dinamico

min (6x12  5x14  2x 23  5x 25  2x 43  3x 45  6x 36  4x 56 )
3x12  4x14  8x 23  5x 25  6x 43  5x 45  2x 36  4x 56  12
x12  x14  1
x 36  x 56  1
Metodo del
x12  x 43  x 45  1
Simplesso
x 23  x 25  x 43  x 45  1
*
*
z
 13
x
0  x  1 (u,v )  E
uv
3
2
x  x  1
s
 *
*
1
x 36  x 56  1 2
 *
*
*
*
x

x

x

x
23
25
45  0
 14
*
12
t
*
43
6
4
5
Metodo del Simplesso Dinamico
2
3
t
s
Cmin  0
6
1
4
x14  x 25  x 23  1
5
*
*
x12
 x 43
1
 *
z *  13
*
x 36  x 56  1 2
 *
*
*
*
x

x

x

x
23
25
45  0
 14
aggiungi a Q
il vincolo
x* P
aTx  b
Metodo del
Simplesso
x*
Oracolo di
Separazione
Metodo del Simplesso Dinamico

min (6x12  5x14  2x 23  5x 25  2x 43  3x 45  6x 36  4x 56 )
3x12  4x14  8x 23  5x 25  6x 43  5x 45  2x 36  4x 56  12
x12  x14  1
x 36  x 56  1
Metodo del
x12  x 43  x 45  1
Simplesso
x 23  x 25  x 43  x 45  1
x*
x14  x 25  x 23  1
z *  13
0  x uv  1
(u,v )  E
2
3
s
t
6
*
*
*
x14
1
 x 43
 x 36
1
 *
*
*
*
*
x12  x 23
 x 25
 x 45
 x 56
0
4
5
Metodo del Simplesso Dinamico
2
3
t
s
6
1
4
5
*
*
*
x14
 x 43
 x 36
1
 *
*
*
*
*
x12  x 23
 x 25
 x 45
 x 56
0
la capacità del taglio
minimo è 1
non c’è nessun
vincolo violato
z *  13
Metodo del
Simplesso
x*
Oracolo di
Separazione
x*P
x* ottima
Metodo del Simplesso Dinamico
2
3
t
s
6
1
4
z *  13
5
*
*
*
x14
 x 43
 x 36
1
 *
*
*
*
*
x12  x 23
 x 25
 x 45
 x 56
0
• x* soluzione ottima
per P
• x* intera
x* ottima per il
problema intero