Swappa : Uni / Ricerca Operativa - PLI - Pronto intervento

Torna alla pagina di Ricerca Operativa

 :: Ricerca Operativa - PLI - Pronto intervento - 16.04.03 ::

Testo del problema

In seguito ad un allarme comunicato dai servizi segreti alcune squadre anti-terrorismo devono essere localizzate in città, per sorvegliare alcuni obiettivi sensibili. Poiché però le squadre disponibili sono in misura minore rispetto agli obiettivi, non tutti gli obiettivi possono essere controllati direttamente. Sono stati identificati alcuni luoghi ove localizzare le squadre di pronto intervento; alcuni di questi luoghi corrispondono con obiettivi sensibili, altri no.
Si vuole che ogni squadra sappia dove deve localizzarsi e quali sono gli obiettivi che le sono assegnati. La decisione deve essere presa in modo che in caso di attacco ad uno degli obiettivi sensibili il tempo di intervento della squadra incaricata sia il più breve possibile.
Perciò sono stati stimati i tempi di intervento da tutti i luoghi in cui può essere localizzata una squadra a tutti gli obiettivi sensibili.
Formulare il problema, classificarlo e risolverlo con i dati del file PRONTO.TXT

Dati

Ci sono 7 obiettivi sensibili e 3 squadre.
I luoghi dove localizzare le squadre sono 6.

=========================================

Tabella 1: Tempi di intervento (minuti)

   Obiettivi   1   2   3   4   5   6   7
Luoghi
  1            0   9   7  15   3   4   2
  2           12   0   2  14   8   4   3
  3            6   4   9   9  19  11  15
  4            5   1   8   0   6  12  17
  5            2  10  11  10   0   6  20
  6            8   7  15   5   5   0  12

=========================================

Formulazione del problema

Dati

ob = 7 (numero di obiettivi sensibili)
sq = 3 (numero di squadre)
lu = 6 (numero di luoghi identificati per localizzare le squadre)
tempi_ij (tempi di intervento dal luogo i=1..6 all'obiettivo j=1..7) [minuti]

Variabili

x_i (indica se nel luogo i=1..6 è posizionata una squadra) (binaria)
y_ij (indica l'assegnamento dell'obiettivo j=1..7 al luogo i=1..6) (binaria)

Funzione obiettivo

Bisogna minimizzare il massimo tempo di intervento possibile, cioè: min max tempi_ij
Introduciamo perciò una variabile ausiliaria z (che definiremo nei vincoli) che rappresenta il massimo dei tempi di intervento:
min z

Vincoli

vincolo sul massimo numero di squadre localizzate:
(somma)_i x_i = sq
vincolo che impedisce che si assegni un obiettivo j a un luogo i in cui non è stata posizionata una squadra:
y_ij <= x_i (per ogni i e per ogni j)
Che si legge: “non ci dev'essere nessun elemento della matrice di assegnamento che valga 1 se l'elemento con stesso indice i sul vettore x vale 0”
vincolo per imporre che ogni obiettivo j abbia esattamente un luogo i assegnato ad esso:
(somma)_i y_ij = 1 (per ogni j)
vincolo per definire la variabile ausiliaria z come il massimo dei tempi di intervento:
z >= tempi_ij * y_ij (per ogni i e per ogni j)

Linghizzazione del problema

! esercizio - Pronto soccorso;

model:

sets:
obiettivo /1..7/;
luogo /1..6/: x;
assegnamenti(luogo,obiettivo): tempi, y;
endsets

data:
tempi =	0     9    7   15    3    4    2
	12    0    2   14    8    4    3 
	6     4    9    9   19   11   15
	5     1    8    0    6   12   17
	2    10   11   10    0    6   20
	8     7   15    5    5    0   12;
squadre = 3;
enddata

! funzione obiettivo;
min = z;

! vincolo sul numero massimo di squadre localizzate;
@sum(luogo(i): x(i)) = squadre;

! vincolo sull'assegnamento di obiettivi a luoghi con squadre;
@for(assegnamenti(i,j): y(i,j) <= x(i));

! vincolo sull'assegnamento di ogni obiettivo ad un luogo;
@for(obiettivo(j): @sum(luogo(i):y(i,j)) = 1);

! vincolo per trovare il massimo tempo di intervento z;
@for(assegnamenti(i,j): z >= tempi(i,j) * y(i,j));

! dichiarazione variabili binarie x e y;
@for(assegnamenti(i,j): @bin(y(i,j)));
@for(luogo(i): @bin(x(i)));

end

Altre domande

Riformulare poi il problema nel caso in cui si vogliano anche distribuire in modo uniforme i compiti di sorveglianza tra le varie squadre, imponendo che il numero di obiettivi controllati da ciascuna squadra sia uguale o tutt’al più differisca di uno nel caso in cui il numero di obiettivi non sia esattamente multiplo del numero di squadre (Es: 3 squadre, 12 obiettivi -> 4 obiettivi per squadra; 3 squadre, 13 obiettivi -> 4 o 5 obiettivi per squadra).

Dobbiamo aggiungere nuovi vincoli al nostro modello per delimitare il numero minimo e massimo di obiettivi controllati da ciascuna squadra.
Il vincolo sul numero minimo è il seguente: @for(luogo(i): @sum(obiettivo(j): y(i,j)) >= (7/squadre-1) * x(i));

Il vincolo sul numero massimo è invece: @for(luogo(i): @sum(obiettivo(j): y(i,j)) <= (7/squadre+1) * x(i) );

Torna alla pagina di Ricerca Operativa