类别 全部 - restricciones - herramientas - sensibilidad - coeficientes

作者:Francini Morillo 7 年以前

392

Investigación en operaciones I

El análisis de sensibilidad en la programación lineal (PL) se refiere a la evaluación de cómo cambios en los parámetros del modelo afectan la solución óptima. Esta disciplina incluye varios tipos de análisis, como el análisis utilizando herramientas específicas como Tora, Solver y AMPL, así como análisis gráfico y algebraico.

Investigación en operaciones I

Investigación en operaciones II y software Areana

Análisis de sensibilidad

Tipos de análisis
Análisis de sensibilidad con Tora, Solver, y AMPL

Ahora contamos con todas las herramientas para descifrar los resultados proporcionados por el software de PL, en particular con respecto al análisis de sensibilidad.

Análisis de sensibilidad algebraica. Función objetivo

Para facilitar la explicación del análisis de sensibilidad de la función objetivo, primero tenemos que definir los costos reducidos.

Análisis de sensibilidad algebraica. Cambios en el lado derecho

Se obtiene esta información con la tabla simplex óptima. Reconociendo que los precios duales y sus intervalos de factibilidad tienen que ver con los cambios del lado derecho de las restricciones.

Análisis de sensibilidad gráfica

2. La sensibilidad de la solución óptima a los cambios en la utilidad unitaria o el costo unitario (coeficientes de la función objetivo).

1. La sensibilidad de la solución óptima a los cambios de la disponibilidad de los recursos (lado derecho de las restricciones).

Definición
Es cuando en PL, los parámetros (datos de entrada) del modelo pueden cambiar dentro de ciertos límites sin que cambie la solución óptima.

Dualidad y análisis postóptimo

Cambios que afectan
2- La optimalidad

Se ve afectada por la realización de cambios de los coeficientes objetivos y la adición de una nueva actividad económica (variable).

1- La factibilidad

Se ve afectada sólo si cambia el lado derecho de las restricciones, o se agrega una nueva restricción al modelo. En ambos casos, la no factibilidad ocurre cuando una o más de las variables básicas actuales se vuelven negativas.

Algoritmos simplex
Generalizado

Se inicia factible pero no óptimo.

Dual

se inicia con una solución mejor que óptima y una solución básica no factible. Las condiciones de optimalidad y factibilidad están diseñadas para preservar la optimalidad de las soluciones básicas a medida que la solución se mueve hacia la factibilidad.

Ideas claves
5. Las reglas rigen el sentido de optimización, la dirección de las desigualdades y los signos de las variables en el dual. Una forma fácil de recordar el tipo de restricción en el dual (es decir, <= o >=) es que si el objetivo dual es de minimización (es decir, apunta hacia abajo), entonces todas las restricciones serán del tipo >= (es decir, apuntan hacia arriba). Lo opuesto aplica cuando el objetivo dual es de maximización.
4. Los coeficientes objetivo duales son iguales a los lados derechos de las ecuaciones de restricción primales.
3. Los coeficientes de restricción (columna) y el coeficiente objetivo de la variable primal j-ésima definen respectivamente los lados izquierdo y derecho de la restricción dual j-ésima.
2. Construya una restricción dual por cada variable primal.
1. Asigne una variable dual por cada restricción primal.

Método simplex

Pasos
Paso 3

Aplique los cálculos de Gauss-Jordan para determinar la nueva solución básica.Vaya al paso 1.

Paso 2

Seleccione una variable de salida utilizando la condición de factibilidad.

Paso 1

Seleccione una variable de entrada utilizando la condición de optimalidad. Deténgase si no hay variable de entrada; la última condición es óptima. De otro modo, prosiga con el paso 2.

Paso 0

Determine la solución factible básica inicial.

Condiciones
Factibilidad

Tanto en problemas de maximización como de minimización, la variable de salida es la variable básica asociada con la relación mínima no negativa con el denominador estrictamente positivo. Los vínculos se rompen arbitrariamente.

Optimalidad

La variable de entrada en un problema de maximización (minimización) es la variable no básica con el coeficiente más negativo (positivo) en la fila z. Los vínculos se rompen arbitrariamente. El óptimo se alcanza en la iteración en la cual los coeficientes en la fila z son no negativos (no positivos).

Métodos
Método de dos fases

Fase II

Use la solución factible de la fase I como una solución factible básica inicial para el problema original.

Fase I

Ponga el problema en forma de ecuación y agregue las variables artificiales necesarias a las restricciones, para tener la certeza de una solución básica. Determine una solución básica de la ecuación resultante que siempre minimice la suma de las variables artificiales, independientemente de si la PL es de maximización o minimización. Si el valor mínimo de la suma es positivo, el problema de PL no tiene una solución factible. De lo contrario, si el valor mínimo es cero, prosiga con la fase II.

Método gran M

Se penalizan las variables artificiales

M, en problemas de minimización

-M, en problemas de maximización

Puntos claves
Variables artificiales

Se utilizan con restricciones (=) y (>=). Desempeñan el papel de holguras en la primera iteración, y que luego se desechan en una iteración posterior.

Holgura

Sobrante de los recursos disponibles

Solución básica

Solución resolviendo las m ecuaciones

Variables básicas

m variables restantes

Variables no básicas

m variables cero