:: Ricerca Operativa - PNL - 11 giugno 2008 ::
Testo
Sono dati N punti in uno spazio Euclideo in D dimensioni. Si vuole trovare il modo ottimo di partizionarli in P sottinsiemi. Il costo di una partizione è dato dalla somma dei costi di ogni sottinsieme di punti. Per ogni sottinsieme di punti il costo del sottinsieme è dato dalla somma dei quadrati delle distanze dei punti del sottinsieme da un altro punto, rappresentativo del sottinsieme, che deve essere posizionato opportunamente.
Formulare il problema, classificarlo e risolverlo con i dati del file SUMSQUARE.TXT. Discutere l’ottimalità della soluzione trovata.
I punti da partizionare sono 16, il numero di sottinsiemi è 3, lo spazio Euclideo considerato ha 4 dimensioni.
Tabella 1: Posizione dei punti dati
Punto Coord 1 Coord 2 Coord 3 Coord 4
1 25 61 110 -57
2 32 -63 90 50
3 28 25 -14 -34
4 -41 -30 56 -29
5 70 -81 -58 30
6 -97 17 -71 -68
7 103 12 -90 67
8 12 -31 135 65
9 -28 -26 85 21
10 33 -78 84 -92
11 -51 44 -23 -94
12 40 -79 -27 63
13 -99 80 39 -70
14 96 -11 -33 38
15 5 6 -12 -91
16 -40 48 140 100
Dati
- N = 16 : punti nello spazio
- P = 3 : sottinsiemi in cui partizionare lo spazio
- D = 4 : dimensioni dello spazio
- xik, i=1..N, j=1..D : coordinate (quattro valori ciascuna) di ogni punto
Variabili
Dobbiamo stabilire a quale sottinsieme un punto appartiene:
- yi,j, i=1..N, j=1..P : appartenenza dell'elemento i-esimo al sottinsieme p-esimo
È una variabile binaria, in cui 1 significa che l'elemento appartiene a quel sottinsieme, e 0 il contrario.
Ogni sottinsieme ha un suo rappresentante, che il prof chiama centroide per oscure ragioni. Dobbiamo anche piazzare questo rappresentante, ovvero dargli 4 coordinate:
- zi,j, i=1..P, j=1..D : coordinate del rappresentante del sottinsieme P
Si tratta di una variabile libera, perché le coordinate possono anche essere inferiori a 0.
Vincoli
Il vincolo è quello sull'appartenenza: un punto deve appartenere ad uno e un solo sottinsieme:
- SOMMA(j) y(i,j) = 1, per ogni i=1..P
Funzione obiettivo
Mmmm... il testo dice che voglio le partizioni di costo minimo.
Il costo di una partizione è la somma dei quadrati delle distanze dei punti dal centroide di quella partizione.
La distanza è la solita distanza, solo che viene calcolata in quattro dimensioni anziché 3.
Siccome voglio minimizzare il costo, allora è un min.
La scrivo direttamente in Lingo, che forse rende di più:
min = @sum(subset(j):
@sum(punti(i):
y(i,j) * @sum(dim(k): (x(i,k) - z(j,k))^2)
)
);
In particolare, la riga @sum(dim(k): (x(i,k) - z(j,k))^2) calcola la distanza per ogni dimensione, e fa la sommatoria di tutte queste distanze.
Let's go unda Lingo stick!
model:
sets:
punti /1..16/;
dim /1..4/;
coord (punti,dim): x; ! Coordinate quadridimensionali date in tabella;
subset /1..3/;
assegnamento(punti,subset): y;
centroide(subset,dim): z; ! Rappresentante;
endsets
data:
x = 25 61 110 -57
32 -63 90 50
28 25 -14 -34
-41 -30 56 -29
70 -81 -58 30
-97 17 -71 -68
103 12 -90 67
12 -31 135 65
-28 -26 85 21
33 -78 84 -92
-51 44 -23 -94
40 -79 -27 63
-99 80 39 -70
96 -11 -33 38
5 6 -12 -91
-40 48 140 100;
enddata
! Funzione obiettivo;
min = @sum(subset(j):
@sum(punti(i):
y(i,j) * @sum(dim(k): (x(i,k) - z(j,k))^2)
)
);
! Vincolo sull'appartenenza;
@for(punti(i): @sum(subset(j): y(i,j)) = 1);
@for(assegnamento(i,j): @bin(y(i,j))); ! Le y sono binarie;
@for(centroide(i,j): @free(z(i,j))); ! Le z sono libere;
end
Torna alla pagina di Ricerca Operativa
