Optimización (matemáticas)

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 25 de septiembre de 2021; las comprobaciones requieren 4 ediciones .

La optimización (en matemáticas , ciencias de la computación e investigación de operaciones ) es la tarea de encontrar un extremo (mínimo o máximo) de una función objetivo en alguna región de un espacio vectorial de dimensión finita , limitado por un conjunto de funciones lineales y/o no igualdades y/o desigualdades lineales .

La teoría y los métodos para resolver un problema de optimización se estudian mediante programación matemática .

La programación matemática es una rama de las matemáticas que desarrolla teoría, métodos numéricos para resolver problemas multidimensionales con restricciones. [una]

Enunciado del problema de optimización

En el proceso de diseño , la tarea generalmente se establece para determinar la mejor, en cierto sentido, estructura o valores de los parámetros del objeto . Tal problema se llama un problema de optimización. Si la optimización está asociada con el cálculo de valores de parámetros óptimos para una estructura de objeto dada, entonces se llama optimización paramétrica . El problema de elegir la estructura óptima es la optimización estructural .

El problema estándar de optimización matemática se formula de esta manera. Entre los elementos χ que forman los conjuntos X, encuentre un elemento χ * que proporcione el valor mínimo f(χ * ) de la función dada f(χ). Para plantear correctamente el problema de optimización, es necesario establecer:

El conjunto admisible es el conjunto ; ${\mathbb {X}}=\{{\vec {x}}|\;g_{i}({\vec {x}})\leq 0,\;i=1,\ldots,m\}\ subconjunto {\mathbb {R}}^{n}$
mapeo de funciones objetivas ; $f:\;{\mathbb {X}}\a {\mathbb {R}}$
Criterio de búsqueda (máx o min).

Entonces resolver el problema significa uno de: $f(x)\to \min_{({\vec {x}}\in {\mathrm {X}}}}$

Muéstrale eso . ${\mathbb {X}}=\varnada$
Demuestre que la función objetivo no está acotada por debajo. $f({\vec {x)))$
Encuentra _ ${\vec {x}}^{*}\in {\mathbb {X}}:\;f({\vec {x}}^{*})=\min_{({\vec {x}} \in {\mathbb {X}}}}f({\vec {x}})$
Si , entonces encuentra . $\nexiste {\vec {x}}^{*}$ $\inf _{({\vec {x}}\in {\mathbb {X}}}}f({\vec {x}})$

Si la función que se minimiza no es convexa , entonces a menudo se limitan a encontrar mínimos y máximos locales: puntos tales que en todas partes en algunos de sus vecindarios para un mínimo y un máximo. $x_{0}$ $f(x)\geq f(x_{0})$ $f(x)\leq f(x_{0})$

Si el conjunto es admisible , entonces dicho problema se denomina problema de optimización incondicional , de lo contrario, problema de optimización condicional . ${\mathbb {X}}={\mathbb {R}}^{n}$

Clasificación de los métodos de optimización

La notación general de los problemas de optimización define una amplia variedad de sus clases. La elección del método (la eficiencia de su solución) depende de la clase del problema. La clasificación de los problemas viene determinada por: la función objetivo y el área admisible (dada por un sistema de desigualdades e igualdades o un algoritmo más complejo). [2]

Los métodos de optimización se clasifican según las tareas de optimización:

Métodos locales: convergen a algún extremo local de la función objetivo. En el caso de una función objetivo unimodal, este extremo es único y será el máximo/mínimo global.
Métodos globales: se ocupan de funciones objetivo multiextremales. En la búsqueda global, la tarea principal es identificar tendencias en el comportamiento global de la función objetivo.

Los métodos de búsqueda existentes actualmente se pueden dividir en tres grandes grupos:

determinista;
aleatorio (estocástico);
conjunto.

Según el criterio de la dimensión del conjunto factible, los métodos de optimización se dividen en métodos de optimización unidimensionales y métodos de optimización multidimensionales .

Por la forma de la función objetivo y el conjunto admisible, los problemas de optimización y los métodos para su solución se pueden dividir en las siguientes clases:

