Método dual simplex

UNIVERSIDAD NACIONAL DE SAN AGUSTIN DE AREQUIPA

FACULTAD DE INGENIERIA DE
PRODUCCION Y SERVICIOS

ESCUELA PROFESIONAL DE
INGENIERIA INDUSTRIAL

CURSO:INVESTIGACIÓN DE OPERACIONES 1

TEMAS:
DUAL SIMPLEX
PROFESOR:
ING. EFRAIN MURILLO
AÑO:
VI SEMESTRE- “b”.

2011

MÉTODO DUAL SIMPLEX

Como sabemos, el método simplex es unalgoritmo iterativo que iniciando en una solución básica factible pero no óptima, genera soluciones básicas factibles cada vez mejores hasta encontrar la solución óptima (sí esta existe). Nótese que labase de su lógica es mantener la factibilidad, mientras busca la optimalidad. Pero surge la posibilidad de usar otro esquema igualmente iterativo, que como contraparte del simplex, comienza en unasolución básica óptima, pero no factible y mantiene la inmejorabilidad mientras busca la factibilidad. Con este procedimiento se llega igualmente a la solución óptima.
El nuevo algoritmo fue desarrolloen 1954 por C. E. Lemke y se conoce con el nombre de Método Dual-Simplex. A continuación se presenta su estructura y un ejemplo para ilustrar su aplicación.
Como en le método simplex (primal), labase el método dual es que cada iteración siempre este asociada a una solución básica. Las condiciones de optimalidad y factibilidad se establecen para preservar la optimalidad de las soluciones básicasy al mismo tiempo mover las iteraciones de la solución hacia la factibilidad.

Condición de Factibilidad: la variable de salida x, es la variable básica que tiene el valor más negativo (los empatesse rompen en forma arbitraria). Si todas las variables básicas son no negativas, termina el algoritmo.

Condición dual de Optimalidad: la variable de entrada se determina entre las variables nobásicas, como la que corresponde a
[pic]

Donde zj – cj es el coeficiente objetivo del renglón z en la tabla, y arj es el coeficiente negativo de restricción de la tabla, asociado con el renglón de...