viernes, 11 de octubre de 2013

Esencia del método símplex (III)

En la sección 5.1se estudian con detalle las propiedades generales de las soluciones factibles en un vértice  para problemas de programación lineal de cualquier tamaño, al igual que las relaciones entre estas propiedades y el álgebra del método símplex que se presenta en las dos secciones siguientes. Las tres propiedades clave que forman el fundamento del método símplex se resume como sigue:

Propiedades de las soluciones factibles en un vértice.

1a. Si existe exactamente una solución óptima, entonces debe ser una solución factible en un vértice.
1b. Si existen soluciones óptimas múltiples, entonces al menos dos de ellas deben ser soluciones factibles en vértices adyacentes.

2. Existe sólo un número finito de soluciones factibles en los vértices.
3. Si una solución en un vértice es igual o mejor (según el valor de Z) que todas las soluciones factibles en los vértices adyacentes a ella, entonces es igual o mejor que todas las demás soluciones en los vértices; es decir, es óptima.

La propiedad 1 significa que la búsqueda de la solución óptima se puede reducir a la consideración de sólo las soluciones factibles en los vértices, de manera que sólo existe un número finito de soluciones que es necesario tomar en cuenta. La propiedad 3 proporciona una prueba de optimalidad muy conveniente.

No hay comentarios.:

Publicar un comentario