Torna alla pagina di Ricerca Operativa
:: Ricerca Operativa - PLI - Spedizione urgente - 26.09.00 ::
Testo del problema
Il Dicastero della Protezione Civile deve affrontare un'emergenza a causa di un cataclisma occorso oltreoceano e sta preparando l'invio di materiale di primo soccorso, tende, attrezzi e medicinali. La spedizione deve avvenire per via aerea, per ovvi motivi di tempestività. Tuttavia esistono regolamenti molto rigidi sulla massima quantità di merce trasportabile sui velivoli in ogni viaggio, per motivi di sicurezza dei voli. In particolare sia il volume sia il peso delle merci spedite sono limitati da valori imposti per legge.
Per trasportare le merci in tempo utile, sono disponibili solo due voli. Ciò che non può essere trasportato su di essi dovrà viaggiare via nave con tempi molto superiori.
Il responsabile deve trovare il modo migliore di effettuare la spedizione ripartendo gli imballi sui due voli disponibili, in modo da minimizzare il numero di imballi che dovranno viaggiare via nave. A parità di numero di imballi spediti, egli deve anche minimizzare il costo complessivo delle spedizioni per via aerea.
I due voli hanno un costo fisso più un costo variabile proporzionale al peso e al volume della merce caricata.
I dati del problema sono nel file SPEDIZ.TXT.
Dati
Gli imballi da spedire hanno i seguenti valori di peso (Kg)
e volume (metri cubi):
Imballo Peso Volume
1 400 9
2 250 12
3 70 8
4 1000 20
5 550 15
6 810 25
7 320 15
8 125 26
9 480 18
10 225 4
11 250 3
12 400 23
I valori massimi di peso e volume ammessi sui due voli sono indicati
nella tabella seguente, insieme ai relativi costi fissi e variabili.
Volo Peso max Vol. max Costo fisso Costo var. Costo var.
[Kg] [mc] [Keuro] [Euro/Kg] [Euro/mc]
1 2900 90 2.0 8 2
2 1950 100 1.5 5 3
Formulazione del problema
Dati
- imb = 12 (numero di imballi da spedire)
- pesoi (peso dell'imballo i=1..12) [Kg]
- voli (volume dell'imballo i=1..12) [metri cubi]
- v = 2 (numero di voli disponibili)
- pmaxj (peso massimo ammesso sul volo j=1..2) [Kg]
- vmaxj (volume massimo ammesso sul volo j=1..2) [metri cubi]
- cfissij (costi fissi per volo j=1..2) [migliaia di €]
- cvarPj (costi variabili per volo j=1..2 collegati al peso) [€/Kg]
- cvarVj (costi variabili per volo j=1..2 collegati al volume) [€/metro cubo]
Variabili
- xij (indica se l'imballo i=1..12 viene spedito sul volo j=1..2) (binaria)
Funzione obiettivo
Gli obiettivi sono massimizzare il numero di imballi spediti per via aerea (1), e minimizzare i costi di spedizione (2):
(1) max (somma)i (somma)j xij
(2) min (somma)i (somma)j xij * (pesoi * cvarPj + voli * cvarVj)
Non possiamo considerare equivalenti le due funzioni obiettivo perché ciò che non viene spedito per via aerea viene inviato per nave, con costi molto maggiori. Questi costi però non ci sono dati, quindi dobbiamo introdurre delle penalità per gli imballi che viaggiano via mare; le uniche penalità che hanno senso sono quelle in termini monetari, ad esempio l'assegnamento di un costo fittizio ai trasporti marittimi molto più alto di quelli aerei. Riscriviamo allora la prima funzione obiettivo, rendendola un problema di minimizzazione degli imballi che non sono spediti per via aerea:
min (somma)i (1 - (somma)j xij)
...aggiungiamo a questa formulazione le penalità che abbiamo motivato prima (fissandole arbitrariamente a 100000):
min (somma)i penalita * (1 – (somma)j xij)
Ci ritroviamo quindi con due funzioni obiettivo di minimizzazione, che combineremo in questo modo:
min [(somma)i penalita * (1 – (somma)j xij)] +
+ [(somma)i (somma)j xij * (pesoi * cvarPj + voli * cvarVj)]
Vincoli
- vincolo che fa sì che l'imballo i possa essere spedito su uno solo dei voli:
(somma)j xij <= 1 (per ogni i)
- vincolo di capacità del volo j:
(somma)i xij * pesoi <= pmaxj (per ogni j)
- vincolo di volume del volo j:
(somma)i xij * voli <= vmaxj (per ogni j)
Linghizzazione del problema
! esercizio - Spedizione urgente;
model:
sets:
imballo /1..12/: peso, volume;
volo /1..2/: pesomax, volmax, cvarP, cvarV;
spedizione (imballo,volo): x;
endsets
data:
peso = 400 250 70 1000 550 810 320 125 480 225 250 400;
volume = 9 12 8 20 15 25 15 26 18 4 3 23;
pesomax = 2900 1950;
volmax = 90 100;
cvarP = 8 5;
cvarV = 2 3;
penalita = 100000;
enddata
! funzione obiettivo;
min = @sum(imballo(i): penalita * (1 - @sum(volo(j): x(i,j))))
+ @sum(spedizione(i,j): x(i,j)
* (peso(i) * cvarP(j) + volume(i) * cvarV(j)));
! vincolo per la spedizione dell'imballo su un unico volo;
@for(imballo(i): @sum(volo(j): x(i,j)) <= 1);
! vincolo di capacità del volo;
@for(volo(j): @sum(imballo(i): x(i,j) * peso(i)) <= pesomax(j));
! vincolo di volume del volo;
@for(volo(j): @sum(imballo(i): x(i,j) * volume(i)) <= volmax(j));
! dichiarazione variabile binaria x;
@for(spedizione(i,j): @bin(x(i,j)));
end
Torna alla pagina di Ricerca Operativa
