Programación lineal

La programación lineal optimiza un objetivo lineal sujeto a restricciones de igualdad y desigualdad lineal. Puede identificar la mejor asignación viable de recursos escasos cuando las relaciones pueden representarse adecuadamente mediante un modelo lineal.

Cuándo usarlo

Utilice la programación lineal para problemas de planificación de producción, programación, enrutamiento, combinación, asignación, red y asignación de cartera donde las decisiones son divisibles o se pueden ampliar con restricciones de números enteros.

Puede responder:

• ¿Qué asignación de recursos factible maximiza la contribución o el servicio?
• ¿Qué horario minimiza el coste o el retraso?
• ¿Qué restricciones limitan el óptimo?
• ¿Cuánto vale la capacidad adicional dentro del modelo?

Orígenes

Leonid Kantoróvich formuló en 1937 uno de los primeros métodos de optimización lineal para la planificación de la producción. Durante y después de la Segunda Guerra Mundial, la investigación operativa amplió estos métodos. George Dantzig introdujo el algoritmo símplex en 1947, lo que hizo computacionalmente viables grandes clases de programas lineales. La técnica no se diseñó para maximizar las bajas enemigas, como a veces afirma una explicación excesivamente simplificada.

Qué es

Un modelo contiene variables de decisión, un objetivo lineal, restricciones y límites. Una solución factible satisface todas las restricciones; un óptimo tiene el mejor valor objetivo entre las soluciones factibles. Los precios sombra y el análisis de sensibilidad pueden revelar qué recursos se unen y qué tan estable es la respuesta.

Los supuestos incluyen proporcionalidad, aditividad, certeza y divisibilidad, a menos que la formulación agregue características enteras, estocásticas u otras. Una respuesta óptima a un modelo deficiente no es una decisión empresarial óptima.