La solución de problemas de programación lineal

OPTIMIZACION DE

SISTEMAS I

DUALIDAD Y ANALISIS DE SENSIBILIDAD

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 permisibles representados por los cambios. Si la suma de los cambios porcentuales no excede del 100%, la solución óptima no se modificará.

Sin embargo, la regla del 100% no nos dice si la solución óptima cambiará si la suma de los cambios porcentuales excede a 100%. La solución óptima pudiera no cambiar, incluso si la suma de los cambios porcentuales excede a 100%. Cuando no se satisfaga la regla del 100%, deberemos resolver el problema y determinar los efectos que tendrán estos cambios en la solución óptima.

b) Una versión similar a la regla del 100% también es aplicable a cambios simultáneos en los lados derechos de las restricciones. Para todos los lados derechos que se modifiquen, sume los porcentajes tanto de los incrementos como de los decrementos permisibles. Si la suma de los porcentajes no excede de 100%, los precios duales no se modificarán.

Ejemplo

Una compañía elabora los productos A, B y C. Cada producto se procesa en tres departamentos: I, II y III. El total disponible de horas de trabajo por semana por cada departamento es de 900, 1080 y 840 horas, respectivamente. Los requisitos de tiempo (en horas por unidad) y la ganancia por cada unidad del producto son:

Producto Producto Producto

A B C

Departamento I 2 1 2

Departamento II 3 1 2

Departamento III 2 2 1

Ganancia $16 $12 $15

¿Cuántas unidades de cada producto debe fabricar la compañía para maximizar las ganancias?

El programa lineal respectivo será la siguiente:

Maximizar Z = 16 x1 + 12 x2 + 15 x3

Sujeto a:

2 x1 + x2 + 2 x3  900

3 x1 + x2 + 2 x3  1080

2 x1 + 2x2 + x3  840

x1, x2, x3  0

Resolviendo por el programa SOLVER, obtenemos los resultados del reporte de Análisis de Sensibilidad:

Microsoft Excel 9.0 Informe de sensibilidad

Hoja de cálculo: [Libro1]Hoja1

Informe creado: 06/12/02 04:47:00 p.m.

Celdas cambiantes

Valor Gradiente Coeficiente Aumento Disminución

Celda Nombre Igual reducido objetivo permisible permisible

$B$5 Cantidad a producir A 0 -2 16 2 1E+30

$C$5 Cantidad a producir B 260 0 12 18 3

$D$5 Cantidad a producir C 320 0 15 9 3

Restricciones

Valor Sombra Restricción Aumento Disminución

Celda Nombre Igual precio lado derecho permisible permisible

$E$7 Departamento 1 900 6 900 180 480

$E$8 Departamento 2 900 0 1080 1E+30 180

$E$9 Departamento 3 840 3 840 960 390

El análisis de sensibilidad nos sirve para responder a las preguntas ¿Qué pasa si?

Preguntas:

1. ¿Conviene programar horas extras en el Departamento 1? Si su respuesta es afirmativa ¿hasta cuantas horas extras conviene programar? ¿Cuánto aumenta la utilidad por cada hora

...