cerca
Ricerca Operativa - PNL - 11 giugno 2008
modifica cronologia stampa login logout

Wiki

UniCrema


Materie per semestre

Materie per anno

Materie per laurea


Help

Uni.RO-PNL-11giugno2008 History

Hide minor edits - Show changes to output

Added line 67:
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.
Deleted line 7:
!!Dati
Changed lines 32-33 from:
to:
!!Dati
* N = 16 : punti nello spazio
* P = 3 : sottinsiemi in cui partizionare lo spazio
* D = 4 : dimensioni dello spazio
* x'_ik_', i=1..N, j=1..D : coordinate (quattro valori ciascuna) di ogni punto

!!Variabili
Dobbiamo stabilire a quale sottinsieme un punto appartiene:
* y'_i,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:
* z'_i,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)
)
);
@]


!!Let's go unda Lingo stick!
Changed lines 4-5 from:
!!...da sistemare...
to:
!!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.

!!Dati
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
@]
Added lines 1-60:
(:title Ricerca Operativa - PNL - 11 giugno 2008:)
%titolo%''':: Ricerca Operativa - PNL - 11 giugno 2008 ::'''

!!...da sistemare...

[@


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 -> Ricerca Operativa]]