Programacion lineal

Programación Lineal

La Programación Lineal es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de ecuaciones lineales, optimizando la función objetivo, también lineal.

Consiste en optimizar (minimizar o maximizar) una función lineal, denominada función objetivo, de tal forma que las variables de dicha función estén sujetas a una serie de restricciones que expresamos mediante un sistema de inecuaciones lineales.

Método Grafico

El método gráfico es una forma fácil y rápida para la solución de problemas de Programación Lineal, siempre y cuando el modelo conste de dos variables. Para modelos con tres o más variables, el método gráfico es imposible.

Consiste en representar geométricamente las restricciones, condiciones técnicas y función objetivo objetivo.

Los pasos necesarios para realizar el método son:

1. hallar las restricciones del problema

2. Las restricciones de no negatividad Xi ≥ 0 confían todos los valores posibles.

3. sustituir ≥ y ≤ por (=) para cada restricción, con lo cual se produce la ecuación de una línea recta.

4. trazar la línea recta correspondiente a cada restricción en el plano. La región en cual se encuentra cada restricción, el área correspondiente a cada restricción lo define el signo correspondiente a cada restricción (≥ ó ≤) se evalúa un punto antes y después de la recta trazada, el punto que cumpla con la inecuación indicara el área correspondiente

5. el espacio en el cual se satisfacen las tres restricciones es el área factible

Cada punto situado en la frontera del espacio del área factible, es decir que satisfacen todas las restricciones, representa un punto factible.

6. Las líneas paralelas que representan la función objetivo se trazan mediante la asignación de valores arbitrarios a fin de determinar la pendiente y la dirección en la cual crece o decrece el valor de la función objetivo.

7. la solución óptima puede determinarse al observar la dirección en la cual aumenta la función objetivo, se procede a graficar la función objetivo, si es un problema de minimización la solución óptima es el primer punto factible que toque la función Z, y si por lo contrario es un problema de maximización, será entonces el último de los puntos factibles que toque la función Z

Método Simplex

El método o algoritmo del simplex se utiliza para hallar las soluciones óptimas de un problema de programación lineal con tres o más variables. Es un procedimiento iterativo de programación lineal que va desechando las soluciones no factibles y, en cada paso, evalúa si la solución obtenida es óptima o no. Las etapas de este algoritmo son:

1. Planteamiento del problema: identificación de las variables y definición de la función objetivo y del sistema de inecuaciones lineales para restricciones.

2. Conversión de las desigualdades en igualdades; en cada restricción se introduce una variable de holgura en el miembro menor (o menor o igual) de la desigualdad.

3. Igualación a cero de la función objetivo.

4. Escritura de una tabla inicial simplex (matriz): en las columnas, las variables del problema; una fila para cada conjunto de coeficientes de una restricción y una fila más para los coeficientes de la función objetivo.

5. Determinación de las variables y los coeficientes.

Análisis de Sensibilidad

El análisis de sensibilidad o postoptimal para los modelos de Programación Lineal, tiene por objetivo identificar el impacto que resulta en los resultados del problema original luego de determinadas variaciones en los parámetros, variables o restricciones del modelo, sin que esto pase por resolver el problema nuevamente.

Es decir, ya sea si resolvemos nuestro modelo gráficamente o utilizando el Método Simplex, lo que se busca es que estas variaciones o sensibilidad hagan uso de la solución y valor óptimo actual, sin tener la necesidad de resolver para cada variación un nuevo problema. En especial nos concentraremos en el análisis de sensibilidad o postoptimal que hace uso de la tabla final del Método Simplex.

TEORÍA

1. Cambio en el "lado derecho" de las restricciones: Lo que se busca identificar si las actuales variables básicas se mantienen luego de la modificación de uno o más parámetros asociados al "lado derecho" del modelo.

2. Inclusión de una nueva variable: Debemos evaluar si la nueva variable es un aporte significativo a los resultados del modelo original. Luego, para decir si la actual solución básica es óptima para el nuevo problema, calculamos el costo reducido de la nueva variable

3. Cambio en los Coeficientes Función Objetivo: Se busca identificar qué ocurre con la actual solución óptima del escenario base si se cambian uno o varios de los coeficientes que definen la función objetivo. La solución

...