|
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:
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:
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]]
|
|