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 €.