Los problemas de optimización donde la función objetivo y las restricciones son funciones lineales se resuelven mediante los llamados métodos de programación lineal . $f({\vec {x)))$ $g_{i}({\vec {x))),\;i=1,\ldots,m$
De lo contrario, se trata de un problema de programación no lineal y se aplican los métodos apropiados. A su vez, se distinguen de ellos dos tareas particulares:
- si y son funciones convexas, entonces dicho problema se denomina problema de programación convexa ; $f({\vec {x)))$ $g_{i}({\vec {x))),\;i=1,\ldots,m$
- si , entonces estamos tratando con un problema de programación entera (discreta) . ${\mathbb {X}}\subconjunto {\mathbb {Z}}$

De acuerdo con los requisitos de suavidad y la presencia de derivadas parciales en la función objetivo, también se pueden dividir en:

métodos directos que requieren únicamente el cálculo de la función objetivo en los puntos de aproximación;
métodos de primer orden : requieren el cálculo de las primeras derivadas parciales de una función;
métodos de segundo orden: requieren el cálculo de segundas derivadas parciales, es decir, la hessiana de la función objetivo.

Además, los métodos de optimización se dividen en los siguientes grupos:

métodos analíticos (por ejemplo, el método de los multiplicadores de Lagrange y las condiciones de Karush - Kuhn - Tucker );
métodos numéricos ;
métodos gráficos .

Dependiendo de la naturaleza del conjunto X , los problemas de programación matemática se clasifican en:

problemas de programación discreta (u optimización combinatoria ) - si X es finito o contable ;
problemas de programación de enteros - si X es un subconjunto del conjunto de enteros;
problemas de programación no lineal si las restricciones o la función objetivo contienen funciones no lineales y X es un subconjunto de un espacio vectorial de dimensión finita .
Si todas las restricciones y la función objetivo contienen solo funciones lineales, entonces este es un problema de programación lineal.

Además, las ramas de la programación matemática son la programación paramétrica , la programación dinámica y la programación estocástica .

La programación matemática se utiliza para resolver problemas de optimización en la investigación de operaciones .

El método para encontrar el extremo está completamente determinado por la clase del problema. Pero antes de obtener un modelo matemático, debe realizar 4 etapas de modelado:

Determinación de los límites del sistema de optimización
- Descartamos aquellas conexiones del objeto de optimización con el mundo exterior que no pueden afectar en gran medida al resultado de la optimización o, más precisamente, aquellas sin las cuales se simplifica la solución.
Elección de variables controladas
- “Congelamos” los valores de algunas variables (variables no gestionadas). Otros se dejan tomar cualquier valor del área de decisiones admisibles (variables controladas)
Definición de restricciones en variables controladas
- … (igualdades y/o desigualdades)
Elección del criterio de optimización numérica (por ejemplo , indicador de rendimiento )
- Crear una función objetivo

Historia

Los problemas de programación lineal fueron los primeros problemas estudiados en detalle para encontrar el extremo de funciones en presencia de restricciones tales como desigualdades . En 1820, Fourier y luego en 1947 George Dantzig propusieron un método de enumeración dirigida de vértices adyacentes en la dirección de la función objetivo creciente : el método simplex , que se convirtió en el principal para resolver problemas de programación lineal.

La presencia del término "programación" en el nombre de la disciplina se explica porque los primeros estudios y las primeras aplicaciones de los problemas de optimización lineal fueron en el campo de la economía, ya que en inglés la palabra "programación" significa planificación , dibujo. elaborar planes o programas. Es bastante natural que la terminología refleje la estrecha relación que existe entre la formulación matemática del problema y su interpretación económica (estudio del programa económico óptimo). El término " programación lineal " fue propuesto por J. Danzig en 1949 para estudiar problemas teóricos y algorítmicos relacionados con la optimización de funciones lineales bajo restricciones lineales.

Por lo tanto, el nombre de "programación matemática" se debe a que el objetivo de la resolución de problemas es elegir el programa óptimo de acciones.

