Dual

Clase # 10

Teoría dual e interpretación económica

Asociado a todo problema de P.L, existe otro problema lineal llamado dual. Por tanto al problema original se le llama primal.

10-1

10-2

TEORÍA DE DUALIDAD

El análisis de sensibilidad se enriquece cuando se estudia el problema dual, dado que la solución del dual corresponde a los precios sombra de las restricciones del primal.Max Z =Σ cj xj
j=1

n

Min y0 =Σ bi yi
i=1

m

Σ aij xj j=1

s.a n

≤

bi

para i = 1,2,....,m

Σ aijyi i=1

s.a m

≥ cj

para j = 1,2,....,n

xj ≥ 0 para j= 1, ...,n
10-3

yi ≥ 0 para i= 1, ...m
10-4

En notación matricial

Veamos como ejemplo el caso de la Wyndor.
Max Z = 3x 1 + 5x2 S.a x1 + 0 x 2 ≤ 4 0 x 1 + 2 x 2 ≤ 12 3 x 1 + 2 x 2 ≤ 18 x 1 , x 2≥ 0
10-5Max Z = c x
S. a

Min y 0 = y b
S. a

Min y 0 = 4y1 + 12y 2+ 18y 3 S.a 1 y 1 + 0 y 2 + 3 y3 ≥ 3 0 y 1 + 2 y2 + 2 y3 ≥ 5 y1 , y2 , y3≥ 0
10-6

A x ≤ b x ≥ 0

y A ≥c y ≥ 0

1

Ahora en forma matricial. Max Z = 3 5 S.a
1 0 3 0 2 2 x1 x2 x1 ≤ x2 0 y1 y2 y3 ≥ 4 12 18 x1 x2

Para hallar la correspondencia entre problemas se utiliza la tabla primal-dual.

ambos

12 18

m

Miny0 = y 1 y 2 y 3 4 S.a
y1 y2 y3 1 0 3 0 2 2 0

de

Problema Primal
Coeficiente de

a

o db u l a el

y1 y2
Coeficiente

x1 a 11 a 21

x2 a 12 a 22

a 2n ≤ b2

≥ 3 5

ym

a m1
≤

a m2
≤

a mn ≤ bm
≤

0

0
10-7

L a d derecho

≥ 0

c1

c2

cn
10-8

Se puede observar el problema primal por filas, es decir verticalmente. Horizontalmente, esto es porcolumnas se observa el problema dual

Fundamentalmente.

m

a

Problema Primal x1 1 0 3
≤

y1
Coeficiente

x2 0 2 2
≤

Coeficientes F . O

Coeficiente de

Un Problema
Restricción i Función objetivo

de

Otro problema
Variable i Lados derechos

Lado derecho

e

≤ 4 ≤ 12 ≤ 18

a u d ol b

l

y2 y3
o d a L d e r e c h o

P

r

3

5

10-9Coeficientes F.O minimizar
10-10 10-12

xn a 1n ≤ b 1

Lado derecho

de

Obtencion de cualquier tabla a partir de la tabla simplex inicial

Origen del problema dual.

1 0

cB B-1 B-1

1 0

-c A

0 I

0 = b

1 0

cB B-1 A - c cB B-1 B-1 A B-1

cB B-1 b B-1 b
10-11

P

r

Si hacemos: y = cB B-1 = (y1,y 2,.. y m) y0 = cB B-1 b = y b =Σ biyi z= cB B-1 A = yA = (z1,z 2 ,.. z n)donde z j = Σ aijyi donde c B son los coeficientes de las variables
basicas en la funcion objetivo y B son los vectores columna en (A,I) de esas mismas variables.

o

de

la

2

Renglón (o) tabla simplex
Iter V.B Ec # Z
Cualquiera

La condición de optimalidad dice que:
x n x n+1
zn-cn y1

Coeficiente de

x1

x2

x n+m
ym

L.D y0

Z

0 1 z1 -c1 z2 -c2

zj - cj ≥0 yi≥ 0 para j = 1,...,n i = 1,....,m

En términos de esta notación, el método simplex trata de buscar un conjunto de variables básicas y la solución B.F correspondiente, tal que todos los coeficientes en el renglón (0) sean no negativos
10-13

10-14

Iter

Problema primal

Problema dual

Renglón (0) 0 1 2
[-3 -5 [-3 0 0 0 0

y 1 y 2 y 3 z1 -c1 z2 -c2
0] 0 0
5/2 3/2

0 0 1-3 -3 0

-5 0 0

0 30 36

0 5/2 0 30 ] 0 0 3/2 1 36 ] 0

[0 0

Cuando se está resolviendo el problema primal, el problema dual es no factible. Sólo se vuele factible cuando se halla la solución óptima.
Veamos algunas propiedades entre el primal y el dual
10-16

Donde z1-c1 = y 1 + 3y3 - 3 z2-c2 = 2y2 + 2y 3 - 5

Valores de las variables de exceso para el problema dual
10-151.Propiedad de dualidad débil.

c x≤ y b

2.Propiedad de dualidad fuerte.

Cualquier solución factible en el primal tiene un valor menor o igual que una solución factible en el dual
x1 x2

c x * = y* b

=

3 3 1 1 2

Z = c x = 24 y0 = y b = 52

y1 y2 y3 =

En el óptimo ambas soluciones son iguales.

Siempre se cumple porque el valor máximo factible de Z es igual al valor mínimo...