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 problemas lineales correspondientes. 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 proceso de bifurcació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 solo lavariable 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 se pueden obtener.
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 Land y Doig 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ón es 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 a XBj.
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 ≥ [ XBj]+ 1.
Paso 4.
De los programas lineales resueltos en el paso 3, inclúyase en análisis a seguir, solo aquellos programas cuya solución (entera o fraccional) sea mejor a cualquiera de las soluciones enteras conocidas.
Paso 5.
Selecciónese aquel programa lineal que tenga el máximo valor de la función objetivo. Si las variables enteras tienen valor entero, se ha conseguido la solución óptima. Sino, regrésese alpaso 2 con la estructura del problema lineal resuelto en este paso.

Figura 1
Se presenta un diagrama de flujo de este algoritmo para facilitar la ilustración de este algoritmo se recomienda al lector se ayude de la figura 2en la solución del siguiente ejemplo.
Ejemplo. Resolver
Problema (0).
Max. Z = 5X1 + 2x2
Sujeto a
2X1+2X2+X3= 9
3X1+X2+X4= 11
X1, X2, X3, X4 ≥ 0 yenteros.
Interacción 1
Paso 1.
La solución óptima del programa lineal correspondiente es

Paso 2.
Se escoge arbitrariamente X2 =1.25 y se resuelven dos problemas lineales distintos,uno con la restricción adicional X2 ≤ [1.25]= 1 y el otro con la restricción adicional X2 ≥ [1.25] + 1 =2 es decir
Problema (1)
Max Z = 5x1 +2x2
Sujeto a
2X1+2X2+X3= 9
3X1+X2+X4= 11
X2 + X5 =1
X1, X2, X3,X4, X5 ≥ 0 enteros.
Problema (2)
Max Z = 5x1 +2x2
Sujeto a
2X1+2X2+X3= 9
3X1+X2+X4= 11
X2 - X5 = 2
X1, X2, X3, X4, X5 ≥ 0 enteros.
Paso 3.
Aplicando el análisis de sensibilidad, cuando se agrega una restricción adicional a un problema lineal, o bien el método de cota superior, ambos discutidos en el capítulo 2, se tienen los siguientes tableaus óptimo de los problemas lineales.
 
Z
X1X̅ 2
X3
X4
XB
 
1
0
0.33
0
1.67
18.75
 
0
0
-1.33
1
-0.67
0.33
Problema (1)
0
1
-0.33
0
0.33
3.33

 
Z
X1
X2*
X3
X4
XB
 
1
0
3
2.5
0
16.5
 
0
0
-2
-1.5
1
1.5
Problema (2)
0
1
1
0.5
0
2.5

Paso 4.
Como no ha habido ninguna solución entera en todo el proceso, se incluyen ambos tableaus en el análisis.
Paso 5.
Como la mejor función objetivo...