Programación lineal
La programación lineal ( LP , también llamada optimización lineal ) es un método para lograr el mejor resultado (como el beneficio máximo o el costo más bajo) 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 función afín (lineal) de valor real 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 a determinar, c y b son vectores dados (con indicación de que los coeficientes de c se usan como una matriz de una sola fila con el fin de formar el producto matricial), y A es una matriz dada . La función cuyo valor se quiere maximizar o minimizar ( en este caso) se llama función objetivo . Las desigualdades A x ≤ b y x ≥ 0 son las restricciones que especifican un politopo convexosobre el cual se va a 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. Es ampliamente utilizado en matemáticas y, en menor medida, en negocios, economía y para algunos problemas de ingeniería. Las industrias que usan modelos de programación lineal incluyen transporte, energía, telecomunicaciones y manufactura. Ha demostrado su utilidad en el modelado de diversos tipos de problemas de planificación , enrutamiento , programación , asignación y diseño.
El problema de resolver un sistema de desigualdades lineales se remonta al menos a 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 gastos y 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] Casi al mismo tiempo que Kantorovich, el economista holandés-estadounidense TC Koopmans formuló problemas económicos clásicos como programas lineales. Kantorovich y Koopmans compartieron más tarde 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 a título póstumo.