ALGORITMO
































ALGORITMO DE BRANCH AND BOUND (RAMIFICACIÓN Y ACOTAMIENTO)
El método de Branch and Bound(o Ramificación y Acotamiento) es un algoritmo diseñado para la resolución demodelos 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ón lineal y luego generar cotas encaso que al menos una variable  de decisión adopte un valor fraccionario. El algoritmo genera en forma recursiva cotas (o restricciones adicionales) que favorecen la obtención de valores enteros paralas 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ón continua del modelo entero.Consideremos el siguiente modelo de programación entera el cual resolveremos con el algoritmo de Branch and Bound:

El paso inicial consiste en resolver este problema como si fuese un modelo deprogramación lineal (relajación continua). Si la solución de dicho problema llegara a respetar las condiciones de integralidad para las variables de decisión, ésta ya sería la solución óptima del problemaentero.
Si bien este procedimiento se puede extender a problemas de mayor dimensión, utilizamos un modelo en 2 variables para poder representar los pasos del algoritmo gráficamente. El gráfico a continuaciónmuestra dicha resolución:

La solución óptima del problema lineal asociado (que llamaremos P0) es X1=2,8 yX2=1,6 con valor óptimo V(P0)=20,8. Claramente esta solución no cumple las condiciones deintegralidad para las variables de decisión por tanto es necesario generar cotas o restricciones adicionales de modo de poder obtener soluciones enteras. Para ello debemos seleccionar una de las 2variables de decisión con valores fraccionarios para poder generar cotas. En estricto rigor es indistinto cuál de ellas seleccionemos debido a que el método nos debe llevar a conclusiones similares (aun...