Swappa : Uni / Ricerca Operativa - PLI - Pacchi postali

Torna alla pagina di Ricerca Operativa

 :: Ricerca Operativa - PLI - Pacchi postali - 17.07.06 ::

Testo del problema

Per spedire oggetti per posta bisogna servirsi di apposite confezioni fornite dagli uffici postali. Ogni tipo di confezione ha un diverso costo di spedizione e deve essere riempito in modo tale da soddisfare dei vincoli sul peso e sul volume degli oggetti contenuti. Tali vincoli riguardano sia il valore massimo che il valore minimo del contenuto di ogni pacco.
Dato un insieme di oggetti da spedire si vuole organizzare la loro spedizione in modo da soddisfare tutti i vincoli imposti dal sistema postale, minimizzando i costi.
Formulare il problema, classificarlo e risolverlo con i dati del file PACCHI.TXT.

Dati

Sono disponibili due pacchi di due tipi diversi.
Gli oggetti da spedire sono 11.

======================================

Tabella 1: Costo e capacità dei tipi di pacco

Tipo  Costo  Volume  Volume   Peso   Peso
             minimo  massimo minimo massimo
 1    10000    0      150       0    1500
 2    15000  120     1000    1000    4000

======================================

Tabella 2: Volume e peso degli oggetti

Oggetto  Volume     Peso
  1        14        750
  2        13        520
  3        62        140
  4        28        910
  5        19        230
  6        20        250
  7        31        600
  8         4        315
  9        10        800
 10        15        320
 11        15        480

Formulazione del problema

Dati

tPacchi = 2 (numero di tipi di pacchi)
nPacchi = 2 (numero di pacchi)
oggetti = 11 (numero di oggetti da spedire)
costoP_i (costo del pacco di tipo i=1..2)
volMinP_i (volume minimo del pacco di tipo i=1..2)
volMaxP_i (volume massimo del pacco di tipo i=1..2)
pesMinP_i (peso minimo del pacco di tipo i=1..2)
pesMaxP_i (peso massimo del pacco di tipo i=1..2)
volO_j (volume dell'oggetto j=1..11)
pesO_j (peso dell'oggetto j=1..11)

Variabili

x_ijk (variabile binaria che mi indica se l'oggetto j è nel pacco k di tipo i)
y_ik (variabile binaria che mi indica se il pacco k di tipo i è utilizzato)

Funzione obiettivo

min (somma)_k y_ik * costoP_i

Vincoli

vincolo sul volume minimo dei pacchi di tipo i:
(somma)_j x_ijk * volO_j >= volMinP_i * y_ik (per ogni pacco k)
vincolo sul volume massimo dei pacchi di tipo i:
(somma)_j x_ijk * volO_j <= volMaxP_i * y_ik (per ogni pacco k)
vincolo sul peso minimo dei pacchi di tipo i:
(somma)_j x_ijk * pesO_j >= pesMinP_i * y_ik (per ogni pacco k)
vincolo sul peso massimo dei pacchi di tipo i:
(somma)_j x_ijk * pesO_j <= pesMaxP_i * y_ik (per ogni pacco k)
vincolo che imponga che ogni oggetto sia esattamente in un pacco:
(somma)_i (somma)_k x_ijk = 1 (per ogni oggetto j)

Linghizzazione del problema

model

sets:
tPacchi /1..2/: costoP, volMinP, volMaxP, pesMinP, pesMaxP;
nPacchi /1..2/;
pacco(tPacchi,nPacchi): y; ! variabile binaria;
oggetto /1..11/: volO, pesO;
assegnamento(tPacchi,oggetto,nPacchi): x; ! variabile binaria;
endsets

data:
costoP = 10000 15000;
volMinP =  0 120;
volMaxP = 150 1000;
pesMinP = 0 1000;
pesMaxP = 1500 4000;
volO = 14 13 62 28 19 20 31 4 10 15 15;
pesO = 750 520 140 910 230 250 600 315 800 320 480;
enddata

! funzione obiettivo;
min = @sum(pacco(i,k): y(i,k) * costoP(i));

! vincolo sul volume minimo;
@for(pacco(i,k): @sum(oggetto(j): x(i,j,k) * volO(j)) >= volMinP(i) * y(i,k));

! vincolo sul volume massimo;
@for(pacco(i,k): @sum(oggetto(j): x(i,j,k) * volO(j)) <= volMaxP(i) * y(i,k));

! vincolo sul peso minimo;
@for(pacco(i,k): @sum(oggetto(j): x(i,j,k) * pesO(j)) >= pesMinP(i) * y(i,k));

! vincolo sul peso massimo;
@for(pacco(i,k): @sum(oggetto(j): x(i,j,k) * pesO(j)) >= pesMinP(i) * y(i,k));

! vincolo sull'assegnamento unico dell'oggetto;
@for(oggetto(j): @sum(pacco(i,k): x(i,j,k)) = 1);

end

Torna alla pagina di Ricerca Operativa