¿Cuáles son algunas aplicaciones de programación lineal que son útiles en la industria o las ciencias?

Answer 1

La programación lineal (LP) es útil para la optimización de recursos, siempre que las restricciones y la función objetivo sean lineales o puedan linealizarse (también, ayuda si existen soluciones factibles y especialmente si existen soluciones óptimas, pero la unicidad no es un impedimento para nada – los lazos se rompen fácilmente por algoritmos específicos). LP solo puede resolver problemas convexos (directamente).

Aplicación 1: Recursos mixtos.
Digamos que tiene varios tipos de recursos, pero no puede extraer libremente ninguna cantidad de un recurso, ya que vienen en paquetes. Por ejemplo, debe consumir una cierta cantidad de carbohidratos , proteínas , grasas y vitaminas todos los días, pero solo se le permite comer barras de granola , cecina , chocolate , palomitas de maíz y ositos de goma . Mientras optimiza las limitaciones nutricionales al comer algunas cantidades de cada alimento, también desea optimizar el costo total en $.

Si usted come [math] x [/ math] barras de granola, [math] y [/ math] trozos de cecina de res, [math] z [/ math] barras de chocolate, etc., entonces la cantidad de carbohidratos se puede expresar como una función lineal de [matemáticas] x, y, z, \ ldots [/ matemáticas] Lo mismo para las proteínas. Entonces, las restricciones son desigualdades lineales.

La función objetivo es lineal: multiplique [matemática] x [/ matemática] por el costo de una barra de granola y agregue a [matemática] y [/ matemática] multiplicada por el costo de una pieza de cecina, luego agregue… Entonces, en En la práctica, puede escribir la matriz de restricciones (los coeficientes en las restricciones) y el vector de objetivos (los coeficientes de la función objetivo) en una hoja de cálculo en Excel e invocar la programación lineal para encontrar una solución. O puede conectar algún software de código abierto como GLPK a su motor de juego o al back-end de un sitio web.

Aplicación 2. Problemas de ubicación.
Si está construyendo una nueva estación de bomberos, debe estar cerca de las ciudades de las que es responsable. Supongamos que desea minimizar la suma de las distancias de Manhattan (rectilíneas) por pares eligiendo cuidadosamente la ubicación [math] (x, y) [/ math]. Hay una solución directa simple para este problema de optimización (¿lo ve?), Pero construyamos un programa lineal para ilustrar la técnica, que luego puede generalizarse. La distancia de [math] (x, y) [/ math] a [math] (x_A, y_A) [/ math] está modelada por variables intermedias [math] d_ {xA}, d_ {yA}, d_A [/ math ] que luego alentaremos a que sea lo más pequeño posible, sujeto a

[matemáticas] d_ {xA} \ geq x-x_A [/ matemáticas] y [matemáticas] d_ {xA} \ geq x_A-x [/ matemáticas],
[matemáticas] d_ {yA} \ geq y-y_A [/ matemáticas] y [matemáticas] d_ {yA} \ geq y_A-y [/ matemáticas],
[matemáticas] d \ geq d_ {xA} + d_ {yA} [/ matemáticas]

Aquí [math] d_ {xA} [/ math] espera representar [math] | x-x_A | [/ math], [math] d_ {yA} [/ math] espera representar [math] | y-y_A | [/ math] y [math] d_A [/ math] espera representar [math] d_ {xA} + d_ {yA} [/ math], es decir, la distancia de Manhattan entre [math] (x, y) [/ matemáticas] y [matemáticas] (x_A, y_A) [/ matemáticas].

Entonces, ¿cómo alentamos a esas tres variables a ser lo más pequeñas posible? – Incluimos [math] d_A [/ math] como un agregado en la función objetivo que se minimiza: [math] d_A + d_B + d_C + \ ldots [/ math]. Puede agregar algunos pesos, si la distancia a A es más importante que la distancia a B. La minimización “empuja” hacia abajo cada una de esas variables, y eso a su vez empuja hacia abajo las variables de nivel inferior [matemáticas] d_ {xA} , d_ {yA}, d_ {xB}, d_ {yB}, \ ldots [/ math].

Ahora, trate de optimizar la ubicación de dos estaciones de bomberos responsables de tres ciudades diferentes cada una, mientras limita la distancia entre las estaciones de bomberos por alguna constante. Además de eso, fomente que esa distancia sea más pequeña si es posible sin mover las estaciones de bomberos más lejos de sus ciudades. Una vez que se familiarice con esto, se vuelve fácil manejar un gran número de variables, restricciones e incluso preferencias suaves.

Cuando llega a tamaños muy grandes, los solucionadores de LP “enlatados” comienzan a ahogarse, y querrá buscar solucionadores de LP especializados para el tipo de instancias que está construyendo. Hay algunas matemáticas muy interesantes que permiten resolver ciertos programas lineales prácticos al aprovechar los solucionadores rápidos de flujo mínimo y costo máximo.

Answer 2

Aquí hay una aplicación algo sorprendente de programación lineal para la bioingeniería: análisis de balance de flujo.

