Optimización lineal, matemáticas para decidir mejor

La optimización lineal, conocida en sus orígenes como programación lineal, es la rama de las matemáticas dedicada a resolver problemas de decisión complejos cuando los recursos son limitados. Mediante modelos matemáticos simples pero poderosos, permite planificar, distribuir y asignar recursos de manera eficiente. Esta metodología tiene un impacto amplio en sectores como la logística, las finanzas y la planificación estratégica.

La programación lineal no debe confundirse con la programación informática. En este contexto, programación se refiere a planificar un conjunto de acciones para resolver un problema de manera óptima, no a escribir código. Para evitar estas confusiones, en 2010 la Mathematical Programming Society decidió cambiar su nombre a Mathematical Optimization Society, de manera que reflejara con mayor claridad su enfoque en la optimización matemática y la toma de decisiones eficiente.

Desarrollo histórico de la Optimización Lineal

La historia de la optimización lineal comienza mucho antes de que se formalizara como disciplina. Ya en 1826, Joseph Fourier desarrolló un método matemático para eliminar variables en sistemas de inecuaciones lineales, conocido hoy como Método de Eliminación de Fourier (Fourier, 1826). Su enfoque era puramente teórico, orientado a estudiar problemas de álgebra y análisis matemático. Casi un siglo después, en 1936, Théodore Motzkin amplió y formalizó este método para sistemas más complejos de inecuaciones, estableciendo así lo que hoy llamamos Método de Eliminación de Fourier-Motzkin (Motzkin, 1936). La diferencia fundamental entre ambos radica en que Fourier buscaba resolver problemas matemáticos generales, mientras que Motzkin sentó las bases para aplicaciones más amplias, acercándose al terreno de la optimización.

En 1939, Leonid Kantorovich publicó un libro, en ruso, (Kantorovich, 1939) donde proponía formulaciones de optimización lineal y un método sencillo, aunque poco eficiente, para resolver problemas de asignación de recursos. Este libro se tradujo al inglés en 1960 (Kantorovich, 1960). Poco después, en 1941, Frank Hitchcock aplicó la optimización lineal al problema de transporte (Hitchcock, 1941), mostrando cómo estas técnicas podían servir en situaciones concretas de logística.

El gran salto ocurrió en 1947, cuando George Dantzig desarrolló el Algoritmo del Símplex (Dantzig, 1951), un procedimiento eficiente capaz de resolver problemas de optimización lineal de manera práctica. Este algoritmo se considera piedra angular de la investigación operativa y uno de los avances más importantes del siglo XX (Cipra, 2000). En 1951, Tjalling Koopmans utilizó la optimización lineal para formular problemas económicos complejos, demostrando su utilidad en la planificación de recursos a gran escala (Koopmans, 1951). Décadas más tarde, en 1984, Narendra Karmarkar presentó el Método de Punto Interior (Karmarkar, 1984), mostrando que los problemas de optimización lineal podían resolverse en tiempo polinómico y no pertenecían a la clase $\mathcal{NP}$, como se pensaba anteriormente. $\mathcal{NP}$ incluye problemas cuya solución puede ser muy difícil de encontrar, mientras que $\mathcal{P}$ agrupa problemas que pueden resolverse eficientemente.

Por sus contribuciones a la teoría de la asignación óptima de recursos, Koopmans y Kantorovich recibieron el Premio Nobel de Economía en 1975. Sin embargo, Koopmans consideró que Dantzig también merecía el premio, dado que el Algoritmo del Símplex era fundamental para la aplicación práctica de la optimización lineal y para que sus ideas pudieran implementarse en el mundo real.

Después de ver cómo se desarrollaron los métodos que dieron forma a la optimización lineal, es útil entender los conceptos básicos que permiten formular y resolver estos problemas.

Conceptos básicos

En la optimización lineal, básicamente se trata de tomar decisiones inteligentes en un entorno con recursos limitados. Para ello, se usan tres elementos clave: las variables de decisión, que representan lo que podemos controlar o ajustar; la función objetivo, que indica lo que queremos lograr, es decir, cómo maximizar ganancias o minimizar costes; y el conjunto de restricciones, que representan las limitaciones del sistema, como por ejemplo, el presupuesto, el tiempo o los materiales disponibles. Juntos, estos elementos forman un conjunto de soluciones posibles, y la tarea de la optimización lineal es encontrar la mejor opción dentro de ese conjunto. Aunque la teoría pueda sonar abstracta, estos conceptos se aplican todos los días, para decidir cuántos productos fabricar hasta planificar rutas de reparto o asignar recursos en un hospital, entre otros múltiples ejemplos.

