Generación de columnas
La generación de columnas o la generación de columnas retrasadas es un algoritmo eficiente para resolver grandes programas lineales.
La idea general es que muchos programas lineales son demasiado grandes para considerar todas las variables explícitamente. La premisa es que la mayoría de las variables no serán básicas y asumirán un valor de cero en la solución óptima. Debido a esto, solo un subconjunto de variables debe considerarse en teoría al resolver el problema. La generación de columnas aprovecha esta idea para generar solo las variables que tienen el potencial de mejorar la función objetiva, es decir, para encontrar variables con un costo reducido negativo (asumiendo sin pérdida de generalidad que el problema es un problema de minimización).
El problema que se está resolviendo se divide en dos problemas: el problema maestro y el subproblema. El problema maestro es el problema original con solo un subconjunto de variables que se consideran. El subproblema es un nuevo problema creado para identificar una nueva variable. La función objetiva del subproblema es el costo reducido de la nueva variable con respecto a las variables duales actuales, y las restricciones requieren que la variable obedezca a las restricciones naturales.
El proceso funciona de la siguiente manera. El problema principal está resuelto: a partir de esta solución, podemos obtener precios dobles para cada una de las restricciones del problema principal. Esta información se utiliza en la función objetiva del subproblema. El subproblema está resuelto. Si el valor objetivo del subproblema es negativo, se ha identificado una variable con un coste reducido negativo. Esta variable se añade al problema maestro y el problema maestro se vuelve a resolver. Volver a resolver el problema maestro generará un nuevo conjunto de valores duales, y el proceso se repetirá hasta que no se identifiquen variables negativas de costo reducido. El subproblema devuelve una solución con un costo reducido no negativo, podemos concluir que la solución al problema maestro es óptima.
En muchos casos, esto permite resolver programas lineales grandes que anteriormente se consideraban intratables. El ejemplo clásico de un problema en el que se utiliza con éxito es el problema de material de corte. Una técnica particular en la programación lineal que utiliza este tipo de enfoque es el algoritmo de descomposición de Dantzig–Wolfe. Además, la generación de columnas se ha aplicado a muchos problemas, como la programación de la tripulación, el enrutamiento del vehículo y el problema de la mediana p capacitada.
 |
Este artículo relacionado con las matemáticas aplicadas es un trozo. Puedes ayudar a Wikipedia expandiéndola. |