La idea básica es modelar qué tan rápido están ocurriendo diferentes reacciones químicas en una célula, también conocido como el flujo a través de esas reacciones (si ha visto el flujo de la red, puede reemplazar la palabra “flujo” con “flujo” en su cabeza, ya que estamos a punto de definir cosas similares a las limitaciones de capacidad y conservación. AFAIK no hay una reducción directa de FBA al flujo de red estándar, ya que nuestras restricciones tienen una forma ligeramente más general). Estas tasas a menudo están limitadas por limitaciones internas (por ejemplo, la tasa máxima de catálisis por la enzima responsable de la reacción) y limitaciones externas (por ejemplo, la cantidad de nutrientes en los medios). Además, para cada molécula en la célula, la conservación de la masa impone una restricción lineal sobre las reacciones que involucran a esa molécula. Por ejemplo, si las dos únicas reacciones posibles que involucran a la molécula A son A + A -> B y C + D -> A, entonces sabemos que la segunda reacción debe ocurrir exactamente al doble de la velocidad de la primera reacción, o de lo contrario A ocurrirá se acumulan o se agotan. En general, obtenemos un montón de restricciones que indican que algunas combinaciones lineales de flujos equivalen a cero (la única excepción es para las moléculas que la célula importa o exporta).

Puede establecer que la función objetivo sea algo así como la producción total de biomasa (representada como una combinación lineal de cierto número de moléculas). Esto tiene sentido, por ejemplo, en poblaciones bacterianas; Se ha demostrado que, dentro de una población de bacterias, un pequeño grupo de bacterias que se dividen más rápidamente dominará rápidamente a la población, como es de esperar.

Ahora, simplemente arrojas todo en un solucionador de LP de caja negra. Terminas con un vector de flujos, que te dan una predicción de cuánto flujo está pasando por cada reacción en la red metabólica que te interesa.

Con este modelo, puede hacer “experimentos” como eliminar genes diferentes, cerrar ciertos flujos y ver cómo cambia la célula para acomodarse a esto. Una buena aplicación es este artículo: ingeniería metabólica de Escherichia coli para la producción de ácido poliláctico y sus copolímeros, en el que utilizan FBA para determinar una serie de alteraciones que podrían hacer que E. Coli produzca mucho ácido poliláctico, Biopolímero usado.

Answer 3

Muchos problemas pueden expresarse como programas enteros. De hecho, la programación de enteros es NP-hard, por lo que cada problema en NP puede (en principio) expresarse como un programa de enteros. Cada programa entero puede ser aproximado por un programa lineal, y la solución a ese problema a menudo puede usarse para encontrar una muy buena solución aproximada al problema original.

También vale la pena señalar que la programación lineal es un caso especial de optimización convexa, que se ocupa de lo que es básicamente la clase más grande de problemas de optimización que se pueden resolver de manera realista. Muchos problemas en geometría computacional, aprendizaje automático / estadísticas e investigación de operaciones son convexos o pueden ser muy aproximados por un problema convexo, por lo que esas técnicas son increíblemente útiles.

Answer 4

Implementación especializada de programas lineales en modelos de flujo, algoritmos de transporte y asignación, aunque especializados, la complejidad se escala lo suficientemente bien como para ser utilizados en muchas soluciones de gestión de inventario.

Los programas lineales son fantásticos si puede diseñar los planos de corte adecuados para sus solucionadores de programación de enteros. LP + arranques en caliente / arranques en frío alimentan varios solucionadores de programación no lineales / enteros. Por lo tanto, la eficiencia de esos enfoques depende en parte de la eficiencia y la efectividad de los programas lineales.

Muchos algoritmos primarios de aproximación dual dependen de las formulaciones de LP para garantías (a través de los límites superior / inferior que definen los criterios de detención), aunque rara vez los resuelven en la práctica.

Answer 5

Williams presenta varias aplicaciones de programación matemática en diversas industrias: petróleo, química, manufactura, transporte y distribución, finanzas, agricultura, salud, minería, mano de obra, alimentos, energía, pulpa y papel, publicidad, defensa, cadena de suministro y otras aplicaciones (2013 )

Referencia

Williams, HP (2013). Construcción de modelos en programación matemática. Quinta edición. [Versión electrónica]. Chichester, West Sussex: John Wiley & Sons Ltd.

Answer 6

Muchas aplicaciones de control de procesos industriales giran en torno a programas lineales. He visto estadísticas que sugieren que la primera generación de computadoras centrales (muy caras) fueron engullidas por las compañías petroleras para resolver modelos de LP que determinaban los flujos en las refinerías … y que el período de recuperación de las compras fue bastante corto.

Answer 7

Considere el caso de que está desarrollando un procesador de ocho núcleos, pero dado el “espacio de piso” y las diferencias en la fabricación del núcleo, tendrá que colocarlos de tal manera que proporcionen el máximo rendimiento teniendo en cuenta también que encajar en el “espacio de piso” disponible. Esa es una versión con azúcar del ejemplo de la vida real.