cerca
Ricerca Operativa - PLI - Spedizione urgente - 26.09.00
modifica cronologia stampa login logout

Wiki

UniCrema


Materie per semestre

Materie per anno

Materie per laurea


Help

Ricerca Operativa - PLI - Spedizione urgente - 26.09.00

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