La región sombreada satisface todas las desigualdades
La programación lineal es un método para maximizar (o minimizar) una cierta cantidad asegurando al mismo tiempo que se cumplen ciertas condiciones sobre otras cantidades. Generalmente estas condiciones son lineales (sus gráficas son líneas rectas), de ahí el nombre de la disciplina: programación lineal. Es una de las técnicas más útiles de la investigación operacional, que es como se conoce el conjunto de instrumentos matemáticos desarrollados después de la segunda guerra mundial para mejorar el rendimiento de los sistemas económicos, industriales y militares, y desde entonces se ha convertido en un ingrediente habitual de los cursos de matemáticas de las escuelas de empresariales. (Véase la entrada sobre El método de simulación de Montecarlo y Matrices).
En vez de seguir invocando inexpresivos términos matemáticos para aclarar su significado, lo ilustraremos reflexionando sobre un simple cálculo del punto muerto. Un pequeño taller fabrica sillas metálicas (o artefactos si prefiere las formulaciones genéricas). Sus costes son 80.000 ptas. (en bienes de equipo, por ejemplo) y 3.000 ptas. por cada silla producida. Así pues, el coste total T contraído por el taller viene dado por la fórmula T = 3.000X + 80.000, donde X es el número de sillas producidas. Si suponemos además que el precio de venta de estas sillas es de 5.000 ptas. la pieza, los ingresos totales R del taller vienen dados por la ecuación R = 5.000X, donde X es el número de sillas vendidas.
Representando ambas ecuaciones sobre el mismo par de ejes coordenados, encontramos que se cortan en un punto en el cual los costes y los ingresos son iguales. El punto muerto, o de beneficio cero, es el (40, 200.000 ptas.), de modo que si se venden menos de 40 sillas, los costes superan los ingresos; si se venden más, los ingresos superan los costes; y si se venden exactamente 40 sillas, tanto los ingresos como los costes son 200.000 ptas. Maximizar los beneficios en este caso se reduce a vender tantas sillas como sea posible. (Para obtener algebraicamente el punto de beneficio cero, 40, se resta la ecuación Y = 3.000X + 80.000 de la Y = 5.000X. La ecuación resultante, 0 = 2.000X − 80.000, se resuelve fácilmente y da X = 40).
La región sombreada satisface todas las desigualdades
Después de este preliminar, consideremos el siguiente problema, que es un caso auténtico de programación lineal. Sin dejar las aplicaciones de la economía, supondremos que una empresa fabrica dos tipos de almohadas. Producir una almohada cara cuesta 1.200 ptas. y se vende a 3.000 ptas., mientras que una barata cuesta 500 ptas. y se vende a 1.800 ptas. La compañía no puede fabricar más de 300 almohadas al mes y no puede gastar más de 250.000 ptas. al mes en su producción (son normas impuestas por la subvención).[15] Si la compañía ha de fabricar al menos 50 almohadas de cada tipo ¿cuántas ha de fabricar de cada clase para maximizar sus beneficios?
Si llamamos X al número de almohadas caras que la compañía fabrica cada mes e Y al de almohadas caras, podemos convertir las condiciones sobre X e Y del problema en: X + Y ≤ 300; X ≥ 50; Y ≥ 50; y 1.200X + 500Y ≤ 250.000. La última desigualdad se debe a que si fabricar una almohada cara cuesta 1.200 ptas., producir X costará 1.200X ptas.; y análogamente, hacer Y almohadas baratas costará 500Y ptas. Obsérvese que estas condiciones se expresan como desigualdades lineales, cuyas gráficas son regiones del plano delimitadas por líneas rectas (o, en problemas más complicados, por sus análogos en espacios de más dimensiones).
La cantidad que hay que maximizar es el beneficio, que en términos de X e Y vale P = 1.800X + 1.300Y. Esto es así porque el beneficio que se tiene por cada almohada cara es de 1.800 ptas. (3.000 ptas. − 1.200 ptas.), y por cada almohada barata 1.300 ptas. (1.800 ptas. − 500 ptas.), con lo que X de las primeras dan un beneficio de 1.800X ptas., e Y de las segundas dan 1.300Y ptas. Una vez tenemos el problema planteado así, hay varias técnicas para hallar la solución. Una es gráfica y consiste en encontrar los vértices y los lados de la región permitida —la parte del plano en la que son válidas todas las desigualdades— y luego probarlas para encontrar en cuál de ellas se tiene el máximo beneficio. Con este método, y un poco de geometría analítica, descubrimos que la compañía de almohadas debería fabricar 143 almohadas caras y 157 baratas al mes si quiere obtener el máximo beneficio.
Otra técnica, llamada método simplex, debida al matemático norteamericano George Danzig, desarrolla y formaliza esta estrategia geométrica de modo que un ordenador pueda examinar rápidamente estos puntos en el caso de que haya más de dos variables. Usado durante más de cuarenta años, el método simplex ha ahorrado una cantidad incalculable de tiempo y dinero. Sin embargo, si el problema de optimización tiene varios miles de variables y desigualdades lineales, como ocurre por ejemplo al establecer el horario de unas líneas aéreas o los recorridos de las llamadas telefónicas, la comprobación puede ser un poco lenta, incluso para un ordenador. Para estas ocasiones existe un algoritmo, inventado recientemente por Narenda Karmarkar, investigador de los AT&T Bell Laboratories, que a menudo es más rápido en la determinación del horario más eficaz o el recorrido más corto.
Cuando las condiciones no son lineales, los problemas son mucho más difíciles de tratar. Me es grato informarles de que los problemas de programación no lineal frecuentemente colapsan los superordenadores más potentes.