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

...