Programacion lineal

PROGRAMACIÓN LINEAL

INTRODUCCIÓN
La programación lineal es un conjunto de técnicas racionales de análisis y de resolución de problemas que tiene por objeto ayudar a los responsables en las decisiones sobre asuntos en los que interviene un gran número de variables.
El nombre de programación lineal no procede de la creación de programas de ordenador, sino de un término militar, programar, quesignifica ‘realizar planes o propuestas de tiempo para el entrenamiento, la logística o el despliegue de las unidades de combate’.
Aunque parece ser que la programación lineal fue utilizada por G. Monge en 1776, se considera a L. V. Kantoróvich uno de sus creadores. La presentó en su libro Métodos matemáticos para la organización y la producción (1939) y la desarrolló en su trabajo Sobre latransferencia de masas (1942). Kantoróvich recibió el premio Nobel de economía en 1975 por sus aportaciones al problema de la asignación óptima de recursos humanos.
La investigación de operaciones en general y la programación lineal en particular recibieron un gran impulso gracias a los ordenadores. Uno de momentos más importantes fue la aparición del método del simplex. Este método, desarrollado por G.B. Dantzig en 1947, consiste en la utilización de un algoritmo para optimizar el valor de la función objetivo teniendo en cuenta las restricciones planteadas. Partiendo de uno de los vértices de la región factible, por ejemplo el vértice A, y aplicando la propiedad: si la función objetivo no toma su valor máximo en el vértice A, entonces existe una arista que parte del vértice A y a lo largo de lacual la función objetivo aumenta. se llega a otro vértice.
El procedimiento es iterativo, pues mejora los resultados de la función objetivo en cada etapa hasta alcanzar la solución buscada. Ésta se encuentra en un vértice del que no parta ninguna arista a lo largo de la cual la función objetivo aumente.
Aunque a lo largo de esta unidad únicamente se resuelven problemas de programación linealbidimensional, este tipo de análisis se utiliza en casos donde intervienen cientos e incluso miles de variables.
OBJETIVOS
* Resolver gráficamente inecuaciones y sistemas de inecuaciones lineales con dos incógnitas
* Conocer la programación lineal y sus aplicaciones a la vida cotidiana.
* Plantear y resolver situaciones con programación lineal.
* Conocer dos ejemplos típicos: problema deltransporte y de la dieta.

TIPOS DE SOLUCIONES
Los programas lineales con dos variables suelen clasificarse atendiendo al tipo de solución que presentan. Éstos pueden ser:
* FACTIBLES. Si existe el conjunto de soluciones o valores que satisfacen las restricciones. Estas a su vez pueden ser: con solución única, con solución múltiple (si existe más de una solución) y con solución no acotada(cuando no existe límite para la función objetivo).
* NO FACTIBLES. Cuando no existe el conjunto de soluciones que cumplen las restricciones, es decir, cuando las restricciones son inconsistentes.
METODOS DE SOLUCION DE PROBLEMAS DE PROGRAMACION LINEAL
Existen tres métodos de solución de problemas de programación lineal:
* Método gráfico o de las rectas de nivel. Las rectas de nivel dan lospuntos del plano en los que la función objetivo toma el mismo valor.
* Método analítico o de los vértices. El siguiente resultado, denominado teorema fundamental de la programación lineal, nos permite conocer otro método de solucionar un programa con dos variables: “En un programa lineal con dos variables, si existe una solución única que optimice la función objetivo, ésta se encuentra en un puntoextremo (vértice) de la región factible acotada, nunca en el interior de dicha región. Si la función objetivo toma el mismo valor óptimo en dos vértices, también toma idéntico valor en los puntos del segmento que determinan. En el caso de que la región factible no es acotada, la función lineal objetivo no alcanza necesariamente un valor óptimo concreto, pero, si lo hace, éste se encuentra en uno…