Combinaciones aleatorias 2

Gracias por tu interés. Me gustaría enviarte un archivo para poder plantearte mejor el caso. Partimos de barras de 12 y 12.8 m. Y tenemos que cortar un surtido de distintas medidas, por ejemplo: 20 de 4.00,2 de 4.80,3 de 5.00, 4 de 2.65, ... Hay que buscar combinaciones para que sobre el menor recorte posible.
Mi e-mail: [email protected]
1

1 respuesta

Respuesta
1
Es un problema jodido. Es parecido al de la mochila, por lo que hay que buscar todas las combinaciones con la ayuda de un ordenador, que seleccione la mejor opción.
El número de combinaciones es también problemático de calcular. Pero las combinaciones en si se pueden calcular exhaustivamente:
Llamare corte a una barra de las del surtido a conseguir y barras a las enteras. Cuando se corta una barra, se obtiene un corte y sobra un resto. Este resto se puede utilizar para el siguiente corte o bien reservarlo para otro corte al que se ajuste mejor. Por lo tanto, hay dos opciones para el segundo corte. Si elegimos cortar una barra entera, entonces tendremos otro resto: cortar de uno de los restos o de una barra entera serían las posibilidades para el tercer corte. Si elegimos un corte también obtendremos un corte y un resto. Luego siempre hay las siguientes opciones: los restos y utilizar una barra entera. Por supuesto, cada vez que obtengamos un resto menor que la longitud del corte más corto lo desechamos.
Hay que conseguir todas las posibles secuencias de elecciones. Mediante backtraching se pueden conseguir. Hya que ir guardando la solucino mejor encontrada hasta el momento y al final imprimirla en pantalla. Una cosa más: primero se cortan todas las de 4.00, luego las de 4.80, etc. no se puede alterar la secuencia en cualquier caso. Si no, se repetirían combinaciones.
Veo que has encarrilado el asunto, otro compañero me habla de "SOLVER". Con mis conocimientos yo no puedo conseguir la solución. Me gustaría poder mandarte el caso práctico por mail. [email protected]
En la práctica vamos detectando manualmente las combinaciones optimas y van quedando los remates para el final. Quizás se podría solucionar en dos fases, aceptando menos y más recorte respectivamente. No se si tienes claro que partimos de dos medidas de barra para las posibilidades de cálculo.
Gracias de antemano.
Eduardo.
Sí, hay dos medidas, es verdad... pero no cambia mucho lo que te he dicho.
Lo mejor es que te muestre un ejemplo. A partir de él es fácil que un programador al que se lo pidas te solucione el problema.
Cortemos 2 de 4.00,1 de 5.00, y 1 de 2.65. Esto lo denotaré por: [2x4 1x5 1x2.65] Denotaré las barras disponibles por <ix12, ix12.8>, donde i significa que hay infinitas barras de esa longitud. Una decisión de hacer obtener una barra de 4 m de una barra de 9 m la denotaré por (4,9). De esta forma se genera un árbol de combinaciones como el que sigue. Se sigue el orden de [2x4 1x5 1x2.65] para los cortes, como ya dije. Luego la primera decisión es si la de 4m la cortamos de 12 o de 12.8.
[2x4 1x5 1x2.65] <ix12 ix12.8>
--(4,12)--> [1x4 1x5 1x2.65] <ix12 ix12.8 1x8>
----(4,12)----> [1x5 1x2.65] <ix12 ix12.8 2x8>
--------(5,12)--------> [1x2.65] <ix12 ix12.8 1x7 2x8>
----------------(2.65,12)----------------> [] <sobrantes: 1x7 2x8 1x9.35 = 32.35>
----------------(2.65,12.8)----------------> [] <sobrantes: 1x7 2x8 1x10.15 = 33.15>
----------------(2.65,7)----------------> [] <sobrantes: 1x4.35 2x8 = 20.35>
----------------(2.65,8)----------------> [] <sobrantes: 1x5.35 1x7 1x8 = 20.35>
--------(5,12.8)--------> [1x2.65] <ix12 ix12.8 1x7.8 2x8>
----------------(2.65,12)----------------> [] <sobrantes: 1x7.8 2x8 1x9.35 = 33.15>
----------------(2.65,12.8)----------------> [] <sobrantes: 1x7.8 2x8 1x10.15 = 33.95>
----------------(2.65,7.8)----------------> [] <sobrantes: 1x5.15 2x8 = 21.15>
----------------(2.65,8)----------------> [] <sobrantes: 1x5.35 1x7.8 1x8 = 21.15>
--------(5,8)--------> [1x2.65] <ix12 ix12.8 1x3 1x8>
----------------(2.65,12)----------------> [] <sobrantes: 1x3 1x8 1x9.35 = 20.35>
----------------(2.65,12.8)----------------> [] <sobrantes: 1x3 1x8 1x10.15 = 21.15>
----------------(2.65,3)----------------> [] <sobrantes: 1x0.35 1x8 = 8.35>
----------------(2.65,8)----------------> [] <sobrantes: 1x3 1x5.35 = 8.35>
----(4,12.8)----> [1x5 1x2.65] <ix12 ix12.8 1x8 1x8.8>
--------(5,12)--------> [1x2.65] <ix12 ix12.8 1x7 1x8 1x8.8>
----------------(2.65,12)----------------> [] <sobrantes: 1x7 1x8 1x8.8 1x9.35= 33.15>
----------------(2.65,12.8)----------------> [] <sobrantes: 1x7 1x8 1x8.8 1x10.15 = 33.95>
----------------(2.65,7)----------------> [] <sobrantes: 1x4.35 1x8 1x8.8 = 21.15>
----------------(2.65,8)----------------> [] <sobrantes: 1x5.35 1x7 1x8.8 = 21.15>
----------------(2.65,8.8)----------------> [] <sobrantes: 1x6.15 1x7 1x8 = 21.15>
--------(5,12.8)--------> [1x2.65] <ix12 ix12.8 1x7.8 1x8 1x8.8>
----------------(2.65,12)----------------> [] <sobrantes: 1x7.8 1x8 1x8.8 1x9.35= 33.95>
----------------(2.65,12.8)----------------> [] <sobrantes: 1x7.8 1x8 1x8.8 1x10.15 = 34.75>
----------------(2.65,7.8)----------------> [] <sobrantes: 1x5.15 1x8 1x8.8 = 21.95>
----------------(2.65,8)----------------> [] <sobrantes: 1x5.35 1x7.8 1x8.8 = 21.95>
----------------(2.65,8.8)----------------> [] <sobrantes: 1x6.15 1x7.8 1x8 = 21.95>
--------(5,8)--------> [1x2.65] <ix12 ix12.8 1x3 1x8.8>
----------------(2.65,12)----------------> [] <sobrantes: 1x3 1x8.8 1x9.35 = 21.15>
----------------(2.65,12.8)----------------> [] <sobrantes: 1x3 1x8.8 1x10.15 = 21.95>
----------------(2.65,3)----------------> [] <sobrantes: 1x0.35 1x8.8 = 9.15>
----------------(2.65,8.8)----------------> [] <sobrantes: 1x3 1x6.15 = 9.15>
--------(5,8.8)--------> [1x2.65] <ix12 ix12.8 1x3.8 1x8>
----------------(2.65,12)----------------> [] <sobrantes: 1x3.8 1x8 1x9.35 = 21.15>
----------------(2.65,12.8)----------------> [] <sobrantes: 1x3.8 1x8 1x10.15 = 21.95>
----------------(2.65,3.8)----------------> [] <sobrantes: 1x1.15 1x8 = 9.15>
----------------(2.65,8)----------------> [] <sobrantes: 1x3.8 1x5.35 = 9.15>
----(4,8)----> [1x5 1x2.65] <ix12 ix12.8 1x4>
--------(5,12)--------> [1x2.65] <ix12 ix12.8 1x7 1x4>
-----------------(2.65,12)----------------> [] <sobrantes: 1x7 1x4 1x9.35 = 20.35>
----------------(2.65,12.8)----------------> [] <sobrantes: 1x7 1x4 1x10.15 = 21.15>
----------------(2.65,7)----------------> [] <sobrantes: 1x4 1x4.35 = 8.35>
----------------(2.65,4)----------------> [] <sobrantes: 1x1.35 1x7 = 8.35>
-------(5,12.8)--------> [1x2.65] <ix12 ix12.8 1x7.8 1x4>
----------------(2.65,12)----------------> [] <sobrantes: 1x3 1x8 1x9.35 = 20.35>
----------------(2.65,12.8)----------------> [] <sobrantes: 1x3 1x8 1x10.15 = 21.15>
----------------(2.65,3)----------------> [] <sobrantes: 1x0.35 1x8 = 8.35>
----------------(2.65,8)----------------> [] <sobrantes: 1x3 1x5.35 = 8.35>
--(4,12.8)--> [1x4 1x5 1x2.65] <ix12 ix12.8 1x8.8>
----(4,12)----> [1x5 1x2.65] <ix12 ix12.8 1x8 1x8.8>
--------(5,12)--------> [1x2.65] <ix12 ix12.8 1x7 1x8 1x8.8>
----------------(2.65,12)----------------> [] <sobrantes: 1x7 1x8 1x8.8 1x9.35 = 33.15>
----------------(2.65,12.8)----------------> [] <sobrantes: 1x7 1x8 1x8.8 1x10.15 = 33.15>
----------------(2.65,7)----------------> [] <sobrantes: 1x8 1x8.8 1x4.35 = 21.15>
----------------(2.65,8)----------------> [] <sobrantes: 1x7 1x8.8 1x5.35 = 21.15>
----------------(2.65,8.8)----------------> [] <sobrantes: 1x7 1x8 1x6.15 = 21.15>
--------(5,12.8)--------> [1x2.65] <ix12 ix12.8 1x7.8 1x8 1x8.8>
----------------(2.65,12)----------------> [] <sobrantes: 1x7.8 1x8 1x8.8 1x9.35 = 20.35>
----------------(2.65,12.8)----------------> [] <sobrantes: 1x7.8 1x8 1x8.8 1x10.15 = 21.15>
----------------(2.65,7.8)----------------> [] <sobrantes: 1x5.15 1x8 1x8.8 = 21.95>
----------------(2.65,8)----------------> [] <sobrantes: 1x5.35 1x7.8 1x8.8 = 21.95>
----------------(2.65,8.8)----------------> [] <sobrantes: 1x6.15 1x7.8 1x8 = 21.95>
--------(5,8)--------> [1x2.65] <ix12 ix12.8 1x3 1x8.8>
----------------(2.65,12)----------------> [] <sobrantes: 1x3 1x8.8 1x9.35 = 21.15>
----------------(2.65,12.8)----------------> [] <sobrantes: 1x3 1x8.8 1x10.15 = 21.15>
----------------(2.65,3)----------------> [] <sobrantes: 1x0.35 1x8.8 = 9.15>
----------------(2.65,8.8)----------------> [] <sobrantes: 1x3 1x6.15 = 9.15>
--------(5,8.8)--------> [1x2.65] <ix12 ix12.8 1x3.8 1x8>
----------------(2.65,12)----------------> [] <sobrantes: 1x3.8 1x8 1x9.35 = 21.15>
----------------(2.65,12.8)----------------> [] <sobrantes: 1x3.8 1x8 1x10.15 = 21.95>
----------------(2.65,3.8)----------------> [] <sobrantes: 1x1.15 1x8 = 9.15>
----------------(2.65,8)----------------> [] <sobrantes: 1x3.8 1x5.35 = 9.15>
----(4,12.8)----> [1x5 1x2.65] <ix12 ix12.8 2x8.8>
--------(5,12)--------> [1x2.65] <ix12 ix12.8 1x7 2x8.8>
----------------(2.65,12)----------------> [] <sobrantes: 1x7 2x8.8 1x9.35 = 33.95>
----------------(2.65,12.8)----------------> [] <sobrantes: 1x7 2x8.8 1x10.15 = 34.75>
----------------(2.65,7)----------------> [] <sobrantes: 1x4.35 2x8.8 = 21.95>
----------------(2.65,8.8)----------------> [] <sobrantes: 1x6.15 1x7 1x8.8 = 21.95>
--------(5,12.8)--------> [1x2.65] <ix12 ix12.8 1x7.8 2x8.8>
----------------(2.65,12)----------------> [] <sobrantes: 1x7.8 2x8.8 1x9.35 = 34.75>
----------------(2.65,12.8)----------------> [] <sobrantes: 1x7.8 2x8.8 1x10.15 = 35.55>
----------------(2.65,7.8)----------------> [] <sobrantes: 1x5.15 2x8.8 = 22.75>
----------------(2.65,8.8)----------------> [] <sobrantes: 1x6.15 1x7.8 1x8.8 = 22.75>
--------(5,8.8)--------> [1x2.65] <ix12 ix12.8 1x3.8 1x8.8>
----------------(2.65,12)----------------> [] <sobrantes: 1x3.8 1x8.8 1x9.35 = 21.95>
----------------(2.65,12.8)----------------> [] <sobrantes: 1x3.8 1x8.8 1x10.15 = 22.75>
----------------(2.65,3.8)----------------> [] <sobrantes: 1x1.15 1x8.8 = 9.95>
----------------(2.65,8.8)----------------> [] <sobrantes: 1x5.15 1x3.8 = 9.95>
----(4,8.8)----> [1x5 1x2.65] <ix12 ix12.8 1x4.8>
--------(5,12)--------> [1x2.65] <ix12 ix12.8 1x7 1x4.8>
----------------(2.65,12)----------------> [] <sobrantes: 1x7 1x4.8 1x9.35 = 21.15>
----------------(2.65,12.8)----------------> [] <sobrantes: 1x7 1x4.8 1x10.15 = 21.95>
----------------(2.65,7)----------------> [] <sobrantes: 1x4.35 1x4.8 = 9.15>
----------------(2.65,4.8)----------------> [] <sobrantes: 1x2.15 1x7 = 9.15>
--------(5,12.8)--------> [1x2.65] <ix12 ix12.8 1x7.8 1x4.8>
----------------(2.65,12)----------------> [] <sobrantes: 1x7.8 1x4.8 1x9.35 = 21.95>
----------------(2.65,12.8)----------------> [] <sobrantes: 1x7.8 1x4.8 1x10.15 = 22.75>
----------------(2.65,7.8)----------------> [] <sobrantes: 1x5.15 1x4.8 = 9.95>
----------------(2.65,4.8)----------------> [] <sobrantes: 1x2.15 1x7.8 = 9.95>
Vemos que hay varias soluciones optimas posibles. Una de ellas es la secuencia de cortes siguiente: (4,12), (4,12), (5,8), (2.65,3), es decir cortar dos de 4 de dos barras de 12 y luego cortar 5 de los 8 restantes de una y cortar 2.65 de los 3 restantes, quedando unos restos de 8.35
Si no lo ves bien cortalo y pégalo en un editor más ancho.
Gracias por tu colaboración. He encontrado un programa que hace la optimización de corte. Si te interesa es 1D-Nest, lo puedes encontrar en google. Eduardo

Añade tu respuesta

Haz clic para o

Más respuestas relacionadas