Programación lineal
La programación lineal ( LP , también llamada optimización lineal ) es un método para lograr el mejor resultado (como la máxima ganancia o el menor costo) en un modelo matemático cuyos requisitos están representados por relaciones lineales . La programación lineal es un caso especial de programación matemática (también conocida como optimización matemática ).
Más formalmente, la programación lineal es una técnica para la optimización de una función objetivo lineal , sujeta a restricciones de igualdad lineal y desigualdad lineal . Su región factible es un politopo convexo , que es un conjunto definido como la intersección de un número finito de medios espacios , cada uno de los cuales está definido por una desigualdad lineal. Su función objetivo es una verdadera -valued afín (lineal) la función definida en este poliedro. Un algoritmo de programación lineal encuentra un punto en el politopo donde esta función tiene el valor más pequeño (o más grande) si tal punto existe.
Aquí, los componentes de x son las variables que se van a determinar, c y b son vectores dados (con lo que se indica que los coeficientes de c se utilizan como una matriz de una sola fila con el fin de formar el producto de la matriz) y A es una matriz dada. . La función cuyo valor se va a maximizar o minimizar ( en este caso) se llama función objetivo . El desigualdades A x ≤ b y x ≥ 0 son las limitaciones que especifican un politopo convexosobre el cual se optimizará la función objetivo. En este contexto, dos vectores son comparables cuando tienen las mismas dimensiones. Si cada entrada en el primero es menor o igual que la entrada correspondiente en el segundo, entonces se puede decir que el primer vector es menor o igual que el segundo vector.
La programación lineal se puede aplicar a varios campos de estudio. Se usa ampliamente en matemáticas y, en menor medida, en negocios, economía y para algunos problemas de ingeniería. Las industrias que utilizan modelos de programación lineal incluyen transporte, energía, telecomunicaciones y manufactura. Ha demostrado ser útil para modelar diversos tipos de problemas en planificación , enrutamiento , programación , asignación y diseño.
El problema de resolver un sistema de desigualdades lineales se remonta al menos hasta Fourier , quien en 1827 publicó un método para resolverlas, [1] y de quien se nombra el método de eliminación de Fourier-Motzkin .
En 1939, el matemático y economista soviético Leonid Kantorovich , quien también propuso un método para resolverlo, dio una formulación de programación lineal de un problema que es equivalente al problema general de programación lineal . [2] Es una forma que desarrolló, durante la Segunda Guerra Mundial , para planificar los gastos y las ganancias con el fin de reducir los costos del ejército y aumentar las pérdidas impuestas al enemigo. [ cita requerida ] El trabajo de Kantorovich fue inicialmente descuidado en la URSS . [3] Aproximadamente al mismo tiempo que Kantorovich, el economista holandés-estadounidense TC Koopmans formuló problemas económicos clásicos como programas lineales. Kantorovich y Koopmans luego compartieron el premio Nobel de economía de 1975 . [1] En 1941, Frank Lauren Hitchcock también formuló problemas de transporte como programas lineales y dio una solución muy similar al método símplex posterior . [2] Hitchcock había muerto en 1957 y el premio Nobel no se otorga póstumamente.