Algoritmo d bifurcacion

ALGORITMO DE BIFURCACION Y ACOTAMIENTO
Es el método más eficiente para encontrar los valores óptimos enteros para las variables de decisión de un Modelo de Programación Lineal Entera.
En términosgenerales, el algoritmo de bifurcación y acotamiento es una metodología que consiste en dividir, progresivamente, un modelo de programación lineal, en modelos cuyas zonas de soluciones factibles sonsub-conjuntos no traslapados de la zona de soluciones factibles del modelo original. Esta división se realiza en la práctica creando, a partir de un modelo dado, dos nuevos modelos que acoten,restrinjan, a una de las variables de valor óptimo decimal. El primer modelo se genera agregando una restricción que acote dicha variable a valores menores o iguales a la parte entera de la solución óptima yel segundo, agregando una restricción que acote la variable a valores mayores o iguales a la parte entera más uno de la solución óptima. Esta metodología se repite sucesivamente hasta encontrar lamejor solución óptima entera. En estas circunstancias se genera un árbol de modelos cuya cúspide es el modelo original, el que se ha expandido sucesivamente al efectuar la bifurcación por el acotamientode las variables de valor óptimo decimal. Cada modelo queda representado por un nodo y cada nueva restricción por una rama que conecta un nodo con el siguiente

Al resolver este modelo de P.L. sellega a la solución óptima teórica: X1*= 3,75 X2
*=4,125 y Z*= 50,625 y debemos reconocer que no existe solución factible que implique un valor mejor para la Función Objetivo.
Para encontrar unaprimera solución factible entera para el modelo, normalmente se recurre a una de dos prácticas: La aproximación del valor decimal de la variable al entero superior o inferior, dependiendo del valor decimal,o bien el truncamiento de la solución decimal de las variables de decisión a su parte entera.
Cualquiera de estas aproximaciones debe ser verificada en cuanto a su factibilidad, es decir, a que...