En optimización lineal, aunque los problemas puedan presentarse de formas muy distintas, se suelen transformar a formulación estándar o formulación canónica:

• Formulación estándar
  • Todas las restricciones se expresan como igualdades.
  • Todas las variables son no negativas.
  • Permite que los algoritmos trabajen de forma uniforme con cualquier problema.

\[\begin{aligned} \min\;\;\; & z = \mathbf{c}^\intercal \mathbf{x} \\ \text{s.a:}\;\;\; & \mathbf{A}\mathbf{x} = \mathbf{b} \\ & \mathbf{x} \geqslant \mathbf{0} \end{aligned}\]

• Formulación canónica
  • Se centra en problemas de maximización (equivalentemente minimización).
  • Las restricciones son del tipo ≤ (equivalentemente ≥).
  • Las variables son no negativas.
  • Es la forma más habitual de presentar problemas antes de aplicar los métodos de optimización.

\[\begin{aligned} \min\;\;\; & z = \mathbf{c}^\intercal \mathbf{x} \\ \text{s.a:}\;\;\; & \mathbf{A}\mathbf{x} \geqslant \mathbf{b} \\ & \mathbf{x} \geqslant \mathbf{0} \end{aligned} \qquad \begin{aligned} \max\;\;\; & z = \mathbf{c}^\intercal \mathbf{x} \\ \text{s.a:}\;\;\; & \mathbf{A}\mathbf{x} \leqslant \mathbf{b} \\ & \mathbf{x} \geqslant \mathbf{0} \end{aligned}\]

Aunque estas formulaciones puedan parecer abstractas, son esenciales para convertir problemas del mundo real en modelos matemáticos resolubles por algoritmos.

Ejemplo ilustrativo

Supongamos que una empresa produce dos productos, A y B, con los siguientes datos:

• Cada unidad de A genera 40€ de beneficio, y cada unidad de B genera 30€.
• Disponemos de 100 unidades de materia prima y 80 horas de tiempo de producción.
• Producir una unidad de A requiere 2 unidades de materia prima y 1 hora de tiempo.
• Producir una unidad de B requiere 1 unidad de materia prima y 2 horas de tiempo.

Podemos definir las variables de decisión:

• $x_A$ = número de unidades de producto A a producir.
• $x_B$ = número de unidades de producto B a producir.

La función objetivo, que queremos maximizar, es el beneficio total:

\[\max\; z = 40x_A + 30x_B\]

Las restricciones del sistema son:

• Materia prima disponible: \(2x_A + 1x_B \leqslant 100\)
• Tiempo disponible: \(1x_A + 2x_B \leqslant 80\)
• No se pueden producir cantidades no negativas: \(x_A \geqslant 0, \quad x_B \geqslant 0\)

Una vez definido así, este problema puede resolverse con el Símplex o métodos de punto interior, obteniendo la combinación óptima de productos A y B.

Aplicaciones prácticas y utilidad

La optimización lineal no es sólo un conjunto de fórmulas y algoritmos, su verdadero valor está en cómo se aplica para mejorar decisiones en la vida real. Hoy en día, esta herramienta se utiliza en logística, para planificar rutas de transporte y gestionar inventarios; en producción industrial, para asignar recursos de manera eficiente y maximizar beneficios; en finanzas, para diseñar carteras de inversión o presupuestos óptimos; en planificación estratégica, desde hospitales que gestionan camas y personal hasta empresas que optimizan la cadena de suministro. Como señalaba George Dantzig, uno de los padres fundadores de la optimización lineal, la optimización lineal permite formalizar objetivos y tomar decisiones óptimas incluso en sistemas complejos:

“Linear programming is viewed as a revolutionary development giving man the ability to state general objectives and to find, by means of the simplex method, optimal policy decisions for a broad class of practical decision problems of great complexity. In the real world, planning tends to be ad hoc because of the many special-interest groups with their multiple objectives” (Dantzig, 1983).

Desde Fourier hasta los métodos modernos, la optimización lineal muestra cómo la teoría matemática puede generar decisiones eficientes y tangibles en el mundo real, en sectores como logística, finanzas o producción industrial.