Ideas básicas sobre programación lineal

En Economía de la Empresa es muy frecuente vernos obligados a optimizar (maximizar o minimizar) una determinada variable objetivo, por ejemplo la productividad, el VAN o el coste de oportunidad de la financiación ociosa.

Optimizar significa buscar la manera de alcanzar el mejor grado de cumplimiento en ese objetivo, actuando sobre las variables de las que depende. En el caso del VAN esas variables son los flujos de caja y el coste de capital, e indirectamente todas aquellas que determinan los movimientos de tesorería y el coste financiero: ingresos y gastos, períodos medios, morosidad, precio de venta, gastos, estructura financiera, etc.

Este propósito plantea dos problemas. En primer lugar, el hecho de que hay muchas variables de decisión, y que éstas pueden tomar múltiples valores: hay centenares, incluso miles de posibles combinaciones para esas variables, y no podemos probarlas una a una; en realidad "no podemos probarlas", porque es imposible experimentar directamente sobre la empresa. En segundo lugar, esas variables no pueden tomar cualesquiera valores: no podemos invertir una cantidad ilimitada de dinero, porque el presupuesto es limitado; no podemos suprimir inmediatamente determinadas líneas de producto o departamentos, debido a la existencia de rigideces y costes de oportunidad. En definitiva, las variables de decisión están acotadas, restringidas.

Se trataría por tanto de identificar una combinación que optimice el objetivo respetando, al mismo tiempo, las restricciones o limitaciones que puedan existir. Estos problemas se denominan "de optimización restringida" y operan sobre dos componentes: una función objetivo (cuyo valor que queremos optimizar) y una o más restricciones (los límites o condiciones que debe cumplir esa solución). La función objetivo y las restricciones son expresiones matemáticas definidas en términos de dos o más procesos, las variables de gestión sobre las que podemos actuar (precio de venta, número de empleados, etc.).

Muchos problemas comunes son lineales, en el sentido de que tanto la función objetivo como las restricciones son formas lineales de las variables de decisión. Este es el campo de trabajo de la programación lineal.

Un modelo de programación lineal (PL) tiene la siguiente estructura genérica:

Máx (Mín)  Z = C₁ λ₁ + C₂ λ₂ + ... + C_n λ_n

Suj. a  A₁₁ λ₁ + A12 λ₂ +...+ A1n λ_n ≤ P₁

           A21 λ₁ + A22 λ₂ +...+ A2n λ_n ≤ P₂

           ...   ...   ...   ...   ...   ...   ...   ...   ...   ...

          A_m1 λ₁ + A_m2 λ₂ +...+ A_mn λ_n ≤ P_m

         λi ≥ 0 (i = 1 … n)

donde λi son las variables de decisión (cuyos valores óptimos queremos identificar), y Ci y aij son los coeficientes aplicados a estas variables.

La expresión

Max. (Mín) Z = C₁ λ₁ + C₂ λ₂ + ... + C_n λ_n

es la función objetivo del problema, define la variable Z cuyo valor queremos optimizar (maximizar o minimizar). Los Ci son los coeficientes de valor directo, y expresan la contribución a la función objetivo de cada unidad de la variable λi. 

Por ejemplo si elaboramos dos productos (X, Y) que proporcionan un margen neto unitario de 2€ y 4€, la función objetivo Max 2X + 4Y expresa el propósito de maximizar el resultado total proporcionado por las ventas de esos dos productos.

A continuación se definen las restricciones. Por ejemplo,

A₁₁ λ₁ + A12 λ₂ +...+ A1n λ_n ≤ P₁

define el valor máximo que puede alcanzar el término izquierdo. Los valores aij son los coeficientes técnicos, y su significado depende de cada problema. Una forma sencilla de comprenderlo es pensar que λi son unidades de producto y los Aij el consumo unitario de un determinado factor: el producto A₁₁ λ₁ expresa la cantidad consumida de ese factor cuando se producei λ₁ unidades del producto 1; como ese factor también se usa en los productos 2, 3... n, el consumo total es [A₁₁ λ₁ + A12 λ₂ +...+ A1n λ_n] y la restricción define el consumo máximo que se puede alcanzar (P₁); no obstante admite que se consuma una cantidad inferior, incluso que se consuma todo el inventario (porque está definida como una desigualdad ≤).

Continuando con el ejemplo anterior, considere que la elaboración de cada unidad de los productos X e Y consume respectivamente 9 y 5 unidades de cierto recurso, del cual actualmente disponemos en una cantidad limitada de 100 unidades. El consumo total es 9X + 5Y y esa cantidad debe ser igual o inferior a la disponibilidad (100 unidades), de manera que nuestro modelo incluiría la siguiente restricción: 9X + 5Y ≤ 100.

Aunque tiene cierta similitud externa con un sistema de (in)ecuaciones, el tratamiento de un modelo de programación matemática es complejo porque implica hallar una única solución óptima, dentro de un conjunto indeterminadamente grande de posibles soluciones. La manera de abordar el problema depende específicamente de su formulación matemática: lineal, cuadrático, aleatorio, etc.

En el caso de la programación lineal, el algoritmo más común es el Simplex, que se basa modificar iterativamente la solución en función de los cambios marginales que experimenta su valor. Es un método eficiente, en el sentido de que nos lleva rápidamente a la solución óptima, pero desde luego requiere un cierto trabajo en términos de tiempo y cálculo.

Existe software capaz de resolver estos modelos y también otros programas más complejos: cuadráticos, multiobjetivo, etc. Pero también podemos tratarlos fácilmente con una hoja de cálculo, empleando el Solver de Excel o el Solucionador de LibreOffice (puede obtener más detalles aquí). Lo realmente importante es que debe centrar su atención en la especificación del modelo, no en cómo lo va a solucionar.

Estas son algunas lecturas recomendadas, en relación a la programación lineal:

• Doldán, F. R. (1989):  Modelos de optimización aplicables a la gestión de la producción. Santiago: Tórculo
  Una exposición precisa y rigurosa de la fundamentación matemática de la PL, de sus teoremas fundamentales, y del algoritmo simplex
• Doldán, F. R. et al. (2000): Análisis económico - financiero de la producción (II). Santiago: Torculo
  Una compilación de ejercicios y casos resueltos de programación lineal, orientados a la programación de la producción (pero extrapolables a la selección de inversiones)