Introducción a la programación lineal

La programación lineal, también conocida como optimización lineal, consiste en minimizar o maximizar una función lineal objetivo sujeta a restricciones de límites, igualdad lineal y desigualdad lineal. Ejemplos de este tipo de problema son la mezcla de componentes en procesos industriales, la planificación de producción en fabricación, el ajuste de flujos de efectivo en finanzas y la planificación en los sectores de energía y transporte.

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

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

Con las siguientes 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}\]

Programación lineal con MATLAB

Puede utilizar MATLAB^® para implementar los siguientes algoritmos utilizados comúnmente para resolver problemas de programación lineal:

• Punto interior: Utiliza un algoritmo predictor-corrector primal-dual, y resulta especialmente útil para programas lineales de gran escala que tienen estructura o pueden definirse utilizando matrices dispersas.
• Símplex: Utiliza un procedimiento sistemático para generar y probar soluciones de vértice candidatas para un programa lineal. Los algoritmos símplex y dual-símplex son más utilizados en optimización lineal.

El solver linprog de Optimization Toolbox™ implementa estas técnicas de optimización lineal.

Casos especiales de programación lineal

Los algoritmos de algunos casos especiales de problemas de optimización lineal en los que las restricciones tienen una estructura de red suelen ser más rápidos que los algoritmos de punto interior y símplex de uso general. Algunos de estos casos especiales son:

• Flujo máximo de red: Utiliza algoritmos augmenting-path y push-relabel.
• Ruta más corta: Utiliza algoritmos de Dijkstra, Bellman-Ford y búsqueda.
• Asignación lineal: Utiliza un algoritmo de coincidencia bipartita.

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