DUALIDAD Y ANALISIS DE SENSIBILIDAD

OPTIMIZACION DE

SISTEMAS I

DUALIDAD Y ANALISIS DE SENSIBILIDAD

Profesor: Ing. Luis Medina Aquino

2012-2

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  Cn

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

Encuentre el dual de:

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:

a) Identifique las variables correspondientes en el dual de su problema primal.

b) 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.

c) Aplique la siguiente tabla de signos:

Modelos max Modelo min

Xi la iésima restricción es 

Xi la iésima restricción es 

Xi srsla iésima restricción es =

la iésima restricción es Yj 

la iésima restricción es Yj 

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

¿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:

Si la restricción j en el primal es buscar en la tabla óptima del primal

 (zj) de la variable de holgura sj

 (zj) de la variable artificial aj

= (zj) de la variable artificial aj

ANÁLISIS DE SENSIBILIDAD

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

a) los coeficientes de las variables de decisión en la función objetivo, y

b) 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.

El costo reducido será cero si la variable correspondiente es básica, y será negativo si la variable es no básica.

Precio Sombra.- También llamado precio dual. Cada restricción tiene un precio dual cuyo valor puede ser positivo, negativo o cero. Si es positivo indica el mejoramiento en el valor óptimo de la función objetivo por cada aumento unitario en el lado derecho de la restricción. Si el valor es negativo indica lo contrario de lo anterior. Si el valor cero no afecta ningún cambio en el valor óptimo de la función objetivo.

Signo del

Precio dual Maximización o Minimización Efecto del aumento de una unidad en el valor del lado derecho

+ Maximización Aumento en los beneficios

- Maximización Disminución en los beneficios

+ Minimización Aumento en los costos

- Minimización Disminución en los costos

Análisis de rango para los coeficientes de la Función Objetivo

Rango en el que la solución óptima no cambie, es decir se encuentra en el mismo punto (se mantiene la misma solución).

Al cambiar un coeficiente, cambia únicamente la pendiente de la función objetivo, por lo que el polígono de soluciones factibles se mantiene sin cambio.

Análisis de rango para el Lado Derecho de las Restricciones

Mientras los lados derechos de las restricciones se mantengan dentro de estos intervalos, el precio dual correspondiente nos indica el mejoramiento del valor de la función objetivo por aumento unitario en el valor del lado derecho.

La base no cambia en este rango, es decir, las variables básicas siguen siendo básicas, aunque sus valores si pueden cambiar.

Cambios Simultaneos

Se aplica la regla del 100% en dos casos:

a) para cambios simultáneos en la función objetivo y,

b) para cambios simultáneos en el lado derecho de las restricciones.

a) Para todos los coeficientes de la función objetivo que se modifican sume los porcentajes tanto de los incrementos como de los decrementos

...