INVESTIGACIÓN DE OPERACIONES I DUALIDAD Y ANALISIS DE SENSIBILIDAD

UNIVERSIDAD NACIONAL DE INGENIERIA [pic 1]

        [pic 2]

        INVESTIGACIÓN DE

      OPERACIONES  I

DUALIDAD Y ANALISIS

DE  SENSIBILIDAD

        Profesor: Ing. Luis Medina Aquino

                            2020-1

DUALIDAD

Asociado con cualquier problema de programación lineal (PPL) existe otro llamado DUAL. Conocer la relación de un PPL y su dual es vital para entender el análisis de sensibilidad.

Cuando se habla del dual de un PPL entonces este último se denomina PRIMAL. Si el PPL primal es un problema de maximización, entonces su dual será un problema de minimización y viceversa. Por conveniencia la variable de la función objetivo del primal se denomina Z, y sus variables primales de decisión se denominan Xi. En el caso del dual la variable de la función objetivo se denomina W, y sus variables duales se denominan Yj.

Primero aprenderemos como hallar el programa dual de un problema primal de maximización, con todas sus variables no negativas y cuyas restricciones son todas del tipo menor o igual (Problema estándar de maximización).

Un problema estándar de maximización se puede escribir como:

Maximizar Z = C1 X1 + C2 X2 + ...... + Cn Xn

Sujeto a:

                a11 X1 + a12 X2 + ..... + a1n  ≤  b1

                a21 X1 + a22 X2 + ..... + a2n  ≤  b2

                    ....          ......       .....     ....        ...

                am1 X1 + am2 X2 + ..... + amn  ≤  bm

                        Xi  ≥ 0  (i = 1, 2, ... , n)

El dual de un problema de maximización se define como:

Minimizar W = b1 Y1 +  b2 Y2 + ..... + bm Ym

Sujeto a:

                a11 Y1 +  a21 Y2 + .... +  am1 Ym  ≥  C1

                a12 Y1 +  a22 Y2 + .... +  am2 Ym  ≥  C2

                    ....          ......       .....     ....        ...

                a1n Y1 +  a2n Y2 + .... +  amn Ym  ≥  C2

                        Yj  ≥ 0  (j = 1, 2, ... , m)

Encuentre el dual de:

[pic 3][pic 4]

Dual de un problema no estandar

No todos los problemas de programación lineal tienen la forma del problema de maximización estándar.

Pasos:

1. Identifique las variables correspondientes en el dual de su problema primal.
2. Aplique el mismo análisis del problema estándar para hallar los coeficientes de la función objetivo, restricciones y de sus respectivos lados derechos.
3. Aplique la siguiente tabla de signos:

                 Modelos max                Modelo min

                Xi ≥ 0           ⇔  la iésima restricción es ≥

                Xi ≤ 0           ⇔  la iésima restricción es ≤

                Xi  srs          ⇔  la iésima restricción es =

la iésima restricción es ≤ ⇔               Yj ≥ 0

la iésima restricción es ≥ ⇔               Yj ≤ 0

la iésima restricción es = ⇔               Yj srs

OBSERVACIÓN: EL DUAL DEL PROBLEMA DUAL ES OTRA VEZ EL PROBLEMA PRIMAL

TEOREMA DEL DUAL: EL VALOR OPTIMO Z DEL PROBLEMA PRIMAL ES IGUAL AL VALOR OPTIMO W EN EL DUAL

[pic 5][pic 6]

¿Cómo leer la solución óptima del Dual desde la tabla óptima del primal de un problema de maximización? 

Valor en el óptimo de la variable yj del Dual es:
 

ANÁLISIS DE SENSIBILIDAD

El objetivo de este análisis es determinar los cambios en el valor de la función objetivo al variar:

1. los coeficientes de las variables de decisión en la función objetivo, y
2. los valores en el lado derecho de las restricciones.

Estos cambios de valor se analizarán en el reporte de análisis de sensibilidad  que se obtiene del programa SOLVER.

A continuación se dará una explicación y análisis de este reporte.

Gradiente Reducido.- También llamado costo reducido. Indica cuánto tendría que mejorar el coeficiente de la función objetivo de  cada variable de decisión antes de que sea posible que tal variable asuma un valor positivo en la solución óptima.

...