Problema de tall de valors
El problema de tall de valors és un problema NP-complet optimisació, essencialment es reduïx al problema de la mochila. Específicament, és un problema de programació llineal en número entero. Sorgix de moltes aplicacions en l'indústria. Imagine que vosté treballa en una fàbrica de paper i té un número de rolls de paper d'ample fix a l'espera de ser tallat, pero diferents clients volen diferents números de rolls de distints tipos d'amples. ¿Cóm es van a tallar els rolls de manera que minimisa els residus (cantitat de sobres)?
D'acort en la Confederació Europees d'Indústries Papereres,[1] en 2012 les 1,331 màquines de paper en la regió, produïxen cada una un promig € 56 millons (aproximadament $ 73 millons US.) de la facturació. Aforrar inclús fraccions de 1% és, per tant, significatiu.
Formulació i solució d'enfocaments
La formulació estàndar per al problema de tall de valors (pero no l'única) comença en una llista de m órdens, cada una requerira peces. A continuació es construïx una llista de totes les combinacions possibles de les retallades (a sovint cridats "patrons"), associant a cada patró una variable sancera positiva que representa quàntes voltes serà utilisat cada patró. El programa sancer llineal és llavors:
- , sancer
a on és el número de voltes que l'orde apareix en el patró i és el cost (a sovint els residus) del patró . La naturalea precisa de la cantitat de restriccions pot dur a característiques matemàtiques diferents. Les mateixes constituïxen la cantitat de restriccions mínimes(per lo manco la cantitat que cada orde deu produir, pero possiblement més). Quan l'objectiu minimisa el número d'elements mestres utilisats i, si la restricció de la cantitat a produir se substituïx per l'igualtat, es diu la problema d'embalage Bin. La formulació més general té restriccions de dos costats (i en este cas una solució de conversió de residus mínim pot consumir més que el número mínim d'elements mestres):
Esta formulació s'aplica no només als problemes d'una sola dimensió. Moltes variacions són possibles, incloent un en el que l'objectiu no és reduir al mínim els rebujos, si no maximizar el valor total dels artículs produïts, permetent que cada orde tinga un valor diferent.
En general, el número de possibles patrons creix exponencialment en funció del número d'órdens m. A mida que el número de demanats aumenta, pugues no ser pràctic enumerar els possibles patrons de cort.
Un enfocament alternatiu utilisa generació-retardada de columnes. Este método resol el problema del tall de valors començant en uns pocs patrons. Genera patrons adicionals quan es necessiten. Per al cas unidimensional, els nous patrons s'introduïxen per mig de la resolució d'un problema d'optimisació auxiliar cridat el problema de la mochila, utilisant informació de variables duals des del programació llineal. El problema de la mochila té métodos de solució, com el conegut ramificació i acotación i programació dinàmica. El método de generació de columnes retardada pot ser molt més eficient que l'enfocament original, en particular com el tamany del problema creix. L'enfocament de generació de columna aplicat al problema de cort va ser iniciat per Gilmore i Gomory en una série d'artículs publicats en la década de 1960.[2][3] Gilmore i Gomory varen demostrar que este enfocament garantisa la convergència a la solució òptima (fraccionada), sense necessitat d'enumerar tots els possibles patrons de bestreta.
Una llimitació del método original de Gilmore i Gomory és que no maneja integralidad, per lo que la solució pot contindre fraccions, per eixemple, un patró particular es deu produir 3,67 voltes. El grosseig al sancer més pròxim a sovint no funciona, en el sentit de que pot dur a una solució subóptima i/o inviabilidad sub- o sobre-producció d'algunes de les órdens (i possible en presència de restriccions de demanda de dos cares ). Esta llimitació se supera en els algoritmes moderns, que poden resoldre óptimamente (en el sentit de trobar solucions en un mínim de desperdici) molt grans instàncies del problema (generalment major de l'habitual en la pràctica[4][5]).
El problema de tall de valors és a sovint degenerado, en que són possibles vàries solucions en el mateix residus. Esta degeneració es deu a que és possible moure els elements entorn, creant nous patrons, sense afectar als residus. Açò dona lloc a tota una colecció de problemes afins que s'ocupen d'algun atre criteri, com el següent:
- El problema de reconte mínim de patrons: per a trobar una solució de la cantitat mínima de patrons entre les solucions de rebuig mínim. Est és un problema molt difícil, inclús quan es coneix els residus.[6][7] Hi ha una conjectura que qualsevol instància unidimensional de restriccions d'igualtat en n órdens té a lo manco una solució mínima de residus en no més n+ 1 patrons. No es coneix tampoc cota superior del número de patrons, eixemples en n + 5 són coneguts.
- El problema de apilamiento mínim: açò es referix a la seqüència dels patrons a fi de no tindre massa órdens parcialment terminats en qualsevol moment. Est era un problema obert fins a 2007, quan es va publicar un algoritme eficient basat en programació dinàmica.[8]
- El problema del canvi mínim del número de gavinet (per a problema unidimensional): açò es referix permutació dels patrons a fi de minimisar el número de voltes que les cuchilles de cort llongitudinal tenen que ser mogut. Est és un cas especial del generalisat problema del viajante.
Ilustració del problema unidimensional de tall de valors
Una màquina de paper pot produir un número illimitat de rolls mestres (jumbo), cada u medix 5600 mm d'ample. Els següents 13 artículs deuen ser tallats:
Width Rolls 1380 22 1520 25 1560 12 1710 14 1820 18 1880 18 1930 20 2000 10 2050 12 2100 14 2140 16 2150 18 2200 20
Solució
Hi ha 308 patrons possibles per a este chicotet eixemple. La resposta òptima requerix 73 rolls mestres i té 0,401% de residus; es pot demostrar computacionalment que en este cas el número mínim de patrons en este nivell de residus és 10. També es pot calcular que existixen 19 diferents solucions, cada una en 10 patrons i una pèrdua de 0,401%, de les que una solució es mostra a continuació:
Repetition Contents 2 1820 + 1820 + 1820 3 1380 + 2150 + 1930 12 1380 + 2150 + 2050 7 1380 + 2100 + 2100 12 2200 + 1820 + 1560 8 2200 + 1520 + 1880 1 1520 + 1930 + 2150 16 1520 + 1930 + 2140 10 1710 + 2000 + 1880 2 1710 + 1710 + 2150 73
Referències
- ↑ «Key Statistics 2012». Confederation of Europear Paper Industries. Archivat des de l'original, el 6 d'octubre de 2014. Consultat el 3 de juliol de 2013.
- ↑ Gilmore P. C., R. E. Gomory (1961). A linear programming approach to the cutting-estoc problem. Operations Research 9: 849-859
- ↑ Gilmore P. C., R. E. Gomory (1963). A linear programming approach to the cutting-estoc problem - Part II. Operations Research 11: 863-888
- ↑ Goulimis C (1990). Optimal solutions for the cutting estoc problem. European Journal of Operational Research 44: 197-208
- ↑ de Carvalho V (1998). Exact solution of cutting estoc problems using column generation and branch-and-bound. International Transactions in Operational Research 5: 35–44
- ↑ S. Umetani, M. Yagiura, and T. Ibaraki (2003). One dimensional cutting estoc problem to minimize the number of different patterns. European Journal of Operational Research 146, 388–402
- ↑ A. Diegel, E. Montocchio, E. Walters, S. van Schalkwyk and S. Naidoo (1996). Setup minimizing conditions in the trim loss problem. European Journal of Operational Research 95:631-640
- ↑ Maria Garcia de la Banda, P. J. Stuckey. Dynamic Programming to Minimize the Maximum Number of Open Stacks. INFORMS Journal on Computing, Vol. 19, No. 4, Fall 2007, 607-617.
Referències
- Este artícul conté una traducció derivada de «Problema de corte de valores» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.