Programacion Lineal
description
Transcript of Programacion Lineal
![Page 1: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/1.jpg)
Maestría Operaciones y Logística
Curso : Modelación y Simulación
Profesor : Ingº Carlos Culquichicón, MBA
Junio 2015
![Page 2: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/2.jpg)
ANÁLISIS DE SENSIBILIDAD DE PROBLEMAS DE PL USANDO LINDOUNIDAD 3
![Page 3: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/3.jpg)
Utilización de software
• Lo primero es convertir las restricciones en igualdades. – Cualquier restricción <= puede ser convertida
en una igualdad sumando una variable de holgura no negativa al lado izquierdo.
– Cualquier restricción >= puede ser convertida en una igualdad sumando una variable de excedente no negativa al Iado izquierdo.
![Page 4: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/4.jpg)
Variables de holgura
• Las variables de holgura se presentan en las restricciones del tipo:
Xl + X2 <= cte .
• A la inecuación se le agrega una variable no negativa, entonces tenemos:
Xl + X2 + S = cte.
S >=0
![Page 5: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/5.jpg)
Variables de holgura
• La variable de holgura S será el " faltante", es decir la cantidad adicional que debe ser sumada al lado izquierdo para convertir la desigualdad en igualdad .
• Cada restricción <= tiene asociada una variable de holgura diferente para cada restricción del modelo.
![Page 6: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/6.jpg)
Variables de excedente
• Para convertir una restricción >= en una igualdad, restamos una variable no negativa en el lado izquierdo y la desigualdad cambia a igualdad.
X1 + X2 >= cte .
• Esto genera las siguientes condiciones: X1 + X2 - s = cte
S >=0
![Page 7: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/7.jpg)
Variables de excedente
• Una variable excedente es el exceso que debe ser reducido al lado izquierdo de la restricción de desigualdad para convertida en una igualdad.
• Cada restricción >= tiene asociada una variables excedente diferente para cada restricción de este tipo.
![Page 8: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/8.jpg)
Valores óptimos de las variables de holgura y excedente
• Las restricciones activas son precisamente aquellas para las cuales los valores óptimos de las variables de excedente o de holgura son nulos.
• Las restricciones inactivas son aquellas para las que los valores óptimos de las variables de excedente y de holgura son positivos.
![Page 9: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/9.jpg)
Análisis de Sensibilidad
• El análisis de sensibilidad de un modelo de programación lineal es un análisis de resultados que se hace una vez solucionado el modelo .
• El análisis de sensibilidad se basa en la proposición que todos los datos a excepción de una parte en el problema, se mantienen fijos.
![Page 10: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/10.jpg)
Análisis de Sensibilidad
• El análisis de sensibilidad se realiza con la finalidad de observar el/los efectos que podría causar un cambio en alguno de los parámetros del modelo .
• Este tipo de análisis es muy importante para obtener información que nos pueda servir para cualquier proceso de toma de decisiones
![Page 11: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/11.jpg)
Análisis de Sensibilidad
• La solución de un problema de programación lineal por computadora tiene, cuando más, m variables positivas, siendo m el número de restricciones.
• Cuando la solución por computadora tiene menos de m variables positivas, se llama degenerada y en este caso especial se deberá tener cuidado al interpretar algunos resultados
![Page 12: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/12.jpg)
TABLA DE RESULTADOS
• Tiene cuatro partes: – Resultados del Valor óptimo y solución
óptima– Resultados de las restricciones – Resultados sobre rangos de los coeficientes
de la función objetivo – Resultados sobre los rangos de los lados
derechos de las restricciones
![Page 13: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/13.jpg)
Modelo en el LINDO
![Page 14: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/14.jpg)
Valor y solución óptimos
Valor óptimo
Solución óptima
![Page 15: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/15.jpg)
Costo Reducido: definición 1
• El costo reducido es la tasa (por unidad de aumento) a la cual disminuye el valor objetivo cuando una variable es forzada a entrar en una solución óptima.
![Page 16: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/16.jpg)
Costo Reducido: definición 2
• Cantidad en la que debe cambiar el coeficiente de una variable en la función objetivo para obtener un valor óptimo positivo. Si la variable ya tiene un valor óptimo positivo su costo reducido será cero
![Page 17: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/17.jpg)
Resultados de las restricciones
RESTRICCION INACTIVA
RESTRICCION ACTIVA
Resultados de holguras y/o excedentes
![Page 18: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/18.jpg)
Caso de degeneración
• Si la suma de variables positivas es igual al número de restricciones del modelo entonces la solución es no degenerada
![Page 19: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/19.jpg)
El precio dual
• El precio dual para una restricción' muestra la mejoría del valor óptimo cuando el lado derecho de una restricción aumenta una unidad, con los demás datos fijos
![Page 20: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/20.jpg)
Rangos de coeficientes de la F.O.
![Page 21: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/21.jpg)
Sensibilidad con la Función Objetivo
• El cambio en los coeficientes de la función objetivo altera la pendiente de los contornos de ésta. Esto puede afectar o no a la solución óptima y al valor óptimo de la función objetivo
![Page 22: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/22.jpg)
Significado de rangos para la FO
• Las columnas "ALLOWABLE INCREASE" y "ALLOWABLE DECREASE" bajo el encabezado" OBJ COEFFICIENT RANGES" dicen cuanto puede aumentar o disminuir sin alterar la solución óptima, mientras los demás datos se conservan constantes. Por supuesto, como la reditualidad en este rango varía, los valores del VO varían.
![Page 23: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/23.jpg)
Significado de rangos para la FO
• Cuando un coeficiente se modifica en menos de la cantidad admisible, la solución óptima actual permanece como única solución óptima del modelo.
![Page 24: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/24.jpg)
Significado de rangos para la FO
• Cuando un coeficiente en particular es aumentado (o disminuido) en la cantidad admisible, habrá una solución óptima alterna con un valor óptimo mayor (o menor) para la variable afectada
![Page 25: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/25.jpg)
Cálculo de los rangos de los coeficientes de la F.O.
• Para calcular el rango del coeficiente de una variable en la función objetivo: al valor actual se le resta la máxima disminución permitida ( lado izquierdo del intervalo), y al valor actual se le suma el máximo aumento permitido ( lado derecho del intervalo)
![Page 26: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/26.jpg)
Rangos de lados derechos de restricciones
![Page 27: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/27.jpg)
El precio dual y el rango válido
• El precio dual es la mejoría o disminución del valor objetivo con el aumento o disminución de una unidad del lado derecho de una restricción activa.
• La interpretación del precio dual es válida para un rango, el cual queda especificado por las columnas "ALLOW ABLE INCREASE" y "ALLOW ABLE DECREASE”
• En este rango el precio dual es constante
![Page 28: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/28.jpg)
Cálculo de los rangos de lados derechos
• Para calcular el rango del lado derecho de una restricción: al valor actual se le resta la máxima disminución permitida ( lado izquierdo del intervalo), y al valor actual se le suma el máximo aumento permitido ( lado derecho del intervalo)
![Page 29: Programacion Lineal](https://reader031.fdocumento.com/reader031/viewer/2022033101/563dbba8550346aa9aaf1b10/html5/thumbnails/29.jpg)
Precios duales y restricciones inactivas
• El precio dual de una restricción inactiva será siempre cero .
• La información de sensibilidad no nos proporciona nada sobre los nuevos valores de las variables de decisión, sólo trata de explicar el comportamiento del valor objetivo.