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

El subproblema 6 se sondea de inmediato con la prueba 2. El subproblema 5 también se puede sondear con la prueba 3, porque la solución óptima de esta soltura de PL tiene valores enteros (x1`= 0, x2 = 0, x3 = 2) para las tres variables restringidas a enteros. (No importa que x4 = 1/2, ya que x4 no está restringida a enteros). Esta solución factible para el problema original se convierte en la primera solución de apoyo (incumbente):

Incumbente = (0, 0, 2, 1/2) con Z* = 13(1/2)

Con esta Z* se vuelve a realizar la prueba de sondeo 1 al otro subproblema (subproblema 4) y pasa la prueba, ya que su cota de 12(1/6) es ≤ Z*.

Esta iteración tuvo éxito en sondear de la tres maneras posibles. Lo que es más, ya no hay subproblemas restantes, por lo tanto la solución incumbente actual es óptima.

Solución óptima = (0, 0, 2, 1/2), con Z* = 13(1/2).

EStos resultados se resumen en el árbol de soluciones de la figura 13.10.