Programación Lineal — Optimización de Objetivos Lineales Bajo Restricciones Lineales
- Propuesto por
- George B. Dantzig
- Año
- 1947
- Tipo
- Mathematical programming / continuous optimization
Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés
¿Qué hace?
La programación lineal (PL), impulsada por George B. Dantzig en 1947, es un método matemático para encontrar el valor óptimo de una función objetivo lineal —como el coste mínimo o el beneficio máximo— sujeta a un conjunto de restricciones de desigualdad y igualdad lineales.
Es la técnica fundamental en investigación de operaciones y subyace a la planificación de la producción, la asignación de recursos, la logística, los problemas de dietas y un sinfín de escenarios de toma de decisiones en ingeniería, economía y ciencias naturales.
La intuición detrás del método
Imagine que dirige una pequeña fábrica que produce dos productos. Cada producto le genera un beneficio determinado, pero su fabricación consume materias primas y tiempo de máquina limitados. La programación lineal encuentra la combinación exacta de productos que exprime el máximo beneficio de sus recursos fijos, sin violar ningún límite físico o contractual. La parte 'lineal' significa que el beneficio y el consumo de recursos escalan en una relación lineal con las cantidades que produce. Las opciones factibles forman un polígono (en dos dimensiones) o un poliedro (en dimensiones superiores), y la respuesta óptima siempre se encuentra en una de sus esquinas.
Historia
El desarrollo sistemático de la programación lineal comenzó en 1947 cuando George B. Dantzig, trabajando para la Fuerza Aérea de EE. UU., inventó el algoritmo Simplex para automatizar la planificación logística militar. Dantzig publicó la teoría fundamental en su monografía de 1963, que sigue siendo la referencia canónica. Trabajos independientes y paralelos de Leonid Kantorovich en la Unión Soviética (1939) abordaron la planificación de la producción utilizando ideas matemáticas similares, y Kantorovich fue galardonado con el Premio Nobel de Economía en 1975 en parte por esta contribución. La cuestión teórica de la resolubilidad en tiempo polinomial se resolvió con el método de elipsoides de Khachian (1979) y más tarde con el método de punto interior de Karmarkar (1984), que demostraron ser prácticamente rápidos para problemas a gran escala. Hoy en día, los solucionadores de PL comerciales y de código abierto están integrados en la planificación de recursos empresariales, la programación de aerolíneas y los sistemas energéticos en todo el mundo.
Cuándo usarlo
La programación lineal es apropiada siempre que necesite optimizar una cantidad que dependa linealmente de un conjunto de variables de decisión, y todas las restricciones también sean lineales. No requiere suposiciones distributivas ni un tamaño de muestra mínimo; es un modelo matemático determinista, no un estimador estadístico. El método se aplica cuando las variables de decisión son continuas (los valores fraccionarios tienen sentido); si las variables deben ser números enteros o binarios, se necesita en su lugar la programación entera. La PL se utiliza ampliamente en la planificación de la producción, la logística de la cadena de suministro, los problemas de dietas y mezclas, la optimización de carteras financieras, los problemas de transporte y asignación, y el despacho de energía.
Limitaciones y consideraciones
- Requisito de linealidad: si el objetivo o alguna restricción es no lineal, el modelo de PL está mal especificado y la solución puede ser incorrecta o infactible.
- Solo variables continuas: cuando las variables de decisión deben tomar valores enteros o binarios, la relajación de PL proporciona un límite inferior pero no una solución válida; se debe utilizar la programación entera.
- Determinista: la PL no modela la incertidumbre en los parámetros; se necesita programación estocástica u optimización robusta cuando los datos son inciertos.
- Degeneración y ciclado: en casos raros, el método Simplex puede ciclar entre bases degeneradas sin converger, aunque las reglas anti-ciclado (p. ej., la regla de Bland) resuelven esto.
Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.
Fortalezas
- Óptimo global garantizado: dado que la región factible es un poliedro convexo, cualquier óptimo local es también un óptimo global, sin riesgo de quedar atrapado en una solución subóptima.
- Altamente escalable: los solucionadores modernos (HiGHS, Gurobi, CPLEX) manejan modelos con millones de variables y restricciones en segundos.
- Rica información post-solución: los precios sombra y los rangos de sensibilidad proporcionan información procesable sobre el valor de los recursos y la robustez de la solución sin ejecuciones adicionales.
- Sin supuestos distributivos: la PL es un modelo puramente algebraico, por lo que no requiere normalidad ni ninguna propiedad estadística de los datos.
Aplicaciones
- Planificación de la producción: encontrar la combinación óptima de productos que maximice el beneficio respetando la capacidad de las máquinas y los límites de materias primas.
- Logística de la cadena de suministro y transporte: minimizar los costes de envío a través de una red de almacenes y clientes.
- Problemas de dietas y mezclas: seleccionar las cantidades de ingredientes que cumplen los requisitos nutricionales al menor coste.
- Optimización de carteras financieras: asignar capital entre activos para maximizar el rendimiento esperado sujeto a restricciones de riesgo y regulatorias.
- Despacho de energía y programación de redes eléctricas: minimizar el coste del combustible mientras se satisface la demanda de electricidad y los límites de capacidad de los generadores.
- Programación de personal y mano de obra: asignar turnos a los trabajadores para cubrir la demanda al menor coste laboral.
Cómo funciona
Cómo funciona
El problema de decisión del mundo real se traduce a símbolos matemáticos. Usted identifica las variables de decisión (las cantidades que puede controlar), escribe la función objetivo (lo que desea maximizar o minimizar) como una combinación lineal de esas variables, y escribe cada restricción —límites de recursos, capacidades máximas, requisitos de demanda— como una desigualdad o igualdad lineal. Una PL bien formulada tiene un objetivo claro, límites explícitos para las variables y cada restricción estructural expresada linealmente.
El modelo se lleva a una forma canónica o estándar que un solucionador puede procesar. Las desigualdades se convierten en igualdades introduciendo variables de holgura o excedente no negativas, y cualquier variable sin restricciones se reemplaza por la diferencia de dos variables no negativas. Este paso mecánico produce el tableau o la representación matricial sobre la que actúa el algoritmo, y no altera el problema, solo lo remodela para el cálculo.
Un solucionador busca en el poliedro factible la esquina óptima. El método Simplex clásico pivota de vértice en vértice a lo largo de las aristas del poliedro, siempre mejorando (o manteniendo) el objetivo, hasta que no existe un vecino que lo mejore. Los métodos de punto interior (barrera) viajan en cambio por el interior de la región factible a lo largo de un camino central, lo que resulta especialmente eficiente para modelos muy grandes. Ambas familias tienen garantizado encontrar un óptimo global cuando existe uno, ya que la región factible es convexa.
El solucionador devuelve los valores óptimos de las variables de decisión y el valor objetivo óptimo, junto con las variables duales (precios sombra) y los rangos de sensibilidad. Los precios sombra cuantifican cuánto mejoraría el objetivo si una restricción vinculante se relajara en una unidad, indicando directamente a un decisor dónde serían más valiosos los recursos adicionales. El análisis de sensibilidad identifica cuánto puede cambiar un coeficiente de coste o un valor del lado derecho antes de que la base actual deje de ser óptima.
Errores comunes
- Aplicar PL cuando las restricciones o el objetivo son no lineales: la solución será incorrecta o el solucionador rechazará el modelo.
- Ignorar los requisitos de integralidad: redondear una solución continua de PL a enteros no produce, en general, una solución entera factible u óptima; utilice programación entera en su lugar.
- Modelos infactibles o no acotados: si la región factible está vacía (restricciones conflictivas) o el objetivo no está acotado (faltan restricciones de cota), el solucionador informará de un fallo; siempre revise la estructura del modelo antes de ejecutar.
- Tratar la salida de PL como una recomendación sin análisis de sensibilidad: una solución que es técnicamente óptima puede estar en un borde muy estrecho donde un pequeño cambio en los datos cambia la recomendación; siempre se deben inspeccionar los rangos de sensibilidad.
Preguntas frecuentes
¿Qué hace que un problema sea 'lineal' a efectos de PL?
Tanto la función objetivo como cada restricción deben ser lineales, lo que significa que cada término es una constante multiplicada por una única variable de decisión, sin productos de variables, sin exponentes y sin funciones no lineales. Si incluso una restricción o el objetivo involucra, por ejemplo, x por y o x al cuadrado, la PL estándar ya no se aplica y se necesita un solucionador de programación no lineal o cuadrática.
¿Por qué la solución óptima siempre se encuentra en una esquina de la región factible?
La región factible definida por restricciones lineales es un poliedro (o politopo) convexo. Una función objetivo lineal es en sí misma lineal, por lo que no puede ser 'atraída' hacia el interior de un conjunto convexo; siempre alcanza su valor extremo en la frontera, y específicamente en un vértice (punto esquina). Esta es la idea geométrica que subyace a la estrategia de vértice a vértice del método Simplex.
¿Cuándo debo usar programación entera en lugar de PL?
Siempre que una o más variables de decisión deban tomar valores enteros o binarios (0/1), por ejemplo, si abrir una instalación (sí/no), cuántos camiones despachar (números enteros) o qué artículos incluir en una selección. Simplemente resolver la PL y redondear la solución continua no es fiable: las soluciones redondeadas pueden ser infactibles o estar lejos de ser óptimas. La programación entera maneja la integralidad correctamente, a un mayor coste computacional.
¿Qué me dicen los precios sombra?
Un precio sombra (variable dual) para una restricción vinculante indica cuánto mejoraría el valor objetivo óptimo si el lado derecho de esa restricción se relajara en una unidad, manteniendo todo lo demás constante. Por ejemplo, un precio sombra de 3 en una restricción de horas de mano de obra significa que añadir una hora más de mano de obra mejoraría el objetivo en 3 unidades. Las restricciones que no están vinculadas tienen un precio sombra de cero; no limitan el óptimo actual.
Métodos relacionados
Fuentes
Dantzig, G.B. (1963). Linear Programming and Extensions. Princeton University Press.
ISBN: 9780691059136Copiado.Vanderbei, R.J. (2014). Linear Programming: Foundations and Extensions. Springer.
Abrir referencia DOICopiado.