Uni.RO-PLI-14set2005 History
Hide minor edits - Show changes to output
Added lines 1-107:
[[Torna alla pagina di Ricerca Operativa -> Ricerca Operativa]]
----
(:title Ricerca Operativa - PLI - Incendi - 14.09.05:)
%titolo%''':: Ricerca Operativa - PLI - Incendi - 14.09.05 ::'''
!!Testo del problema
Il tempo necessario per spegnere un incendio cresce col tempo, poiché l’incendio aumenta di dimensioni. Nel caso in cui diversi focolai di incendio vengano segnalati contemporaneamente e si abbia a disposizione una sola squadra antincendio, si pone il problema decisionale di scegliere l’ordine in cui spegnere gli incendi.\\
Una volta iniziate le operazioni di spegnimento di un incendio esse non possono essere interrotte prima che l’incendio sia stato spento completamente.\\
Si ipotizza che la relazione tra il tempo necessario per lo spegnimento e l’istante di inizio dello spegnimento sia la seguente: d(i) = a(i) + b(i)*r(i), dove d(i) è la durata delle operazioni di spegnimento dell’incendio i-esimo, r(i) è il ritardo, cioè la distanza in tempo tra l’istante in cui inizia l’incendio e l’istante in cui inizia lo spegnimento, ed infine a(i) e b(i) sono parametri caratteristici dell’incendio.\\
Si vuole minimizzare la durata complessiva delle operazioni di spegnimento, conoscendo per un dato insieme di incendi gli istanti di accensione ed i parametri caratteristici a e b.\\
Formulare il problema, classificarlo e risolverlo con i dati del file INCENDI.TXT. Discutere l’ottimalità e l’unicità della soluzione ottenuta.
!!!Dati
[@
Gli incendi sono 5.
I coefficienti che descrivono il tempo necessario a spegnere ogni
incendio sono i seguenti:
Incendio 1 2 3 4 5
a 5 8 10 9 3
b 0.1 0.3 0.2 0.5 0.4
accens. 0 0 2 0 4
L'ultima riga della tabella indica l'istante in cui inizia l'incendio.
@]
!!Formulazione del problema
!!!Dati
* '''inc = 5''' (numero di incendi in atto)
* '''par = 2''' (numero di parametri caratteristici)
* '''param'_ij_'''' (parametro j=1..2 dell'incendio i=1..5)
* '''temAcc'_i_'''' (istante di accensione dell'incendio i=1..5)
!!!Variabili
* '''x'_ik_'''' (indica se lo spegnimento dell'incendio i=1..5 precede quello dell'incendio k=1..5) (binaria)
* '''y'_i_'''' (istante di tempo in cui si inizia lo spegnimento dell'incendio i=1..5)
!!!Funzione obiettivo
Bisogna minimizzare la massima durata complessiva delle operazioni di spegnimento, quindi introduciamo la variabile ausiliaria z ma che poi definiremo nei vincoli:\\
'''min z'''
!!!Vincoli
Come prima cosa definiamo la variabile ausiliaria z introducendone una nuova: temFin'_i_', che indica l'istante di tempo in cui si conclude lo spegnimento dell'incendio i:\\
'''z >= temFin'_i_'''' (per ogni i)
Per definire temFin abbiamo bisogno di un'altra variabile ausiliaria: temIni'_i_', che indica l'istante di tempo in cui inizio lo spegnimento dell'incendio i:\\
'''temFin'_i_' = temIni'_i_' + (param'_i1_' + param'_i2_' * (temIni'_i_' – temAcc'_i_'))''' (per ogni i)\\
che si legge “istante in cui finisce lo spegnimento dell'incendio i = istante in cui inizia lo spegnimento di i + (primo parametro dell'incendio i + secondo parametro * (istante inizio spegnimento – istante accensione incendio))”
Ora bisogna imporre che l'istante di inizio spegnimento dell'incendio i sia maggiore o uguale all'istante di fine spegnimento dell'incendio k (posso dedicarmi a un solo incendio alla volta), a meno che k non preceda i:\\
'''temIni'_i_' >= temFin'_k_' – 10000 * x'_ik_''''
Perché abbiamo moltiplicato per 10000? Per rispondere a questa domanda dobbiamo prima spiegare perché abbiamo sottratto un valore a temFin'_k_', e cioè che bisogna tener conto dell'eventualità in cui l'incendio k preceda l'incendio i. Nel caso in cui x'_ik_' vale 0 (quindi se i non precede k) non c'è niente da spiegare: temIni'_i_' deve essere maggiore o uguale a temFin'_k_', ovvero prima di iniziare a spegnere l'incendio i dobbiamo aver finito con il k. Se invece x'_ik_' vale 1 significa che i precede k, e quindi che temIni'_i_' dovrà essere minore di temFin'_k_'! Ma se sottraiamo soltanto 1 a temFin'_k_' c'è il rischio che il risultato sia ancora troppo alto perché possa essere correttamente pesato nella valutazione complessiva di tutti gli incendi, quindi moltiplichiamo il tutto per 10000 (arbitrariamente), così che temIni'_i_' debba semplicemente essere maggiore o uguale a un numero negativo (vincolo molto meno stringente) e se la possa giocare alla pari con tutti gli altri incendi.
!!Linghizzazione del problema
[@
! esercizio: Incendi;
model:
sets:
incendi /1..5/: paramA, paramB, temIni, temAcc, temFin;
coppia (incendi,incendi): x;
endsets
data:
paramA = 5 8 10 9 3;
paramB = 0.1 0.3 0.2 0.5 0.4;
temAcc = 0 0 2 0 4;
enddata
! funzione obiettivo;
min = z;
! vincolo per definire la variabile ausiliaria z;
@for(incendi(i): z >= temFin(i));
! vincolo per definire la variabile ausiliaria temFin;
@for(incendi(i): temFin(i) = temIni(i) +
(paramA(i) + paramB(i)*(temIni(i)-temAcc(i))));
! vincolo per regolare la sequenza di incendi da affrontare;
@for(incendi(i):
@for(incendi(k) | k #ne# i:
temIni(i) >= temFin(k) - 10000 * x(i,k)
));
!vincolo per far sì che se i precede j non può valere il contrario, e viceversa;
@for(incendi(i):
@for(incendi(k) | k #ne# i:
x(i,k) + x(k,i) = 1
));
! definizione delle variabili binarie;
@for(coppia (i,k): @bin(x(i,k)));
end
@]
----
[[Torna alla pagina di Ricerca Operativa -> Ricerca Operativa]]
|
