Programación lineal

Minimización de funciones lineales sujetas a restricciones

La programación lineal (PL) implica la minimización o maximización de una función objetivo sujeta a restricciones de límites, igualdad lineal y desigualdad. Algunos ejemplos de estos problemas son la optimización de diseños en ingeniería, la maximización de beneficios en la fabricación, la optimización de carteras en finanzas y la planificación en el ámbito de la energía y el transporte.

La programación lineal es el problema matemático consistente en hallar un vector x que minimice la función:

\[\min_{x} \left\{f^{\mathsf{T}}x\right\}\]

Conforme a las restricciones lineales:

\[\begin{eqnarray}Ax \leq b & \quad & \text{(inequality constraint)} \\A_{eq}x = b_{eq} & \quad & \text{(equality constraint)} \\lb \leq x \leq ub & \quad & \text{(bound constraint)}\end{eqnarray}\]

Los siguientes algoritmos se utilizan habitualmente para solucionar problemas de programación lineal:

  • Punto interior: Utiliza un algoritmo predictor-corrector primal-dual y resulta especialmente útil para problemas a gran escala que tienen estructura o pueden definirse utilizando matrices dispersas.
  • Conjunto activo: Minimiza el objetivo en cada iteración sobre el conjunto activo (un subconjunto de las restricciones que están activas localmente) hasta que llega a una solución.
  • Símplex: Emplea un procedimiento sistemático a fin de generar y comprobar las soluciones vértice candidatas para un programa lineal. El algoritmo símplex es el algoritmo de uso más extendido en la programación lineal.

Para obtener más información sobre los algoritmos y la programación lineal, consulte Optimization Toolbox.



Referencias de software

También puede consultar: Optimization Toolbox, MATLAB, Optimization Toolbox, Global Optimization Toolbox, programación entera, programación cuadrática, programación no lineal, optimización multiobjetivo, algoritmo genético, recocido simulado (simulated annealing)