La identificación de una clase de problemas extremos definidos por un funcional lineal en un conjunto definido por restricciones lineales debe atribuirse a la década de 1930. Uno de los primeros en estudiar los problemas de programación lineal de forma general fueron: John von Neumann , matemático y físico que demostró el teorema principal sobre los juegos de matrices y estudió el modelo económico que lleva su nombre, y L. V. Kantorovich , académico soviético, Nobel Ganador del premio (1975), que formuló una serie de problemas de programación lineal y propuso en 1939 un método para resolverlos ( el método de resolución de factores ), que difiere ligeramente del método simplex.

En 1931, el matemático húngaro B. Egervari consideró una formulación matemática y resolvió un problema de programación lineal llamado "problema de elección", el método de solución se denominó " método húngaro ".

L. V. Kantorovich y M. K. Gavurin desarrollaron el método de los potenciales en 1949 , que se utiliza para resolver problemas de transporte . En trabajos posteriores de L. V. Kantorovich, V. S. Nemchinov , V. V. Novozhilov , A. L. Lurie , A. Brudno , A. G. Aganbegyan , D. B. Yudin , E. G. Golshtein y otros matemáticos y economistas desarrollaron aún más la teoría matemática de la programación lineal y no lineal y la aplicación de sus métodos. al estudio de diversos problemas económicos.

Muchos trabajos de científicos extranjeros están dedicados a los métodos de programación lineal. En 1941, F. L. Hitchcock planteó el desafío del transporte . El método básico para resolver problemas de programación lineal, el método simplex , fue publicado en 1949 por J. Dantzig. Los métodos de programación lineal y no lineal se desarrollaron aún más en los trabajos de G. Kuhn , A. Tucker , Gass (Saul I. Gass), Charnes (A. Charnes), Beale (EM Beale) y otros.

Simultáneamente con el desarrollo de la programación lineal, se prestó mucha atención a los problemas de programación no lineal , en los que la función objetivo , las restricciones o ambas son no lineales. En 1951 se publicó el trabajo de G. Kuhn y A. Tucker , en el que se daban las condiciones de optimalidad necesarias y suficientes para la resolución de problemas de programación no lineal. Este trabajo sirvió de base para investigaciones posteriores en esta área.

Desde 1955 se han publicado numerosos trabajos dedicados a la programación cuadrática (trabajos de Beal, Barankin y R. Dorfman , Frank (M. Frank) y F. Wolf , G. Markowitz , etc.). Los trabajos de Dennis (JB Dennis), Rosen (JB Rosen) y Zontendijk (G. Zontendijk) desarrollaron métodos de gradiente para resolver problemas de programación no lineal.

En la actualidad, para la aplicación efectiva de métodos de programación matemática y resolución de problemas en computadoras, se han desarrollado lenguajes de modelado algebraico , cuyos representantes son AMPL y LINGO .

Véase también

Notas

↑ Fuente: Biblioteca Científica Universal Regional de Altai. V. Ya. Shishkova (AKUNB) Archivado el 5 de marzo de 2022 en Wayback Machine . Métodos de optimización: Proc. tolerancia. Brazovskaya NV; Universidad Técnica Estatal de Altai I. I. Polzunova, [Centro de Distancia. formación].-Barnaul: Editorial de AltSTU, 2000, 120 p. -UDC/LBC 22.183.4 B871
↑ Encontrar el Óptimo: La Computadora Expande las Posibilidades . - M. : Nauka, 1989. - S. 14 . — ISBN 5-02-006737-7 .

Literatura

