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 óptimo a 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 …ver más…

La estructura seleccionada es la que lleva el número (1).
Interacción 2.
Paso 2.
Arbitrariamente, de la estructura (1) se escoge la variable X1 =3.33 y se resuelven dos nuevos problemas. Uno que es igual al problema (1) más la restricción X1 ≤ [3.33] = 3. El otro que es igual al problema (1) más la restricción X1 ≥ [3.33] + 1 =4. Es decir
Problema (3)
Max Z = 5x1 +2x2
Sujeto a
2X1+2X2+X3 = 9
3X1+X2+X4 = 11
X2 + X5 = 1
X1+X6 = 3
X1, X2, X3, X4, X5, X6 ≥ 0 enteros.
Problema (4)
Max Z = 5x1 +2x2
Sujeto a
2X1+2X2+X3 = 9
3X1+X2+X4 = 11
X2 + X5 = 1
X1-X6 = 4
X1, X2, X3, X4, X5, X6 ≥ 0 enteros.
Aplicando el método de cota superior, o cualquier otro método, se obtiene n las soluciones óptimas al problema lineal correspondiente a la estructura (3). La estructura (4), no tiene solución factible (el problema es inconsciente), y por lo tanto no se le incluye en el listado de estructuras a analizar. Z
X̅1
X̅2
X3
X4
XB

1
5
2
0
0
17

0
-2
-2
1
0
1
Problema (3)
0
-3
-1
0
1
1

Paso 4.
Por ser una solución entera se incluye en el análisis.
Paso 5.
Por ser el mejor valor de la función objetivo y además, ser entero, es la solución óptima, es decir Z = 17, X̅1 = 3- X1 = 0, X̅2 = 1- X2 = 0, X3 =1, o sea
Z = 17, X1 = 3, X2 = 1, X3 =1, X4 =1.
El problema anterior puede describirse por medio de una representación gráfica que está constituida por una red con estructura de árbol, donde a cada nodo se le asocia lo siguiente: un