Programación lineal
La programación lineal es una rama de la matemática que consiste en optimizar una función lineal que se encuentra sujeta a restricciones lineales de variables reales. Es decir, es un conjunto de técnicas que facilitan la resolución de problemas de planificación económica o social y su objetivo es el de optimizar, en otras palabras, minimizar los gastos o maximizar los beneficios, utilizando las restricciones o condiciones impuestas por el problema.
Veamos el siguiente ejemplo para comprenderlo mejor:
Un jardinero necesita 20 cajas de rosas, 15 de suculentas y 10 de cactus. Dos mayoristas pueden suministrarle las cantidades necesarias, sin embargo, ellos venden las plantas en contenedores completos. El mayorista A envía en cada contenedor 2 cajas de rosas, 4 de suculentas y 3 de cactus y el mayorista B envía 4 cajas de rosas, 3 de suculentas y 2 de cactus.
Sabiendo que el mayorista A se encuentra a 150 km de distancia y el mayorista B, a 300 km, ¿Cuántos contenedores de cada mayorista habría que comprar de manera que se ahorre en tiempo y dinero, reduciendo al mínimo la distancia de lo solicitado?
Como verás, tenemos muchos datos que debemos organizar para poder resolver este problema:
Ahora nos queda definir las variables, llamaremos "x" al número de contenedores que enviará el mayorista A e "y" al número de contenedores que enviará el mayorista B.
En base a esta definición, ya podremos armar la función objetivo, la cual será aquella que nos indicará la cantidad que debemos pedir de cada mayorista. Esta función quedará de la siguiente manera:
G(x;y)= 150.x + 300.y
Como vemos, tanto x como y están multiplicados por la cantidad de km que recorrerá cada mayorista.
Ahora nos queda definir las restricciones:
Para poder representar gráficamente estas restricciones, debemos despejar en las tres inecuaciones la incógnita "y".
Ahora solo nos queda graficar estas inecuaciones y la zona que quede comprometida por las tres inecuaciones será lo que llamaremos "región factible", la cual será un polígono y los extremos de estos polígonos serán los posibles valores que minimicen los gastos.
La región factible es la zona violeta ya que, no podemos tomar valores negativos tanto de "x" como de "y". En conclusión, uno de los dos valores marcados será el valor que nos minimizará los gastos, para saber cuál de los dos, solo nos queda reemplazar esos dos datos en la función objetivo:
G(10;0)= 150.10 + 300.0=1500
G(0;5)=150.0+300.5=1500
En este caso, como en casos obtuvimos el mismo resultado, el jardinero tendrá dos posibilidades, o compra 10 contenedores del mayorista A y ninguno del B o ninguno del A y 5 del B y en ambos casos minimizará los gastos.
Si, por ejemplo, nos hubieran quedado los puntos (10;2) y (2;5) en vez de los dos valores obtenidos anteriormente, al reemplazar, obtendríamos lo siguiente:
G(10;2)= 150.10 + 300.2=2100
G(2;5)=150.2+300.5=1800
En este caso deberíamos elegir comprar 2 empaquetados al mayorista A y 5 al mayorista B ya que solo recorrería 1800 km y el deseo del problema es minimizar los costos de viaje y dinero.
¿Cómo surgió la programación lineal?
La programación lineal es una rama de la matemática relativamente joven ya que surgió durante la Segunda Guerra Mundial con el objetivo de reducir los costos del ejército y aumentar las pérdidas del enemigo. Veamos un poco su historia:
En 1946 comenzó la guerra fría entre la Unión Soviética (URSS) y las potencias aliadas (Inglaterra y Estados Unidos principalmente). A su vez, Berlín también se dividía en tres partes y quedaba enclavada como un islote en la zona soviética. En 1948, la URSS bloquea las comunicaciones terrestres con la ciudad de Berlín desde las zonas alemanas en poder de los aliados, iniciando el bloqueo de Berlín. De esta manera se planteó un problema de abastecimiento muy difícil y donde había que elegir con buen criterio los productos que debían llegar y en qué orden. Este problema logístico fue el primer gran problema de programación lineal de la historia. Los aliados tuvieron dos opciones: o romper el bloqueo terrestre por la fuerza o llegar a Berlín por el aire.
Se decidió organizar un gigantesco puente aéreo para abastecer la ciudad. En diciembre de 1948 se transportaron 4500 toneladas diarias de víveres y aumentando a 8000 en marzo de 1949, la misma cantidad que se transportaba por carretera y ferrocarril antes del corte de las comunicaciones. Todos los inmensos cálculos para lograr esto se realizaron sobre "papel", utilizando inmensas tablas y los mejores matemáticos del momento del lado Occidental.
El 12 de mayo de 1949 cuando los soviéticos levantaron el bloqueo.