Relaciones Básicas Entre Primal-Dual

METODOS CUANTITATIVOS APLICADOS A LA ADMINISTRACION - 2005 -
RELACIONES PRIMAL-DUAL en PROGRAMACION LINEAL

DUALIDAD en Programacin Lineal - 1/5 - Prof. Hugo Roche

RELACIONES BASICAS ENTRE PRIMAL-DUAL

(1) Propiedad de Dualidad Dbil.

Si x es una Solucin Factible para el Problema Primal e y es una Solucin Factible para
el Problema Dual, entonces cx yb

Esta Propiedad describe la relacin entre cualquier par de soluciones factibles del Primal
y del Dual respectivamente.
Ver Ejemplo Wyndor Glass Co.. (Tabla N 3 ). Una Sol. Factible cualquiera para el
Primal es x = (0,6) que corresponde a una Z=30. Una Sol. Factible cualquiera
para el Dual es y = (3, 5/2, 0) que corresponde a una funcin objetivo W=42.

(2) Propiedad de Dualidad Fuerte.

Si x* es una Solucin Optima para el Problema Primal e y* es una Solucin Optima para
el Problema Dual, entonces cx* = y*b

Estas dos propiedades ( 1 ) + ( 2 ) implican que cx <ybpara soluciones factibles si una o
ambas no son ptimas para sus PL respectivos, o cx =yb si son ptimas.

(3) Propiedad de Soluciones Complementarias

En cada iteracin, el mtodo Simplex identifica de manera simultnea una solucin FEV x
para el problema PRIMAL y una solucin complementaria y para el problema DUAL
(disponible en el Rengln 0 como coeficientes de las variables de holgura) donde :
cx =yb
Si xno es ptima para el PRIMAL, entonces yno es factible para el problema DUAL.

Ver Ejemplo Wyndor Glass.
En la FEV x = (0,6) el PRIMAL alcanza un valor Z=30, pero no es ptimo pues existen
otros FEV adyacentes que mejoran la Funcin Objetivo. A esta solucin en el PRIMAL
corresponde una Solucin y = (0, 3/2, 0) que corresponde a una Funcin Objetivo en el
Dual W=30, pero que no es factible pues no satisface la 2 Restriccin del DUAL.

(4) Propiedad de Soluciones Complementarias ptimas

En la ltima iteracin, el mtodo Simplex identifica de manera simultnea una solucin
ptima x* para el problema PRIMAL y una solucin Optima complementaria y* para el
problema DUAL (disponible en el Rengln 0 como coeficientes de las variables de
holgura) donde :

cx* =y*b

Los y* representan los Precios Sombra para el Problema Primal.



(4.a) Propiedad de Soluciones Bsicas Complementarias.

Cada solucin Bsica en el problema PRIMAL tiene una solucin Bsica Complementaria
en el problema DUAL, donde los valores respectivos de la funcin objetivo son iguales
Z=W.

A partir del Rengln 0 de la Tabla SIMPLEX para la Solucin Bsica del PRIMAL, la
solucin bsica DUAL complementaria (y, z-c) se encuentra a nivel de los coeficientes de
las variables de holgura y de las variables de decisin respectivamente, como lo indica la
siguiente Tabla :

(4.b) Propiedad de Holgura Complementaria (Relacin entre Variables Bsicas y No-
Bsicas del Primal y del Dual)

Dada la asociacin entre variables dadas en la Tabla anterior, las variables en la Solucin
Bsica Primal y en la Solucin Bsica Dual complementaria satisfacen las siguientes
relaciones de holgura complementaria:

Esta relacin es simtrica, de manera que las dos soluciones bsicas son
complementarias entre s.

(5) Propiedad de Simetra

Para cualquier problema PRIMAL y su Problema DUAL, las relaciones entre ellos deben
ser simtricas debido a que el DUAL de este problema Dual es el problema PRIMAL.
x
1
x
2
x
3
x
4
x
5
L.D.
0 (0) z
1
-c
1
z
2
-c
2
y
1
y
2
y
3
0
x1 z1-c1
x2 z2-c2
x3 y1
x4 y2
x5 y3
Variables de Decisin
Variables de Holgura
Variables de Superavit
(Costos Reducidos)
Variables de Decisin del
DUAL
(Precios Sombra)
PROBLEMA PRIMAL: Ej. " Wyndor Glass Co."
Coeficientes Tabla Simplex
N
Iteracin
N
Rengln
PRIMAL DUAL
Var. Bsica Var. No Bsica "m" variables
Var. No Bsica Var. Bsica "n-m" variables


TEOREMA DE LA DUALIDAD

EN PROGRAMACION LINEAL

Las siguientes relaciones son las nicas relaciones posibles entre los Problemas PRIMAL y
DUAL de un Problema de Programacin Lineal :

