Lezione n°19-20
- Problema del trasporto
R. Cerulli – F. Carrabs
Lezioni di Ricerca Operativa
Università degli Studi di Salerno
Problema del flusso a costo minimo: Formulazione
= quantità di flusso che transita sull’arco (i,j)
= costo di trasporto di una unità di flusso sull’arco (i,j)
= valore intero associato al nodo i (ne definisce il ruolo nel problema):
: nodo di offerta
: nodo di domanda
: nodo di passaggio
In forma matriciale:
Osservazioni:
1. La matrice A è la matrice di incidenza nodo-arco con dimensione n
xm. Ogni colonna è associata all’arco (i,j), ed in particolare abbiamo che:
2. Il rango di questa matrice è: r(A) = n - 1
(e
ivettore colonna con tutti 0 eccetto un 1 nella posizione i-ma)
Problema del Flusso a Costo Minimo: Formulazione
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
Il grafo sottostante è un grafo bipartito dove i nodi origine (fornitori) hanno solo archi uscenti ed i nodi destinazione (clienti) hanno solo archi entranti.
Ad ogni arco (i,j) è associato un costo c
ijpositivo.
Un particolare problema di flusso a costo minimo:
Il Problema del Trasporto
Determinare la quantità di merce da trasportare su ogni arco (i,j) (fornitore- cliente) affinchè ogni fornitore i invii la merce o
iprodotta, ogni cliente j riceva la quantità d
jrichiesta ed il costo complessivo di trasporto sia minimizzato.
-d
1-d
j-d
no
1o
io
mProblema del Trasporto: Obiettivo
c
ij
Le variabili:
la quantità di prodotto trasportata sull’arco (i,j). Sono variabili continue e non negative.
La funzione obiettivo:
il costo del trasporto complessivo
Il problema del trasporto: Formulazione
�
��≥ 0 �=1 , …, � ; �=1 , … , �
min ∑
�=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
∑ �=1
�
� �� − 0= � � �=1 , …, �(1)
0 − ∑
�=1
�
�
��= − �
��=1 , …,�(2)
Il problema del trasporto: Formulazione
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.
Ipotesi di ammissibilità (condizioni di bilanciamento)
∑ �=1
�
� � − ∑
�=1
�
� � = 0
Vogliamo dimostrare che la precedente soluzione è ammissibile per il problema del trasporto.
Per farlo bisogna dimostrare che i vincoli del problema siano soddisfatti.
Esistenza di una soluzione ammissibile
Sia e
� �= ��
∆ ∆ =¿ ��
∑
� =1�
���=
∑
� =1
� �� � �
∆ = ��
∆
∑
� =1
�
¿
��=− � �
∆ ∆=¿ − � �
−
∑
� =1
�
���=−
∑
� =1
� �� � �
∆ =− � �
∆
∑
�=1
�
¿
1
2
1
2 5
10
Problema del Trasporto: Esempio
-7
-8
50
60
300 320
Soluzione ottima: x
11=5, x
12=0, x
21=2, x
22=8 con z*=1370
A partire dal valore ottimo appena calcolato, è possible che, aumentando la domanda e l’offerta (di una stessa quantità), il nuovo valore ottimo sia minore di ?
In alcuni casi è possibile!!!
1
2
1
2 5
10
Il Paradosso del Trasporto
-7
-8
50
60
300 320
Soluzione ottima: x
11=6, x
12=0, x
21=1, x
22=9 con z*=1160
1
2
1
2 6
10
-7
-9
50
60
300 320
Soluzione ottima: x
11=5, x
12=0, x
21=2, x
22=8 con z*=1370
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 2 3
2
4
5
-4 6 -6
12
4 2
6
1
3
5 2 3
2
4
5
-4 6 -6
2 1 4 2
6
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
-I -I -I
Il problema del trasporto
1 n n+1 2n (m-1)n+1 mn 1
2
m 1
n
… …
…… …… ……
-I -I -I
Struttura della matrice dei vincoli
n 2n 3n mn 1 1
2
m 1
n-1
… … … …
…… 2 …… n-1
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):
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
Rango della matrice dei vincoli
Possiamo rappresentare il problema tramite due tabelle, una relativa alle variabili l’altra relativa ai costi:
Utilizziamo queste due tabelle per risolvere il problema
Problema del trasporto: Risoluzione
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
Problema del trasporto: Risoluzione
Teorema. Condizione necessaria e sufficiente affinchè una soluzione ammissibile per il problema del trasporto sia di base è che essa abbia al più m+n-1 componenti non nulle tali che nessun loro sottoinsieme formi cicli.
Definizione (ciclo). In un problema del trasporto, si dice che una successione di variabili della tabella forma un ciclo se è possibile congiungere tali variabili con una successione di segmenti alternativamente orizzontali e verticali, aventi come estremi due di tali variabili. Inoltre partendo da una qualunque di queste variabili è possible ritornare ad essa, tramite questa successione, senza passare mai due volte per una stessa variabile.
x x x
x
x x
x x
x
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
2. Migliorare la soluzione di base ammissibile corrente trovata fino a soddisfare le condizioni di ottimalità:
REGOLA DEL CICLO
Per risolvere il problema dobbiamo:
1. Trovare una soluzione di base ammissibile iniziale:
METODO DELL’ANGOLO DI NORD-OVEST
Problema del trasporto: Risoluzione
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
Consideriamo la seguente tabella dei costi:
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 8
4 3
9 3
25 6
7 2
8 2
25 7
6 5
10 1
4 3
2
1
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
Le variabili di base della soluzione ammissibile iniziale sono:
Ora dobbiamo verificare se questa soluzione è ottima; se non è ottima cerchiamo un’altra soluzione con la regola del ciclo.
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
34 33
23 22
12
11 , x , x , x , x , x
x
Condizioni di ottimalità del simplesso:
Moltiplicatori del simplesso Moltiplicatori del simplesso
Colonna della matrice corrispondente alla variabile xj
Colonna della matrice corrispondente alla variabile xj
Coefficiente di costo della variabile xj
Coefficiente di costo della variabile xj
Condizioni di Ottimalità
N j
c
z
j
j 0
z
j c
j= c
BTA
B1a
j c
j 0 j N
(u
i) (v
j)
Duale del problema del trasporto
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
m1 i
n 1 j
j i
=
=
= =
ij j
i
j i
c -v
u
v
u
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 offerta e
• v
jè la variabile duale associata al j-simo vincolo di domanda.
Consideriamo la matrice dei costi iniziali e la matrice delle variabili corrispondente alla soluzione di base trovata:
Condizioni di Ottimalità
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
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:
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à
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
Fissando u
1=0 otteniamo:
v
1= -10 , v
2= - 5 , v
3= -10 , v
4= -14 , u
2= -3 , u
3= -6 Da cui otteniamo :
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 x
14.
Condizioni di Ottimalità
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
Supponiamo di avere la seguente tabella in cui le x rapresentano le variabili di base e la y la nuova variabile entrante.
1. Consideriamo le variabili in base che formano un ciclo con la variabile entrante;
2. I segni + e – sono assegnati in modo alternato negli angoli del ciclo partendo dalla variabile fuori base y a cui viene assegnato il + perchè deve essere incrementata di un nuovo valore ≥ 0;
3. Le variabili di base che si trovano negli angoli del ciclo verranno incrementate di , se hanno segno positivo, e decrementate di , se hanno segno negative;
4. La variabile uscente sarà quella che si azzererà 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 }
Variabile Uscente: Regola del Ciclo
x x
x x
x y
x x
x
4 3 2 1
5 4
3 2
1
