Esercizio ricerca operativa
salve a tutti,
sono nuovo di questo forum.
mi è stato posto un quesito molto interessante di ottimizzazione. sono riuscito a risolverlo grazie a Matlab nel caso specifico, ma poi mi è stato chiesto di modellizzare il problema utilizzando meno di 300 tra variabili e vincoli.
vi espongo il problema:
ho una griglia 10x10 dove 20 caselle a caso sono occupate da 20 case.
io devo posizionare 2 antenne per aiutare queste case. ogni antenna può collegarsi a infinite case (ovvero teoricamente tutti le case potrebbero andare dalla stessa antenna).
il mio obiettivo è quello di minimizzare la somma delle distanze.
di conseguenza ogni casa andrà dall antenna piu vicina. la distanza considerata è quella euclidea.
vi espongo il mio ragionamento: per semplicità ho numerato le caselle da 1 a 100 in modo da non dover usare troppi indici.
ho pensato di utilizzare 2 variabili per le 2 antenne binarie.
Xi=1 se l antenna si trova nella casella i , 0 altrimenti
Yj uguale a sopra
cosi sono a 200 variabili
ho considerato le distanze Dij (distanza dalla casella i alla casella j) come dati.
ora la mia funzione obiettivo è min(sum(min(distanze dalle antenne)))
il problema è che non riesco a trovare un modo per esprimere la scelta della distanza minore tra le 2 possibili senza passare alla programmazione non lineare (non accetta).
infatti avevo pensato la sommatoria interna come sum(Dij*Xi*a+Dij*Yi*(1-a)) ma "a" diventava un altra variabile per dire la distanza minima delle due.
se avete consigli su come è possibile eliminare la non linearità sono ben accetti
grazie in anticipo
sono nuovo di questo forum.
mi è stato posto un quesito molto interessante di ottimizzazione. sono riuscito a risolverlo grazie a Matlab nel caso specifico, ma poi mi è stato chiesto di modellizzare il problema utilizzando meno di 300 tra variabili e vincoli.
vi espongo il problema:
ho una griglia 10x10 dove 20 caselle a caso sono occupate da 20 case.
io devo posizionare 2 antenne per aiutare queste case. ogni antenna può collegarsi a infinite case (ovvero teoricamente tutti le case potrebbero andare dalla stessa antenna).
il mio obiettivo è quello di minimizzare la somma delle distanze.
di conseguenza ogni casa andrà dall antenna piu vicina. la distanza considerata è quella euclidea.
vi espongo il mio ragionamento: per semplicità ho numerato le caselle da 1 a 100 in modo da non dover usare troppi indici.
ho pensato di utilizzare 2 variabili per le 2 antenne binarie.
Xi=1 se l antenna si trova nella casella i , 0 altrimenti
Yj uguale a sopra
cosi sono a 200 variabili
ho considerato le distanze Dij (distanza dalla casella i alla casella j) come dati.
ora la mia funzione obiettivo è min(sum(min(distanze dalle antenne)))
il problema è che non riesco a trovare un modo per esprimere la scelta della distanza minore tra le 2 possibili senza passare alla programmazione non lineare (non accetta).
infatti avevo pensato la sommatoria interna come sum(Dij*Xi*a+Dij*Yi*(1-a)) ma "a" diventava un altra variabile per dire la distanza minima delle due.
se avete consigli su come è possibile eliminare la non linearità sono ben accetti
grazie in anticipo
Risposte
Domanda, le antenne a cui puoi collegare le case sarebbero disposte nelle caselle rimaste vuote?!?
PS: Se ce la fai potresti scrivere le formule con il sistema messo a disposizione...si fa fatica a capire bene!
PS: Se ce la fai potresti scrivere le formule con il sistema messo a disposizione...si fa fatica a capire bene!
non è specificato ma credo che un antenna possa anche andare su una casa (di conseguenza la distanza da quella casa all antenna è 0).
non capisco cosa intendi per formule. provo a rispiegare il problema più schematicamente.
ho una griglia 10x10 con 20 caselle casuali occupate da case.
io devo posizionare 2 antenne in 2 caselle in modo che la somma delle distanze da ogni casa all antenna piu vicina sia minima. cioe cerco \(\ min \sum(min(distanza dalle antenne)) \)
le variabili che io ho identificato sono:
Xi={1 se l antenna si trova nella casella i
0 altrimenti
Yj={1 se l antenna si trova nella casella j
0 altrimenti
e sono 200 variabili.
con Dij ho invece considerato le costanti che indicano la distanza tra la casella i e quella j
la mia idea era \(\ min \sum(Dij*Xi*a+Dij*Yi*(1-a)) \) dove a è una variabile che mi dice quale delle due antenne è la piu vicina.
cosi però è non lineare
spero sia un po piu chiaro
non capisco cosa intendi per formule. provo a rispiegare il problema più schematicamente.
ho una griglia 10x10 con 20 caselle casuali occupate da case.
io devo posizionare 2 antenne in 2 caselle in modo che la somma delle distanze da ogni casa all antenna piu vicina sia minima. cioe cerco \(\ min \sum(min(distanza dalle antenne)) \)
le variabili che io ho identificato sono:
Xi={1 se l antenna si trova nella casella i
0 altrimenti
Yj={1 se l antenna si trova nella casella j
0 altrimenti
e sono 200 variabili.
con Dij ho invece considerato le costanti che indicano la distanza tra la casella i e quella j
la mia idea era \(\ min \sum(Dij*Xi*a+Dij*Yi*(1-a)) \) dove a è una variabile che mi dice quale delle due antenne è la piu vicina.
cosi però è non lineare
spero sia un po piu chiaro
Non sono nemmeno sicuro di aver capito bene il problema. Se ho capito bene i dati sono:
Dati: 100 caselle. 20 sono case. Nelle altre 80 ci si possono mettere delle antenne. matrice delle distanze tra tutte le posizioni della 100 caselle.
trovare: posizione delle due antenne
tale che: viene minimizzata la somma delle distanze tra le 20 case e le due antenne.
Se così fosse tu avresti una matrice:
$ D= ((d_(1,1),...,d_(1,100)), (.,.,.), (.,d_(i,j),.), (.,.,.),(d_(100,1),...,d_(100,100))) $
Che ti indica la distanza della casella $i$ dalla $j$. Ovviamente $d_(i,j)=0 $ se $i=j$.
Questa matrice ti da le distanze anche tra due case. Cosa che non serve (se le antenne possono stare solo altrove). Per questo se trovi la posizione delle case puoi estrarre dalla matrice precedente una nuova matrice:
$\tilde D= ((\tilde d_(1,1),...,\tilde d_(1,80)), (.,.,.), (.,\tilde d_(h,k),.), (.,.,.),(\tilde d_(20,1),...,\tilde d_(20,80)))$
Dove sulle righe hai la $text(h-esima)$ casa e sulle colonne hai la $text(k-esima)$ antenna. Dalle $100$ colonne di prima ora ne hai solo $80$ perchè sto considerando come se le antenne non potessero andare nelle posizioni delle case ma solo in quelle libere e quindi la matrice ti darebbe le distanze di ogni casa (la $text(h-esima)$ casa sta sulla riga $h$) dalle 80 antenne poste altrove.
In questo caso sto immaginando che ci siano gia 80 antenne (o meglio che si possano montare nelle 80 postazioni rimaste libere).
A questo punto considerando il vettore ad $80$ componenti $ x$ tale che $x_k=\{(1, text(se nella casella k c'è l'antenna)),(0, text(altrimenti)) :}$
Quindi scriverei la formulazione come:
$min \sum_{h=1}^20(sum_{k=1}^80 \tilde d_(h,k) x_k )$
$\sum_{k=1}^80 x_k=2$
$x in {0,1}^80$
In questo caso avresti $1$ vincolo e un vettore con la soluzione avente $80$ componenti.
Se invece l'antenna potesse stare anche su una casa. Individuate le 20 case ti rimane la matrice $\tilde tilde D$ avente stesso numero di righe della matrice $\tilde D$ ma con 100 colonne. Infatti in questo caso dovresti tenere in considerazione la distanza casa/casa perchè su una delle due ci potrebbe stare l'antenna. Inoltre andrebbero riscritti gli estremi della sommatoria nella f.o. e nel vincolo
Ovviamente non sono certo che sia giusto però è un mio ragionamento.
PS: Per "usare le formule" intendevo esattamente quello che hai fatto dopo. Infatti non capivo le sommatorie che avevi scritto.
PPS: Io sto studiando questi argomenti in questo periodo...quindi tieni in conto possibili errori (magari anche stupidi ed evidenti) che mi possono essere sfuggiti!
Dati: 100 caselle. 20 sono case. Nelle altre 80 ci si possono mettere delle antenne. matrice delle distanze tra tutte le posizioni della 100 caselle.
trovare: posizione delle due antenne
tale che: viene minimizzata la somma delle distanze tra le 20 case e le due antenne.
Se così fosse tu avresti una matrice:
$ D= ((d_(1,1),...,d_(1,100)), (.,.,.), (.,d_(i,j),.), (.,.,.),(d_(100,1),...,d_(100,100))) $
Che ti indica la distanza della casella $i$ dalla $j$. Ovviamente $d_(i,j)=0 $ se $i=j$.
Questa matrice ti da le distanze anche tra due case. Cosa che non serve (se le antenne possono stare solo altrove). Per questo se trovi la posizione delle case puoi estrarre dalla matrice precedente una nuova matrice:
$\tilde D= ((\tilde d_(1,1),...,\tilde d_(1,80)), (.,.,.), (.,\tilde d_(h,k),.), (.,.,.),(\tilde d_(20,1),...,\tilde d_(20,80)))$
Dove sulle righe hai la $text(h-esima)$ casa e sulle colonne hai la $text(k-esima)$ antenna. Dalle $100$ colonne di prima ora ne hai solo $80$ perchè sto considerando come se le antenne non potessero andare nelle posizioni delle case ma solo in quelle libere e quindi la matrice ti darebbe le distanze di ogni casa (la $text(h-esima)$ casa sta sulla riga $h$) dalle 80 antenne poste altrove.
In questo caso sto immaginando che ci siano gia 80 antenne (o meglio che si possano montare nelle 80 postazioni rimaste libere).
A questo punto considerando il vettore ad $80$ componenti $ x$ tale che $x_k=\{(1, text(se nella casella k c'è l'antenna)),(0, text(altrimenti)) :}$
Quindi scriverei la formulazione come:
$min \sum_{h=1}^20(sum_{k=1}^80 \tilde d_(h,k) x_k )$
$\sum_{k=1}^80 x_k=2$
$x in {0,1}^80$
In questo caso avresti $1$ vincolo e un vettore con la soluzione avente $80$ componenti.
Se invece l'antenna potesse stare anche su una casa. Individuate le 20 case ti rimane la matrice $\tilde tilde D$ avente stesso numero di righe della matrice $\tilde D$ ma con 100 colonne. Infatti in questo caso dovresti tenere in considerazione la distanza casa/casa perchè su una delle due ci potrebbe stare l'antenna. Inoltre andrebbero riscritti gli estremi della sommatoria nella f.o. e nel vincolo
Ovviamente non sono certo che sia giusto però è un mio ragionamento.
PS: Per "usare le formule" intendevo esattamente quello che hai fatto dopo. Infatti non capivo le sommatorie che avevi scritto.
PPS: Io sto studiando questi argomenti in questo periodo...quindi tieni in conto possibili errori (magari anche stupidi ed evidenti) che mi possono essere sfuggiti!
la posizione delle 20 case è fissa.. ho detto che è random perchè devo modellizzarlo ma a noi è nota.
la cosa che non capisco (cioe non capisco se l hai considerata, ma se ho capito bene i tuoi ragionamenti non l hai fatto) è che ogni casa va solamente da 1 antenna della due, non da entrambe.
altrimenti basterebbe trovare la casella migliore e metterne due nella stessa casella.
p.s. l idea dell unica matrice è piu sensata della mia di utilizzare 20 vettori per le 20 case per le distanze.
grazie per i suggerimenti
la cosa che non capisco (cioe non capisco se l hai considerata, ma se ho capito bene i tuoi ragionamenti non l hai fatto) è che ogni casa va solamente da 1 antenna della due, non da entrambe.
altrimenti basterebbe trovare la casella migliore e metterne due nella stessa casella.
p.s. l idea dell unica matrice è piu sensata della mia di utilizzare 20 vettori per le 20 case per le distanze.
grazie per i suggerimenti
Non avevo fatto caso che fosse richiesto che una casa fosse connessa ad una sola antenna!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo