Modelos de Programación Lineal

• Modelos de Programación Lineal.

La Programación Lineal es una de la más vieja y aún una de las más importantes herramientas de la investigación de operaciones, se utiliza cuando un problema se puede describir utilizando ecuaciones y desigualdades que son todas lineales.

La Programación Lineal (PL) es una técnica matemática de optimización. Por técnica de optimización se entiende un método que trata de maximizar o minimizar un objetivo; por ejemplo, maximizar las utilidades o minimizar los costos. La programación lineal es un subconjunto de un área más extensa de procedimientos de optimización matemática llamada Programación Matemática.

La Programación Lineal trata la planeación de las actividades para obtener un resultado optimo, esto es, el resultado que mejor alcance la meta especificada (según el modelo matemático) entre todas las alternativas de solución.

La Programación Lineal no da espacio para que haya incertidumbre en ninguna de las relaciones; no incluye ninguna probabilidad o variable aleatoria. Por consiguiente, el problema de maximizar la función objetivo, sujeta a las distintas restricciones, es conceptualmente simple. Cuando hay sólo unas pocas variables, el sentido común y algo de aritmética pueden dar una solución, y es que así se han resuelto esos problemas por generaciones. Sin embargo, como es frecuente, la intuición es poco valida cuando el problema es más complejo; ya que cuando el número de variables de decisión aumenta de tres o cuatro a cientos de miles, el problema desafía los procedimientos empíricos. La programación lineal ha hecho posible manejar de una manera ordenada, problemas con grandes cantidades de restricciones.

Esta técnica tiene excepcional poder y aplicación general. Es aplicable a una gran variedad de problemas organizacionales de los negocios modernos y puede manejarse como una rutina con la ayuda de los computadores actuales. Es una de las técnicas cuantitativas que le ha dado a la gerencia elementos eficaces para abordar un conjunto de problemas que admitían sólo soluciones parciales hasta hace pocos años.

En todo problema de programación lineal hay que tomar ciertas decisiones. Estas se representan con variables de decisión xj que se utilizan en el modelo de programación lineal. La estructura básica de un problema de este tipo es maximizar o minimizar la función objetivo, satisfaciendo al mismo tiempo un grupo de condiciones restrictivas o restricciones (que limitan el grado en que se puede perseguir algún objetivo).

La función objetivo.

En un problema de programación lineal, la función por maximizar o minimizar se llama función objetivo. Aunque por lo regular existe un numero infinito de soluciones para el sistema de restricciones (llamadas soluciones factibles o puntos factibles), la meta es encontrar una que sea una solución óptima (esto es, una que dé el valor máximo o mínimo de la función objetivo).

Restricciones estructurales y restricciones de no negatividad.

Las restricciones son limitaciones impuestas al grupo de decisiones permisibles. Algunos ejemplos específicos de tales restricciones son:

1. Un administrador de cartera tiene determinada cantidad de capital a su disposición. Las decisiones están limitadas por la cantidad de capital disponible y por las regulaciones gubernamentales.

2. Las decisiones del administrador de una planta están limitadas por la capacidad de dicha planta y por la disponibilidad de recursos.

3. Los planes de una aerolínea para llevar a cabo la asignación del personal y los vuelos están restringidos por las necesidades de mantenimiento de los aviones y por la cantidad de empleados disponibles.

El Modelo de programación lineal se ocupa de maximizar o minimizar una función objetivo lineal sujeta a dos tipos de restricciones:

1. Restricciones estructurales.

2. Restricciones de no negatividad.

Las restricciones estructurales reflejan factores como la limitación de recursos y otras situaciones que impone la situación del problema.

Las restricciones de no negatividad garantizan que ninguna variable de decisión sea negativa.

El Método Gráfico

Este método se fundamenta en la versión gráfica que presentemos de todas las restricciones planteadas; las cuales se superpondrán una sobre otra, hasta llegar a limitar un área, denominada área factible.

El procedimiento más funcional para la aplicación de este método es introducir una pequeña modificación en las restricciones, las cuales generalmente están planteadas como inecuaciones, transformándolas en ecuaciones.

Ya convertidas las restricciones en ecuaciones para su grafica aplicamos el método de los interceptos consistente en determinar los puntos donde la recta intercepta los ejes (X e Y).

Graficada la recta se sombrea la parte superior o inferior de esta dependiendo del tipo de inecuación.

Si la restricción tiene el signo  se sombrea a la derecha y por encima de la línea, pero si el signo es  se subraya a la izquierda por debajo del gráfico de la línea recta. La región que satisface de manera simultanea las restricciones ya sombreada se llama área o región factible, donde cada punto en esta región representa una solución factible. Aunque existe un numero infinito de soluciones factibles, debemos encontrar una que maximice o minimice la función objetivo.

La condición de no negatividad hace que el grafico de la restricción X1, X2  0, sea todo en el primer cuadrante.

Caso I.

Un fabricante esta tratando de decidir sobre las cantidades de producción para dos artículos x1 y x2. Se dispone de 96 unidades de material y 72 horas de mano de obra. Cada producto x1 requiere 12 unidades de materiales y 6 horas de obra al máximo. Mientras que el producto x2 usaría 8 unidades de material y 12 horas de mano de obra. El margen de beneficio es el mismo para ambos artículos US$5. El fabricante prometió construir por lo menos dos artículos del producto x1 Determinar la cantidad a producir y vender de cada artículo que garanticen mayores beneficios.

Función objetivo: Z = 5x1 + 5x2

Restricciones x1 y x2  0 (condición de no negatividad)

12x1 + 8x2  96

6x1 + 12x2  72

x1  2

Maximice: Z = 5x1 + 5x2

1. Convertimos las restricciones en ecuaciones.

12x1 + 8x2 = 96

...