Programacion lineal

INTRODUCCIÓN

Este informe tendrá como propósito dar a conocer el concepto de programación lineal partiendo de la premisa que La Programación Lineal (PL) es una de las principales ramas de la Investigación Operativa. En esta categoría se consideran todos aquellos modelos de optimización donde las funciones que lo componen, es decir, función objetivo y restricciones, son funciones lineales en las variables de decisión

Corresponde a un algoritmo a través del cual se resuelven situaciones reales en las que se pretende identificar y resolver dificultades para aumentar la productividad respecto a los recursos (principalmente los limitados y costosos), aumentando así los beneficios.

El objetivo primordial de la Programación Lineal es optimizar, es decir, maximizar o minimizar funciones lineales en varias variables reales con restricciones lineales (sistemas de inecuaciones lineales), optimizando una función objetivo también lineal.

Los resultados y el proceso de optimización se convierten en un respaldo cuantitativo de las decisiones frente a las situaciones planteadas. Decisiones en las que sería importante tener en cuenta diversos criterios administrativos como:

Los hechos, la experiencia, la intuición y la autoridad.

OBJETIVOS

• Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas prácticos.

• Dominar el lenguaje propio de la programación lineal: función objetivo, restricciones, región factible, etc.

• Aplicar las técnicas de resolución de sistemas de ecuaciones e inecuaciones lineales.

• Saber representar regiones factibles y determinar gráficamente los puntos donde puede darse la solución óptima.

• Saber encontrar esa solución óptima.

• Saber plantear un problema de programación lineal partiendo de su enunciado en términos generales.

• Conocer y valorar el origen de la programación lineal y su influencia en la historia de este siglo.

• Utilizar y valorar las nuevas tecnologías.

PROGRAMACIÓN LINEAL

Concepto

La programación lineal es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de un sistema de inecuaciones 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.

El nombre de programación lineal no procede de la creación de programas de ordenador, sino de un término militar, programar, que significa '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 la transferencia 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.

Algunos casos especiales de programación lineal, tales como los problemas de flujo de redes y problemas de flujo de mercancías se consideraron en el desarrollo de las matemáticas lo suficientemente importantes como para generar por si mismos mucha investigación sobre algoritmos especializados en su solución.

La programación lineal es muy usada en la microeconomía y la administración de empresas, ya sea para aumentar al máximo los ingresos o reducir al mínimo los costos de un sistema de producción. Algunos ejemplos son la mezcla de alimentos, la gestión de inventarios, la cartera y la gestión de las finanzas, la asignación de recursos humanos y recursos de máquinas, la planificación de campañas de publicidad, etc.

En un problema de programación lineal intervienen:

La función f(x,y) = ax + by + c

Llamada función objetivo y que es necesario optimizar. En esa expresión x e y son las variables de decisión, mientras que a, b y c son constantes.

Las restricciones

Deben ser inecuaciones lineales. Su número depende del problema en cuestión. El carácter de desigualdad viene impuesto por las limitaciones, disponibilidades o necesidades, que son: inferiores a ... ( menores: < o ); como mínimo de ... (mayores: > o ) . Tanto si se trata de maximizar como de minimizar, las desigualdades pueden darse en cualquiera de los dos sentidos.

Al conjunto de valores de x e y que verifican todas y cada una de las restricciones se lo denomina conjunto (o región ) factible. Todo punto de ese conjunto puede ser solución del problema; todo punto no perteneciente a ese conjunto no puede ser solución. En el apartado siguiente veremos cómo se determina la región factible.

La solución óptima (x0, y0) del conjunto factible que haga que f(x,y)

Es el conjunto de los vértices del recinto se denomina conjunto de soluciones factibles básicas y el vértice donde se presenta la solución óptima se llama solución máxima (o mínima según el caso).

Cada desigualdad del sistema de restricciones determina un semiplano.

El conjunto intersección, de todos los semiplanos formados por las restricciones, determina un recinto,

...