Capítulo 3. Método de Generación de Columnas- Evaluación del método de generación de columnas para el problema de corte -Cutting Stock- usando heurísticas para la obtención de patrones de corte - DepartamentReportar como inadecuado




Capítulo 3. Método de Generación de Columnas- Evaluación del método de generación de columnas para el problema de corte -Cutting Stock- usando heurísticas para la obtención de patrones de corte - Departament - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Capítulo 3. Método de Generación de Columnas- Evaluación del método de generación de columnas para el problema de corte -Cutting Stock- usando heurísticas para la obtención de patrones de corte - Departamento de Ingeniería Industrial y Mecánica. - - Licenciatura en Ingeniería Industrial con área de manufactura. - Escuela de Ingeniería, - Universidad de las Améric

Autor: Díaz Smith, Santiago

Fuente: http://catarina.udlap.mx/


Introducción



Capitulo 3 Método de Generación de Columnas El método de generación de columnas, es muy útil en problemas con un gran número de variables pero con un relativamente pequeño número de restricciones (Hunsaker, 2004). En 1958 Ford y Fulkenson sugirieron por primera vez lidiar implícitamente solo con algunas variables para problemas de flujo en redes, en 1960, Dantzig y Wolfe desarrollaron una estrategia para extender las columnas de un problema lineal lo necesario para obtener una solución.
Esta técnica fue implementada por primera vez por Gilmore y Gomory en 1961 para resolver el problema “cutting stock” (Desrosiers & Lübbecke, 2005). La técnica del método de generación de columnas consiste en resolver problemas de programación lineal donde las columnas (variables del problema) no son conocidas o es impráctico generarlas explícitamente, generalmente en problemas que tienen un número exponencial de variables.
Para resolver estos problemas se empieza con un problema maestro, el cual es una relajación lineal del problema original y debe de tener una estructura relativamente simple (se genera solo un número pequeño de columnas, necesario para obtener una solución factible para el problema relajado). Después hay un sub-problema (al que se le denomina sub-problema de pricing) que permite identificar columnas (variables) adicionales que no han sido incluidas en el problema maestro y que mejoren el valor de la función objetivo. Hoy en día, el método de generación de columnas es ampliamente usado en una gran cantidad de problemas, como por ejemplo: problemas de rutas de vehículos, algunos problemas del agente viajero, programación de horarios para equipos de trabajo, etc.
(Desrosiers & Lübbecke, 2005). En el siguiente capítulo se hablará del uso del método de generación de columnas para resolver el problema de corte (“cutting stock”). 3.1 Problema de corte (“Cutting Stock”) Como vimos anteriormente, el problema “cutting stock” ...






Documentos relacionados