¿Se pueden convertir los problemas de optimización del cálculo en problemas de programación lineal?

Question

Encontré un libro de texto de Programación Lineal en algún lugar, y hojeé las primeras páginas. Aunque no estoy lo suficientemente preparado para repasarlo, las cosas que trataba se parecían mucho a los problemas de optimización de cálculo, sólo que mucho más complicados. ¿Se pueden convertir los primeros en problemas de Programación Lineal?

Por ejemplo, lo que estamos haciendo ahora en el cálculo es expresar alguna variable como función de otra, mientras que originalmente se expresan como función de dos o más (área, volumen, etc...). Así podemos usar las derivadas y sus extremos y demás. El libro de texto de Programación Lineal parece estar bien con dejar la función original como una de múltiples variables. Entonces, ¿podría técnicamente hacer esas preguntas con métodos de optimización lineal?

Perdón si todo esto está mal, como dije no estoy para nada preparado para la programación lineal.

Answer 1

Aparte del manejo de los problemas de optimización, son bastante diferentes.

Cuando se utiliza el cálculo para resolver un problema de optimización, se depende del teorema de que (bajo condiciones adecuadas) el mínimo se encuentra en un punto con derivada cero, o en la frontera del dominio . Se utiliza el cálculo para encontrar los puntos con derivada cero, y luego suele ser sencillo compararlos con el valor de la función en el límite. Los dominios de los problemas preparados para el cálculo son sencillos, normalmente un intervalo de la recta real, por lo que encontrar sus límites apenas requiere reflexión.

En los problemas de programación lineal, lo complicado es comprender cómo es el límite . Por definición, la programación lineal se refiere a problemas en los que la función para minimizar es lineal -- así que todo lo que el cálculo puede decirnos (y lo hace muy rápidamente) es que no hay extremos en la interior del dominio. Pero el dominio suele ser un espacio de muy alta dimensión, por lo que uno no puede Sólo hay que imaginar su forma; en su lugar se tiene un gran número de desigualdades que definen un complicado poliedro en, digamos, $\mathbb R^{100}$ . Es fácil ver que el mínimo debe estar en una de las esquinas del poliedro -- la dificultad es encontrar las esquinas, y averiguar la que tiene el valor mínimo de la función, preferiblemente sin encontrar e intentar todo las esquinas, porque también puede haber un gran número de ellas.

Los dos estilos de problemas se combinan en general programación convexa donde ambos tienen una función objetivo que no es lineal (por lo que puede haber extremos interiores) y un dominio complicado que no se puede manejar intuitivamente.

Answer 2

La programación lineal es realmente un fenómeno combinatorio. El cálculo optimiza mediante un proceso totalmente diferente. Los dos no me parecen muy interrelacionados.