metodo Dual y Metodo Dual Simplex

El Problema Dual y el Método Dual Simplex

Capítulo 8
El problema Dual y el Método Dual Simplex

Introducción
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, Problemaprimero), de programación lineal, tiene un problema dual que tiene
las siguientes muy interesantes 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 deiteraciones.
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-Avit), 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 elproblema original.
El presente capítulo tiene como objetivo principal, formular 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 lasrestricciones <
115

El Problema Dual y el Método Dual Simplex
Si tenemos un problema de programación lineal así:

Existe otro problema, el
Dual, que se expresa así:

Problema Principal

Problema Dual

En donde:
Problema Principal

Problema Dual

El siguiente ejemplo numérico ilustra lo anterior:
Problema Principal

Problema Dual

Fíjese que cada restricción del problema principal está representadapor una variable en el
dual.
Otro ejemplo numérico es el siguiente:
116

El Problema Dual y el Método Dual Simplex
Problema Principal
Max ZX = 3X1 –
c.s.r.
X1
< 4
X2 < 6
X1 + X2 < 5
- X2 < -1

2X2
(Y1)
(Y2)
(Y3)
(Y4)

Problema Dual
Min ZY = 4Y1 + 6Y2 + 5Y3 - Y4
c.s.r.
Y1
+ Y3
> 3
Y2 + Y3 - Y4 > -2
YJ > 0 ; J = 1, 2, 3, 4

XJ > 0 ; J = 1, 2
El problema principal tiene cuatro (4) restricciones,entonces el dual tendrá cuatro (4)
variables. 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 sinrestricció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 formuladoel 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. Fíjese que es
lo contrario al método Simplex, en donde se empiezamediante 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:

117

El Problema Dual y el Método Dual Simplex
Solución Optima
y Factible

Método Simplex
Solución Factible
Pero NO Óptima

Método Simplex
Mejora su Optimalidad
Conservando su Factibilidad

Método Dual Simplex
Solución NO...