Programación lineal
La programación lineal (PL) optimiza una función objetivo lineal sobre una región factible definida por restricciones lineales de igualdad y desigualdad. Es la base de la investigación operativa y el problema que resuelve el método Simplex. La clave geométrica: el óptimo siempre está en un vértice del politopo factible.
Formulación estándar
Un programa lineal en forma estándar:
\[\min_{x} \mathbf{c}^T x \quad \text{sujeto a} \quad \mathbf{A}x = \mathbf{b},\quad x \geq \mathbf{0}\]
donde \(x \in \mathbb{R}^n\) son las variables de decisión, \(\mathbf{c} \in \mathbb{R}^n\) son los coeficientes de la función objetivo, \(\mathbf{A} \in \mathbb{R}^{m \times n}\) es la matriz de restricciones y \(\mathbf{b} \in \mathbb{R}^m\) son los valores del lado derecho.
Cualquier PL con restricciones de desigualdad \(\mathbf{A}x \leq \mathbf{b}\) puede convertirse a forma estándar introduciendo variables de holgura \(s \geq 0\):
\[\mathbf{A}x + s = \mathbf{b}, \quad x \geq 0, \quad s \geq 0\]
Un problema de maximización \(\max \mathbf{c}^T x\) se convierte minimizando \(-\mathbf{c}^T x\).
Geometría: por qué el óptimo está en un vértice
La región factible \(\mathcal{F} = \{x : \mathbf{A}x \leq \mathbf{b},\, x \geq 0\}\) es un politopo convexo: la intersección de finitos semiespacios. Como \(f(x) = \mathbf{c}^T x\) es lineal (y por tanto convexa), su mínimo sobre un conjunto convexo se alcanza en un punto extremo, un vértice del politopo.
Este es el hecho clave que hace tratable la PL: en lugar de buscar en todo \(\mathcal{F}\) (infinitos puntos), solo hay que comprobar los vértices (finitos). El método Simplex lo aprovecha moviéndose de vértice en vértice por las aristas, mejorando siempre la función objetivo.
La región sombreada es el conjunto factible. Las curvas de nivel del objetivo (líneas de igual valor) se desplazan en la dirección de aumento de \(3x+2y\). El óptimo está en el vértice \((3,1)\), donde \(3(3)+2(1)=11\): el último vértice alcanzado antes de salir de la región factible.
Ejemplo completo: planificación de la producción
Una fábrica produce dos productos, A y B. Cada unidad de A requiere 1 hora de mecanizado y 2 horas de montaje. Cada unidad de B requiere 2 horas de mecanizado y 1 hora de montaje. Disponibilidad diaria: 8 horas de mecanizado y 10 horas de montaje. Beneficio: 5 € por unidad de A y 4 € por unidad de B.
Formulación:
\[\max\; 5x_A + 4x_B\]
\[\text{sujeto a:} \quad x_A + 2x_B \leq 8 \quad \text{(mecanizado)}\]
\[2x_A + x_B \leq 10 \quad \text{(montaje)}\]
\[x_A, x_B \geq 0\]
Vértices de la región factible:
| Vértice | \(x_A\) | \(x_B\) | Beneficio |
|---|---|---|---|
| \((0, 0)\) | 0 | 0 | 0 |
| \((5, 0)\) | 5 | 0 | 25 |
| \((4, 2)\) | 4 | 2 | 28 |
| \((0, 4)\) | 0 | 4 | 16 |
La intersección de las dos restricciones activas da \((4, 2)\): resolver \(x_A + 2x_B = 8\) y \(2x_A + x_B = 10\) de forma simultánea.
Solución óptima: producir 4 unidades de A y 2 unidades de B para un beneficio de 28 €.
Casos especiales
⚠️ Tres situaciones en las que el PL no tiene un óptimo finito único
1. Problema infactible: las restricciones son contradictorias y la región factible está vacía. Ejemplo: exigir \(x \geq 5\) y \(x \leq 3\) simultáneamente. El PL no tiene solución.
2. Problema no acotado: la región factible se extiende hasta el infinito en la dirección de mejora. Ejemplo: maximizar \(x\) con solo la restricción \(x \geq 0\). El PL no tiene óptimo finito. Comprueba siempre que tu problema está acotado.
3. Óptimos múltiples: la función objetivo es paralela a una de las fronteras de las restricciones. El óptimo se alcanza en todos los puntos de una cara (arista en 2D) del politopo, no en un único vértice. Cualquier combinación convexa de los dos vértices óptimos es también óptima.
Dualidad
Todo PL (el primal) tiene asociado un PL dual. Para el primal \(\min \mathbf{c}^T x\) s.a. \(\mathbf{A}x \geq \mathbf{b}\), \(x \geq 0\), el dual es:
\[\max \mathbf{b}^T y \quad \text{s.a.} \quad \mathbf{A}^T y \leq \mathbf{c},\quad y \geq 0\]
Dualidad fuerte: si el primal tiene un valor óptimo finito, el dual también lo tiene, y son iguales: \(\mathbf{c}^T x^* = \mathbf{b}^T y^*\). Las variables duales \(y^*\) son los precios sombra: miden cuánto mejora el objetivo óptimo si la restricción correspondiente se relaja en una unidad.
💡 Programación lineal en R
library(lpSolve)
# Ejemplo de planificación de la producción: max 5*xA + 4*xB
obj <- c(5, 4)
mat <- matrix(c(1,2, 2,1), nrow=2, byrow=TRUE)
rhs <- c(8, 10)
dir <- c("<=", "<=")
sol <- lp("max", obj, mat, dir, rhs)
sol$solution # x óptimo
sol$objval # valor óptimo
# Con el paquete lpSolveAPI para problemas más complejos
# Con CVXR para optimización convexa (LP, QP, SOCP)
library(CVXR)
x <- Variable(2, nonneg = TRUE)
prob <- Problem(Maximize(c(5,4) %*% x),
list(c(1,2) %*% x <= 8,
c(2,1) %*% x <= 10))
solve(prob)
