Método de enumeración

El método de enumeración (método de búsqueda uniforme, enumeración de cuadrícula) es el más simple de los métodos para encontrar los valores de las funciones de valor real de acuerdo con cualquiera de los criterios de comparación (al máximo , al mínimo , a cierta constante). Aplicado a problemas extremos, es un ejemplo de un método directo de optimización pasiva unidimensional condicional .

Descripción

Ilustremos la esencia del método de búsqueda uniforme considerando el problema de encontrar el mínimo.

Sea dada una función . Y el problema de optimización se ve así: . Sea también el número de observaciones . $f(x):\;[a,\;b]\to {\mathbb {R}}$ $f(x)\to \min _{{x\in [a,\;b]}}$ $norte$

Entonces el segmento se divide en partes iguales por puntos de división: $\izquierda[a,b\derecha]$ $(n+1)$

x_{i}=a+i{\frac {\left(ba\right)}{(n+1)))),\quad i=1,\ldots,n

Habiendo calculado los valores en los puntos , encontramos por comparación el punto , donde es un número de a tal que $F\izquierda(x\derecha)$ $x_{i},\;i=1,\ldots,n$ $x_{m}$ $metro$ $una$ $norte$

F\left(x_{m}\right)=\min F\left(x_{i}\right)

para todos de a .

i

una

norte

Entonces el intervalo de incertidumbre es , y el error al determinar el punto mínimo de la función, respectivamente, es : . $2{\frac {\izquierda(ba\derecha)}{(n+1)))$ $x_{m}$ $F\izquierda(x\derecha)$ $\varepsilon ={\frac {\left(ba\right)}{n+1}}$

Modificación

Si el número dado de dimensiones es par ( ), entonces la partición se puede realizar de una manera diferente y más sofisticada: $n=2k$

x_{2i}=a+{\frac {(ba)}{(n/2+1)}}2i,\quad i=1,\ldots,n/2

x_{2i-1}=x_{2i}-\delta

, donde es alguna constante del intervalo .

\delta

\left(0,\;{\frac{(ba)}{(n/2+1)}}\right)

Entonces, en el peor de los casos, el intervalo de incertidumbre tiene una longitud de . ${\frac{(ba)}{(n/2+1)}}+\delta$

Combinatoria

El método de enumeración es uno de los métodos combinatorios más simples. [una]

Literatura

Akulich I.L. Programación matemática en ejemplos y tareas: Proc. Subsidio para la economía de los estudiantes. especialista. universidades - M. : Superior. escuela, 1986.
Gill F., Murray W., Wright M. Optimización práctica. Por. De inglés. — M .: Mir, 1985.
Maksimov Yu.A.,Filipovskaya E.A. Algoritmos para la resolución de problemas de programación no lineal. — M. : MEPHI, 1982.
Korn G., Korn T. Manual de matemáticas para científicos e ingenieros. - M. : Nauka, 1970. - S. 575-576.

Notas

↑ Elementos de combinatoria. Métodos para resolver algunos problemas.

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 metodo 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