Ejemplo Resumen del algoritmo de ramifiación y acotamiento de PEM (IX)

Iteración 3

De los dos subproblemas restantes (3 y 4) que se crearon al mismo tiempo, se selecciona el que tiene la cota más grande (subproblema 3, con 14(1/6) > 12(1/6) para la siguiente ramificación). Como x1 = 5/6 tiene un valor no entero en la solución óptima de la soltura de PL de su subproblema, x1 se convierte en la variable de ramificación. (Obsérvese que x1 es ahora una variable de ramificación recurrente, pues también se seleccionó en la iteración 1.) Esto conduce a los siguientes subproblemas:

Ejemplo Resumen del algoritmo de ramifiación y acotamiento de PEM (VIII)

Al resolver las solturas de PL se obtienen los siguientes resultados:

Soltura de PL del subproblema 3: (x1, x2, x3, x4) = (5/6, 1, 11/6, 0), con Z = 14(1/6)

Cota para el subproblema 3: Z ≤ 14(1/6)

Soltura de PL del subproblema 4: (x1, x2, x3, x4) = (5/6, 2, 11/6, 0), con Z = 12(1/6)
Cota para el subproblema 4: Z ≤ 12(1/6)

Como ambas soluciones existen (soluciones factibles) y tienen valores no enteros para variables restringidas a enteros, ninguno de los subproblemas se sondea. (La prueba I no es operativa, puesto que todavía Z* = - ∞, hasta que se encuentre la primera solución de apoyo.)

El árbol de solución hasta este punto se da en la figura 13.9.

Ejemplo Resumen del algoritmo de ramifiación y acotamiento de PEM (VII)

Subproblema 4:

problema original más las restricciones adicionales:


x1 ≤ 1
x2 ≥ 2

Ejemplo Resumen del algoritmo de ramifiación y acotamiento de PEM (VI)

Subproblema 3: problema original más las restricciones adicionales:

x1 ≤ 1

x2 ≤ 1

Ejemplo Resumen del algoritmo de ramifiación y acotamiento de PEM (V)

ITERACION 2

Con sólo un subproblema restante que corresponde al nodo x1 ≤ 1 en la figura 13.8, la siguiente ramificación se hace desde ahí. Al examinar la solución óptima de la soltura de PL que se da en seguida, en este nodo revela que la variable de ramificación es x2, ya que x2 = (6/5) es la primera variable restringida a enteros que no tienen un valor entero. Al agregar una de las restricciones, x2 ≤ 1 o x2 ≥ 2, se crean los dos nuevos subproblemas que siguen.

Ejemplo Resumen del algoritmo de ramifiación y acotamiento de PEM (IV)

De nuevo se elimina el conjunto de restricciones a valores enteros y se resuelven las solturas de PL de estos dos subproblemas; los resultados son:

Soltura de PL del subproblema 1: (x1, x2, x3, x4) = (1, 6/5, 9/5, 0), con Z = 14(1/5).

Cota para el subproblema 1: Z ≤ 14(1/5).

Soltura de PL del subproblema 2: no tiene soluciones factibles

Este resultado para el subproblema 2 significa que queda sondeado por la prueba 2. Igual que en el caso del problema completo, el subproblema 1 no pasa las pruebas de sondeo. En la figura 13.8 se resumen todos estos resultados en el árbol de solución.

Ejemplo Resumen del algoritmo de ramifiación y acotamiento de PEM (III)

Iteración I

En esta solución óptima de la soltura de PL la primera variable restringida a enteros que tiene un valor no entero es x1 = (5/4), entonces ésta se convierte en la variable de ramificación. Al ramificar desde el nodo de todo el problema (soluciones factibles de todo) con esta variable se crean los siguientes dos subproblemas:

Subproblema 1: problema original más la restricción adicional:

x1 ≤ 1.

Subproblema 2: problema original más la restricción adiciona:

x1 ≥ 2.