🚀 go-pugleaf

Hola Jesus.

Me acaban de pasar un caso real de pedido.
Te cuento:

Una barra mide 6400 mm.

Y en el pedidon piden:

+ 80 de 648,4 mm
+ 100 de 768,4 mm
+ 100 de 708,4 mm

De ahi hay que sacar cuantas barras se van a necesitar y la combinaci�n de 
los cortes para que el desperdicio sea el menor posible. Un desperdicio 
optimo para la empresa son 30 mm o menos por barra. O si no que me sobre 
entre 768,4 mm y 1248,4 mm (480mm).

Lo optimo serian usar :
80 * 348,4 + 100 * 768,4 + 100 *  708,4 = 175552 mm
28 * 6400 = 179200 mm
179200 - 175552 = 3648 mm = 3,648 m

Y a ver, si he entendido bien tu planteamiento.

Si corto la barra REAL (6400mm) con una combinacion de cortes X y nos sobran 
menos de 30mm, entonces perfecto esa combinacion es correcta.
Ahora, si nos sobran m�s de 30mm, entonces paso a la barra VIRTUAL de 5920 
mm (6400mm - 480 mm) y si en esta barra nos sobran menos de 30mm entonces 
esta es la mejor opcion. Y si nos sobran m�s de 30 mm entonces elijo la 
barra REAL.

�Es correcto?
O viendo el pedido que te he puesto arriba, �como lo solucionarias?, �de la 
misma forma que me has dicho?.

Muchas Gracias, Jesus.




