UNIDAD 3 TEORIA DE LA DUALIDAD

TEORIA DE LA DUALIDAD

CONTENIDO:

3.1.- FORMULACION DEL PROBLEMA DUAL

3.2.- RELACION PRIMAL-DUAL

3.3.- INTERPRETACION ECONOMICA DEL DUAL

3.4.- DUAL-SIMPLEX

3.1.- FORMULACION DEL PROBLEMA DUAL

V. GAUCIN C. - 1 -

UNIDAD

2

UNIDAD 3 TEORIA DE LA DUALIDAD

Emos visto como la programación lineal puede ser usada para resolver una extensa variedad de

problemas propios de negocios, ya sea para maximizar utilidades o minimizar costos. En cada

caso la solución óptima nos explicó cómo podrían ser asignados los recursos.HEn esta sección veremos que a cada problema de programación lineal se le asocia otro problema de

programación lineal llamado el “Problema de Programación Dual”. La solución óptima del problema de

programación dual, proporciona la siguiente información respecto al problema de programación original.

La solución óptima del problema dual proporciona los precios en el mercado o los beneficios de los

recursos escasos asignados en el problema original. Por lo tanto tenemos lo siguiente:

PROBLEMA PRIMAL PROBLEMA DUAL

POR EJEMPLO: ( EL DE LA IBM QUE ESTUDIAMOS EN LA UNIDAD 2)

La IBM de México, produce y vende 2 tipos de máquinas de escribir. (Eléctricas y manuales). Cada

máquina de escribir manual es vendida con un ingreso de $40.0 y cada maquina de escribir eléctrica produce

un ingreso de $60.0, ambas máquinas tienen que ser procesadas (ensambladas y empacadas).

La IBM tiene las siguientes capacidades mensuales en cada proceso:

2,000 Horas para ensamble

1,000 Horas para empaque

El número de horas requeridas para producir un modelo terminado se da en la siguiente tabla:

V. GAUCIN C. - 2 -

Maximizar Z = Cx

Sujeto a:

Ax b

Y

X 0

Minimizar Z = Yo

Sujeto a:

YA c

Y

Y 0

UNIDAD 3 TEORIA DE LA DUALIDAD

FORMULACION DEL PROBLEMA PRIMAL-DUAL

PROBLEMA PRIMAL PROBLEMA DUAL

MODELO PRIMAL MODELO DUAL

2,000 MIN. C = 2,000 y1 + 1,000 y2

1,000

MODELO PRIMAL MODELO DUAL

V. GAUCIN C. - 3 -

Maximizar Z = 40 X1 + 60 X2

S.A

3X1 + 2X2 2,000 X1 + 2X2 1,000

OBJETIVO: Encontrar el número óptimo de máquinas de escribir a fabricar para incrementar las utilidades.

3X1 + 2X2 2,000.- las horas requeridas deben ser iguales o menores que las 2,000 horas que tiene disponible el Depto. de Ensamble.

Minimizar C = 2,000 Y1 + 1,000 Y2

S.A.

3Y1 + Y2 402Y1 + 2Y2 60

OBJETIVO: Determinar los precios a los cuales la IBM debería valorar sus recursos mínimos, para arrendar o vender, sea Y1 y Y2 la renta o venta percibida por hora para las operaciones de empacado y ensamblado.

3Y1 + Y2 40, los precios de 3Y1 + Y2 deben ser iguales o mayores a la contribución a la utilidad de $40.0

UNIDAD 3 TEORIA DE LA DUALIDAD

MAX. Z = 40X1 + 60X2 40

60

MODELO PRIMAL MODELO DUAL

FILA 1

FILA 2

COLUMNA1 COLUMNA2

CONSTRUCCION DEL MODELO DUAL A TRAVES DEL MODELO PRIMAL

Una de las condiciones para la elaboración de un planteamiento del modelo primal al dual, es que

todas las restricciones del modelo primal, deben de tener la condición de , y como MAXIMIZAR.