Abakarov A. Sh., Sushkov Yu. A. Estudio estadístico de un algoritmo de optimización global . - Actas de FORA, 2004.
Akulich I. L. Programación matemática en ejemplos y tareas: Proc. Subsidio para la economía de los estudiantes. especialista. universidades - M. : Escuela Superior, 1986.
Gill F., Murray W., Wright M. Optimización práctica. Por. De inglés. — M .: Mir, 1985.
Girsanov IV Conferencias sobre la teoría matemática de los problemas extremos. - M .; Izhevsk : Centro de investigación "Dinámica regular y caótica", 2003. - 118 p. — ISBN 5-93972-272-5 .
Zhiglyavsky A. A., Zhilinkas A. G. Métodos para buscar un extremo global. — M .: Nauka, Fizmatlit , 1991.
Karmanov VG Programación matemática. - Editorial de Phys.-Math. Literatura, 2004.
Korn G., Korn T. Manual de matemáticas para científicos e ingenieros. - M. : Nauka, 1970. - S. 575-576.
Korshunov Yu. M., Korshunov Yu. M. Fundamentos matemáticos de la cibernética. — M .: Energoatomizdat , 1972.
Lotov A. V. , Pospelova I. I. Notas de clase sobre la teoría y los métodos de optimización multicriterio. Archivado el 21 de enero de 2022 en Wayback Machineasentamiento M., 2005. 127 págs.
Maksimov Yu. A., Filippovskaya EA Algoritmos para resolver problemas de programación no lineal. — M. : MEPHI, 1982.
Maksimov Yu. A. Algoritmos de programación lineal y discreta. — M. : MEPhI, 1980.
Plotnikov A.D. Programación matemática = curso rápido. - 2006. - S. 171. - ISBN 985-475-186-4 .
Rastrigin L. A. Métodos estadísticos de búsqueda. - M. , 1968.
Sergeev Ya. D., Kvasov D. E. Métodos diagonales de optimización global . Archivado el 26 de octubre de 2017 en Wayback Machine . — M.: FIZMATLIT, 2008. 341s.
Hemdy A. Taha. Introducción a la Investigación Operativa = Investigación Operativa: Una Introducción. - 8ª edición. - M .: Williams , 2007. - S. 912. - ISBN 0-13-032374-8 .
Kini RL, Raifa H. Toma de decisiones bajo múltiples criterios: preferencias y sustituciones. - M. : Radio y comunicación, 1981. - 560 p.
Zukhovitsky S. I. , Avdeeva L. I. Programación lineal y convexa. - 2ª ed., revisada. y adicional .. - M . : Editorial "Nauka", 1967.
Minaev Yu. N. Estabilidad de los modelos de optimización económica y matemática. - M. : Estadísticas, 1980.
Moiseev NN Métodos numéricos en la teoría de sistemas óptimos . - M. : Nauka, 1971. - 424 p.
Moiseev NN Elementos de la teoría de los sistemas óptimos . — M .: Nauka, 1975. — 528 p.
Moiseev NN , Ivanilov Yu. P. , Stolyarova EM Métodos de optimización . - M. : Nauka, 1978. - 352 p.

Degtyarev Yu. I. Métodos de optimización. - M. : radio soviética, 1980. - 272 p.
Rekleitis G., Reyvindran A., Ragsdel K. Optimización en ingeniería. - M. : Mir, 1986. - 400 p.
Romanovsky IV Algoritmos para la resolución de problemas extremos. — M .: Nauka, 1977. — 352 p. - 16.000 copias.
Umnov A.E. , Umnov E. A. Problemas paramétricos en programación matemática Archivado el 9 de julio de 2021 en Wayback Machine (pdf)
Khokhlyuk VI Algoritmos de optimización de enteros paralelos. Archivado el 18 de enero de 2021 en elCurso de conferencias Wayback Machine . Novosibirsk , 2007.
Khokhlyuk V. I. Métodos de optimización discretos. Archivado el 18 de enero de 2021 en Wayback Machine . NSU, 2013. 154 págs.

Enlaces

Polyak B.P. Historia de la programación matemática en la URSS: análisis del fenómeno // Actas del 14º seminario escolar de Baikal "Métodos de optimización y sus aplicaciones". - 2008. - T. 1 . - S. 2-20 .

diccionarios y enciclopedias	Gran danés gran ruso Britannica (en línea)
En catálogos bibliográficos	BNF : 11932649z TIERRA : 4043664-0 J9U : 987007538691105171 LCCN : sh85107312 NKC : ph122672

