Esta nueva restricción es una cortadura "Corta" la solución óptima de la soltura de PL (5/6, 1, 0, 1), pero no elimina ninguna solución entera factible. Si se agrega tan sólo esta cortadura al modelo original, se mejora el desempeño de algoritmo de ramificación y acotamiento de PEB de la sección 13.4 (véase la figura 13.7) en dos formas. Primero, la solución óptima para la nueva (y más estrecha) soltura de PL sería (1, 1, 1/5, 0), con Z = 15(1/5) de manera que la cotas para los nodos de todo el problema, x1 = 1 y x2 = 1, serían ahora de 15 en lugar de 16. Segundo, se necesitaría una iteración menos, porque la solución óptima de la soltura de PL en el nodo x3 = 0 sería (1, 1, 0, 0), que proporciona una nueva solución de apoyo con Z* = 14. Por tanto, en la tercera iteración (véase la figura 13.6) se sondearía este nodo por la prueba 3 y el nodo x2 = 0 se sondearía por la prueba 1, indicando que esta nueva solución de apoyo es la solución óptima para el problema de PEB original.
El nuevo enfoque algorítmico presentado en las referencias selectas 1,4 y 13 implica la generación de muchas cortaduras en forma parecida antes de aplicar las técnicas de ramificación y acotamiento. Los resultados al incluir cortaduras pueden ser importantes para estrechar las solturas de PL. Por ejemplo, para el problema de prueba con 2756 variables binarias del artículo de 1983, se generaron 326 cortaduras. El resultado fue que la distancia entre el valor de Z de la solución óptima de la soltura de PL del problema completo de PEB y el valor de Z de la solución óptima del problema se redujo en un 98%. En casi la mitad de los problemas se obtuvieron resultados similares.
No hay comentarios.:
Publicar un comentario