METODO DUAL

METODO DUAL

METODO DUAL SIMPLEX

En el algoritmo dual símplex, el problema empieza optimo y no factible. Las iteraciones sucesivas están diseñadas para avanzar hacía la factibilidad, sin violar la optimalidad. En iteración, cuando se restaura la factibilidad, el algoritmo termina.

El método dual símplex contrasta con el método regular (primal simplex), en el sentido de que las iteraciones empiezan factibles y no optimas y no continúan siendo factibles hasta que se logra la factibilidad.

En el método dual símplex, el cuadro simplex inicial debe tener un renglón objetivo optimo por lo menos con una variable básica no factible (< 0). Para mantener la optimalidad y, simultáneamente, avanzar hacia la factibilidad en cada nueva iteración, se emplearan las dos condiciones siguientes:

Condición Dual de Factibilidad: La variable de salida, x, es la variable básica que tiene el valor más negativo, con empates que se rompen arbitrariamente. Si todas las variables básicas son no negativas, el algoritmo termina.

Condición Dual de Optimalidad : La variable de entrada esta determinada entre las variables no básicas como la correspondiente a

min {øzj - cj ø, rj < 0}

no básicas rj

Donde rj es el coeficiente de restricción de la tabla símplex asociada con el renglón de la variable de salida x, y la columna de la variable de entrada Xj. Los empates se rompen arbitrariamente.

Cada problema de programación lineal tiene un segundo problema asociado con el. Uno se denomina primal y el otro dual. Los 2 poseen propiedades muy relacionadas, de tal manera que la solución óptima a un problema proporciona información completa sobre la solución óptima para el otro.

Las relaciones entre el primal y el dual se utilizan para reducir el esfuerzo de computo en ciertos problemas y para obtener información adicional sobre las variaciones en la solución óptima debidas a ciertos cambios en los coeficientes y en la formulación del problema. Esto se conoce como análisis de sensibilidad o post-optimidad.

DEFINICION DEL PROBLEMA DUAL.

Para poder elaborar el problema dual a partir del primal, este se debe presentar en su forma canónica de la siguiente forma:

Maximizar

Sujeto a:

El problema dual se puede obtener a partir del problema primal y viceversa de la siguiente manera:

1. Cada restricción de un problema corresponde a una variable en el otro.

2. Los elementos del lado derecho de las restricciones en un problema son iguales a los coeficientes respectivos de la función objetivo en el otro.

3. Un problema busca maximizar y el otro minimizar.

4. El problema de maximización tiene restricciones que y el problema de minimización tiene restricciones que.

5. Las variables en ambos casos son no negativas.

EJEMPLO:

Considere el problema primal siguiente:

Maximizar

Sujeto a:

Elaborar el dual a partir del primal.

Minimizar

Sujeto a:

Cuando el problema primal no está en forma canónica, es necesario hacer ajustes para poder presentarlo así. Los cambios más frecuentes son:

1. Si la función objetivo es minimizar, se puede transformar a una función objetivo de maximizar de la siguiente forma:

Minimizar

Maximizar

2. Una restricción mayor o igual que se transforma en una restricción menor o igual que de la siguiente manera:

3. Una restricción de igualdad se transforma en 2 inecuaciones.

EJEMPLO: (PRIMAL).

Maximizar

Sujeto a:

Maximizar

Sujeto a:

Dual

Miminizar

Sujeto a: