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, acotado o no, que recibe el nombre de región de validez o zona de soluciones factibles.

Valor del programa lineal

El valor que toma la función objetivo en el vértice de solución óptima se llama valor del programa lineal.

Métodos

Los Supuestos Básicos de la Programación Lineal son: Linealidad, Modelos Deterministas, Variables reales, No Negatividad.

Un modelo de Programación Lineal (PL) considera que las variables de decisión tienen un comportamiento lineal, tanto en la función objetivo como restricciones del problema. En este sentido, la Programación Lineal es una de las herramientas más utilizadas en la Investigación Operativa debido a que por su naturaleza se facilitan los cálculos y en general permite una buena aproximación de la realidad.

Método Gráfico o Método de las de rectas de nivel

Las rectas de nivel dan los puntos del plano en los que la función objetivo toma el mismo valor. Si la función objetivo es f(x,y) = ax + by + c, la ecuación de las rectas de nivel es de la forma:

ax + by + c = 0 ax + by = k

Variando k (o p) se obtienen distintos niveles para esas rectas y, en consecuencia, distintos valores para f(x,y).

En un problema todas las rectas de nivel son paralelas, pues los coeficientes a y b de la recta ax + by = k son los que determinan su pendiente. Por tanto, si k1 es distinto de k2 , las rectas ax + by = k1 y ax + by = k2 son paralelas. Luego, trazada una cualquiera de esas rectas, las demás de obtienen por desplazamientos paralelos a ella.

Si lo que se pretende es resolver un problema de programación lineal, los únicos puntos que interesan son los de la región factible, y las únicas rectas de nivel que importan son aquellas que están en contacto con dicha región. Como el nivel aumenta (o disminuye) desplazando las rectas, el máximo (o el mínimo) de f(x,y) se alcanzará en el último (o en el primer) punto de contacto de esas rectas con la región factible.

Método Analítico o Método de los Vértices

La evaluación de la función objetivo en los vértices de la región factible nos va a permitir encontrar el valor óptimo (máximo o mínimo) en alguno de ellos.

En un programa lineal con dos variables, si existe una solución única que optimice la función objetivo, esta se encuentra en u punto extremo (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 de los vértices de la región

Método de Simplex

Es un procedimiento iterativo que permite ir mejorando la solución de cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución.

Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución.

El método del simplex se basa en la siguiente propiedad: si la función

...