sábado, 21 de diciembre de 2013

El método símplex comienza con una solución básica factible

El método símplex comienza con una solución básica factible y se mueve en forma iterativa a una solución básica adyacente mejor, hasta que logra una solución óptima. Cómo se alcanza la solución básica factible adyacente en cada iteración?

Recuérdese que para el problema original se obtiene una solución en un vértice adyacente a partir de la solución actual cuando: 1) se elimina una ecuación de frontera (ecuación de definición) del conjunto n restricciones que definen la solución actual, 2) se hace un movimiento alejándose de la solución actual, enla dirección factible a lo largo de las (n-1) restricciones de frontera (una arista de la región factible) restantes y 3) el movimiento se detiene al encontrar la primera restricción (ecuación de definición) nueva.

De manera equivalente, en la terminología nueva el método simplex llega a una solución básica factible adyacente a partir de la solución actual cuando: 1) se elimina una variable (la variable básica entrante) del conjunto de n variables no básicas que definen la solución actual, 2) se aleja de la solución actual incrementando el valor de esta variable (y ajustando las otras variables básicas para que sigan satisfaciendo el sistema de ecuaciones) y manteniendo las (n-1) variables restantes a nivel cero y 3) se detiene cuando el valor de la primera variable básica (la variable básica que sale) llega a cero (a su ecuación de frontera). Con cualquiera de estas dos interpretaciones, la elección entre las n alternativas en el paso 1 se hace escogiendo aquella que da la tasa más alta para mejorar el valor de Z (por cada unidad de incremento de la variable básica entrante) durante el paso 2.

No hay comentarios.:

Publicar un comentario