Clase10 - teoria dual e interpretacion economica

Clase # 10

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

Teoría dual e interpretación económica

10-1

10-2

TEORÍA DE DUALIDAD n

Max Z =Σ cj xj

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.

j=1

s.a n

Σj=1 aij xj

≤

m

Min y0 =Σ bi yi i=1

s.am

bi

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

xj ≥ 0 para j= 1, ...,n

Σi=1 aijyi

≥ cj

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

yi ≥ 0 para i= 1, ...m

10-3

En notación matricial

Max Z = c x S. a

A x ≤ b x ≥ 0

10-4

Veamos como ejemplo el caso de la Wyndor.

Min y 0 = y b S. a

y A ≥c

Max Z = 3x 1 + 5x2 S.a

Min y 0 = 4y1 + 12y 2+ 18y 3 S.a

x1 + 0 x 2 ≤ 4

1 y 1 + 0 y 2 + 3 y3 ≥ 3

0 x 1 + 2 x 2 ≤ 12

y ≥ 0

3 x 1 + 2 x 2 ≤ 18 x 1 , x 2≥ 0 10-5

0 y 1 + 2 y2 + 2 y3 ≥ 5 y1 , y2 , y3≥ 0 10-6

1

la de

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

0

0 3

2 2

≥ 3 5

0

≥ 0

y1 y2 y3 ≥

0

0

0

y2

a 21

a 22

a 2n ≤ b2

a m1

a m2

a mn ≤ bm

c1

c2

cn

ym

Coeficientes F.O r minimiza

x2

18

1

≤

x1

y1 y2 y3

≤

4 12

x1 ≤ x2

xn a 1n ≤ b 1

≤

2 2

y1

x2 a 12

o

0

0 3

P

1

18

x1 a 11

L a d derecho

S.a

r

S.a

Lado derecho

Coeficiente de

12

m

x2

o db u l a el

Min y0 = y 1 y 2 y 3 4

Coeficiente

de

x1

Max Z = 3 5

ambos

Problema Primal

a

Ahora en forma matricial.

10-8

de

10-7

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

m

a

Fundamentalmente.

2

≤ 12

3

2

≤ 18

≤

3

5

o d a L d e r e c h o

0

y3

≤ 4

Un Problema

Otro problema

Restricción i

Variable i

Función objetivo

Lados derechos

10-9

10-10

de

P

Coeficiente

y2

≤

e l

x2 0

r

y1

x1 1

ab u o ld

Lado derecho

Coeficientes F . O

Problema Primal Coeficiente de

Obtencion de cualquier tabla a partir de la tabla simplex inicial

1 0

1 0

cB B-1 B-1

1

-c

0

0

0

A

I

b

=

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

B-1

cB B-1 b B-1

Origen del problema dual.

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

b

(A,I) de esas mismas variables. 10-11

10-12

2

Renglón (o) tabla simplex Coeficiente de

Iter V.B Ec # Z Cualquiera

Z

La condición de optimalidad dice que:

x1

x2

x n x n+1

0 1 z1 -c1 z2 -c2

zn-cn

x n+m

y1

ym

L.D y0

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

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

i = 1,....,m

10-13

Problema primal

Iter

Renglón (0)

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

0

0

-3

-5

0

0 5/2 0 30 ] 0

5/2

0

-3

0

30

0 3/2 1 36 ] 0

3/2

1

0

0

36

0

[-3 -5

0 0 0

1

[-3

2

[0 0

0

Problema dual

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

Valores de las variables de exceso para el problema dual

10-14

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-15

1.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

=

3 3

y1 y2 y3 =

Z = c x = 24 1

1

2

10-16

c x * = y* b

En el óptimo ambas soluciones son iguales.

y0 = y b = 52

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

10-17

10-18

3

3.Propiedad de soluciones complementarias. En cada iteración, el simplex determina una solución FEV X del primal, y una solución complementaria Y del dual que puede ser no factible. Es decir, en cada paso se obtienen variables básicas para el primal, y los valores de las variables de holgura son las soluciones del dual

4.Propiedad de soluciones complementarias óptimas. En la tabla simplex final, se obtiene la solución óptima x* del primal, y se obtiene la solución óptima complementaria y* del dual, y en este punto ambas son factibles.

c x * = y* b

cx= y b Los valores de yi* se denominan precios sombra para el problema primal. 10-19

10-20

5.Propiedad de simetría. RELACIONES ENTRE LOS PROBLEMAS PRIMAL Y DUAL 1. Si un problema tiene soluciones factibles y funcion objetivo acotada, entonces el otro tambien y los valores de la funcion objetivo en el optimo son iguaales.

Para cualquier problema, el dual del dual es el primal.

2. Si uno de los problemas tiene soluciones factibles y funcion objetivo no acotada, entonces el otro es no factible. 3. Si un problema no tiene soluciones factibles, entonces el otro no tienes soluciones factibles o tiene la funcion objetivo no acotada

10-21

10-22

4