Empaquetado de rectángulos
From Wikipedia, the free encyclopedia
El empaquetado de rectángulos es un problema de empaquetado donde el objetivo es determinar si un conjunto determinado de rectángulos pequeños se puede colocar dentro de un polígono grande determinado, de modo que no se superpongan dos rectángulos pequeños. Se han estudiado distintas variantes de este problema.
En esta variante, hay varias unidades de un único rectángulo de tamaño (lxw) y un rectángulo de tamaño más grande (LxW). El objetivo es empaquetar tantos rectángulos pequeños como sea posible en el rectángulo grande sin superposición entre los rectángulos pequeños. Restricciones comunes del problema incluyen limitar la rotación de los rectángulos pequeños a múltiplos de 90° y exigir que cada rectángulo pequeño sea ortogonal con respecto al rectángulo grande.
Este problema tiene algunas aplicaciones, como la carga de cajas sobre pallets y, en concreto, la estiba de pulpa de celulosa. Como ejemplo de un resultado en este campo, es posible empaquetar 147 rectángulos pequeños de tamaño (137x95) en un rectángulo grande de tamaño (1600x1230).[1]
Empaquetar cuadrados idénticos en un polígono rectilíneo
Dado un polígono rectilíneo (cuyos lados se encuentran en ángulos rectos) R en el plano, un conjunto S de puntos en R y un conjunto de cuadrados idénticos, el objetivo es encontrar el mayor número de cuadrados no superpuestos que se pueden empaquetar en puntos de S.
Supóngase que, para cada punto p en S, se coloca un cuadrado centrado en p. Sea GS el grafo de intersección de estos cuadrados. Un embalaje cuadrado equivale a un conjunto independiente en GS. Encontrar el empaquetamiento cuadrado más grande es NP-difícil; se puede probar esto reduciendo la cuestión a un problema de satisfacibilidad booleana.[2]
Empaquetar diferentes rectángulos en un rectángulo determinado
En esta variante, los rectángulos pequeños pueden tener longitudes y anchuras variables y deben empaquetarse en un rectángulo grande determinado. El problema de decisión sobre si existe tal empaquetadura es NP-difícil. Esto se puede demostrar mediante su reducción a una 3-partición. Dada una instancia de 3 particiones con 3m enteros positivos: a1, ..., a3m, con una suma total de m T, se construyen 3 m rectángulos pequeños, todos con un ancho de 1, de modo que la longitud del rectángulo i sea ai + m. El rectángulo grande tiene un ancho m y un largo T + 3m. Cada solución para la instancia de 3 particiones induce un empaquetamiento de los rectángulos en m subconjuntos de modo que la longitud total en cada subconjunto sea exactamente T, de modo que encajen exactamente en el rectángulo grande. Por el contrario, en cualquier embalaje del rectángulo grande, no debe haber "agujeros", por lo que los rectángulos no deben girarse. Por lo tanto, el embalaje debe incluir exactamente m filas donde cada fila contenga rectángulos con una longitud total de exactamente T. Esto corresponde a una solución de la instancia de 3 particiones.[3][4]
Cuando existe una restricción adicional de que el embalaje debe ser exacto (sin desperdiciar espacio), los rectángulos pequeños se pueden girar solo en múltiplos de 90°. En este caso, el problema es de complejidad NP. Sin este requisito, los pequeños rectángulos se pueden girar en ángulos arbitrarios. En este caso más general, no está claro si el problema es de dificultad NP o no, ya que es mucho más difícil verificar una solución.[4]
