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)
- costoPi (costo del pacco di tipo i=1..2)
- volMinPi (volume minimo del pacco di tipo i=1..2)
- volMaxPi (volume massimo del pacco di tipo i=1..2)
- pesMinPi (peso minimo del pacco di tipo i=1..2)
- pesMaxPi (peso massimo del pacco di tipo i=1..2)
- volOj (volume dell'oggetto j=1..11)
- pesOj (peso dell'oggetto j=1..11)
Variabili
- xijk (variabile binaria che mi indica se l'oggetto j è nel pacco k di tipo i)
- yik (variabile binaria che mi indica se il pacco k di tipo i è utilizzato)
Funzione obiettivo
min (somma)k yik * costoPi
Vincoli
- vincolo sul volume minimo dei pacchi di tipo i:
(somma)j xijk * volOj >= volMinPi * yik (per ogni pacco k)
- vincolo sul volume massimo dei pacchi di tipo i:
(somma)j xijk * volOj <= volMaxPi * yik (per ogni pacco k)
- vincolo sul peso minimo dei pacchi di tipo i:
(somma)j xijk * pesOj >= pesMinPi * yik (per ogni pacco k)
- vincolo sul peso massimo dei pacchi di tipo i:
(somma)j xijk * pesOj <= pesMaxPi * yik (per ogni pacco k)
- vincolo che imponga che ogni oggetto sia esattamente in un pacco:
(somma)i (somma)k xijk = 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
