Swappa :: Ricerca Operativa

 :: Ricerca Oeprativa - Robot ::

Testo del problema

Ci sono 6 robot, in grado di ruotare a 360°, e con un raggio di azione differente. Ciascun robot va collegato con tutti gli altri robot tramite cavi in fibra ottica. Sapendo che le aree operative dei robot non devono intersecarsi, occorre disporli in modo tale da minimizzare l'estensione dei cavi, che sono costosi.

Ecco i raggi di azione di ogni robot:

Risoluzione

Le variabili di questo problema sono le coordinate di ciascun robot. Avremo quindi due variabili indicizzate con 6 elementi ciascuna: x_i e y_i.

Il vincolo è che non devono sovrapporsi. Pertanto, la distanza tra i centri di due robot deve essere maggiore o uguale alla somma dei raggi operativi dei due robot. La distanza la si trova con il teorema di Pitagora.

C'è una cosa da far notare, a questo proposito. Quando si scrive questo vincolo, si deve combinare ciascun robot con ogni altro robot. Ma così facendo occorre stare attenti a non prendere in esame lo stesso robot, altrimenti il vincolo non sarà mai soddisfatto. Se non si tiene in considerazione questa cosa, il problema risulterà irrisolvibile.

Lo stesso principio va applicato alla funzione obiettivo, che è minimizzare la distanza totale dei cavi posati. La distanza è sempre quella tra i centri di tutte le coppie di robot, ma bisogna stare attenti perché il cavo che collega il robot 1 ed il robot 2, ad esempio, è lo stesso che collega il robot 2 al robot 1.

Codice LINGO

model:



SETS:
robot /1..6/: r, x, y;
coppie (robot, robot): d;
ENDSETS

DATA:
r = 120 80 100 70 45 120;
ENDDATA


!Funzione obiettivo: minimizzare la somma su tutte le coppie i,j;
! C'è il 1/2 davanti per via delle considerazioni viste sopra;
min = 1/2 * @sum(coppie(i,j): d(i,j));

!Vincoli: per ogni coppia i,j con i diverso da j la loro distanza deve essere
! maggiore o uguale alla somma dei raggi di ognuno dei due robot;

@for (coppie(i,j) | i #NE# j: d(i,j) >= r(i) + r(j));

!Adesso tiriamo in piedi le distanze;
@for(coppie(i,j): d(i,j) = ((x(i) - x(j))^2 + (y(i) - y(j))^2)^1/2);

end

Ottimo locale?

Eh sì, quando si risolve sto problema Lingo ci avvisa che l'ottimo trovato non è affatto globale, bensì locale. Questo viene dal fatto che l'algoritmo utilizzato è quello del gradiente, e pertanto non c'è garanzia di ottimo globale.

Lingo deciderà più o meno a caso da dove partire a mettere i robot. Se si potesse "obbligarlo" a partire da una certa posizione stabilita per ogni robot, sarebbe come farlo partire da una soluzione diversa da quella che decide lui arbitrariamente all'inizio.

Per obbligare Linho a fare questa cosa c'è un nuovo costrutto da imparare:

INIT:
! Li dispongo attorno ad un quadrato di lato 400, ma l'ultimo lo metto fuori;
x = 1000 200 -200 -200 0 1000;
y = 1000 -200 -200 200 0 1000;
ENDINIT

E' abbastanza intuitivo: si inizializzano le variabili scrivendole come fossero una matrice (e in effetti lo sono!).

Dobbiamo però notare che, pur inizializzando le variabili in questo modo, alla fine l'ottimo è sempre lo stesso:D Eh beh:)

Problema convesso?

Questo problema è concavo o convesso? Prima di lanciarci in astrusi ragionamenti matematici (affrontabili solo dopo aver studiato e capito la teoria, e quindi non ora:D), il prof ci ha suggerito un metodo più artigianale ma non per questo meno ragionevole.

Consideriamo due cerchi, tangenti in un punto. Le variabili in gioco sono quattro, ovvero le coordinate del centro di ciascuno di questi cerchi. Supponiamo di tenerne ferme tre, cioè teniamo ferme entrambe le coordinate di un centro, ma solo una delle coordinate dell'altro centro. Questo vuol dire tenere un cerchio fermo e permettere all'altro di muoversi solamente lungo un asse.

Notiamo subito che, da una posizione di tangenza, spostando il cerchio lungo quell'asse, si arriva all'intersezione, per poi ritornare ad una posizione di tangenza. Ricordando che il vincolo ci imponeva di non sovrapporre i cerchi, vuol dire che passiamo da una soluzione ammissibile ad una inammissibile e poi ancora ad una ammissibile: il problema è quindi concavo.

Torna alla pagina di Ricerca Operativa