Uni.RO-PNL-12gen2009 History
Hide minor edits - Show changes to output
Changed line 48 from:
* ...sia dall'estremità "sinistra": to:
* ...sia dall'estremità "sinistra":\\
Changed line 44 from:
'''[(somma)'_j_' (y'_ij_' – y'_kj_')'^2^'] >= (rag'_i_' + rag'_k_')'^2^' \\ to:
'''[(somma)'_j_' (y'_ij_' – y'_kj_')'^2^'] >= (rag'_i_' + rag'_k_')'^2^'''' \\
Added lines 1-85:
[[Torna alla pagina di Ricerca Operativa -> Ricerca Operativa]]
----
(:title Ricerca Operativa - PNL - Palle inscatolate - 12.01.09:)
%titolo%''':: Ricerca Operativa - PNL - Palle inscatolate - 12.01.09 ::'''
!!Testo del problema
Un’azienda produttrice di addobbi natalizi produce palle colorate per gli alberi di Natale.\\
L’ufficio vendite ha studiato un kit di palle colorate di vari colori e dimensioni da vendere in un’unica scatola. Si tratta di progettare in modo ottimale la scatola, in modo che possa contenere tutto il kit e che occupi il minor volume possibile. Per motivi di facilità di trasporto, la scatola deve essere a forma di parallelepipedo.\\
Formulare il problema, classificarlo e risolverlo con i dati del file PALLE.TXT.
!!!Dati
[@
Il kit è così composto:
Tipo Colore Raggio Numero
Ciliegina Rosso 2 3
Classica Rosso 4 2
Candida Bianco 3 3
Palla di neve Bianco 4 4
Stellina Azzurro 2 3
Luminosa Trasparente 3 2
Il raggio è espresso in centimetri.
@]
!!Formulazione del problema
!!!Dati
* '''pal = 6''' (numero di tipi di palline che compongono il kit)
* '''rag'_i_'''' (raggio della pallina di tipo i=1..6) [cm]
* '''num'_i_'''' (quantità di palline di tipo i=1..6)
* '''dim = 3''' (numero di dimensioni in cui si estende la scatola, evidentemente 3 dato che viviamo in un mondo tridimensionale)
!!!Variabili
* '''x'_j_'''' (dimensioni della scatola) (con j = 1..3) [cm]
* '''y'_ij_'''' (coordinata della pallina i=1..6 nella dimensione j=1..3)
!!!Funzione obiettivo
Bisogna minimizzare il volume della scatola:\\
'''min x'_1_' * x'_2_' * x'_3_'''' [cm^3]
!!!Vincoli
* vincolo che imponga che le palline non siano sovrapposte, quindi che faccia in modo che la distanza tra i loro centri non sia inferiore alla somma dei loro raggi (questo garantisce la non sovrapposizione in tutte e tre le dimensioni). Considerando due palline alla volta, la prima con indice i e la seconda con indice k, avremo:\\
'''[(somma)'_j_' (y'_ij_' – y'_kj_')'^2^'] >= (rag'_i_' + rag'_k_')'^2^' \\
(per ogni i e per ogni k diversa da i)
Abbiamo bisogno poi di due vincoli che impongano che ogni pallina sia interamente contenuta nella scatola, quindi che la sua distanza dalle pareti sia maggiore uguale al raggio:
* ...sia dall'estremità "sinistra":
'''y'_ij_' >= rag'_i_'''' (per ogni i e per ogni j)
* ...che da quella "destra":\\
'''y'_ij_' <= x'_j_' – rag'_i_'''' (per ogni i e per ogni j)
!!Linghizzazione del problema
[@
! esercizio - Palle inscatolate;
model:
sets:
pallina /1..14/: rag;
dimensione /1..3/: x;
coordinata (pallina,dimensione): y;
endsets
data:
enddata
! funzione obiettivo;
min = x(1) * x(2) * x(3);
! vincoli di non-sovrapposizione tra palline;
@for(pallina(i):
@for(pallina(k) | k #GT# i:
@sum(dimensione(j): (y(i,j) - y(k,j))^2) >= (rag(i) + rag(k))^2
)
);
! vincoli di contenimento nella scatola;
@for (pallina(i): @for(dimensione(j): y(i,j) >= rag(i)) );
@for (pallina(i): @for(dimensione(j): y(i,j) <= x(j) - rag(i)));
end
@]
----
[[Torna alla pagina di Ricerca Operativa -> Ricerca Operativa]]
|
