Programación lineal, técnica de modelado matemático en la que una función lineal se maximiza o minimiza cuando está sujeta a varias restricciones. Esta técnica ha sido útil para guiar las decisiones cuantitativas en la planificación empresarial, en la ingeniería industrial y, en menor medida, en las ciencias sociales y físicas.
optimización: programación lineal
Aunque ahora se usa ampliamente para resolver problemas de decisión cotidianos, la programación lineal era relativamente desconocida antes de 1947. Ningún trabajo significativo
La solución de un problema de programación lineal se reduce a encontrar el valor óptimo (mayor o menor, según el problema) de la expresión lineal (llamada función objetivo)
sujeto a un conjunto de restricciones expresadas como desigualdades:
Las a, b y c son constantes determinadas por las capacidades, necesidades, costos, ganancias y otros requisitos y restricciones del problema. La suposición básica en la aplicación de este método es que las diversas relaciones entre demanda y disponibilidad son lineales; es decir, ninguna de las x i se eleva a una potencia distinta de 1. Para obtener la solución a este problema, es necesario encontrar la solución del sistema de desigualdades lineales (es decir, el conjunto de n valores de las variables x i que simultáneamente satisfacen todas las desigualdades). La función objetivo se evalúa sustituyendo los valores de x i en la ecuación que define f.
El matemático soviético Leonid Kantorovich y el economista estadounidense Wassily Leontief intentaron por primera vez las aplicaciones del método de programación lineal en las áreas de los horarios de fabricación y de la economía, respectivamente, pero su trabajo fue ignorado durante décadas. Durante la Segunda Guerra Mundial, la programación lineal se utilizó ampliamente para tratar el transporte, la programación y la asignación de recursos sujetos a ciertas restricciones, como los costos y la disponibilidad. Estas aplicaciones hicieron mucho para establecer la aceptabilidad de este método, que ganó mayor impulso en 1947 con la introducción del método simplex del matemático estadounidense George Dantzig, que simplificó enormemente la solución de los problemas de programación lineal.
Sin embargo, a medida que se intentaban problemas cada vez más complejos que involucraban más variables, el número de operaciones necesarias se expandió exponencialmente y excedió la capacidad computacional de incluso las computadoras más poderosas. Luego, en 1979, el matemático ruso Leonid Khachiyan descubrió un algoritmo de tiempo polinomial, en el que la cantidad de pasos computacionales crece como una potencia de la cantidad de variables en lugar de exponencialmente, lo que permite la solución de problemas hasta ahora inaccesibles. Sin embargo, el algoritmo de Khachiyan (llamado método elipsoide) era más lento que el método simplex cuando se aplicaba prácticamente. En 1984, la matemática india Narendra Karmarkar descubrió otro algoritmo de tiempo polinómico, el método del punto interior, que demostró ser competitivo con el método simplex.
