La Descomposición de Benders es, como su nombre lo dice, un Método de Descomposición. La idea de este método es bastante simple: dividir para conquistar. El objetivo es literalmente descomponer el problema en dos partes: El Master Problem (Problema Maestro) y el Subproblem (Subproblema) (también llamado Slave Problem o Problema Esclavo). En el siguiente artículo revisaremos de qué se […]
En el siguiente artículo detallaremos cómo funciona el Método Simplex a través de un ejemplo sencillo correspondiente a un modelo de Programación Lineal que considera 3 variables de decisión. El Método Simplex corresponde a un algoritmo iterativo publicado por George Bernard Dantzig en el año 1947 en donde se busca alcanzar el máximo (o mínimo) […]
En algunos casos los ceros que se producen en los Pasos 1 y 2 del Método Húngaro no producen una solución factible en forma directa, es decir, la asignación alcanzada es infactible. En este caso se necesitan más pasos para alcanzar la asignación óptima (factible). Para ilustrar esta situación consideremos el siguiente ejemplo que consiste […]
En la resolución de un modelo de Programación Lineal se pueden enfrentar ciertos casos especiales que merecen particular atención. Estos casos (infinitas soluciones óptimas, problema no acotado sin solución óptima, problema infactible, solución óptima degenerada) se pueden detectar a través de la aplicación del Método Simplex según hemos tratado previamente en el Blog. A continuación […]
Un problema infactible en Programación Lineal es una situación que se detecta cuando en la aplicación del Método Simplex de 2 Fases el valor óptimo del problema de la Fase 1 es distinto a cero (para continuar a la Fase 2 se requiere que el valor óptimo de la Fase 1 sea cero). Cabe recordar […]