Programación Lineal (LP)

La programación lineal es la clase de problemas max c^T x s.a. Ax ≤ b, x ≥ 0 en forma canónica, donde c ∈ R^n es el vector de costes, A ∈ R^(m×n) la matriz de restricciones, b ∈ R^m el lado derecho y x ∈ R^n las variables de decisión reales continuas. La región factible X = {x : Ax ≤ b, x ≥ 0} es un politopo convexo y un objetivo lineal alcanza su óptimo en un vértice (solución básica factible). La disciplina nació con el algoritmo simplex de George B. Dantzig en 1947, motivado por problemas de planificación de la Fuerza Aérea de EE. UU. (de ahí el término 'programación', anterior a su uso informático). La teoría de dualidad (von Neumann 1947) asocia un LP dual a cada LP primal; el teorema de dualidad fuerte establece que, si ambos son factibles y acotados, sus valores óptimos coinciden; los precios sombra se leen de las variables duales. Complejidad: Klee y Minty (1972) demostraron el peor caso exponencial del simplex; Khachiyan (1979) aportó el primer algoritmo polinómico para LP mediante el método del elipsoide (teórico); Karmarkar (1984) introdujo un método de punto interior polinómico y práctico. Los solucionadores modernos combinan simplex revisado y punto interior, con presolve, factorización LU dispersa y arranque crash, resolviendo problemas de millones de variables en segundos. Aplicaciones: planificación de la producción, problemas de mezclas, transporte, gestión de flujos de caja y el problema de la dieta.