Metodo Simplex


TAREA 6
MÉTODO SIMPLEX

INTRODUCCIÓN:
El método de Branch and Bound (en español Ramificación y Acotamiento) aborda la resolución de modelos de programación entera a través de la resolución de unasecuencia de modelos de programación lineal que constituirán los nodos o subproblemas del problema entero.
DESARROLLO:
El método de Branch and Bound (o Ramificación y Acotamiento) es un algoritmodiseñado para la resolución de modelos de programación entera. Su operatoria consiste en “linealizar” el modelo de programación entera, es decir, resolver éste como si fuese un modelo de programaciónlineal y luego generar cotas en caso que al menos una variable de decisión adopte un valor fraccionario. El algoritmo genera en forma recursiva cotas (o restricciones adicionales) que favorecen laobtención de valores enteros para las variables de decisión. En este contexto resolver el modelo lineal asociado a un modelo de programación entera se conoce frecuentemente como resolver la relajacióncontinua del modelo entero.

Ejemplo 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ónLineal. El siguiente 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 continuadel problema entero. 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 desoluciones factibles 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 cotasuperior del valor ó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...