Metodo Dual

MÉTODO DEL DUAL (TEORIA DE DUALIDAD)

Para hablar del método dual es importante saber que todo problema de programación lineal esta asociado con otro problema de programación lineal, conocido como su problema DUAL, juntos son llamados problemas duales ya que ambos están formados por el mismo conjunto de datos. Ambos están relacionados estrechamente, hasta el punto de que el modelo de uno puede obtenerse a partir del modelo del otro y la solución óptima del modelo del primero proporciona información completa acerca de la solución óptima del segundo.

La solución básica factible óptima de estos problemas es tal que una

puede fácilmente ser usada para la solución de la otra. La dimensión del problema de programación

lineal influencia la elección del cálculo del primo o del dual.

Si el primo tiene mas ecuaciones que variables, es frecuentemente mas fácil obtener la solución del

dual ya que menor numero de iteraciones son requeridas. Además si el primo tiene solución, el dual

tendrá solución. Una vez que el problema dual es formulado, el procedimiento de solución es

exactamente el mismo que para cualquier problema de programación lineal.

Mecánicamente el dual es formulado partiendo del problema primo en la siguiente forma:

Si el primo es un problema de Maximización, el dual es un problema de Minimización y viceversa.

1. Los coeficientes de la función objetivo del primo se convierten en las restricciones constantes de

las ecuaciones del dual.

2. Las restricciones de las ecuaciones del primo se convierten en los coeficientes de la función

objetivo del dual.

3. Los coeficientes de las variables del dual en las ecuaciones restrictivas son obtenidas sacando la

transpuesta de la matriz de coeficientes del primo ( los arreglos de los coeficientes en las columnas

del primo se convierten en los coeficientes de las filas en el dual y viceversa ).

4. Los signos de la desigualdad son invertidos.

5. Las Xn variables del primo son remplazadas por Wm variables en el dual.

Notación matemática:

Primo Contiene m ecuaciones y n variables.

Dual Contiene n ecuaciones y m variables.

La notación matricial del Primo es:

Max Z = CX

Sujeto a :

AX £ b

x ³ 0

La notación matricial del Dual es:

Min Z = b

t

W

Sujeto a :

A

tW ³ C

t

W ³ 0

EL MÉTODO DUAL SIMPLEX

Como sabemos, el método simplex es un algoritmo iterativo que iniciando en una solución básica factible pero no óptima, genera soluciones básicas factibles cada vez mejores hasta encontrar la

...