Programación lineal

La programación lineal (LP) consiste en minimizar o maximizar una función objetivo lineal sujeta a restricciones de límite, igualdad lineal y desigualdad. Algunos ejemplos de estos problemas son el mezclado en las industrias de procesos, la planificación de la producción en la fabricación, el ajuste del flujo de efectivo en finanzas, y la planificación en los sectores de energía y transporte.

La programación lineal es un problema matemático que consiste en hallar un vector x para minimizar la función:

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

Conforme a las restricciones:

\[\begin{eqnarray}Ax \leq b & \quad & \text{(restricción de desigualdad)} \\A_{eq}x = b_{eq} & \quad & \text{(restricción de igualdad)} \\lb \leq x \leq ub & \quad & \text{(restricción de límite)}\end{eqnarray}\]

Puede utilizar MATLAB^® para implementar los siguientes algoritmos de uso habitual para resolver problemas de optimización lineal:

• Punto interior: utiliza un algoritmo predictor-corrector primal-dual y resulta especialmente útil para programas lineales a gran escala que tienen estructura o se pueden definir utilizando matrices dispersas.
• Símplex: emplea un procedimiento sistemático para generar y probar las soluciones de vértice candidatas para un programa lineal. El algoritmo símplex y el algoritmo símplex dual relacionado son los algoritmos de uso más amplio en la programación lineal.

Los algoritmos para algunos casos especiales de programas lineales, en que las restricciones tienen una estructura de red, suelen ser más rápidos que los algoritmos símplex y de punto interior de uso general. Estos son algunos casos especiales:

• Flujo máximo de redes: utiliza algoritmos push-relabel y de camino de aumento.
• Ruta más corta: utiliza algoritmos de Dijkstra, de Bellman-Ford y de búsqueda.
• Asignación lineal: utiliza un algoritmo de coincidencia bipartita.

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