:: Ricerca Operativa - PNL - 11 giugno 2008 ::
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
Dobbiamo stabilire a quale sottinsieme un punto appartiene:
È 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:
Si tratta di una variabile libera, perché le coordinate possono anche essere inferiori a 0.
Il vincolo è quello sull'appartenenza: un punto deve appartenere ad uno e un solo sottinsieme:
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.
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