Ahora es necesario obtener, para cada subproblema, una cota que muestre qué tan buena puede ser su mejor solución factible. La forma más común para hacer esto es resolver rápidamente una soltura sencilla del subproblema. Casi siempre, una soltura de un problema se obtiene elininando ("soltando") un conjunto de restricciones que hacen que el problema sea difícil de resolver. En los problemas de PE las restricciones de más dificultad son las que requieren que las variables sean enteras. Entonces, la soltura que más se usa es la soltura de PL que elimina este conjunto de restricciones.
Trabajando con el ejemplo, considérese primero el problema completo dado en la sección 13.1. Su soltura de PL se obtiene al eliminar el último renglón del modelo (xj es entera, para j = 1,2,3,4) pero conservando las restricciones de xj ≤ 1 y xj ≥ 0. Al aplicar el método símplex para resolver esta soltura de PL se obtiene su solución óptima.
(x1, x2, x3, x4 ) = (5/6, 1, 0, 1), con Z = 16(1/2)
No hay comentarios.:
Publicar un comentario