Recopilación completa de datos detallados para programación no lineal
Introducción básica Nombre chino: Programación no lineal mbth: Aplicación de programación no lineal: ingeniería, gestión, importancia económica: proporciona una herramienta poderosa para un diseño óptimo. Tema: Conceptos básicos de la investigación de operaciones: historia del desarrollo de la programación matemática con restricciones u objetivos no lineales, análisis en profundidad, preguntas frecuentes, modelos matemáticos, métodos de optimización, métodos no restringidos, métodos restringidos, programación convexa, programación cuadrática, programación geométrica, aplicaciones Alcance e historia del desarrollo La programación no lineal es una nueva disciplina que comenzó a formarse en la década de 1950. En 1951, H.W Kuhn y A.W Tucker publicaron un artículo sobre las condiciones de optimización (más tarde llamadas condiciones de Kuhn-Tucker), que es un símbolo importante del nacimiento formal. de no linealidad En la década de 1950, se obtuvieron N tipos de soluciones para la programación separable y la programación cuadrática, la mayoría de las cuales se basaron en el método simplex para resolver la programación lineal propuesto por G B Danzig. Desde finales de los años cincuenta hasta finales de los sesenta, aparecieron muchos algoritmos eficaces para resolver problemas de programación no lineal. Desde la década de 1980, con el rápido desarrollo de la tecnología informática, los métodos de programación no lineal han logrado grandes avances y se han logrado resultados fructíferos en los campos de los métodos de región de confianza, métodos cuasi-Newton dispersos, computación paralela, métodos de puntos interiores y métodos de almacenamiento finito. , etc. resultados. Análisis en profundidad de problemas comunes Para un problema práctico, cuando se reduce a un problema de programación no lineal, generalmente se deben tener en cuenta los siguientes puntos: (1) Determinar alternativas: primero, recopilar información y datos relacionados con el problema, y luego de manera integral entender el problema Sobre la base del problema, determinar qué alternativas están disponibles y expresarlas con un conjunto de variables. (2) Proponer objetivos a perseguir: después del análisis de los datos, en función de las necesidades y posibilidades reales, proponer objetivos a perseguir para la minimización o maximización. Además, se utilizan diversos principios científicos y tecnológicos para expresarlos como relaciones matemáticas. (3) Indique el estándar de valor: después de proponer el objetivo a perseguir, establezca el estándar de valor "bueno" o "malo" del objetivo bajo consideración y descríbalo de alguna forma cuantitativa. (4) Encontrar restricciones: Dado que el objetivo que se persigue generalmente es lograr el efecto mínimo o máximo bajo ciertas condiciones, también es necesario conocer todas las restricciones del problema. Estas restricciones generalmente se expresan mediante algunas desigualdades o ecuaciones entre variables. . Modelo matemático Para realizar un análisis cuantitativo de problemas de planificación reales, se debe establecer un modelo matemático. Para establecer un modelo matemático, primero debemos seleccionar las variables objetivo y las variables de decisión apropiadas, y establecer la relación funcional entre las variables objetivo y las variables de decisión, lo que se denomina función objetivo. Luego se abstraen diversas restricciones y se obtienen algunas ecuaciones o desigualdades que deben satisfacer las variables de decisión, las cuales se denominan restricciones. El modelo matemático general de problemas de programación no lineal se puede expresar como encontrar las cantidades desconocidas x1, x2,..., xn) = 0J = donde f, gi, hj son todas funciones de valor real definidas en un subconjunto d (dominio) de Espacio vectorial n-dimensional Rn, y al menos uno de los modelos anteriores se puede abreviar como: min f(x) s.t gi(x)≥0 i=1,…,m hj(x)=0 j=1,… ,p donde x=(x1,…,xn) pertenece al dominio d, y los puntos en el dominio d que satisfacen las condiciones de restricción se denominan solución factible del problema. Al conjunto de todas las soluciones factibles se le llama conjunto factible de un problema. Para una solución factible x*, si existe una vecindad de x* tal que el valor f (x*) de la función objetivo en x* es mejor (ni mayor ni menor que) el valor de la función en cualquier otra solución factible en la vecindad, entonces x* se llama la solución óptima local del problema (denominada solución local). Si f(x*) es mejor que el valor de la función objetivo en todas las soluciones factibles, entonces x* se denomina solución óptima global del problema (denominada solución global). Los problemas reales de programación no lineal requieren soluciones globales, pero la mayoría de las soluciones existentes sólo buscan soluciones locales.
El método óptimo se refiere al método de encontrar el punto de valor óptimo de una función de una variable dentro de un intervalo determinado. Estos métodos no sólo tienen valor práctico, sino que una gran cantidad de métodos de optimización multidimensional se basan en una serie de optimizaciones unidimensionales. Los métodos de optimización unidimensionales comúnmente utilizados incluyen el método de la sección áurea, el método de la tangente y el método de interpolación. El método de la sección áurea también se llama método 0,618. Funciona para funciones unimodales. La idea básica es diseñar una serie de puntos en el intervalo de búsqueda inicial y reducir gradualmente el intervalo de búsqueda comparando sus valores de función uno por uno, obteniendo así el punto de valor óptimo aproximado. ②El método de la tangente también se llama método de Newton. También apunta a funciones unimodales. La idea básica es linealizar la función derivada de la función objetivo cerca de un punto de conjetura, utilizar el punto cero de esta función lineal como un nuevo punto de conjetura y acercarse gradualmente al punto óptimo. ③El método de interpolación también se denomina método de aproximación polinomial. La idea básica es ajustar un polinomio (normalmente un polinomio cuadrático o cúbico) a la función objetivo. Además, existen el método de Fibonacci, el método de la secante, el método de interpolación racional y el método de búsqueda por lotes. El método sin restricciones se refiere a un método para encontrar el punto óptimo de una función real f de n dimensiones en todo el espacio vectorial de n dimensiones Rn. La importancia de este tipo de método es que, aunque la mayoría de los problemas de planificación prácticos son restringidos, muchos métodos de optimización restringidos pueden transformar el problema restringido en varios problemas no restringidos para resolver. La mayoría de los métodos de optimización sin restricciones son algoritmos iterativos para búsqueda unidimensional continua. Estos algoritmos iterativos se pueden dividir en dos categorías. Una función derivada que requiere una función objetivo se llama método analítico. El otro tipo no implica derivadas y solo utiliza valores de función, lo que se denomina método directo. La idea básica de estos algoritmos iterativos es seleccionar una dirección de búsqueda favorable en un punto aproximado, buscar en esta dirección en una dimensión y obtener un nuevo punto aproximado. Luego se aplica el mismo proceso a nuevos puntos y la iteración se repite hasta que se cumplan los requisitos de precisión predeterminados. Existen varios algoritmos según el método de dirección de búsqueda. Los algoritmos analíticos incluyen: ① Método de gradiente: también conocido como método de descenso más pronunciado. Este es un método analítico temprano y tiene una velocidad de convergencia lenta. ② Método de Newton: la velocidad de convergencia es rápida, pero inestable y difícil de calcular. ③ * * *Método de gradiente de yugo: convergencia más rápida y mejor efecto. ④Método de escala variable: este es un método eficaz. Entre ellos, el método de escala variable de Davidon-Fletcher-Powell, conocido como método DFP, es el método más utilizado. Los algoritmos directos incluyen el método de dirección alterna (también conocido como método de rotación de coordenadas), el método de búsqueda de patrones, el método de dirección de rotación, el método de dirección del yugo de Powell y el método de aceleración simplex. El método de restricción se refiere al método de solución del modelo general de programación no lineal mencionado anteriormente. Hay cuatro métodos de optimización restringida comúnmente utilizados. ①Método del multiplicador de Lagrange: transforme el problema original para encontrar el punto estacionario de la función de Lagrange. ②Método de función restringida: también conocido como método de minimización sin restricciones en serie, denominado método SUMT. Se divide en dos categorías, una se llama método de función de penalización o método de valores atípicos y la otra se llama método de función de obstáculo o método de punto interior. Todos convierten el problema original en una serie de problemas sin restricciones para resolver. (3) Método de dirección factible: este es un algoritmo iterativo que se acerca al punto óptimo seleccionando direcciones de descenso factibles una por una. Como el método Zotandik, el método Frank-Wolff, el método de gradiente proyectado y el método de gradiente reducido pertenecen a este tipo de algoritmo. ④Algoritmos de aproximación: estos algoritmos incluyen programación lineal secuencial y programación cuadrática secuencial. El primero transforma el problema original en una serie de problemas de programación lineal y el segundo transforma el problema original en una serie de problemas de programación cuadrática. Programación convexa Este es un tipo especial de programación no lineal. En el modelo matemático de programación no lineal mencionado anteriormente, si F es una función convexa, todas las GI son funciones cóncavas y todas hj son funciones lineales, se denomina programación convexa. F es una función convexa, lo que significa que su dominio es un conjunto convexo, y para dos puntos cualesquiera X e Y en el dominio y cualquier número positivo α menor que 1, se cumple la siguiente fórmula: F((1-α)X αY ) α≤(1-α)F(X). El llamado conjunto convexo se refiere a un conjunto con las siguientes propiedades: todos los puntos en el segmento de línea recta que conecta dos puntos cualesquiera del conjunto pertenecen al conjunto. Para problemas generales de programación no lineal, las soluciones locales no son necesariamente soluciones globales. Sin embargo, la solución local de la programación convexa debe ser la solución global, y el conjunto factible y el conjunto de solución óptima de la programación convexa son ambos conjuntos convexos. La programación cuadrática es un tipo especial de programación no lineal. Su función objetivo es una función cuadrática y las restricciones son lineales. Hay muchas formas de resolver la programación cuadrática. Un método más sencillo y sencillo es el método de Wolff. Se ha mejorado sobre la base de la condición de Kuhn-Tucker y el método simplex de programación lineal.
Además, existen el método Lemke, el método Beer y el método Keller. Programación geométrica La programación geométrica es un tipo especial de programación no lineal cuya función objetivo y función de restricción son polinomios definidos positivos (o términos positivos). La programación geométrica en sí misma generalmente no es convexa, pero puede volverse convexa reemplazando las variables apropiadas. La solución óptima local de la programación geométrica debe ser la solución óptima global. Hay dos métodos para resolver la programación geométrica. Uno es utilizar programación dual para resolver; el otro es resolver directamente la programación original. La mayoría de estos algoritmos se basan en la idea de convertir polinomios en monomios basándose en desigualdades geométricas. El ámbito de aplicación generalmente se optimiza en gestión, diseño de ingeniería, investigación científica, mando militar, etc. Por ejemplo, cómo organizar razonablemente la producción de productos para obtener las mayores ganancias con los recursos humanos, materiales y financieros existentes, cómo diseñar un producto para lograr el menor costo y al mismo tiempo cumplir con las especificaciones y requisitos de desempeño, cómo determinar un control automático determinado; parámetros del sistema para que el sistema funcione de manera óptima; cómo asignar la carga de cada central eléctrica en el sistema de energía para minimizar el consumo total y al mismo tiempo garantizar ciertos requisitos de indicadores cómo organizar las reservas de inventario para garantizar el suministro y maximizar los costos de almacenamiento; organizar el suministro para satisfacer las necesidades de los clientes y maximizar la rotación de capital. Para problemas de optimización estática, cuando la función objetivo o las condiciones de restricción tienen funciones no lineales desconocidas que son incómodas de linealizar, o la linealización causará grandes errores, se pueden aplicar métodos de programación no lineal.