Torna alla pagina di Ricerca Operativa
:: Ricerca Operativa - PLI - Cestini - 19.01.04 ::
Testo del problema
La raccolta differenziata nel dipartimento non è cosa facile: ci sono rifiuti sparsi qua e là. Il direttore del dipartimento ritiene che l'attuale disposizione dei cestini dei rifiuti sia poco razionale e incarica gli studenti del corso di Ricerca Operativa di studiare il problema. Dopo una breve indagine effettuata dagli studenti, essi hanno a disposizione i dati riguardanti le possibili locazioni dei cestini (che sono disponibili in numero limitato), le fonti di pattume, le quantità prodotte da ciascuna fonte e il tempo che ciascun utente deve impiegare per raggiungere il cestino dalla fonte di pattume in cui si trova. Si vogliono posizionare i cestini in modo ottimo per minimizzare il tempo massimo di conferimento del pattume.
Formulare il problema, classificarlo e risolverlo con i dati del file CESTINI.TXT.
Dati
Ci sono 5 fonti di pattume:
1: Piano docenti
2: Aule Nord
3: Aule Sud
4: Laboratori Didattici
5: Laboratori di Ricerca
Ci sono 6 possibili luoghi in cui localizzare i cestini:
1: Piano docenti
2: Zona macchine caffè
3: Ingresso bar lato Nord
4: Ingresso bar lato Sud
5: Biblioteca
6: Corridoio laboratori
I cestini disponibili sono 4.
=========================================================
Tabella 1: Tempo di raggiungimento dei cestini dalle fonti
(secondi)
Fonti 1 2 3 4 5
Luoghi
1 4 20 20 35 40
2 20 5 10 20 20
3 20 5 8 20 20
4 20 8 5 25 25
5 40 15 12 10 12
6 40 15 20 8 2
=========================================================
Tabella 2: Quantità di pattume prodotto (Kg/giorno)
1: 12
2: 8
3: 8
4: 15
5: 12
=========================================================
Capacita': 20 Kg
Formulazione del problema
Dati
- fonti = 5 (numero di fonti di pattume)
- luoghi = 6 (numero luoghi possibili in cui localizzare i cestini)
- cestini = 4 (numero cestini disponibili)
- tRaggij (tempo di raggiungimento del cestino posizionato nel luogo i=1..6 dalla fonte j=1..5) [secondi]
- quantitaj (quantità pattume prodotto dalla fonte j=1..5) [kg/giorno]
Variabili
- xi (variabile binaria che indica se nel luogo i=1..6 c'è il cestino)
- yij (variabile binaria che indica se la fonte j=1..5 deve buttare il pattume nel cestino posto nel luogo i=1..6)
Funzione obiettivo
Si vuole minimizzare il massimo tempo di raggiungimento di un cestino, quindi dovremo introdurre una variabile ausiliaria che definiremo meglio poi nei vincoli:
min z
Vincoli
- vincolo disponibilità cestini:
(somma)i xi = 4
- vincolo che associ ad ogni fonte un cestino:
(somma)i yij = 1 (per ogni j)
- vincolo che impone a una fonte di non buttare il pattume in un luogo in cui non c'è il cestino:
yij <= xi (per ogni j)
In altre parole se la xi vale 0, nessuna fonte potrà avere yij maggiore di 0 dato che non ci son cestini in cui buttare roba; se invece la xi vale 1 significa che lì c'è il cestino, quindi le yij delle varie fonti possono buttare o meno lì il pattume.
- vincolo per introdurre la variabile ausiliaria z, definita come il massimo tempo di raggiungimento di un cestino:
z >= yij * tRaggij (per ogni i e per ogni j)
Linghizzazione del problema
! esercizio: cestini;
model:
sets:
fonti /1..5/;
luoghi /1..6/: x;
associazioni(fonti, luoghi): tRagg,
y;
endsets
data:
tRagg = 4 20 20 20 40 40
20 5 5 8 15 15
20 10 8 5 12 20
35 20 20 25 10 8
40 20 20 25 12 2;
cestini = 4;
enddata
! funzione obiettivo;
min = z;
! vincolo disponibilità cestini;
@sum(luoghi(i): x(i)) = cestini;
! vincolo che associ ad ogni fonte un cestino;
@for(luoghi(i): @sum(fonti(j): y(i,j)) = 1);
! vincolo che impone alle fonti di buttare pattume dove c'è
un cestino;
@for(luoghi(i): @for(fonti(j): y(i,j) <= x(i)));
! vincolo per definire la variabile ausiliaria z;
@for(luoghi(i): @for(fonti(j): z >= tRagg(i,j) * y(i,j) ));
! definisco le variabili binarie;
@for(luoghi(i): @bin(x(i)));
@for(luoghi(i): @for(fonti(j): @bin(y(i,j))));
end
Altre domande
Determinare inoltre la capacità minima richiesta per ciascun cestino.
Per rispondere a questa domanda bisogna verificare quali sono le fonti associate ad ogni cestino, e quindi sommare le quantità di pattume prodotte da ognuna di esse. Quindi osservando il report della soluzione possiamo affermare che:
- nel cestino situato nel luogo 1 le fonti associate sono la 1, quindi guardando i dati la capacità minima dovrà essere di 12 kg/giorno
- nel cestino situato nel luogo 3 le fonti associate sono la 2 e la 3, quindi la capacità minima dovrà essere di 8 + 8 = 16 kg/giorno
- nel cestino situato nel luogo 5 non ci sono fonti associate
- nel cestino situato nel luogo 6 le fonti associate sono la 4 e la 5, quindi la capacità minima dovrà essere di 15 + 12 = 27 kg/giorno
Come andrebbe modificato il modello se la capacità dei cestini fosse nota a priori?
Se la capacità dei cestini fosse nota a priori, e in particolare come definito dai dati capacita = 20 [kg/giorno], allora bisogna aggiungere un nuovo vincolo al modello:
- vincolo sulle capacità massime dei cestini:
(somma)j yij * quantitaj <= capacita (per ogni i)
Che in Lingo si traduce come:
@for(luoghi(i): @sum(fonti(j): y(i,j) * quantita(j)) <= capacita);
Studiare poi il caso in cui si voglia minimizzare il tempo medio di conferimento dei rifiuti nei cestini.
Bisognerà cambiare la funzione obiettivo, sbarazzandoci della variabile ausiliaria z, e minimizzando al suo posto il tempo medio necessario per buttare i rifiuti nei cestini. In altre parole bisognerà minimizzare la media pesata dei tempi di conferimento, e quindi:
min (somma)i (somma)j yij * tRaggij
Che in Lingo diventa:
min = @sum(luoghi(i): @sum(fonti(j): y(i,j) * tRagg(i,j)));
Torna alla pagina di Ricerca Operativa
