Programación Lineal Determinista — LP Clásico con Parámetros Ciertos
- Propuesto por
- George B. Dantzig
- Año
- 1947
- Tipo
- Deterministic mathematical optimization
- Familia
- Simulation / 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 Determinista (PLD) es la forma clásica de programación lineal en la que todos los coeficientes de la función objetivo, los coeficientes de las restricciones y los valores del lado derecho se conocen con certeza.
Encuentra la asignación óptima de recursos para maximizar o minimizar un objetivo lineal sujeto a restricciones lineales, proporcionando una solución exacta y reproducible bajo datos fijos y ciertos.
La intuición detrás del método
Imagine asignar un presupuesto fijo a proyectos, cada uno con costos y rendimientos conocidos, sujeto a límites de recursos que conoce con precisión. La PLD codifica esto como un sistema de desigualdades lineales y encuentra la solución de punto extremo que extrae el máximo valor de esas restricciones. Dado que cada parámetro es cierto —sin distribuciones de probabilidad, sin ambigüedad— el solucionador devuelve un único plan óptimo exacto en lugar de una distribución de resultados. Esta claridad hace que la PLD sea el modelo de primera elección natural cuando los datos están bien medidos y la incertidumbre no es una preocupación principal.
Historia
La programación lineal fue formalizada por George B. Dantzig en 1947 con el desarrollo del algoritmo Simplex mientras trabajaba para la Fuerza Aérea de EE. UU. La monografía de Dantzig de 1963 se convirtió en la referencia canónica. El calificador 'determinista' surgió a medida que se introdujeron variantes de PL estocástica (Dantzig y Beale, años 50-60) para distinguir el modelo original de parámetros ciertos de sus extensiones probabilísticas.
Cuándo usarlo
Utilice Programación Lineal Determinista cuando el problema de decisión pueda modelarse con un objetivo lineal y restricciones lineales, y cuando todos los parámetros se conozcan con suficiente certeza como para justificar su tratamiento como constantes fijas. Los entornos ideales incluyen la planificación de la producción, el transporte y la logística, los problemas de dietas y mezclas, y el flujo en redes bajo condiciones estables. NO utilice PLD cuando los parámetros sean genuinamente inciertos y el riesgo sea importante — prefiera PL Estocástica o PL Robusta en su lugar. Evite la PLD cuando el objetivo o las restricciones sean no lineales, cuando las variables deban ser enteras (use PIM), o cuando se deban equilibrar múltiples objetivos conflictivos simultáneamente sin agregarlos en una suma ponderada (use PL multiobjetivo o programación por objetivos).
Limitaciones y consideraciones
- Requiere que todas las relaciones sean estrictamente lineales: las curvas de costos no lineales o los rendimientos decrecientes no pueden capturarse sin aproximación.
- Todos los parámetros deben ser conocidos y fijos; el modelo no proporciona un mecanismo nativo para manejar la incertidumbre o el error de estimación de parámetros.
- La solución óptima puede no ser única (degenerada), lo que hace que la elección de la base a reportar sea ambigua sin criterios adicionales.
- Los requisitos enteros o combinatorios (p. ej., decisiones de sí/no) requieren una extensión a la programación entera mixta, que es computacionalmente más difícil.
- Los problemas a gran escala con matrices de restricciones densas pueden consumir mucha memoria incluso para solucionadores modernos.
Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.
Fortalezas
- Solución óptima global garantizada para cualquier instancia de PL factible y acotada debido a la convexidad.
- Altamente escalable: los solucionadores modernos manejan millones de variables y restricciones en segundos.
- Las variables duales y el análisis de sensibilidad proporcionan una rica interpretación económica de los precios sombra y el rango.
- Formulación transparente y auditable: cada suposición es explícita en la matriz de restricciones.
- Ecosistema de software maduro (CPLEX, Gurobi, HiGHS, GLPK) con implementaciones confiables y bien probadas.
- Señal clara de factibilidad de pasar/fallar: la infactibilidad revela inmediatamente una mala especificación del modelo.
Aplicaciones
- Planificación de producción y fabricación con capacidades de recursos fijas y demanda conocida.
- Transporte y logística: encontrar rutas de envío de costo mínimo a través de una red.
- Problemas de dietas y mezclas: formular mezclas nutricionales o químicas de menor costo que satisfagan las restricciones de composición.
- Optimización de carteras financieras bajo rendimiento lineal y restricciones presupuestarias.
- Planificación de sistemas energéticos: despacho óptimo de unidades de generación de energía con costos y capacidades conocidas.
- Diseño de redes de cadenas de suministro cuando la demanda y los tiempos de entrega se tratan como constantes conocidas.
Cómo funciona
Cómo funciona
Defina las variables de decisión x (p. ej., cantidades de producción, flujos), la función objetivo c^T x a minimizar o maximizar, y el conjunto de restricciones Ax <= b con x >= 0. Todos los coeficientes en c, A y b se tratan como constantes exactas y conocidas — esto es lo que hace que el modelo sea determinista. Escriba la PL en forma estándar: min c^T x sujeto a Ax = b, x >= 0.
Fórmula
\min_{x} \; c^\top x \quad \text{s.t.} \quad Ax \leq b, \; x \geq 0Antes de optimizar, verifique que la región factible no esté vacía (el conjunto de restricciones tiene al menos una solución) y que el objetivo esté acotado. Si la región factible está vacía, el problema es infactible; si el objetivo no está acotado, el modelo está mal especificado. Estas comprobaciones las realizan automáticamente los solucionadores, pero deben ser interpretadas por el analista para detectar errores de formulación.
Resuelva la PL utilizando el algoritmo Simplex (pivotando a lo largo de los bordos del politopo convexo hacia el vértice óptimo) o un método de punto interior (siguiendo un camino a través del interior de la región factible). Ambos enfoques explotan la convexidad del conjunto factible y la linealidad del objetivo, garantizando que cualquier óptimo local sea global. Los solucionadores modernos (CPLEX, Gurobi, HiGHS) manejan eficientemente millones de variables y restricciones.
El solucionador devuelve el vector de decisión óptimo x* y el valor objetivo óptimo c^T x*. Dado que la región factible es un politopo convexo y el objetivo es lineal, el óptimo siempre se alcanza en un vértice (solución básica factible). Registre x* y verifique que satisface todas las restricciones, luego tradúzcalo de nuevo a términos gerenciales (p. ej., unidades a producir, rutas a utilizar).
Fórmula
x^* = \arg\min \{ c^\top x : Ax \leq b,\; x \geq 0 \}Después de obtener x*, realice un análisis de sensibilidad (post-óptimo) para determinar cuánto puede cambiar cada coeficiente en c o b antes de que la base actual —y, por lo tanto, la solución óptima— cambie. Los precios sombra (variables duales) cuantifican el valor marginal de relajar cada restricción. Aunque el modelo es determinista, el análisis de sensibilidad revela la robustez de la solución ante errores de estimación de parámetros sin abandonar el marco determinista.
Errores comunes
- Tratar parámetros inciertos como estimaciones puntuales fijas sin un análisis de sensibilidad posterior puede producir soluciones que son óptimas en el papel pero frágiles en la práctica.
- Olvidar incluir restricciones de no negatividad o límites lógicos puede producir soluciones matemáticamente óptimas pero operativamente infactibles (p. ej., cantidades de producción negativas).
- Malinterpretar los precios sombra como valores marginales garantizados fuera del rango de validez identificado en el análisis de rango.
- Usar PLD cuando el problema real tiene estructura entera (p. ej., número de camiones) y redondear soluciones de PL — esto puede violar restricciones o perder óptimos verdaderos.
- Agregar excesivamente objetivos en una única suma ponderada sin validar que los pesos reflejen con precisión las preferencias de las partes interesadas, ocultando compensaciones importantes.
Preguntas frecuentes
¿Qué hace que la PL sea 'determinista' en contraposición a 'estocástica'?
En PL determinista, cada coeficiente en la función objetivo, la matriz de restricciones y el vector del lado derecho es una constante conocida. La PL estocástica, por el contrario, trata algunos o todos estos como variables aleatorias con distribuciones de probabilidad, buscando soluciones que funcionen bien en promedio o con alta probabilidad en diferentes escenarios.
¿El algoritmo Simplex es siempre eficiente?
En la práctica, sí: el método Simplex resuelve prácticamente todas las PL del mundo real de forma extremadamente rápida. Teóricamente puede llevar tiempo exponencial en el peor de los casos (ejemplos de Klee-Minty), pero los métodos de punto interior (p. ej., algoritmo de Karmarkar) se ejecutan en tiempo polinomial y son competitivos para instancias muy grandes.
¿Puedo usar PLD si algunas de mis variables de decisión deben ser números enteros?
No. Si las variables deben ser enteras (p. ej., número de máquinas a comprar), el modelo se convierte en un programa lineal mixto o entero puro. Resolver la relajación de PL y redondear puede violar restricciones o perder el óptimo entero verdadero; use un solucionador PIM dedicado en su lugar.
¿Cómo ayudan los precios sombra después de resolver?
El precio sombra (variable dual) de una restricción le indica cuánto mejoraría el valor objetivo si el lado derecho de esa restricción se relajara en una unidad, dentro del intervalo de rango válido. Esto guía las decisiones sobre dónde invertir para expandir la capacidad de manera más rentable.
¿Cuándo debo actualizar de PLD a PL Robusta o Estocástica?
Actualice cuando la incertidumbre de los parámetros no sea trivial y el costo de una solución infactible o pobre bajo los valores de parámetros realizados sea significativo. Si una desviación del 10-20% en un coeficiente clave cambiara la solución preferida o causara una violación de la restricción, la suposición de certeza de la PLD es demasiado fuerte.
Métodos relacionados
Fuentes
Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press, Princeton, NJ.
ISBN: 9780691059136Copiado.Linear programming. Wikipedia.
Abrir referencia de la publicaciónCopiado.