Cuando se combinan los dos cambios al algoritmo de PEB que se acaban de describir, puede ocurrir un interesante fenómeno de una variable de ramificación recurrente. Para ilustrar esto, sea j = 1 en el ejemplo anterior en donde x*j = 3(1/2) y considérese el nuevo subproblema con x1 ≤ 3. Supóngase que cuando se resuelve la soltura de PL para un descendiente de este subproblema se obtiene x*1 = 1(1/4). Entonces, x1 recurre como variable de ramificación y los dos nuevos subproblemas creados tienen la restricción adicional x1 ≤ 1 y x1 ≥ 2, respectivamente (además de la restricción adicional anterior, x1 ≤ 3). Más adelante, cuando se resuelva la soltura de PL de un descendiente del subproblema que contiene, digamos x1 ≤ 1, se supondrá que x*1 = 3/4. Entonces x1 recurre de nuevo como variable de ramificación, y los dos nuevos subproblemas creados tienen x1 = 0 (debido a la nueva restricción x1 ≤ 0 y la restricción de no negatividad sobre x1) y x1 = 1 (por la nueva restricción x1 ≥ 1 y la anterior x1 ≤ 1).
El tercer cambio se hace en el paso de acotamiento. Antes, con un problema de PE pura y coeficientes enteros en la función objetivo, el valor de Z para la solución óptima de la soltura de PL del subproblema, se redondeaba hacia abajo para obtener la cota, ya que cualquier solución factible para el problema debía tener una Z entera. Ahora, Con algunas variables sinla restricciónn de enteras, la cota es el valor de Z sin redondear.
No hay comentarios.:
Publicar un comentario