La propiedad 2 sugiere que puede obtenerse una solución óptima mediante la enumeración exhaustiva, esto es, se pueden encontrar y comparar todas las soluciones factibles en los vértices, pues son un número finito. Desafortunadamente existen números finitos que (para propósitos prácticos) bien podráin ser infinitos. Por ejemplo, un problema de programación líneal bastante pequeño que consta de sólo m = 50 restricciones y n =50 variables, tendría (100!)/(50!) ≈ 10^29 sistemas de ecuaciones que resolver. En contraste, el método símplex necesitaría examinar nada más alrededor de 100 soluciones factibles en los vértices para un problema de este tamaño. este ahorro tan grande se puede obtener gracias a la prueba de optimalidad que proporciona la propiedad 3:
Propiedad 3. Si una solución factible en un vértice no tiene soluciones factibles en vértices adyacentes que sean mejores (en cuanto al valor de Z), entonces no existen soluciones factibles en un vértice que sean mejores, es decir, la solución es óptima.
A manera de ilustración de la propiedad 3 considérese la figura 5.1 (o la figura 3.3) para el ejemplo de la Wyndor Glass Co. Las soluciones facrtibles en los vértices (0,6) y (4,3) son adyacentes a la solución factible en el vértice (2,6) y ninguna te las dos tiene un valor mejor de Z. Esto implica que ninguna de las otras soluciones factibles en un vértice (0,0) y (0,4), pueden ser mejores que (2,6) y por lo tanto (2,6) debe ser óptima.
No hay comentarios.:
Publicar un comentario