Il problema del trasporto
•
Consideriamo il problema di trasportare una merce da m depositi (aventi disponibilità ai ) ad n
mercati (con richieste b j ) in presenza di costi unitari di spedizione cij dal deposito i al mercato j.
•
•
L’obiettivo che ci si pone è quello di minimizzare il costo complessivo del trasporto soddisfacendo
tutte le domande dei mercati e tenendo conto delle disponibilità dei vari depositi.
Questo problema è stato affrontato rigorosamente per la prima volta nel 1940 da Koopmans, un
economista olandese che successivamente ottenne il Nobel per questa ed altre ricerche.
Graficamente, il problema può essere illustrato come nel disegno che segue:
a1 1
1 b1
c21
a2 2
2 b2
.
.
.
.
.
.
n bn
am m
•
Per formulare il modello matematico di questo problema conviene introdurre le variabili:
xij
•
quantità di merce trasportata dal deposito i al mercato j
Il problema può essere formulato come:
m
n
∑∑ c x
min
ij ij
=i 1 =j 1
n
∑x
s.t.
j =1
ij
m
∑x
i =1
ij
≤ ai
i=
1,..., m
≥ bj
j=
1,..., n
xij ≥ 0
•
•
•
( P)
i = 1,..., m; j = 1,..., n
Nel primo vincolo, se xij è la quantità trasportata dal deposito i al mercato j, allora la sommatoria
indica, per il singolo deposito i, il totale della quantità di bene che da i giunge a tutti i mercati j =
1,2,…,m.
Il secondo vincolo è il vincolo di domanda ovvero il totale delle spedizioni che arrivano al singolo
mercato j deve soddisfare la richiesta del mercato j
E’ facile dimostrare che questo modello ammette soluzioni solo quando la disponibilità totale è
non minore della richiesta totale. Infatti, sommando i due gruppi di disuguaglianze si ottiene:
n
n
m
∑ b ≤∑∑
j =1
j
j =1 i =1
m
n
m
xij =∑∑ xij ≤∑ ai
i =1 j =1
i =1
•
•
Dunque con questo modello
o non si può trattare il caso in cui la domanda sia superiore alla disponibilità
o non si assegna alcun costo alla eventuale giacenza di merce nei vari depositi (o si suppone
che i costi siano uguali in tutti i depositi) nel caso in cui la disponibilità complessiva superi la
domanda totale.
Per tenere conto di questi costi e per estendere il modello al caso in cui non sia possibile soddisfare
tutta la domanda è sufficiente introdurre un deposito fittizio m+1 e/o un mercato fittizio n+1
interpretando i costi e le variabili decisionali nel modo seguente:
o
xi ,n +1 quantità di merce giacente nel deposito i
o
xm +1, j quantità di domanda non soddisfatta nel mercato j
o
ci ,n +1 costo unitario di giacenza nel deposito i
o
cm +1, j penalità unitaria per la carenza di merce nel mercato j
Esempio
a1 1
a2 2
c21
1 b1
2 b2
.
.
.
.
.
.
Per studiare cosa accade qualora vi sia eccesso di disponibilità ai depositi,
si aggiunge un nodo alle destinazioni e lo si collega a tutti i depositi; esso
avrà una domanda pari al totale dell’eccesso. Il costo, ci , n +1 , sarà pari al
costo unitario di giacenza nel deposito i.
n bn
am m
n+1
Ad esempio, trascurando il costo di giacenza ai depositi, esaminiamo il
seguente problema, tratto da Pezzella, Faggioli, Ricerca Operativa –
Problemi di gestione della Produzione, Pitagora Editrice.
Un’azienda deve trasportare i prodotti finiti dagli stabilimenti ai magazzini di distribuzione. Gli stabilimenti
sono situati a Houston, Casper e Titus e la loro produttività è tale da non poter inviare merce in quantità di
350, 250 e 300 unità rispettivamente. I magazzini sono situati a LA, Saint Louis, Indiana, Newark e Atlanta e
devono soddisfare rispettivamente una domanda di 200, 120, 230, 190, 150 unità. La rete di trasporto non
permette di collegare tutti gli stabilimenti a tutti i magazzini e i costi unitari di trasporto sono dati:
Da\A
Houston
LA
250
Saint Louis
180
Indiana
190
Casper
280
220
210
Titus
∞
∞
170
Q. richiesta
200
120
230
Determinare il piano di trasporti a costo minimo.
Il problema (P) è stato risolto con Lingo con il codice:
model:
sets:
depots/1..3/:availab;
markets/1..5/:demand;
dm(depots,markets):costs,x;
endsets
Newark
∞
∞
140
190
Atlanta
200
Q. disponibili
350
∞
250
160
150
300
data:
availab=350,250,300;
demand=200,120,230,190,150;
costs=200,180,190,30000,200,
280,220,210,30000,30000,
30000,30000,170,140,160; !gli infiniti sono mappati in 30000;
enddata
min=@sum(depots(i):@sum(markets(j):costs(i,j)*x(i,j)));
@for(depots(i):@sum(markets(j):x(i,j))<=availab(i));
@for(markets(j):@sum(depots(i):x(i,j))>=demand(j));
end
X( 1, 1)
200
X( 1, 2)
110
X( 1, 3)
0
X( 1, 4)
0
X( 1, 5)
40
X( 2, 1)
0
X( 2, 2)
10
X( 2, 3)
230
X( 2, 4)
0
X( 2, 5)
0
X( 3, 1)
0
X( 3, 2)
0
X( 3, 3)
0
X( 3, 4)
190
X( 3, 5)
110
250
200
150
da depot 3
da depot 2
100
da depot 1
50
0
1
2
3
4
5
La soluzione mostra come dal deposito 1 non si vada al mercato 4, dal 2 al 4 e al 5, dal 3 all’1 e al 2: 30000
è, in questo caso, una “buona approssimazione” di infinito.
Si osservi come la domanda totale sia di 890 unità contro una disponibilità di 900; il residuo di 10 resta non
spedito nel deposito 2. La prova di estensione del modello di trasporto consiste nel rendere piuttosto
costoso il deposito 2 per merce non spedita.
Il codice Lingo diviene:
model:
sets:
depots/1..3/:availab;
markets/1..6/:demand;
dm(depots,markets):costs,x;
endsets
data:
availab=350,250,300;
demand=200,120,230,190,150,10;
costs=200,180,190,30000,200,100,
280,220,210,30000,30000,500,
30000,30000,170,140,160,100; !gli infiniti sono mappati in 30000;
enddata
min=@sum(depots(i):@sum(markets(j):costs(i,j)*x(i,j)));
@for(depots(i):@sum(markets(j):x(i,j))<=availab(i));
@for(markets(j):@sum(depots(i):x(i,j))>=demand(j));
end
dove il mercato fittizio 6 ha una domanda di 10 e il deposito 2 ha un costo di stoccaggio di 500, a fronte di
un costo di stoccaggio di 100 degli altri 2 depositi. La soluzione cambia:
X( 1, 1)
200
X( 1, 2)
100
X( 1, 3)
0
X( 1, 4)
0
X( 1, 5)
40
X( 1, 6)
10
X( 2, 1)
0
X( 2, 2)
20
X( 2, 3)
230
X( 2, 4)
0
X( 2, 5)
0
X( 2, 6)
0
X( 3, 1)
0
X( 3, 2)
0
X( 3, 3)
0
X( 3, 4)
190
X( 3, 5)
110
X( 3, 6)
0
250
200
150
da 3
da 2
100
da 1
50
0
1
2
3
4
5
6
Nei fatti è solo il deposito 1 che mantiene il residuo (poiché è il solo a spedire al cliente fittizio 6).