Swappa :: Ricerca Operativa - PNL

 :: Ricerca Operativa - PNL - 7 novembre 2007 ::

Testo

Nel sottosuolo della città bisogna scavare un tunnel rettilineo per la nuova linea della metropolitana. Esso dovrà essere poi collegato tramite altri tunnel secondari alle uscite, collocate in alcune piazze già identificate, che ovviamente non sono tutte perfettamente allineate. Si vuole definire la posizione del tunnel in modo da minimizzare la lunghezza degli scavi dei tunnel secondari, cioè in modo da minimizzare la somma delle distanze tra il tunnel principale e le uscite.

Formulare il problema, classificarlo e risolverlo con i dati del file TUNNEL.TXT.
Discutere poi l’ottimalità della soluzione ottenuta.

[Suggerimento: la distanza di un punto (x0,y0) da una retta ax+by+c=0 è data da |ax0+by0+c| / sqrt(a²+b²) ]

Le piazze sono localizzate nel piano cartesiano nei punti seguenti:

Piazza   X   Y
   1   -10  14
   2    -8   7
   3    -5  10
   4    -3  10
   5     0   9
   6     2   8
   7     5   8
   8     8   7
   9     9   5
  10    11   6
  11    14   7
  12    16   5

Soluzione

Dati

I dati che abbiamo in mano sono solo le coordinate delle piazze, e il numero delle piazze:

N = 12 : numero delle piazze
coord_ij, i=1..12, j=1..2 : coordinata della piazza (ogni piazza ha due valori, la x e la y). L'unità di misura non credo che ci sia...

Variabili

Il problema ci chiede di identificare una retta. Una retta ha equazione ax + by + c. In partenza avrei messo tutte e 5 ste robe, cioè a, b, c, x e y, come variabili. Ma in realtà x e y non servono mai, si usano solo a, b e c, come spiegato nella formula per calcolare la distanza che il prof ci ha dato.

a, b, c: variabili libere (infatti una retta può essere inclinata come vogliamo, i suoi coefficienti possono essere < 0)

Funzione obiettivo

La funzione obiettivo è minimizzare la distanza dei tunnel secondari che vanno dalla nostra retta alle piazze di coordinate note. Quindi, devo

trovare la distanza tra ogni piazza e il tunnel
minimizzare la somma di queste distanza

min SOMMA_i distanza(tunnel, piazza(i)), per ogni i = 1..N

Notiamo anche che la distanza richiede un valore assoluto. Il trucco per avere un valore assoluto è questo: introdurre una funzione ausiliaria ed imporle questi vincoli:

delta > qualcosa
delta > -qualcosa

Il qualcosa di cui stiamo parlando è l'equazione che il professore ci ha dato. Lui ha infatti scritto:

|ax0+by0+c| / sqrt(a²+b²)

Noi vogliamo il valore assoluto di a*x_i + b*y_i + c. Per ogni piazza, ci serve il valore assoluto di questa distanza, pertanto...

Variabili strikes back!

...introduciamo un'altra variabile ausiliaria, delta, che sarà indicizzata con il numero delle piazze:

delta_i, i=1..N : distanza in valore assoluti dalla piazza i-esima al tunnel

Torniamo alla funzione obiettivo

Ora che abbiamo la variabile ausiliaria, facciamo così:
Per ogni i-esima piazza, delta_i deve essere il valore assoluto della prima parte dell'equazione della distanza.
La nostra funzione obiettivo diventa quindi:

min = @sum(piazza(i): delta(i) / sqrt(a'^2^'+b'^2^'));

@for(piazza(i): delta(i) > a*x(i) + b*y(i) + c);
@for(piazza(i): delta(i) > 0 - (a*x(i) + b*y(i) + c));

Vincoli

L'unico vincolo esistente è quello che serve per definire il delta; per il resto, le variabili sono libere di fare quello che vogliono.

Codice Lingo

model:

sets:
piazza /1..12/: x, y, delta;
retta /1..1/: a, b, c;
endsets

data:
x = -10 -8 -5 -3 0 2 5 8 9 11 14 16;
y = 14  7 10 10 9 8 8 7 5  6  7  5;

enddata

!Funzione obiettivo;
min = @sum(piazza(i): delta(i) / ((a(1))^2 + (b(1))^2)^0.5);

!Funzione ausiliaria delta per il valore assoluto;
@for(piazza(i): delta(i) > (a(1) * x(i) + b(1)*y(i) + c(1)));
@for(piazza(i): delta(i) > 0 - (a(1) * x(i) + b(1)*y(i) + c(1)));

! Dichiariamo libere le variabili;
@free(a(1));
@free(b(1));
@free(c(1));

end

Nota sul codice

Qui ho introdotto il set retta con le proprietà a, b e c. In realtà NON È affatto necessario, perché Lingo quello che non viene definito lo assume come variabile.

Discussione sull'ottimalità

Mmmm... dalla teoria, si sa che l'ottimo trovato di una roba non lineare è locale, e che questo locale coincide con il globale se la funzione è convessa. La domanda è quindi: la funzione è convessa?

La risposta è sì: la distanza di un punto da una retta variabile è una roba convessa: c'è un esatto punto che ha un minimo, e tutto il resto non lo è. Ho tante funzioni convesse, e la somma di funzioni convesse è a sua volta una funzione convessa. Quindi, il problema è convesso, e l'ottimo locale è anche globale.

Torna alla pagina di Ricerca Operativa