1. Si un Problema PRIMAL tiene SOLUCIONES FACTIBLES y una FUNCION
OBJETIVO ACOTADA (por lo tanto existe al menos una solucin ptima) entonces
ocurre lo mismo con el DUAL. Esta relacin tambin es vlida de manera simtrica. En
estas condiciones se aplican las propiedades de Dualidad Dbil y Fuerte.

2. Si uno de los Problemas (Primal o Dual) tiene SOLUCIONES FACTIBLES Y UNA
SOLUCIN OBJETIVO NO ACOTADA (es decir no existe solucin ptima), entonces
el otro Problema no tiene SOLUCIONES FACTIBLES.

3. Si un Problema (Primal o Dual) NO TIENE SOLUCIONES FACTIBLES, entonces el
otro Problema NO TIENE SOLUCIONES FACTIBLES o bien la funcin objetivo es NO
ACOTADA.



EJEMPLO: WYNDOR GLASS Co.

Problema PRIMAL : Wyndor Glass Co

Max Z = 3 x
1
+ 5 x
2

sr
x
1
4
2 x
2
12
3 x
1
+ 2 x
2
18

x
1
0 , x
2
0

Problema DUAL : Wyndor Glass Co

Min y0 = 4 y
1
+ 12 y
2
+ 18 y
3

sr
y
1
+ 3 y
3
3
2 y
2
+ 2 y
3
5

y
1
0 , y
2
0 , y
3
0

Tabla N 1 : TABLA SIMPLEX del Ejemplo Wyndor Glass Co.
Problema Primal

N Iter. N Ec. Var. Bsica Z X
1
X
2
X
3
X
4
X
5
Lado
Derecho
(0) Z 1 -3 -5 0 0 0 0
(1) X
3
0 1 0 1 0 0 4
(2) X
4
0 0 2 0 1 0 12
(3) X
5
0 3 2 0 0 1 18
(0) Z 1 -3 0 0 5/2 0 30
(1) X
3
0 1 0 1 0 0 4
(2) X
2
0 0 1 0 0 6
(3) X
5
0 3 0 0 -1 1 6
(0) Z 1 0 0 0 3/2 1 36
(1) X
3
0 0 0 1 1/3 -1/3 2
(2) X
2
0 0 1 0 0 6
(3) X
1
0 1 0 0 -1/3 1/3 2
0
1
2


Tabla N 2 :

Coeficientes del Rengln 0 del Ejemplo Wyndor Glass Co.y la Solucin del DUAL

Tabla N 3 :

SOLUCIONES BASICAS COMPLEMENTARIAS PRIMAL-DUAL
Ejemplo Wyndor Glass Co.

x
1
x
2
x
3
x
4
x
5
L.D. z
1
-c
1
z
2
-c
2
y
1
y
2
y
3
W
0 (0) -3 -5 0 0 0 0 -3 -5 0 0 0 0
1 (0) -3 0 0 5/2 0 30 -3 0 0 5/2 0 30
2 (0) 0 0 0 3/2 1 36 0 0 0 3/2 1 36
N
Iteracin
PROBLEMA PRIMAL
SOLUCION Variables del DUAL N
Rengln
Coeficientes Tabla Simplex
SOLUCION PROBLEMA DUAL
Solucin Bsica Solucin Bsica
( x
1
, x
2
, x
3
, x
4
, x
5
) ( y
1
, y
2
, y
3
, y
4
, y
5
)
1 (0, 0, 4, 12, 18) SI 0 NO (0, 0, 0, -3, -5)
2 (4, 0, 0, 12, 6) SI 12 NO (3, 0, 0, 0, -5)
4 (4, 3, 0, 6, 0) SI 27 NO ( -9/2, 0, 5/2, 0, 0 )
5 (0, 6, 4, 0, 6) SI 30 NO ( 0, 5/2, 0, -3, 0 )
6 (2, 6, 2, 0, 0) SI 36 SI ( 0, 3/2, 1, 0, 0)
7 (4, 6, 0, 0, -6) NO 42 SI ( 3, 5/2, 0, 0, 0 )
8 (0, 9, 4, -6, 0) NO 45 SI ( 0, 0, 5/2, 9/2, 0)
PROBLEMA PRIMAL PROBLEMA DUAL
N Sol.
Factible?
Z = W
Factible?

Relaciones Básicas Entre Primal-Dual

Cargado por

Copyright:

Formatos disponibles

Relaciones Básicas Entre Primal-Dual

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Relaciones Básicas Entre Primal-Dual

Cargado por

Copyright:

Formatos disponibles

METODOS CUANTITATIVOS APLICADOS A LA ADMINISTRACION - 2005 -

RELACIONES PRIMAL-DUAL en PROGRAMACION LINEAL

También podría gustarte