:: Ricerca Operativa - PNL - 7 novembre 2007 ::
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(a2+b2) ]
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
I dati che abbiamo in mano sono solo le coordinate delle piazze, e il numero delle piazze:
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.
La funzione obiettivo è minimizzare la distanza dei tunnel secondari che vanno dalla nostra retta alle piazze di coordinate note. Quindi, devo
min SOMMAi 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:
Il qualcosa di cui stiamo parlando è l'equazione che il professore ci ha dato. Lui ha infatti scritto:
|ax0+by0+c| / sqrt(a2+b2)
Noi vogliamo il valore assoluto di a*xi + b*yi + c. Per ogni piazza, ci serve il valore assoluto di questa distanza, pertanto...
...introduciamo un'altra variabile ausiliaria, delta, che sarà indicizzata con il numero delle piazze:
Ora che abbiamo la variabile ausiliaria, facciamo così:
Per ogni i-esima piazza, deltai 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));
L'unico vincolo esistente è quello che serve per definire il delta; per il resto, le variabili sono libere di fare quello che vogliono.
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
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.
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.