MODELO PRIMAL MODELO DUAL

V. GAUCIN C. - 4 -

3X1

X1

2X2

2X2+

+

3Y1 + Y2

2Y1 + 2Y2

MAXIMIZAR Z= 2X1 + 3X2 + 2X3

S.A.

X1 + 2X2 + 3X3 42X1 + X2 + X3 6

DONDE X1,X2 y X3 0

MINIMIZAR C = 4Y1 + 6Y2

S.A.

Y1 + 2Y2 22Y1 + Y2 33Y1 + Y2 2

DONDE Y1,X2 0

UNIDAD 3 TEORIA DE LA DUALIDAD

MODELO PRIMAL 1 MODELO DUAL

MODELO PRIMAL 2

MODELO PRIMAL 1 MODELO DUAL

MODELO PRIMAL 2

V. GAUCIN C. - 5 -

MAXIMIZAR Z= -10X1 + 20X2

S.A.

X1 + 2X2 42X1 - 3X2 6 (MULTIPLICAMOS ESTA ECUACION (-1) PARA CONVERTIRLA A ECUACION )

DONDE X1,X2 0

MAXIMIZAR Z= -10X1 + 20X2

S.A.

X1 + 2X2 4-2X1 +3X2 -6

DONDE X1,X2 0

MINIMIZAR C = 4Y1 – 6Y2

S.A.

Y1 – 2Y2 -102Y1 + 3Y2 20

DONDE Y1,Y2 0

MAXIMIZAR Z= 10X1 + 20X1

S.A.

X1 + 2X2 = 4 (*) 2X1 - 3X2 7 (*) EL EQUIVALENTE A ESTA ECUACION SON 2 ECUACIONES CON UNA POSITIVA Y OTRA NEGATIVA.

MAXIMIZAR Z= 10X1 + 20X1

S.A.

X1 + 2X2 4 -X1 - 2X2 -4 2X1 - 3X2 7

MINIMIZAR C = 4Y1 – 4Y2 + 7Y3

S.A.

Y1 - Y2 + 2Y3 10 2Y1 -2Y2 – 3Y3 20

UNIDAD 3 TEORIA DE LA DUALIDAD

MODELO PRIMAL 1 MODELO DUAL

MODELO PRIMAL 2

MODELO PRIMAL 1 MODELO DUAL

MODELO PRIMAL 2

V. GAUCIN C. - 6 -

MINIMIZAR Z= 10X1 - 20X2 + 10X3

S.A.

X1 + X2 – 4X3 112X1 + 6X2 + 10X3 20

MINIMIZAR Z = 10X1 – 20X2 + 10X3

S.A.

X1 + 2X2 – 3X3 = 64X1 – 11X2 + 10X3 172X1 + 5X2 + 7X3 9

MINIMIZAR C= 11Y1 + 20Y2

S.A.

Y1 + Y2 -10 Y1 + 6Y2 20-4Y1 + 10Y2 -10

PARA CONVERTIR EN MODELO DE MAXIMIZAR MULTIPLICAMOS LA ECUACION DE LA FUNCION OBJETIVO POR (-1) Y NOS QUEDA:

MAXIMIZAR Z = -10X1 + 20X2 – 10X3 S.A. X1 + X2 - 4X3 112X1 + 6X2 + 10X3 20

MAXIMIZAR Z = -10X1 + 20X2 - 10X3

S.A.

X1 + 2X2 – 3X3 6-X1 - 2X2 + 3X3 -6 -4X1 + 11X2 - 10X3 -172X1 + 5X2 + 7X3 9

MINIMIZAR C = 6Y1 – 6Y2 – 17Y3 + 9Y4

S.A.

Y1 - Y2 - 4Y3 + 2Y4 -102Y1 – 2Y2 + 11Y3 + 5Y4 20-3Y1 + 3Y2 – 10Y3 + 7Y4 -10

UNIDAD 3 TEORIA DE LA DUALIDAD

V. GAUCIN C. - 7 -