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

Paso Inicial

Después de establecer Z* = -∞, se forma la soltura de PL de este problema eliminado el conjunto de restricciones xj es entero para j = 1, 2, 3. Si se apliac el método símplex a esta soltura de PL, la solución óptima es

Soltura de PL de todo el problema: (x1, x2, x3, x4) = (5/4, 3/2, 7/4, 0), con Z = 14(1/4)

Como tiene soluciones factibles y esta solución óptima tiene valores no enteros para sus variables restringidas a enteros, se sondea todo el problema y el algoritmo continua con al primera iteración completa.

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

Ahora se ilustrará este algoritmo mediante su aplicación al siguiente problema de PEM:

Nótese que el número de variables restringidas a enteros es I = 3, de manera que x4 es la única variable continua.

Resumen del algoritmo de ramifiación y acotamiento de PEM - Pasos para cada iteración (IV)

Prueba de optimalidad:  el proceso se detiene cuando no hay subproblemas restantes; la solución incumbente actual es óptima. De otra manera, se realiza otra iteración.

Resumen del algoritmo de ramifiación y acotamiento de PEM - Pasos para cada iteración (III)

Sondeo: para cada nuevo subproblema  se aplican las pruebas de sondeo que se dan en seguida y se descartan aquellos subproblemas que quedan sondeados por cualquiera de las pruebas:

Prueba 1: su cota ≤ Z*, donde Z* es el valor de Z en la solución de apoyo actual.
Prueba 2:su soltura de PLno tiene soluciones factibles
Prueba 3: la solución óptima para su soltura de PL tiene valores enteros para todas sus variables restringidas a enteros. (Si esta solución esmejor que la de apoyo, se convierte en la nueva solución de apoyo y se vuelve a aplicar la prueba 1 con la nueva Z* a todos los subproblemas no sondeados.)

Resumen del algoritmo de ramifiación y acotamiento de PEM - Pasos para cada iteración (II)

Ramificación: para cada subproblema se obtiene su cota aplicando el método sinplex (o el método símplex dual si se reoptimiza) a su soltura de PL y utilizando el valor de Z para la solución óptima resultante.

Resumen del algoritmo de ramifiación y acotamiento de PEM - Pasos para cada iteración (I)

1. Ramificación: entre los subproblemas restantes (no sondeados), se selecciona el de más reciente creación. (Los empates se rompen con la cota más grande). Entre las variables restringidas a enteros, que tienen valores no enteros en la solución óptima de la soltura de PL del subproblema, se elige la primera en el orden natural, como la variable de ramificación. Sea xj esta variable y x*j su valor en esta solución. Se ramifica desde el nodo del subproblema para crear dos nuevos subproblemas agregando las restricciones respectivas xj ≤ [x*j] y xj ≥ [x*j] +1.

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

Paso inicial

Se establece Z* = -∞. Se aplica los pasos de acotamiento y de sondeo y la prueba de optimalidad que se describen a continuación al problema completo. Si no queda sondeado, se clasifica este problema como el único "subproblema" restanta para realizar la primera interación completa.