Programación lineal
Programación lineal — es una rama de la programación matemática y un método ampliamente utilizado en la investigación de operaciones, dedicado al desarrollo de la teoría y los métodos para resolver problemas de búsqueda de un extremo (máximo o mínimo) de una función lineal sujeta a restricciones lineales.
La PL es una de las herramientas más potentes y frecuentemente aplicadas para resolver problemas de optimización en economía, gestión, planificación, logística y otras áreas.
Objeto y propósito
La tarea principal de la programación lineal es encontrar la mejor manera (óptima) de asignar recursos limitados para alcanzar un objetivo determinado, cuando tanto el objetivo como las restricciones en el uso de los recursos pueden expresarse mediante dependencias lineales.
- La programación lineal permite resolver problemas prácticos tales como:
- Planificación óptima de la producción.
- Optimización de los flujos de transporte (problema de transporte).
- Distribución óptima de las inversiones.
- Corte óptimo de materiales. Problema de la asignación.
Formulación matemática del problema de PL
El problema estándar de la programación lineal se formula de la siguiente manera:
Se requiere encontrar los valores de las variables de decisión que maximizan o minimizan una función objetivo lineal. Al mismo tiempo, a las variables de decisión se les imponen restricciones en forma de un sistema de igualdades y/o desigualdades lineales. Por lo general, se añade la condición de no negatividad de las variables de decisión (sus valores deben ser mayores o iguales a cero), lo que a menudo está dictado por el sentido físico o económico del problema.
Matemáticamente, esto implica trabajar con funciones lineales y sistemas de ecuaciones y/o desigualdades lineales.
Conceptos básicos de la PL
- Variables de decisión (Variables controlables): Magnitudes cuyos valores deben determinarse durante la resolución del problema (por ejemplo, los volúmenes de producción de diferentes productos, la cantidad de recursos asignados a diferentes fines).
- Función objetivo: Una función lineal de las variables de decisión cuyo valor se busca maximizar o minimizar. Expresa cuantitativamente el objetivo del problema (por ejemplo, el beneficio total, los costes totales).
- Restricciones: Un sistema de igualdades y/o desigualdades lineales que deben satisfacer las variables de decisión. Las restricciones reflejan los límites de los recursos, los requisitos tecnológicos, las metas de planificación y otras condiciones del problema.
- Región de soluciones factibles (RSF): El conjunto de todas las combinaciones de valores de las variables de decisión que satisfacen todas las restricciones del problema. Geométricamente, en un espacio multidimensional, la RSF representa un poliedro convexo, posiblemente no acotado o vacío.
- Solución factible: Cualquier combinación de valores de las variables que pertenece a la RSF.
- Solución óptima: Una solución factible en la que la función objetivo alcanza su valor extremo (máximo o mínimo). Si existe una solución óptima, siempre se encuentra en la frontera de la RSF, como mínimo en uno de los vértices del poliedro convexo que conforma la RSF (teorema fundamental de la PL).
Métodos para resolver problemas de PL
Existen varios métodos principales para resolver problemas de programación lineal:
- Método gráfico: Se aplica a problemas con dos variables de decisión. Permite representar visualmente la RSF y la función objetivo en un plano para encontrar la solución óptima mediante el análisis de los vértices de la RSF o el desplazamiento de la línea de nivel de la función objetivo.
- Método símplex: Un algoritmo iterativo universal desarrollado por George Dantzig. El método se mueve secuencialmente de un vértice de la RSF a otro adyacente, mejorando el valor de la función objetivo en cada paso hasta encontrar la solución óptima. Es el método clásico y más conocido para resolver problemas de PL.
- Métodos de punto interior: Una clase alternativa de algoritmos que surgieron después del método símplex. Se mueven hacia la solución óptima por el interior de la RSF, en lugar de a lo largo de sus fronteras. Estos métodos son especialmente eficaces para resolver problemas de PL de muy gran dimensión.
Dualidad en la programación lineal
A cada problema de programación lineal (llamado problema primal) se le puede asociar otro problema de PL, llamado problema dual. Los problemas primal y dual están estrechamente relacionados entre sí:
La solución de un problema proporciona información sobre la solución del otro. Los valores óptimos de las funciones objetivo en ambos problemas coinciden (si existen). Las variables del problema dual tienen una importante interpretación económica: corresponden a los precios sombra (o valoraciones duales) de los recursos, mostrando cuánto cambiará el valor óptimo de la función objetivo del problema primal ante un pequeño cambio en la restricción del recurso correspondiente.
Aplicaciones de la PL
La programación lineal encuentra una amplia aplicación en:
- Economía y negocios (planificación de la producción, logística, finanzas, marketing).
- Industria (optimización de procesos tecnológicos, gestión de inventarios, corte de materiales).
- Transporte (optimización de rutas, horarios). Agricultura (optimización de superficies de cultivo, raciones de alimentación).
- Sector energético (optimización de la carga de las unidades de generación).
Véase también
Bibliografía
- Dantzig, G. Programación lineal, sus aplicaciones y generalizaciones. — Moscú: Progreso, 1966.
- Yudin, D. B., Golstein, E. G. Programación lineal (teoría, métodos y aplicaciones). — Moscú: Nauka, 1969.
- Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
- Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)