Swappa : Uni / Ricerca Operativa - PNL - Dispersione

Torna alla pagina di Ricerca Operativa

 :: Ricerca Operativa - PNL - Dispersione - 20.01.05 ::

Testo del problema

In un dato territorio si vogliono localizzare alcune infrastrutture “critiche” (depositi di munizioni, impianti chimici, fonti di rumore,...). Ciascuna di esse esercita un’influenza negativa su una superficie circolare di un dato raggio.
Si vuole localizzare le infrastrutture in modo da massimizzare la distanza minima che intercorre tra le loro aree di influenza.
In altri termini si vogliono localizzare nel piano alcuni cerchi in modo da massimizzare la distanza minima tra le loro circonferenze.
Formulare il problema, classificarlo e risolverlo con i dati del file DISPERS.TXT.

Dati

I cerchi sono 20.

Cerchio   1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20

Raggio   24 31 15  7 18 22 10  8 25 27 14 13 11 19  2  3  9  4  5 20

La superficie in cui possono essere localizzati i cerchi è circolare, 
con centro nel punto (0,0) e raggio 200.
I cerchi devono essere INTERAMENTE contenuti in tale superficie.

Formulazione del problema

Dati

cerchi = 20 (numero cerchi relativi alle infrastrutture)
raggio_i (raggio del cerchio i=1..20)
raggioTerr = 200 (raggio del cerchio che individua il territorio)

Variabili

Dobbiamo decidere dove localizzare le infrastrutture, quindi dobbiamo stabilire dove collocare i centri dei cerchi. Avremo bisogno di una variabile per coordinata:

x_i (coordinata X del centro del cerchio i)
y_i (coordinata Y del centro del cerchio i)

Le variabili sono libere, quindi anche negative.

Funzione obiettivo

Dobbiamo massimizzare la distanza minima tra le aree di influenza, quindi utilizziamo una variabile ausiliaria per rappresentare il minimo delle distanze:
max z

Vincoli

vincolo che impone che i cerchi delle infrastrutture siano interamente contenuti nella superficie del territorio. Dovremo calcolare la distanza euclidea tra il centro del cerchio i e quella del cerchio del territorio (quindi [(x_i - 0)² + (y_i - 0)²]^1/2), e imporre che sia minore o uguale alla differenza tra il raggio del territorio e quello del cerchio i. Omettendo di sottrarre per 0 otteniamo:
(x_i² + y_i²)^1/2 <= raggioTerr - raggio_i (per ogni cerchio i)
abbiamo detto che la variabile ausiliaria z è la distanza minima tra le aree di influenza. In generale per ottenere questa distanza dovremo sottrarre al "segmento che congiunge le origini di due cerchi" la somma dei loro raggi, ma dato che noi vogliamo il valore minimo scriveremo così:
[(x_i - x_j)² + (y_i - y_j)²]^1/2 - (raggio_i + raggio_j) >= z (per ogni cerchio i e j, con i<j)

Lighizzazione del problema

! esercizio: Dispersione;
model:

sets:
cerchi /1..20/: raggio,
		x, y; ! variabili;
endsets

data:
raggio = 24 31 15  7 18 22 10  8 25 27 14 13 11 19  2  3  9  4  5 20;
raggioTerr = 200;
enddata

! funzione obiettivo;
max = z;

! vincolo che impone che i cerchi siano interamente interni al territorio; 
@for(cerchi(i): (x(i)^2 + y(i)^2)^0.5 <= raggioTerr - raggio(i));

! vincolo per definire la distanza minima z; 
@for(cerchi(i): 
   @for(cerchi(j) | j #GT# i: 
      ((x(i)-x(j))^2 + (y(i)-y(j))^2)^0.5 - (raggio(i) + raggio(j)) >= d
   )
);

! definisco le variabili libere;
@for(cerchi(i): @free(x(i)));
@for(cerchi(i): @free(y(i)));

end

Torna alla pagina di Ricerca Operativa