Siii
Páginas: 3 (583 palabras)
Publicado: 24 de mayo de 2011
ALGORITMO DE RAMIFICACIÓN Y ACOTAMIENTO PARA PROGRAMACIÓN ENTERA MIXTA
El método de Branch and Bound (en español Ramificación y Acotamiento) aborda la resolución de modelos de programación entera através de la resolución de una secuencia de modelos de programación lineal que consituirán los nodos o subproblemas del problema entero. Si bien el procedimiento es extendible a un número mayor devariables, para efectos prácticos ilustraremos su aplicación para modelos de programación entera en 2 variables.
Resuelva el siguiente modelo de programación entera a través del algoritmo deramificación y acotamiento (Branch and Bound).
El primer paso consiste en resolver el problema sin considerar las condiciones de integralidad, es decir, asumiendo que es un modelo de Programación Lineal. Elsiguiente gráfico muestra la resolución gráfica donde el área en verde corresponde al dominio de soluciones factibles asociado al problema lineal lo que se denomina la relajación continua del problemaentero. Adicionalmente, sólo con el objetivo de ilustrar se han marcado con azul las posibles soluciones enteras para este problema. En este sentido resulta evidente que el dominio de solucionesfactibles del problema entero es un subconjunto del dominio del problema lineal y esto en el caso de un problema de maximización determina que el valor óptimo del problema lineal será una cota superior delvalor óptimo del problema entero.
La relajación continua (Problema P0) nos da como solución óptima X1=20/9 y X2=14/9 con valor óptimo V(P0)=319,1. Dado que al menos una variable de decisión tomavalor fraccionario se debe buscar una aproximación a valor entero. En este caso en particular con 2 soluciones fraccionarias como criterio se puede seleccionar aquella con un mayor impacto (coeficiente)en la función objetivo, sin embargo, no importando cuál de ellas se seleccione en un inicio los resultados serán los mismos.
En consecuencia, seleccionaremos X1 y aproximaremos los resultados...
El método de Branch and Bound (en español Ramificación y Acotamiento) aborda la resolución de modelos de programación entera através de la resolución de una secuencia de modelos de programación lineal que consituirán los nodos o subproblemas del problema entero. Si bien el procedimiento es extendible a un número mayor devariables, para efectos prácticos ilustraremos su aplicación para modelos de programación entera en 2 variables.
Resuelva el siguiente modelo de programación entera a través del algoritmo deramificación y acotamiento (Branch and Bound).
El primer paso consiste en resolver el problema sin considerar las condiciones de integralidad, es decir, asumiendo que es un modelo de Programación Lineal. Elsiguiente gráfico muestra la resolución gráfica donde el área en verde corresponde al dominio de soluciones factibles asociado al problema lineal lo que se denomina la relajación continua del problemaentero. Adicionalmente, sólo con el objetivo de ilustrar se han marcado con azul las posibles soluciones enteras para este problema. En este sentido resulta evidente que el dominio de solucionesfactibles del problema entero es un subconjunto del dominio del problema lineal y esto en el caso de un problema de maximización determina que el valor óptimo del problema lineal será una cota superior delvalor óptimo del problema entero.
La relajación continua (Problema P0) nos da como solución óptima X1=20/9 y X2=14/9 con valor óptimo V(P0)=319,1. Dado que al menos una variable de decisión tomavalor fraccionario se debe buscar una aproximación a valor entero. En este caso en particular con 2 soluciones fraccionarias como criterio se puede seleccionar aquella con un mayor impacto (coeficiente)en la función objetivo, sin embargo, no importando cuál de ellas se seleccione en un inicio los resultados serán los mismos.
En consecuencia, seleccionaremos X1 y aproximaremos los resultados...
Leer documento completo
Regístrate para leer el documento completo.