EL PROBLEMA DUAL Y EL METODO SIMPLEX
En el desarrollo de la programación Lineal, se descubrió la existencia de un
problema que se encuentra estrechamente relacionado con un problema de
Programación Lineal dado: Dicho problema se denominó PROBLEMA DUAL.
Cada problema dado (Problema principal, Problema primo, Problema primero), de
programación lineal, tiene un problema dual que tiene las siguientes
características:
1. En problemas de un gran número de restricciones, resolver el problema dual en
la computadora es más eficiente que resolver el problema principal.
2. En algunas ocasiones resulta más sencilla la resolución del problema dual que
la del problema principal, en
términos de menor número de
iteraciones.
3. Los valores óptimos de las
variables del dual, proporcionan una
interpretación económica del
problema principal, interesante.
4. Algunas veces se puede evitar el
uso de las variables artificiales
(Superávit), mediante la aplicación
del método de solución denominado Dual – Simplex, sobre el problema dual.
5. Facilita el estudio del impacto sobre la optimalidad por cambios en el problema
original.
Formularemos el problema dual y mostrar el método de solución para el problema
dual, denominado Método Dual-Simplex, para problemas de maximización, ya que,
por medio de la regla de equivalencia (Min(z) = Max(-z))Toda formulación de un
problema de programación lineal se puede expresar de la forma estándar:
Maximice (z), con todas las restricciones <
Si tenemos un problema de programación lineal expresado de la forma:
- 85 -
Observe que cada restricción del problema principal está representada por una
variable en el dual.
Otro ejemplo numérico es el siguiente:
- 86 -
Cada uno de los recursos del problema principal estará representado por una
variable en el problema dual.
Entre el problema principal y el problema dual existen las siguientes relaciones:
1. El dual del dual, tiene como resultado el problema principal.
2. Una restricción que es una igualdad en el problema principal, genera una
variable en el dual sin restricción en el signo
3. Una variable del problema principal, sin restricción en el signo, genera una
restricción de igualdad en el problema dual.
4. El número de restricciones del problema principal es igual al número de
variables en el problema dual.
5. El número de variables del problema principal es igual al número de
restricciones en el problema dual.
EL MÉTODO DUAL – SIMPLEX
Una vez formulado el problema dual, debemos encontrar su solución. El método a
emplear será el denominado Método Dual-Simplex el cuál empieza con una
solución óptima o mejor que óptima (Zj – Cj > 0; ∀j), pero no factible (Algunos bi
son < 0), y se mueve hacia el óptimo mediante iteraciones que mejoran su
factibilidad conservando su optimalidad.
Observe que es lo contrario al método Simplex, en donde se empieza mediante
una solución factible pero no óptima y mediante iteraciones se mejora la
optimalidad, conservando la factibilidad.
Esto se ilustra mediante la siguiente gráfica:
- 87 -
ALGORITMO PARA MAXIMIZAR EN EL MÉTODO DUAL – SIMPLEX
Se requiere que el problema esté expresado en términos de Maximizar la Función
objetivo y todas sus restricciones con mayor ó igual (>)
Variable que sale de la Base: Aquella que tenga el valor menos factible ó sea la
más negativa, matemáticamente: XB,r = Mínimo i XB,i , XB,i < 0 ; XB,i < 0 implica que la
solución es NO factible.
Variable que entra a la Base: Aquella variable que tenga el valor menos negativo
en su expresión: ( Zj - Cj ) / ar,j , matemáticamente: (ZK - CK ) / ar,k = Máximo j (Zj - Cj )
/ ar,j ; Siendo ar,j < 0 .
El siguiente ejemplo ilustra un paralelo entre el Método Simplex y el Método Dual –
Simplex en donde se resalta para cada iteración, la relación entre los dos (2)
Métodos.
Hallar la solución óptima al problema siguiente:
- 88 -
89
Observe que en el Dual – Simplex se hizo uso de la regla de equivalencia,
multiplicando la función objetiva por (-1), y al final, nuevamente se multiplicó el valor de
Z por (-1).
En cada iteración del Método Simplex se muestra que:
1. Los Zj – Cj de las variables de holgura X3,X4,X5 (Z3-C3 , Z4-C4 , Z5-C5) son los valores
de las variables reales del Dual (Y1,Y2,Y3)
2. Los Zj – Cj de las variables reales X1,X2 (Z1-C1 , Z2-C2) son los valores de las variables
de holgura del Dual (Y4,Y5)
En cada iteración del Método Dual – Simplex se muestra que:
1. Los Zj – Cj de las variables de holgura Y4,Y5 (Z4-C4 , Z5-C5) son los valores de las
variables reales del problema principal (X 1,X2)
2. Los Zj – Cj de las variables reales Y1,Y2 ,Y3 (Z1-C1 , Z2-C2 , Z3-C3) son los valores de
las variables de holgura del problema principal (X 3,X4,X5)
En general se observa al armar una tabla que los encabezados del primal están en
posición horizontal mientras que para leer los del dual necesitamos girar el dibujo 90º.
Como dijimos:
1) Los parámetros de la restricción son los coeficientes de una variable en el otro
2) Los coeficientes de la función objetivo en un problema son los valores del lado
derecho en el otro.
La solución óptima del dual proporciona los precios sombra.
Veamos una aplicación de la tabla: supongamos el siguiente primal y su dual
PRIMAL DUAL
Max Z = 3 X1 + 5 X2 Min Y0 = 4Y1+12 Y2 +18 Y3
s.a. X1 <= 4 Y1 + 3Y 3 >= 3
2 X2 <= 12 2 Y2 + 2 Y3 >= 5
3X1 + 2 X2 <= 18 Y1,Y2,Y3 >=0
X1,X2 >= 0
Correspondencia entre los elementos del Problema Primal – Dual
Restricción i Variable i
Función Objetivo Lados derechos.
- 90 -
