Modelli e Algoritmi della Logistica
Lezione – 15
Metodo di Ascesa Duale
ANTONIO SASSANO
Università di Roma“La Sapienza”
Dipartimento di Informatica e Sistemistica
Roma, 25-11-01
Metodo di Ascesa Duale: Esempio
[cij + uij] =
12 13
8 4

2 6

3 5
8 0

2 0
2 10
5 10
3 4
1
2

1

8
8

1
1
1
1
1
 
 
1
1
    Vk   
1
1
5
3
 
 
1
1
6
9
6
0
1
0
D =[
4
3
1
4
7
]
f =[
4
3
1
4
7
]
- max Vk=3
- arg max Vk=5
Vk=min(Dj(k) ,k)
il minimo della riga 5 deve
essere incrementato di 3
ukj(k)= u52 = u52+3
Metodo di Ascesa Duale: Esempio
12
8

2
[cij + uij] =  3

8

2
13
4
6
6
9
6
1
1 
1
1 
1
2
 
 

1 
1
1
   1  Vk  1
8
 
 
2
0 
8
 
 

1
1 
0 
0
1
0
5
2 10
0  3 5 10
0
3 4
D =[
4
0
1
4
7
]
f =[
4
3
1
4
7
]
- max Vk=1
- arg max Vk=1
Vk=min(Dj(k) ,k)
il minimo della riga 1 deve
essere incrementato di 1
ukj(k)= u14 = u14+1
Metodo di Ascesa Duale: Esempio
[cij + uij] =
12
8

2

3
8

2
D =[
f =[
- max Vk=1
- arg max Vk=2
4
4
13
4
6
6
9
6
5
2
03 5
0
3
0
3
1
1
0  1 1
0
0 
1 
1
1
2
 
 

1 
1
0
1
   1  Vk  1
10
8
 
 
2
0 
10
8
 
 

4
1
1 
0 
3
4
7
7
]
]
Vk=min(Dj(k) ,k)
il minimo della riga 2 deve
essere incrementato di 1
ukj(k)= u24 = u24+1
Metodo di Ascesa Duale: Esempio
[cij + uij] =
12
8

2

3
8

2
D =[
f =[
- max Vk=1
- arg max Vk=3
4
4
13
4
6
6
9
6
5
2
03 5
0
3
0
3
1
1
0  1 1
0
0 
0
0 
1  1 2
 
 

1 
1
0
1
   1  Vk  1
10
8
 
 
2
0 
10
8
 
 

4
1
1 
0 
2
4
7
7
]
]
Vk=min(Dj(k) ,k)
il minimo della riga 3 deve
essere incrementato di 1
ukj(k)= u34 = u34+1
Metodo di Ascesa Duale: Esempio
[cij + uij] =
12
8

2

3
8

2
D =[
f =[
- max Vk=1
- arg max Vk=4
4
4
13
4
6
6
9
6
5
2
03 5
0
3
0
3
1
1
0  1 1
0
0 
0
0 
1  1 2
 
 

0
0 
0  1 1
   1  Vk  1
10
8
 
 
2
0 
10
8
 
 

4
1
1 
0 
1
4
7
7
]
]
Vk=min(Dj(k) ,k)
il minimo della riga 4 deve
essere incrementato di 1
ukj(k)= u43 = u43+1
Metodo di Ascesa Duale: Esempio
12
8

2
[cij + uij] = 3

8

2
13
4
6
5
03
0
0  1 1
0
0 
0
0 
1  1 2
 
 

0
0 
0  1 1
   0 Vk  0
2  1 10
8
 
 
2
0 
5
10
8
 
 

3
4
1
1 
0 
6
9
6
D =[ 4
0
0
1
7
]
f =[ 4
3
1
4
7
]
Tutte le righe sono bloccate:
LB= zk=10
kI
1 
 2
 
1 
z 
 3
 3
 
0 
Metodo di Ascesa Duale: Osservazione
1 = 0 …..
12
8

2

3
8

2
D =[ 4
incrementiamo due minimi di riga contemporaneamente
13
4
6
5
03
0
0
0  1 1
1  1 2

0  1 1

2  1 10
8
5
10
8

3
4
1
6
9
6
0
LB= zk=11
kI
1
7]
z
2
13
6
0  2 1  1  
12
 
8
4
9
11
2  2


6
6
0 1
1  1 
2

 
3
5
2

1
10
8

 3
8 03
5
10
8  

 3
2
0
3
4
1

 
0

[ 4
0
0
0
6 ]
PROCEDURA DI ASCESA DUALE
Ad un generico passo:
- Ogni riga k ha un insieme dei minimi di riga m(k) (j(k)  m(k))
- s(k)= min {ckj+ ukj } minimo successivo della riga k
jJ-m(k)
- k= s(k) - (ck j(k)+uk j(k)) (max incremento di riga ( se J=m(k)))
-
Dm(k) min
jm(k)
{ fj -  uij } (massimo incremento di colonna)
-k=2
- m(k) = {4,5}
- s(k) = 4
- k = 4-2=2
- Dm(k) min {3,7}
iI
12 13
8
4

2 6

3 5
8 0

2 0
6
0
9 1  (u24  1)
6
0
2
5
3
10
10
4
1
2

1

8
8

1
[ 4
1
4
7 ]
3
PROCEDURA DI ASCESA DUALE
Ad un generico passo:
- Ogni riga k ha un insieme dei minimi di riga m(k) (j(k)  m(k))
- Una riga e’ BLOCCATA se Dm(k)=0 o k=0
- Per ogni riga k, poni
Vk =min(Dm(k) ,k)
- Scegli un riga k NON BLOCCATA con valore massimo della
quantita’ Vk /|m(k)|:
- Incrementa tutti le variabili uk j : jm(k) della quantita’ Vk
Quando tutte le righe sono bloccate, poni:
• Zk =
(ck j(k)+uk j(k))
• LB= zk
kI
per ogni kI
PROCEDURA DI ASCESA DUALE
Definizione di una soluzione primale:
- Attiva gli impianti
J*={ jJ: fj =  ukj }
kI
v =fj + min ckj)
jJ*
12
8

2

3
8

2
[ 4
0  2 1  1
11
2 

6
6
0 1
1 

5
2  1 10
8 
03
5
10
8 

0
3
4
1 
13
4
6
9
0
0
0
6 ]
kI jJ*
soluzione primale (“upper bound”)
g(z,u) =zk=(ck j(k)+uk j(k)) = ck j(k)+  uk j(k)
kI
kI
kI
kI
soluzione duale (“lower bound”)