Uni.RO-PLI-16apr2009 History
Hide minor edits - Show changes to output
Changed line 94 from:
to:
Changed line 102 from:
to:
Deleted lines 123-131:
!!Altre domande
!!!Il numero di ambulanze disponibili per coprire il territorio può variare nel tempo, poiché alcune di esse vengono impegnate in servizi. Quando un’ambulanza viene richiesta per un servizio, si vuole mantenere massima la copertura del territorio ottenibile con le ambulanze rimanenti. Risolvere perciò il problema precedente per ogni numero di ambulanze da 1 fino al massimo disponibile. Supponendo di conoscere per quale frazione di tempo sono disponibili a ambulanze per ogni valore di a, calcolare qual è il corrispondente livello di copertura ottima che si può ottenere.
Nella variante (b) occorre moltiplicare le variabili per tutti gli scenari corrispondenti ai diversi numeri di ambulanze disponibili. Lo scenario con 0 ambulanze si può trascurare perché non dà alcun contributo alla funzione obiettivo. Gli scenari vengono risolti del tutto indipendentemente tra di loro: non c’è alcuna relazione tra le decisioni ottime nei diversi scenari. Il modello è nel file Ambulanze_b.lg4 e la soluzione ottima nel file Ambulanze_b.lgr.
!!!Si supponga infine che nel momento in cui un’ambulanza viene occupata da un servizio sia possibile rilocalizzare (istantaneamente) solo una delle ambulanze rimanenti e risolvere il problema precedente con questo ulteriore vincolo, discutendone l’effetto sulla copertura ottima.
Added lines 1-135:
[[Torna alla pagina di Ricerca Operativa -> Ricerca Operativa]]
----
(:title Ricerca Operativa - PLI - Ambulanze - 16.04.09:)
%titolo%''':: Ricerca Operativa - PLI - Ambulanze - 16.04.09 ::'''
!!Testo del problema
Un territorio che comprende un certo numero di centri abitati deve essere coperto da un dato numero di ambulanze per il pronto intervento. Le ambulanze possono sostare presso apposite rimesse dislocate nel territorio, in posizioni date. Da ciascuna di queste posizioni ogni ambulanza può coprire alcuni dei centri abitati, ma non tutti. Un centro abitato si intende coperto quando esiste almeno un’ambulanza in grado di raggiungerlo entro un dato tempo limite.\\
Conoscendo la popolazione residente in ciascuno dei centri abitati, localizzare le ambulanze in modo da massimizzare la copertura della popolazione.
!!!Dati
[@
I centri abitati sono 9, le postazioni disponibili sono 6,
le ambulanze sono 3.
Tab. 1: Popolazione [n. abitanti]
Paese Popolazione
1 250
2 450
3 1000
4 825
5 1100
6 940
7 120
8 280
9 480
Tab. 2: Tempo di intervento [minuti]
Paese Postazione
1 2 3 4 5 6
1 1 3 12 6 12 4
2 2 2 11 2 13 8
3 5 3 12 0 19 7
4 7 5 14 1 21 9
5 5 0 8 3 11 3
6 14 8 0 12 6 12
7 17 12 3 16 2 9
8 12 8 8 12 2 4
9 7 3 12 7 7 0
Tab. 3: Disponibilità ambulanze
N. Ambulanze Frazione di tempo
0 15%
1 20%
2 30%
3 35%
Tempo max di intervento = 8 minuti.
@]
!!Formulazione del problema
!!!Dati
* '''centri = 9''' (numero di centri abitati)
* '''post = 6''' (numero di postazioni disponibili)
* '''ambul = 3''' (numero ambulanze disponibili)
* '''popol'_i_'''' (popolazione del centro abitato i=1..9)
* '''tInt'_ij_'''' (tempo di intervento dalla postazione j=1..6 al centro abitato i=1..9) [minuti]
* '''dispAmb'_k_'''' (disponibilità ambulanza k=1..3 espressa come frazione di tempo) [%]
* '''maxInt = 8''' (tempo massimo di intervento) [minuti]
!!!Variabili
* '''x'_i_'''' (variabile binaria che indica se il centro abitato i è coperto o no)
* '''y'_j_'''' (variabile binaria che indica se nella postazione j c'è un'ambulanza)
!!!Funzione obiettivo
'''(somma)'_i_' max x'_i_' * popol'_i_''''
!!!Vincoli
* vincolo sulla disponibilità di ambulanze:\\
'''(somma)'_j_' y'_j_' = ambul'''
* vincolo che impone che le città coperte siano solo quelle a cui le ambulanze possono arrivare entro il tempo limite:\\
'''x'_i_' <= (somma)'_j_' y'_j_' "per cui tInt'_ij_' <= maxInt"'''\\
Non sapendo come altro scriverlo ho messo la condizione tra virgolette. In altre parole verranno conteggiate nella somma solo quelle postazioni che distano meno di maxInt dal centro abitato. In questo modo se non ce n'è nemmeno una, allora x'_i_' dovrà essere <= 0 (come è ovvio che sia), altrimenti potrà valere anche 1.
!!Linghizzazione del problema
[@
! esercizio: ambulanze;
model:
sets:
centro /1..9/: popol,
x;
postazione /1..6/: y;
intervento(centro,postazione): tInt;
endsets
data:
popol = 250 450 1000 825 1100 940 120 280 480;
tInt = 1 3 12 6 12 4
2 2 11 2 13 8
5 3 12 0 19 7
7 5 14 1 21 9
5 0 8 3 11 3
14 8 0 12 6 12
17 12 3 16 2 9
12 8 8 12 2 4
7 3 12 7 7 0;
ambul = 3;
maxInt = 8;
enddata
! funzione obiettivo;
max = @sum(centro(i): x(i) * popol(i));
! vincolo sulla disponibilità di ambulanze;
@sum(postazione(j): y(j)) = ambul;
! vincolo sulla copertura dei centri;
@for(centro(i):
x(i) <= @sum(postazione(j) | tInt(i,j) #LE# maxInt: y(j))
);
! definisco le variabili binarie;
@for(centro(i): @bin(x(i)));
@for(postazione(j): @bin(y(j)));
end
@]
!!Altre domande
!!!Il numero di ambulanze disponibili per coprire il territorio può variare nel tempo, poiché alcune di esse vengono impegnate in servizi. Quando un’ambulanza viene richiesta per un servizio, si vuole mantenere massima la copertura del territorio ottenibile con le ambulanze rimanenti. Risolvere perciò il problema precedente per ogni numero di ambulanze da 1 fino al massimo disponibile. Supponendo di conoscere per quale frazione di tempo sono disponibili a ambulanze per ogni valore di a, calcolare qual è il corrispondente livello di copertura ottima che si può ottenere.
Nella variante (b) occorre moltiplicare le variabili per tutti gli scenari corrispondenti ai diversi numeri di ambulanze disponibili. Lo scenario con 0 ambulanze si può trascurare perché non dà alcun contributo alla funzione obiettivo. Gli scenari vengono risolti del tutto indipendentemente tra di loro: non c’è alcuna relazione tra le decisioni ottime nei diversi scenari. Il modello è nel file Ambulanze_b.lg4 e la soluzione ottima nel file Ambulanze_b.lgr.
!!!Si supponga infine che nel momento in cui un’ambulanza viene occupata da un servizio sia possibile rilocalizzare (istantaneamente) solo una delle ambulanze rimanenti e risolvere il problema precedente con questo ulteriore vincolo, discutendone l’effetto sulla copertura ottima.
----
[[Torna alla pagina di Ricerca Operativa -> Ricerca Operativa]]
|
