Investigación en operaciones II y software Areana

Puntos claves

Variables no básicas

m variables cero

Variables básicas

m variables restantes

Solución básica

Solución resolviendo las m ecuaciones

Holgura

Sobrante de los recursos disponibles

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.

Métodos

Método gran M

Se penalizan las variables artificiales

-M, en problemas de maximización

M, en problemas de minimización

Método de dos fases

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.

Fase II

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

Condiciones

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).

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.

Pasos

Paso 0

Determine la solución factible básica inicial.

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 2

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

Paso 3

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

Ideas claves

1. Asigne una variable dual por cada restricción primal.

2. Construya una restricción dual por cada variable primal.

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.

4. Los coeficientes objetivo duales son iguales a los lados derechos de las ecuaciones de restricción primales.

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.

Algoritmos simplex

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.

Generalizado

Se inicia factible pero no óptimo.

Cambios que afectan

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.

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).

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.

Tipos de análisis

Análisis de sensibilidad gráfica

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

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).

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 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 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.