"Jes�s M. NAVARRO" <jmnavarrol@able.es> escribi� en el mensaje 
news:qph7s2-asj.ln1@mithrandir.intranet...
> Hola, Tomey:
>
> Tomey escribi� en es.comp.os.linux.programacion:
>
>> Si, correcto.
>> Se me olvido poner el ^ :P
>>
>> Voy a probar el algoritmo que me has pasado a ver que tal.
>>
>> Te explico exactamente el problema a ver si asi te sirve de algo mas de
>> ayuda.
>> Una empresa me ha pedido que haga un programa que es el siguiente.
>>
>> Ellos tienen barras de aluminio de 30 metros (supongamos, medida
>> standard). Y necesitan sacar de esas barras de aluminio 3 secciones de
>> 10m, 5 de 43m y 4 de 27m.
>> Hay que optimizar los cortes de las barras para que la perdida de 
>> material
>> sea el minimo.
>> O si no puede ser eso, que por lo menos, el trozo de barra que te sobre
>> sea reutililizable.
>
> �De cu�ntas barras estamos hablando?
>
> En principio, el problema parece NP-Dif�cil (t=>a^n), no obstante, con un
> n�mero relativamente bajo de barras, y si el tiempo no es cr�tico, puedes
> optar por la cosa m�s sencilla: hacer una b�squeda exhaustiva en el 
> espacio
> de soluciones (es decir, calcular *todas* las soluciones posibles y
> quedarte con la mejor).  Es problable que si el stock es menor que,
> digamos, 100 barras, eso te sea suficiente si puedes obtener la soluci�n
> en, digamos, menos de una o dos horas (el hecho de que una soluci�n sea
> "fea" en t�rminos absolutos, no quiere decir que no pueda ser 
> perfectamente
> viable en tu entorno real).
>
> Si ves que el proceso es demasiado largo para tus necesidades, puedes
> utilizar el m�todo de bipartici�n, que deber�a ser lineal: simplemente 
> coge
> la secci�n m�s larga, y luego la m�s larga que te quede (y que entre en el
> resto), de entre las restantes, sucesivamente hasta que no te quepa 
> ninguna
> m�s.  No voy a echar n�meros ahora, pero tiene pinta de ser una
> aproximaci�n "suficientemente buena".  La suposici�n que hago es que todas
> las barras que utilizas son del mismo tama�o, ya que no dices otra cosa.
>
>> Que sobre un trozo de 6m no sirve para nada porque la medida menor de una
>> barra es de 10m.
>> Entonces digamos que el sobrante debe estar lo mas cercanoa a 0 posible o
>> superiro a 10m.
>
> Con esta constricci�n, juega con dos barras, una "real" y otra "virtual"
> diez metros m�s corta; si consigues que a la barra "virtual" le sobre 
> menos
> material que a la barra "real", �sa es tu soluci�n; en caso contrario, usa
> la soluci�n obtenida para la barra "real".
>
> Veamos un ejemplo pr�ctico con los datos que das:
>
> Primera barra:
>        27m (nos sobran tres metros, que es un tama�o mayor que la secci�n 
> m�s
> peque�a, por lo que ya no podemos seguir; veamos que pasa con la barra
> "virtual" de 20m):
>                10m+10m (no sobra nada, por lo tanto cogemos esta soluci�n 
> y nos queda un
> "resto" de 10m, que volvemos a partir):
>                10m (no sobra nada, y ya hemos acabado con las secciones de 
> 10m)
> Segunda barra:
>        27m (nos sobran tres metros; veamos que pasa con la barra "virtual" 
> de 20m;
> voy a suponer que donde dices 5 secciones de 43m son 10 secciones de 5m, 
> ya
> que las de 43m no "caben" en la barra de 30m, y con 43 barras, el ejemplo
> sale demasiado largo):
>                5m+5m+5m+5m (no sobra nada, por lo tanto cogemos esta 
> soluci�n y nos queda
> un "resto" de 10m, que volvemos a partir):
>                5m+5m (no sobra nada)
> Tercera barra:
>        27m (nos sobran tres metros; veamos que pasa con la barra "virtual" 
> de
> 20m):
>                5m+5m+5m+5m (no sobra nada, por lo tanto cogemos esta 
> soluci�n y ya no nos
> quedan secciones de cinco metros; nos queda un "resto" de 10m, que
> intentamos volver a partir, pero no podemos, porque no nos quedan ya
> perfiles iguales o menores que 10m para encajar).
> Cuarta, quinta, sexta y s�ptima barras: 27m, y nos sobran tres pedazos de 
> 3m
> de cada una (la soluci�n de la "barra virtual" la omito porque es evidente
> que no va a ser mejor).
>
> Ya hemos acabado.  En este caso, adem�s, se puede demostrar que hemos
> encontrado la soluci�n �ptima*1: el reparto no pod�a hacerse de mejor
> manera, porque la secci�n m�s larga (la de 27m) no dejaba sitio en la 
> barra
> para la secci�n m�s peque�a (la de 10m)
>
> Pueden existir optimizaciones locales "parientes" de los algoritmos de
> ordenaci�n, pero no las busques a menos que realmente las necesites (ya
> sabes, "early optimization is the root of all evils"): por ejemplo, puesto
> que hemos ordenado las secciones de mayor a menor, una vez que la barra 
> m�s
> corta que nos queda no quepa en la "barra virtual", sabemos que ya no nos
> hace falta intentar con ella en iteraciones posteriores; o, si en la barra
> entran muchas secciones, o si tenemos muchos tama�os distintos a encajar,
> podemos avanzar "a saltos" 2:1 o 3:1 para encontrar la secci�n adecuada
> cuando las mayores ya no nos quepan, o puedes probar a colocar los 
> perfiles
> en lugar de mayor a menor, de forma alterna mayor-menor-mayor-menor...
>
> *1 En general, puedes calcular heur�sticamente si esta aproximaci�n es
> razonablemente buena utilizando un m�todo de montecarlo para generar
> pedidos aleatorios (la generaci�n de pedidos la puedes sustituir, por
> ejemplo, por el listado de pedidos del �ltimo a�o, si tienes acceso a �l),
> y luego calculando el resto �ptimo si s�lo tuvieras una barra de longitud
> m�ltiplo de la barra real, compar�ndolo con el que te da el procedimiento
> que te he contado.
> En el ejemplo: 3*10 + 10*5 + 4*27 = 188m
>               7*30=210m
>               210-188=22m sobrantes
> As�, sabemos que en la soluci�n ideal nos van a sobrar por lo menos 22m
> (justo lo que nos sobr� a nosotros, por eso sabemos que nuestra soluci�n
> era ideal).  Puesto que no tenemos una barra de 210m, sino muchas de 30,
> podr�a darse el caso de la soluci�n �ptima te�rica no existiese: por
> ejemplo, supongamos que nos piden 12 perfiles de 25m; el �ptimo te�rico
> ser�a (12*25=300; 300/30=10) utilizar diez barras sin que nos sobrase 
> nada,
> pero es obvio que en este caso necesitar�amos 12 barras y nos sobrar�an 12
> trozos de cinco metros.  As�, aunque no sabemos realmente cu�n cerca
> estamos del �ptimo real (para ello habr�a que calcular exhaustivamente los
> �ptimos reales y compararlos con las soluciones obtenidas, o poder
> demostrar matem�ticamente la aproximaci�n del algoritmo en el paso al
> l�mite -existe toda una rama de la matem�tica que se dedica a estas 
> cosas-)
> s� tenemos una idea aproximada de lo bien que lo estamos haciendo.  Si,
> adem�s, tienes acceso a los pedidos del �ltimo a�o, puedes establecer si 
> el
> m�todo es mejor que el que ten�a la empresa, tanto calcul�sticamente
> (cu�ntas barras utilizaron realmente y cu�ntas hubieran utilizado caso de
> usar tu programa), como en tiempo (cu�nto tiempo les llev� hacer los
> c�lculos -si esa informaci�n existe- y cu�nto les hubiera costado de haber
> utilizado tu programa).  Puede darse el caso de que incluso si tu programa
> fuese peor que el m�todo que estuviesen utilizando hasta ahora, fuese
> rentable si, por ejemplo, se pasase de usar dos horas diarias de operador
> con l�piz y papel, a utilizar 10 minutos diarios de tiempo de ordenador.
> Si la diferencia es sustancial, incluso puedes plantear un aumento de
> sueldo por una fracci�n del dinero que les est�s ahorrando.
> -- 
> SALUD,
> Jes�s