METODOS DE BIFURCACION Y ACOTACION

METODOS DE BIFURCACION Y ACOTACION
El método de bifurcación y acotación, que es muy elegante y simple, redondea y acota variables enteras, resultante de la solución de los problemaslinealescorrespondientes. Este proceso de acotamiento y redondeo se hace de una manera secuencial lógica heurística, que permite eliminar con anticipación un buen número de soluciones factibles alejadas delóptimoa medida que se itera. De tal suerte que si una variable entera Xj, j=1…., n, está acotada entre un límite inferior entero dj, j=1,…, n, y un límite superior entero uj, j=1,…, n, el procesodebifurcación y acotación sólo analiza un número muy pequeño de todas las posibles soluciones. Para que el lector se dé cuenta de la tremenda cantidad de posibles soluciones, debe tener presente que sololavariable Xj puede tomar cualquiera de los siguientes valores enteros: dj, dj+1, dj+2,…, uj-2, uj-1, uj. Si se tienes n variables enteras, imagínese el número de posibles combinaciones que sepuedenobtener.
ALGORITMO DE LAND-DOIG
El primer algoritmo de bifurcación y acotación se presenta en Land y Doig(84). El nombre de bifurcación y acotación se lo dan posteriormente Little, Murty, Sweeney,Karel(89). El algoritmo de Land y Doig, fue modificado más tarde por Dakin (48), que lo hace un poco más general. A continuación se presenta el algoritmo de algoritmo de bifurcación y acotación de LandyDoig con la modificación hecha por Dakin, y suponiendo que se maximiza la función objetivo.
Paso 1.
Resuelva el problema entero por medio del método simplex de la programación lineal. Si lasoluciónes entera, parte, se ha conseguido la solución óptima. Si no, continúe en el paso 2.
Paso 2.
Escójase arbitrariamente una variable entera Xj cuyo resultado en el paso 1 sea fraccional e igual aXBj.Paso 3.
Resuelva un par de nuevos problemas, similares al problema anterior, pero uno con la restricción adicional Xj ≤ [ XBj], mientras que el otro tendrá la restricción adicional Xj ≥...