Uni.RO-PLI-19gen2004 History
Hide minor edits - Show changes to output
Changed line 154 from:
[@min = @sum(luoghi(i): @sum(fonti(j): y(i,j) * tRagg(i,j))); to:
[@min = @sum(luoghi(i): @sum(fonti(j): y(i,j) * tRagg(i,j)));@]
Deleted line 13:
Deleted line 14:
Deleted line 15:
Deleted line 16:
Deleted line 17:
Deleted lines 19-20:
Deleted line 20:
Deleted line 21:
Deleted line 22:
Deleted line 23:
Deleted line 24:
Deleted line 25:
Deleted lines 27-28:
Deleted lines 29-30:
Deleted lines 31-32:
Deleted line 35:
Deleted line 36:
Deleted line 37:
Deleted line 38:
Deleted line 39:
Deleted line 40:
Deleted line 41:
Deleted lines 43-44:
Deleted lines 45-46:
Deleted line 48:
Deleted line 49:
Deleted line 50:
Deleted line 51:
Deleted lines 53-54:
Deleted lines 55-56:
Deleted line 56:
Added lines 1-196:
[[Torna alla pagina di Ricerca Operativa -> Ricerca Operativa]]
----
(:title Ricerca Operativa - PLI - Cestini - 19.01.04:)
%titolo%''':: 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)
* '''tRagg'_ij_'''' (tempo di raggiungimento del cestino posizionato nel luogo i=1..6 dalla fonte j=1..5) [secondi]
* '''quantita'_j_'''' (quantità pattume prodotto dalla fonte j=1..5) [kg/giorno]
!!!Variabili
* '''x'_i_'''' (variabile binaria che indica se nel luogo i=1..6 c'è il cestino)
* '''y'_ij_'''' (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_' x'_i_' = 4'''
* vincolo che associ ad ogni fonte un cestino:\\
'''(somma)'_i_' y'_ij_' = 1''' (per ogni j)
* vincolo che impone a una fonte di non buttare il pattume in un luogo in cui non c'è il cestino:\\
'''y'_ij_' <= x'_i_'''' (per ogni j)
In altre parole se la x'_i_' vale 0, nessuna fonte potrà avere y'_ij_' maggiore di 0 dato che non ci son cestini in cui buttare roba; se invece la x'_i_' vale 1 significa che lì c'è il cestino, quindi le y'_ij_' 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 >= y'_ij_' * tRagg'_ij_'''' (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_' y'_ij_' * quantita'_j_' <= 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_' y'_ij_' * tRagg'_ij_''''
Che in Lingo diventa:
[@min = @sum(luoghi(i): @sum(fonti(j): y(i,j) * tRagg(i,j)));
----
[[Torna alla pagina di Ricerca Operativa -> Ricerca Operativa]]
|
