Manual de investigación de operaciones. La dualidad y análisis de sensibilidad

Manual de Investigación de Operaciones

Temas:

Análisis de dualidad y sensibilidad

Y

Modelo de transporte y sus variantes

Análisis de dualidad y sensibilidad

1. Introducción

El propósito de un estudio de programación lineal es ayudar a guiar la decisión final de la administración con un panorama de las consecuencias posibles de seguir varias opciones administrativas bajo una variedad de suposiciones acerca de las condiciones futuras.

La mayoría de las percepciones importantes se logran al realizar un análisis después de hallar una solución óptima para la versión original del modelo básico.

Este análisis suele recibir el nombre de análisis de sensibilidad porque involucra estudiar algunas preguntas de qué ocurre con la solución óptima si se hacen diferentes supuestos acerca de condiciones futuras.

2. Acerca de Dualidad

Todo problema de optimización (primal), tiene un problema asociado (dual) con numerosas propiedades que los relacionan y nos permiten hacer un mejor análisis de los problemas. A continuación se describen los resultados que se ocuparan en la resolución de los problemas.

2.1. Construcción del problema dual Bastante en general, para encontrar el dual de un problema lineal:

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

2. En el dual habrá tantas variables como restricciones 2 en el primal.

3. En el dual habrá tantas restricciones como variables en el primal.

4. Los coeficientes de la función objetivo del dual vendrán dados por los coeficientes del lado derecho de las restricciones del primal.

5. Los coeficientes del lado derecho del dual vendrán dados por los coeficientes de la función objetivo del primal.

6. Los coeficientes que acompañaran a las variable en una restricción del dual corresponderán a aquellos coeficientes que acompañan a la variable primal correspondiente a la restricción dual 3 .

7. Para saber si las restricciones duales son de ≤, = ´o ≥, se recurre a la tabla de relaciones primal-dual

2Suponemos restricciones l.i

3O si se prefiere, los coeficientes serán el resultado de transponer la matriz A de coeficientes.

8. Para saber si las variables duales son ≤ 0, = 0 ´o ≥ 0, se recurre a tabla de relaciones primal dual.

2.3. Acerca de los precios sombra

Los valores de las variables duales en el ´optimo tienen una interpretación económica interesante en problemas de programación lineal: Corresponde a las tasas marginales de variación del valor de la función objetivo ante variaciones unitarias del lado derecho de una restricción. Por este motivo se le llama precio sombra al vector de variables duales en el óptimo.

3. Acerca de sensibilidad

Como ya se dijo, nos interesa ver como se ve afectada la solución de un problema de optimización si cambia alguno de los parámetros del problema. En este ´ámbito, podemos distinguir 2 tipos de análisis: Análisis de sensibilidad: Consiste en determinar cual es el rango de variación de los parámetros del problema de modo que la base ´optima encontrada siga siendo ´optima. Análisis post optimal: Consiste en determinar como varía la base ´optima si cambia alguno de los parámetros del problema. En la presente sesión nos concentraremos en análisis de sensibilidad dejando el análisis post optimal para un poco más adelante.

Modelo Primal en Forma canónica

Maximizar

Sujeta a:

i = 1,2, …..…m

Xj 0 j = 1,2, ………n

Modelo Dual Asociado

MinimizarY0 = bt Yi

Sujeta a:

atYi ³ Ct

Yi = 0

Modelo Dual Asociado

MinimizarY0 = bt Yi

Sujeta a:

atYi ³ Ct

Yi = 0

Ejemplo Modelo primal en forma canónica:

Obtener el modelo dual asociado del siguiente modelo primal en forma canónica:

Max. z = 3x1 + 5x2

S.A.

x1 # 4

2x2 # 12

3x1+ 2x2 # 18

x1³0 , x2³0

Primer paso:

Verificar que el modelo cumple con las características de la forma canónica, es decir:

i) La función objetivo es de Máximizar

ii) Todas las restricciones son del tipo #

iii) Todas las variables de decisión son no negativas

Sí no es así, aplicar las reglas de equivalencia correspondientes hasta obtener la forma canónica.

Para el ejemplo que nos ocupa, si se cumplen todas y cada una de dichas características.

Segundo paso

El número de variables del modelo dual corresponderá al número de restricciones del modelo primal. Para nuestro ejemplo serán tres variables duales porque el modelo primal en forma canónica tiene tres restricciones.

Y1, Y2, y Y3 son las variables duales.

x1 # 4 ................ Y1

2x2 # 12 ................ Y2

3x1+ 2x2 # 18 ................ Y3

Tercer paso:

La función objetivo dual se formula obteniendo (la transpuesta del vector de disponibilidad de recursos), es decir

Por lo que la función objetivo del modelo dual es:

Minimizar Y0 = 4Y1 + 12Y2 + 18Y3

Cuarto paso:

Las restricciones duales se formulan obteniendo (la transpuesta del vector de costos o utilidades) y (la transpuesta de la matríz de coeficientes tecnológicos).

Las restricciones duales son:

Quinto paso:

Para identificar la naturaleza de las variables duales, debemos observar el tipo de restricciones que tenemos en el modelo primal en forma canónica, para el ejemplo que nos ocupa, todas las restricciones en el modelo primal son del tipo # por lo que las variables duales serán todas del tipo ³0, es decir:

Y1³0

Y2³0

Y3³0

En resumen el modelo dual asociado al modelo primal en forma canónica es el siguiente:

Minimizar Y0 = 4Y1 + 12Y2 + 18Y3

Sujeta a:

Y1 + 3Y3 ³ 3

Y2 + 2Y3 ³ 5

...