- Problema del trasporto
Lezioni di Ricerca Operativa
Corso di Laurea in Informatica Università di Salerno
Prof. Cerulli – Dott.ssa Gentili – Dott. Carrabs
2
Problema del Flusso a costo Minimo FORMULAZIONE
A i
0
1
: i con vincol min
)
( ( )
) , (
∈
≥
=
=
∑ − ∑
∑
∈ ∈
∈
ij i FS
j k BS i
i ki
ij A j i
ij ij
x
,...n i
b x
x
x c
j) (i, arco sull'
flusso di
unità un'
di trasporto di
costo
j) (i, arco sull'
flusso di
quantità
=
=
ij ij
c x
passaggio di
nodo :
0 se
domanda nodo
: 0 se
offerta nodo
: 0 se
: i nodo al
associato valore
=
<
>
=
i i i i
b b b b
Problema del Flusso a costo Minimo FORMULAZIONE
0 min
≥
= x
b Ax
x c
TIn forma matriciale:
NOTA:
1. La matrice A(m,n) è la matrice di incidenza nodo-arco, ogni colonna a
ijè associata all’arco (i,j), ed in particolare abbiamo che:
a
ij= e
i− e
j2. Il rango di questa matrice è: r(A)=m-1
(e
ivettore colonna con tutti 0 eccetto un 1 in posizione i-ma.)
Un particolare problema di flusso a costo minimo:
Il Problema del Trasporto
m fornitori producono o
1,...,o
mquantità di un certo prodotto
n clienti richiedono d
1,...,d
nquantità di prodotto
il prodotto può essere trasportato da ogni fornitore ad ogni cliente
NOTA:
Il grafo sottostante è un grafo bipartito dove i nodi origine
(fornitori) hanno solo archi uscenti ed i nodi destinazione
(clienti) hanno solo archi entranti
Il problema: determinare le quantità di prodotto da trasportare su ogni arco (i,j) (fornitore-cliente) in modo da minimizzare il costo complessivo del trasporto.
M M
M M
c ij
-d
1-d
j-d
no
1o
jo
mFormulazione del problema.
Le variabili:
la quantità di prodotto trasportata su ciascun arco
n j
m i
x
ij≥ 0 = 1 ,..., ; = 1 ,...,
sono variabili continue e non negative
La funzione obiettivo:
il costo del trasporto complessivo
i m
ij ij j
n
= = c x
∑ ∑
1 1
I vincoli:
la quantità totale di prodotto fornita da ciascun fornitore deve essere uguale alla disponibilità del fornitore stesso
la quantità totale di prodotto ricevuta da ciascun
cliente deve essere uguale a quella richiesta
Il problema del trasporto: FORMULAZIONE
n 1,..., j
m;
1,..., i
R
x
(3) n
1,..., j
m;
1,..., i
0
x
(2)
n;
1,..., j
d
x
(1)
m;
1,..., i
o
x
x c min
ij ij
j m
1 i
ij
i n
1 j
ij m
1 i
n
1 j
ij ij
=
=
∈
=
=
≥
=
−
=
−
=
=
∑
∑
∑ ∑
=
=
= =
Ipotesi di ammissibilità (condizione di bilanciamento):
Affinchè il problema possa ammettere una soluzione deve essere verificata la seguente condizione sui dati
ossia, la quantità totale di prodotto disponibile deve essere uguale alla richiesta totale del prodotto stesso.
0 d
o
n
1 j
j m
1 i
i
− ∑ =
∑
= =Esistenza di una soluzione ammissibile
x
ij= o
id
j∆ i = 1...m , j = 1...n e ∆ = o
ii=1 m
∑ = d
jj=1 n
∑
x
ijj=1 n
∑ = o
id
jj=1
∆
n
∑ = o
i∆ d
j=
j=1 n
∑ o
i∆ ∆ = o
i− x
iji=1 m
∑ = − o
id
ji=1
∆
m
∑ = − d
j∆ o
i= −
j=1 n
∑ d
j∆ ∆ = − d
jSia
Vogliamo dimostrare che la precedente soluzione è ammissibile per il problema del trasporto.
Per farlo bisogna dimostrare che i vincoli (1) e (2) del sistema
siano soddisfatti.
Il problema del trasporto
Sottocaso particolare del flusso a costo minimo
• Non esistono nodi di passaggio
• E’ possibile andare da ogni nodo offerta (insieme O) a ogni nodo richiesta (insieme D)
• Il grafo sottostante è un grafo bipartito
1
3
5 55 5 222 2 3 3 3 3
2
4
5
- - - -4444 - - - -6666 666
6 2 22 2 11 11 44 44
2 2 2 2 6 66 6
1
3
5 5 5 5 22 22 3 3 3 3
2
4
5
-- --4444 -- --6666 6
66 6 222 2 11 11 44 44
2 2 2 2 66 66
A (1,4) (1,5) (2,4) (2,5) (3,4) (3,5)
1 1 1 0 0 0 0
2 0 0 1 1 0 0
3 0 0 0 0 1 1
4 -1 0 -1 0 -1 0
5 0 -1 0 -1 0 -1
Consideriamo la matrice di incidenza nodo-arco A per il problema del trasporto
Il problema del trasporto
-I -I -I
Struttura della matrice dei vincoli
1 n n+1 2n (m-1)n+1 mn
1 2
m 1
n
… …
…… …… ……
-I -I -I
1
m
1 n
Rango della matrice dei vincoli
n 2n 3n mn 1
1 2
m 1
n- 1
…. .… ……
…… 2 …… n-1
3
Eliminando l’ultima riga della matrice e selezionando le seguenti m+n-1 colonne: n, 2n, 3n,...,mn,1,2,3,...,n-1 (nell’ordine indicato) otteniamo la seguente sottomatrice quadrata (triangolare superiore):
1
m
n
Th: Se A è una matrice diagonale o triangolare superiore o triangolare inferiore allora il determinante di A è dato dal prodotto degli elementi sulla diagonale principale.
Quindi la sottomatrice costruita è invertibile ed il rango di A è pari ad m+n-1
Problema del Trasporto: RISOLUZIONE
Possiamo rappresentare il problema tramite due tabelle, una relativa alle variabili l ’ altra relativa ai costi:
n
m mn
m m
n n
d d
d
O x
x x
m
O x
x x
O x
x x
n
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
2
...
...
1
...
...
2 1
2 1
2 1
2 2
22 21
1 1
12 11
mn m
m
n n
c c
c m
c c
c
c c
c
n
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
2
...
...
1
...
...
2 1
2 1
2 22
21
1 12
11
Utilizziamo queste due tabelle per risolvere il problema
2. Migliorare la soluzione ammissibile trovata fino a soddisfare le condizioni di ottimalità:
REGOLA DEL CICLO
Problema del trasporto: RISOLUZIONE
per risolvere il problema dobbiamo:
1. Trovare una soluzione ammissibile iniziale:
METODO DELL ’ ANGOLO DI NORD-OVEST
Metodo dell ’ angolo di Nord-Ovest
Passo 4: Poni j=j+1; O
i=O
i-d
je vai al passo 2 Passo 0: Poni x
ij=0 per ogni i e per ogni j Passo 1: i=1, j=1
Passo 2: x
ij=minimo { O
i, d
j}
Se il minimo è uguale a O
iallora vai al passo 3 Se il minimo è uguale a d
jallora vai al passo 4
Passo 3: Poni i=i+1; d
j=d
j-O
ie vai al passo 2
Metodo dell ’ angolo di Nord-Ovest: ESEMPIO
Consideriamo la seguente tabella dei costi:
35 30
20 15
50 8
4 3
9 3
25 6
7 2
8 2
25 7
6 5
10 1
4 3
2 1
Le iterazioni dell ’ algoritmo danno luogo alle seguenti tabelle di variabili:
NOTA:
m=3, n=4 quindi il rango della matrice A è r(A)=3+4-1=6.
Quindi dobbiamo selezionare 6 variabili per ottenere una
soluzione di base
Metodo dell ’ angolo di Nord-Ovest: ESEMPIO
35 30
20 15
50 0
0 0
0 3
25 0
0 0
0 2
25 0
0 0
0 1
4 3
2 1
35 30
20 15
50 0
0 0
0 3
25 0
0 0
0 2
25 0
0 0
15 1
4 3
2 1
35 30
20 0
50 0
0 0
0 3
25 0
0 0
0 2
10 0
0 0
15 1
4 3
2 1
35 30
10 0
50 0
0 0
0 3
25 0
0 10 0
2
0 0
0 10 15 1
4 3
2 1
35 30
10 0
50 0
0 0
0 3
25 0
0 0
0 2
0 0
0 10 15 1
4 3
2 1
35 30
20 0
50 0
0 0
0 3
25 0
0 0
0 2
10 0
0 10 15
1
4 3
2 1
35 30
0 0
50 0
0 0
0 3
15 0
0 10 0
2
0 0
0 10 15 1
4 3
2 1
35 30
0 0
50 0
0 0
0 3
15 0
15 10
0 2
0 0
0 10 15 1
4 3
2 1
35 15
0 0
50 0
0 0
0 3
0 0
15 10
0 2
0 0
0 10 15
1
4 3
2 1
Metodo dell ’ angolo di Nord-Ovest: ESEMPIO
35 30
20 15
50 35
15 0
0 3
25 0
15 10
0 2
25 0
0 10 15
1
4 3
2 1
Le variabili di base della soluzione ammissibile iniziale sono:
34 33
23 22
12
11 , x , x , x , x , x x
Ora dobbiamo verificare se questa soluzione è ottima, se non
è ottima cerchiamo un ’ altra soluzione con la regola del ciclo.
Condizioni di ottimalità
Condizioni di ottimalità del simplesso:
N j
c
z
j−
j≤ 0 ∀ ∈
z
j− c
j= c
BTA
B−1a
j− c
j≤ 0 ∀ j ∈ N
Soluzione duale di base associata alla soluzione di
base primale
Colonna della matrice corrispondente alla variabile xj
Coefficiente di costo della variabile xj
n 1,..., j
m;
1,..., i
R x
(3) n 1,...,
j m;
1,..., i
0 x
(2) n;
1,..., j
d
x
(1) m;
1,..., i
o
x
x c min
ij ij
j m
1 i
ij i n
1 j
ij m
1 i
n
1 j
ij ij
=
=
∈
=
=
≥
=
−
=
−
=
=
∑
∑
∑ ∑
=
=
= =
n;
1,..., j
m;
1,..., i
d o
max
m
1 i
n
1 j
j i
=
=
≤
∑
−∑
= =
ij j
i
j i
c -v
u
v u
(u
i) (v
j)
Duale del problema del trasporto
Condizioni di ottimalità
Dobbiamo verificare i valori z
ij-c
ijper ogni x
ijnon in base.
Il calcolo di queste differenze si riduce al calcolo delle differenze dei valori delle variabili duali associate ai vincoli:
z
ij-c
ij=u
i-v
j-c
ijdove u
iè la variabile duale associata all ’ i-simo vincolo di origine e v
jè la variabile duale associata al j-simo vincolo di destinazione.
Consideriamo la matrice dei costi iniziali e la matrice delle variabili corrispondente alla soluzione di base trovata:
35 30
20 15
50 35
15 0
0 3
25 0
15 10
0 2
25 0
0 10
15 1
4 3
2 1
35 30
20 15
50 8
4 3
9 3
25 6
7 2
8 2
25 7
6 5
10 1
4 3
2
1
Condizioni di ottimalità
Le variabili duali sono 7 (4 associate ai vincoli di destinazione:
v
1,v
2,v
3,v
4e 3 associate ai vincoli di origine: u
1,u
2,u
3).
Possiamo determinare questi valori sapendo che z
ij-c
ij=0 per ogni variabile x
ijin base. Per cui otteniamo:
8 4 7 2 5 10
34 4
3 34
33 3
3 33
23 3
2 23
22 2
2 22
12 2
1 12
11 1
1 11
=
=
−
⇒
=
=
−
⇒
=
=
−
⇒
=
=
−
⇒
=
=
−
⇒
=
=
−
⇒
c v
u x
c v
u x
c v
u x
c v
u x
c v
u x
c v
u x
Questo è un sistema di 6 equazioni in 7 incognite, per cui fissando a zero il valore di una variabile otteniamo i valori delle altre
Condizioni di ottimalità
Fissiamo u1=0 ed otteniamo:
v
1= -10 v
2= - 5 v
3= -10 v
4= -14 u
2= -3 u
3= -6
Da cui otteniamo :
4 3
5 6
5 9
10 6
5 6
14 3
1 8
10 3
7 7
14
4 6
10
32 2
3 32
32
31 1
3 31
31
24 4
2 24
24
21 1
2 21
21
14 4
1 14
14
13 3
1 13
13
−
=
− +
−
=
−
−
=
−
−
=
− +
−
=
−
−
=
−
=
− +
−
=
−
−
=
−
−
=
− +
−
=
−
−
=
−
=
−
=
−
−
=
−
=
−
=
−
−
=
−
c v
u c
z
c v
u c
z
c v
u c
z
c v
u c
z
c v
u c
z
c v
u c
z
La soluzione non è ottima, quindi dobbiamo scegliere una variabile non in base da introdurre in base. Facciamo entrare in base la variabile con coefficiente di costo massimo ossia x14.
Selezioniamo la variabile uscente con la regola del ciclo.
Supponiamo di avere la seguente tabella in cui le x rapresentano le variabili di base e la y la nuova variabile entrante.
x x
x x
x y
x x
x
4 3 2 1
5 4
3 2
1
+
−
− +
1. Consideriamo le variabili che formano un ciclo con la variabile entrante 2. Incrementiamo la variabile entrante da 0 ad un nuovo valore ∆>0
3. Le variabili di base coinvolte nel ciclo verranno incrementate di ∆, se hanno segno positivo, mentre verranno decrementate di ∆, se hanno segno negativo.
4. La variabile uscente sara’ quella che si azzera per prima.
La variabile entrante forma un ciclo con le variabili x24,x34,x33. Tra queste dobbiamo selezionarne una da far uscire dalla base. La scelta viene effettuata nel seguente modo:
Nella matrice incrementiamo y, decrementiamo x24, incrementiamo x34 e decrementiamo x41. Quanto vale ∆ ?
∆ = minimo{ xij: xij è coinvolta nel ciclo con segno meno }
