Programacion lineal . Ejemplo

Introducción a la Programación Lineal.

En cualquier empresa, muchas de las decisiones que se toman tienen por objeto hacer el mejor uso posible (optimización) de los recursos de la misma. Por recursos de una empresa entendemos la maquinaria que ésta posea, sus trabajadores, capital financiero, instalaciones, y las materias primas de que disponga. Tales recursos pueden ser usados para fabricar productos (electrodomésticos, muebles, comida, ropa, etc.) o servicios (horarios de producción, planes de marketing y publicidad, decisiones financieras, etc.). La Programación Lineal (PL) es una técnica matemática diseñada para ayudar a los directivos en la planificación y toma de decisiones referentes a la asignación de los recursos.

Como ejemplos de problemas donde la Programación Lineal desarrolla un papel fundamental, podríamos citar:

   1. A partir de los recursos disponibles, determinar las unidades a producir de cada bien de forma que se maximice el beneficio de la empresa.

   2. Elegir materias primas en procesos de alimentación, para obtener mezclas con unas

      determinadas propiedades al mínimo coste.

   3. Determinar el sistema de distribución que minimice el coste total de transporte, desde

      diversos almacenes a varios puntos de distribución.

   4. Desarrollar un plan de producción que, satisfaciendo las demandas futuras de los productos de una empresa, minimice al mismo tiempo los costes totales de producción e inventario.

Características de un problema de Programación Lineal

Las técnicas de Programación Lineal han sido ampliamente utilizadas en ámbitos tan diferentes como el militar, industrial, financiero, de marketing, e incluso agrícola. A pesar de tal diversidad de aplicaciones, todos los problemas de Programación Lineal tienen cuatro propiedades comunes:

   1. Pretenden optimizar (maximizar o minimizar) alguna cantidad (función objetivo). Así, por ejemplo, el principal objetivo de un banquero sería maximizar beneficios, mientras que el principal objetivo de una empresa transportista podría ser minimizar los costes de los envíos.

   2. Habrá que tener en cuenta las restricciones que limitan el grado en el cual es posible modificar las variables que afectan a nuestra función objetivo. Así, a la hora de decidir cuántas unidades de cada bien se han de producir, deberemos considerar, entre otras, las limitaciones de personal y maquinaria de que disponemos.

   3. El problema debe presentar distintas alternativas posibles: si una compañía produce cuatro bienes diferentes, la dirección puede usar Programación Lineal para determinar las cantidades de recursos que asigna a la producción de cada uno de ellos (podría optar por hacer una asignación ponderada, dedicar todos los recursos a la producción de un único bien abandonando la producción del resto, etc.).

   4.  En Programación Lineal, la función objetivo debe ser una función lineal, y las restricciones deben ser expresables como ecuaciones o inecuaciones lineales.

Planteamiento de un problema de Programación Lineal

Ejemplo: Una empresa fabrica dos modelos de mesas para ordenador, M1 y M2. Para su producción se necesita un trabajo manual de 20 minutos para el modelo M1 y de 30 minutos para el M2; y un trabajo de máquina de 20 minutos para M1 y de 10 minutos para M2. Se dispone de 100 horas al mes de trabajo manual y de 80 horas al mes de máquina. Sabiendo que el beneficio por unidad es de 1,5 y 1 € para M1 y M2, respectivamente, planificar la producción para obtener el máximo beneficio.

Nos limitaremos ahora a plantear formalmente el problema (ya lo resolveremos más adelante):

Llamando: X = “nº unidades producidas al mes de M1”, e Y = “nº unidades producidas al

mes de M2 ”,

nuestra función objetivo sería: Maximizar:

Z(X,Y) = 1,5X + Y

y las restricciones vendrán dadas por:

Sujeto a:

20X + 30Y <= 100*60

20X + 10Y <= 80*60                           X >= 0                    Y >= 0

Las dos últimas restricciones, si bien no constan de forma explícita en el enunciado, sí figuran de forma implícita, pues el número de mesas a producir no puede ser inferior a 0.

Supuestos básicos de la Programación Lineal

Desde un punto de vista técnico, hay cinco supuestos que debe cumplir todo problema de programación lineal:

   1. Los coeficientes, tanto de la función objetivo como de las restricciones, son conocidos con exactitud y además no varían durante el período de tiempo en que se realiza el estudio (supuesto de certidumbre).

   2. Tanto en la función objetivo como en las restricciones hay proporcionalidad: si para la producción de un bien empleamos 5 horas de un determinado recurso (mano de obra, maquinaria, etc.), para producir diez unidades de dicho bien serán necesarias 50 horas del mismo recurso.

   3. Aditividad de actividades: tanto en la función objetivo como en las restricciones, la contribución de cada variable es independiente de los valores del resto de las variables, siendo el total de todas las actividades igual a la suma de cada actividad individual. Así, por ejemplo, si producimos dos tipos de bienes, uno que nos reporte un beneficio de 20 €/unidad, y otro que nos reporte un beneficio de 10 €/unidad, la producción de un bien de cada tipo supondrá un beneficio total de 30 €.

   4. Las soluciones del problema serán, en general, números reales no necesariamente enteros (supuesto de divisibilidad). Para aquellos problemas en los cuales sólo tenga sentido obtener soluciones enteras (cuando las soluciones se refieran a objetos indivisibles), se usarán técnicas de Programación Lineal Entera (PLE).

   5. Las variables de nuestro modelo tomarán siempre valores positivos (supuesto de no negatividad), dado que no tiene sentido hablar de cantidades negativas de objetos físicos.

Resolución gráfica de un problema de Programación Lineal

El método gráfico de resolución tan sólo es aplicable a problemas con dos variables (X e Y). Para aquellos casos en que el número de variables del problema sea superior a dos, no será posible encontrar la solución a partir de un gráfico bidimensional y, por tanto, tendremos que usar métodos de resolución más complejos. Aún así, el método gráfico es de un gran valor pedagógico dado que nos permite vislumbrar de una forma intuitiva las ideas básicas de la Programación Lineal.

Volviendo al ejemplo de las mesas de ordenador, dado que en él tenemos sólo dos variables, podremos representar cada una de las restricciones en el plano real. Estas restricciones son semiespacios (por ser lineales), la intersección de los cuales se denomina región factible (área de color verde en la figura):

  

La teoría matemática establece que, dado un problema de Programación Lineal que tenga solución, ésta vendrá dada por uno de los vértices (o puntos extremos) del polígono que configura la región factible. Por tanto, será suficiente hallar las coordenadas de dichos vértices (intersecciones de rectas) y determinar (sustituyendo en la función objetivo) cuál de ellos es la solución óptima. En nuestro ejemplo, tendríamos sólo cuatro puntos candidatos a ser solución del problema (los cuatro vértices del polígono), sustituyendo sus coordenadas en la función objetivo obtenemos:

Z(0,0) = 0; Z(0,200) = 200; Z(210,60) = 375; y Z(240,0) = 360

Como en este caso buscábamos maximizar Z(X,Y), concluiremos que el punto óptimo es el (210,60), dado que con él obtenemos el valor máximo de la función objetivo. Así pues, la solución a nuestro dilema será fabricar 210 mesas de tipo M1 y sólo 60 de tipo M2, con ello conseguiremos unos beneficios de 375 €.