Swappa : Uni / Ricerca Operativa - PNL - Palle inscatolate

Torna alla pagina di Ricerca Operativa

 :: 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₁ * x₂ * x₃ [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)²] >= (rag_i + rag_k)²
(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