Métodos de optimización
unidimensional	método de la sección áurea Dicotomía método de parábola búsqueda de cuadrícula Método de búsqueda de bloque uniforme método fibonacci búsqueda ternaria método Piyavsky Método Strongin
orden cero	método de Gauss Método Nelder-Mead Método Hook-Jeeves método de Rosenbrock Método Powell
Primer orden	descenso de gradiente método Zeutendijk Descenso coordinado método de gradiente conjugado Métodos Cuasi-Newtonianos Algoritmo de Levenberg-Marquardt
segundo orden	método de newton Método de Newton-Raphson Algoritmo de Broyden-Fletcher-Goldfarb-Shanno (BFGS)
estocástico	Método de Montecarlo recocido simulado Algoritmos evolutivos evolución diferencial Algoritmo de hormiga método de enjambre de partículas Algoritmo de colonia de abejas Método de paseo aleatorio
Métodos de programación lineal	método símplex algoritmo de gomori método elipsoide método potencial
Métodos de programación no lineal	Programación cuadrática secuencial

ciencia economica
Teoría económica Economía política Economía Aplicada
Metodología	Modelos económicos Sistemas economicos economía matemática Econometría economía experimental Economía Computacional Microfundamentos de la macroeconomía
Microeconomía	conjunto de presupuesto Salario curva de indiferencia Elección intertemporal Incertidumbre Aversión al riesgo Tasa de retorno bienes públicos Utilidad Esperado limitando Teoría del consumo Lucro Por ciento Equilibrio General Distribución Racionamiento Rareza de recursos Renta Mercado Oferta y demanda Precio Estructura del mercado Competencia monopolio Perfecto Monopolio doble cara Monopsonio oligopolio oligopsonio Déficit de productos básicos fiasco del mercado teoría de la empresa Precio externalia Elasticidad efecto ingreso efecto de sustitución efecto de escala Eficiencia de Pareto Costos Alternativa implícito No reembolsable Público Límite Medio transaccional Análisis coste-beneficio excedente Elección social
Macroeconómica	Desempleo Divisa Dinero Demanda Frase Emisión Política de dinero-crédito Deflación Inflación Hiperinflación cruz keynesiana curva de phillips Una crisis La gran Depresión Modelo AD-AS Modelo IS-LM Dureza nominal " Teoría general " de Keynes Expectativas Adaptado Racional Paridad del poder adquisitivo saldo de pago Tasa de interés Recesión teoría del crecimiento Ahorro Sistema de Cuentas Nacionales La demanda agregada Estanflación la política fiscal Banco Central teoría del ciclo contracción de la inflación Demanda efectiva DSGE NAIRU Modelos Medición de la Renta Nacional y la Producción Inversiones Nivel de precio Choque de oferta Choque de demanda
economía matemática	La investigación de operaciones Econometría Teoría de la decisión Teoría de juego Diseño del mecanismo El modelo de entrada-salida matemáticas financieras
Economía Aplicada	Bienestar Geografía económica Ciudades demografía económica teoría del dinero Conocimiento educación Salud historia economica internacional y mundial elección pública Ambiente economía ecológica organización de la industria Política económica Desarrollo Regional Religiones Familias socioeconomía sociología económica Mano de obra sector público planificación económica Análisis económico del derecho Recursos Naturales Agricultura (inglés) Estadísticas económicas Financiero
Escuelas ( historia ) del pensamiento económico	Pensamiento económico del Antiguo Oriente Pensamiento económico de la Antigüedad austriaco Bloomington Budista harvard Georgiaismo institucionalismo histórico Catedrático-socialismo keynesianismo Neokeynesianismo ( síntesis neoclásica-keynesiana ) Poskeynesianismo Teoría de la circulación monetaria Nuevo clásico constitucional maltusianismo Manchester marginalismo marxista neomarxista _ Corriente principal económica Mercantilismo teoría del sistema mundial monetarismo neoclásico Lausana heterodoxo Nuevo institucional Nuevo clásico Teoría del ciclo económico real conductual Economía del lado de la oferta Salamanca Estocolmo Fisiocracia chartalismo Teoría monetaria moderna chicago evolutivo Ecológico Pensamiento económico de la Edad Media anarquista Mutualismo No equilibrio socialista Termoeconomía feminista
ver también	mesoeconomía Clasificación de la literatura económica JEL Las publicaciones más importantes en el campo de la economía