Metodo Dual

Universidad de San Carlos de Guatemala
Facultad de Ingeniería
Escuela de Mecánica Industrial
Practica de Investigación de Operaciones I
Aux. Randy Monzón Garrido

MÉTODO DUAL
Practica 4

La condición de optimalidad dice que el método simplex se puede interpretar como la búsqueda de los valores de y1, y2,....ym. tales que:

Yo = Σ biyi,
i = 1

Sujeta a:Σ aij yi ≥ cj, para j = 1, 2, ...n.
i = 1

y

yi >= 0, para i = 1, 2,...m.

Pero excepto porque no se ha establecido un objetivo para la función Y0, (este problema es precisamente el PROBLEMA DUAL). Para completar la formulación, se explorará cual debe ser ese objetivo que falta.

Como Y0, es sencillamente el valor de Z, y comoel objetivo del problema PRIMAL es MAXIMIZAR Z, una reacción natural seria que Y0, se maximizara también. Sin embargo, esto no es correcto debido a una razón bastante sutil: las únicas soluciones factibles para este nuevo problema son aquellas que satisfacen la condición de OPTIMALIDAD para el problema primal. Por tanto, nada más la solución optima para el problema primal corresponde a lasolución factible para este nuevo problema. En consecuencia, el valor óptimo de Z en el problema primal es el VALOR MÍNIMO FACTIBLE de Y0, en el nuevo problema de manera que Y0, debe MINIMIZARSE.

De este modo, el problema dual se puede ver como otra forma de establecer, en términos de programación lineal, la META DEL MÉTODO SIMPLEX, a saber alcanzar una solución para el problema primal que cumpla conla prueba de optimalidad.

RESUMEN DE LAS RELACIONES PRIMAL – DUAL:

PROPIEDAD DE DUALIDAD DÉBIL: si x es una solución factible para el problema primal ÿ y es una solución factible para el problema cual, entonces:
Cx =< yb.

PROPIEDAD DE DUALIDAD FUERTE: Si X0 es una solución óptima para el problema primal y Y0 es una solución optima para el problema dual, entonces:
Cx0 = y0 b.Características Dual

1. Si el primal es un problema de maximización su dual será un problema de minimización y viceversa.

2. Los coeficientes de la función objetivo del problema primal se convierten en los coeficientes del vector de la disponibilidad en el problema dual.

3. Los coeficientes del vector de disponibilidad del problema original se convierten en los coeficientes de la función objetivo(vector de costo o precio) en el problema dual.

4. Los coeficientes de las restricciones en el problema primal, será la matriz de los coeficientes tecnológicos en el dual.

5. Los signos de desigualdad del problema dual son contrarios a los del primal.

6. Cada restricción en un problema corresponde a una variable en el otro problema. Si el primal tiene m restricciones y n variables, el dualtendrá n restricciones y m variables. Así, las variables Xn del primal se convierten en nuevas variables Ym en el dual.

TIPOS DE DUAL

❖ RELACIÓN ENTRE LOS VALORES OBJETIVO Y PRIMAL:

Los valores objetivos en un par de problemas primal-dual deben satisfacer las 2 siguientes relaciones:

1. en cualquier par de soluciones primal y dual factibles

2. en la solución optima de ambosproblemas

❖ SOLUCIÓN DUAL ÓPTIMA:

La solución dual óptima se puede determinar en forma directa a partir de la tabla primal óptima.

❖ Específicamente, establecimos que los precios duales representan el valor por unidad de los recursos PL. Por otra parte, los costos reducidos representan el incremento en las ganancias marginal o el decremento en el costo por unidad de recurso.

Ejemplo:Dado el las siguientes datos encontrar las ecuaciones de restricción, la función objetivo y resolver por el método dual.

|  |Capacidad de Producción |  |
|  |Producto 1 |Producto 2 |Producto 3 |Requerimiento Mínimo |
|Planta 1 |1...