Swappa :: Ricerca Operativa - PNL - Costi di trasporto

Torna alla pagina di Ricerca Operativa

 :: Ricerca Operativa - PNL - Costi di trasporto - 12.04.06 ::

Testo del problema

Si vuole risolvere il seguente problema di ottimizzazione relativo ai costi da sostenere per il trasporto di scorie pericolose da un dato insieme di impianti chimici che le producono ad un dato insieme di impianti di trattamento che le trasformano. E’ nota la quantità di scorie che deve essere rimossa da ogni impianto chimico ed è nota la capacità di ogni impianto di trattamento. La somma di tali capacità è uguale alla totale quantità di scorie prodotte dagli impianti chimici. E’ possibile effettuare il trasporto da qualunque impianto chimico a qualunque impianto di trattamento, ma tutte le operazioni di trasporto devono essere eseguite simultaneamente nello stesso giorno per motivi di sicurezza. Bisogna quindi predisporre un adeguato numero di convogli scortati dagli agenti di pubblica sicurezza. Ogni convoglio corrisponde ad una diversa coppia origine/destinazione tra cui si decide di eseguire un trasporto.
Esistono diverse ipotesi sui costi che potrebbero derivare dalle operazioni di trasporto.
Secondo un’ipotesi A trasportare grandi quantità di scorie insieme nello stesso convoglio aumenterebbe il rischio di incidente, provocando quindi una diseconomia di scala. Secondo questa ipotesi i costi per ogni coppia origine/destinazione sono definiti come costo(i,j) = a(j) * q(i,j) + b(i) / q(i,j dove q(i,j) indica la quantità trasportata dall’impianto chimico i all’impianto di trattamento j, mentre a(j) e b(i) sono coefficienti di costo che dipendono il primo dalla destinazione e il secondo dall’origine del viaggio.
Secondo un’ipotesi B il costo di trasporto su ogni tratta è invece da considerarsi direttamente proporzionale alla quantità trasportata su quella tratta secondo un coefficiente di proporzionalità c(i,j) diverso per ogni tratta.
Secondo un’ipotesi C il costo è soggetto ad economie di scala, cioè trasportare grandi quantità provoca un abbassamento del costo unitario di trasporto. Secondo questa ipotesi i costi di trasporto su ogni tratta sono dati da costo(i,j) = sqrt(d(j)*e(i)*q(i,j)) dove q(i,j) indica la quantità trasportata dall’impianto chimico i all’impianto di trattamento j, mentre d(j) ed e(i) sono coefficienti di costo che dipendono il primo dalla destinazione e il secondo dall’origine del viaggio. Infine secondo un’ipotesi D i costi dipenderebbero solo dal numero di convogli da utilizzare.
Si chiede di formulare e risolvere il problema di minimizzazione dei costi in ciascuna delle quattro ipotesi indicate, specificando per ciascuno dei modelli di programmazione matematica risultanti il tipo di modello e l’algoritmo usato per risolverlo e discutendo di conseguenza l’ottimalità della soluzione ottenuta in ciascuno dei quattro casi.
I dati sono contenuti nel file TRASPORTO.TXT.

Dati

Le origini sono 6, le destinazioni sono 8.

Tab.1: Costi con diseconomie di scala

Destin.  1  2  3  4  5  6  7  8
a       18 19 10 14 16 17 18 15

Origine  1  2  3  4  5  6
b       50 48 57 52 52 51

Tab.2: Costi proporzionali

c    1  2  3  4  5  6  7  8

1   10 12 14 16 15 20 22 24
2   13 17 15 13 11 14 18 20
3   12 20 24 25 13 18 19 23
4   15 18 19 23 25 28 29 14
5   15 28 16 16 29 29 25 21
6   25 10 10 14 10 27 29 20

Tab.3: Costi con economie di scala

Destin.  1  2  3  4  5  6  7  8
d        7  3  8  2  9  4  3  2

Origine  1  2  3  4  5  6
e        3  4  2  2  3  5

Tab.4: Domande ed offerte

Origine    1   2   3   4   5   6
offerta  240 320 500 210 600 330

Destin.   1   2   3   4   5   6   7   8
domanda 200  90 310 100 350 650 240 260

Formulazione del problema

In questo problema abbiamo quattro ipotesi, a cui ci riferiremo con le sigle: "hp A", "hp B", "hp C", "hp D".

Dati

orig = 6 (numero di origini)
dest = 8 (numero di destinazioni)
coeffA_j (hp A: coefficiente di costo che dipende dalla destinazione j=1..8)
coeffB_i (hp A: coefficiente di costo che dipende dall'origine i=1..6)
coeffC_ij (hp B: coefficiente di proporzionalità dei costi per ogni tratta che va dall'origine i=1..6 alla destinazione j=1..8)
coeffD_j (hp C: coefficiente di costo che dipende dalla destinazione j=1..8)
coeffE_i (hp C: coefficiente di costo che dipende dall'origine i=1..6)
offerta_i (offerta di scorie dall'origine i=1..6)
domanda_j (domanda di scorie dalla destinazione j=1..8)

Variabili

x_ij (quantità di scorie inviate dall'origine i alla destinazione j)

La variabile è continua e non negativa.

Funzione obiettivo

Elenchiamo le funzioni obiettivo delle varie ipotesi:

hp A:
min (somma)_i (somma)_j (coeffA_j * x_ij) + (coeffB_i / x_ij)
hp B:
min (somma)_i (somma)_j coeffC_ij * x_ij
hp C:
min (somma)_i (somma)_j (coeffD_j * coeffE_i * x_ij)^1/2
hp D. Richiede la definizione di una variabile ausiliaria binaria y_ij, che definiremo nei vincoli, e che indica se un convoglio percorre la tratta i-j oppure no:
min (somma)_i (somma)_j y_ij

Vincoli

vincolo che impone che la quantità di scorie inviate da ogni origine coincida con l'offerta:
(somma)_j x_ij = offerta_i (per ogni i)
vincolo che impone che la quantità di scorie ricevuta da ogni destinazione coincida con la domanda:
(somma)_i x_ij = domanda_j (per ogni j)
vincolo che definisce la variabile ausiliaria binaria y_ij legandola alla variabile x_ij:
1000 * y_ij >= x_ij (per ogni i e per ogni j)

Nell'ultimo vincolo perchè abbiamo moltiplicato proprio per 1000? Perché è un numero maggiore di qualsiasi valore possa assumere x_ij. Se infatti x_ij è pari a 0, il minimo valore di y_ij per essergli maggiore o uguale è 0; se invece x_ij è pari a una qualche cifra positiva (sicuramente minore di 1000), il minimo valore di y_ij per esergli maggiore o uguale è 1. Perché parliamo di “minimo valore”? Perché la funzione obiettivo legata a questa variabile (quella dell'hp D) chiede di minimizzare la somma delle y_ij.

Linghizzazione del problema

Nel seguente listato abbiamo quattro funzioni obiettivo corrispondenti alle quattro ipotesi. Ovviamente il problema può essere risolto solo in funzione di una di esse alla volta, quindi le altre andranno commentate.

! esercizio - Costi di trasporto;

model:

sets:
origini /1..6/: coeffB, coeffE, offerta;
destinazioni /1..8/: coeffA, coeffD, domanda;
tratta (origini,destinazioni): x, y, coeffC; 
! x è variabile continua non negativa;
! y è variabile binaria;
endsets

data:
coeffC = 	10 12 14 16 15 20 22 24
    		13 17 15 13 11 14 18 20
    		12 20 24 25 13 18 19 23
    		15 18 19 23 25 28 29 14
    		15 28 16 16 29 29 25 21
    		25 10 10 14 10 27 29 20;
coeffB = 50 48 57 52 52 51;
coeffA = 18 19 10 14 16 17 18 15;
coeffD =  7  3  8  2  9  4  3  2;
coeffE =  3  4  2  2  3  5;
offerta = 240 320 500 210 600 330;
domanda = 200  90 310 100 350 650 240 260;
enddata

! funzione obiettivo - hp A;
! min = @sum(tratta(i,j): coeffA(j) * x(i,j) + coeffB(i) / x(i,j)); ;

! funzione obiettivo - hp B;
! min = @sum(tratta(i,j): coeffC(i,j) * x(i,j)); ;

! funzione obiettivo - hp C;
! min = @sum(tratta(i,j): (coeffD(j) * coeffE(i) * x(i,j))^0.5); ;

! funzione obiettivo - hp D;
! min = @sum(tratta(i,j): y(i,j));;

! vincolo sulla quantità di scorie inviate;
@for(origini(i): @sum(destinazioni(j): x(i,j)) = offerta(i));

! vincolo sulla quantità di scorie ricevute;
@for(destinazioni(j): @sum(origini(i): x(i,j)) = domanda(j));

! dichiaro binaria la variabile ausiliaria y;
@for(tratta(i,j): @bin(y(i,j)));

! definisco la variabile ausiliaria y;
@for(tratta(i,j): 1000*y(i,j) >= x(i,j));

end

Torna alla pagina di Ricerca Operativa