Swappa :: Ricerca Operativa - PLI - Incendi

Torna alla pagina di Ricerca Operativa

 :: 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