Torna alla pagina di Ricerca Operativa
:: Ricerca Operativa - PLI - Cestini - 19.01.04 ::
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.
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
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
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.
! 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
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:
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:
Che in Lingo si traduce come:
@for(luoghi(i): @sum(fonti(j): y(i,j) * quantita(j)) <= capacita);
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)));