cerca
Ricerca Operativa - PNL - 7 novembre 2007
modifica cronologia stampa login logout

Wiki

UniCrema


Materie per semestre

Materie per anno

Materie per laurea


Help

Uni.RO-PNL-7novembre2007 History

Hide minor edits - Show changes to output

Added lines 107-111:

!!!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.
Added lines 4-107:
!!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'^2^'+b'^2^') ]

[@
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'^2^'+b'^2^')

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.
Added lines 1-5:
(:title Ricerca Operativa - PNL - 7 novembre 2007:)
%titolo%''':: Ricerca Operativa - PNL - 7 novembre 2007 ::'''

----
[[Torna alla pagina di Ricerca Operativa -> Ricerca Operativa]]