Metoda de enumerare

Metoda de enumerare (metoda de căutare uniformă, enumerarea grilă) este cea mai simplă dintre metodele de găsire a valorilor funcțiilor cu valori reale în funcție de oricare dintre criteriile de comparație (la maxim , la minim , la o anumită constantă). Aplicat problemelor extreme, este un exemplu de metodă directă de optimizare pasivă unidimensională condiționată .

Descriere

Să ilustrăm esența metodei de căutare uniformă luând în considerare problema găsirii minimului.

Să fie dată o funcție . Și problema de optimizare arată astfel: . Să fie dat și numărul de observații . $f(x):\;[a,\;b]\la {\mathbb {R}}$ $f(x)\la \min _{{x\in [a,\;b]}}$ $n$

Apoi segmentul este împărțit în părți egale prin puncte de împărțire: $\left[a,b\right]$ $(n+1)$

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

După ce am calculat valorile în puncte , găsim prin comparație punctul unde este un număr de la până la astfel încât $F\stânga(x\dreapta)$ $x_{i},\;i=1,\ldots ,n$ $x_{m}$ $m$ $unu$ $n$

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

pentru toată lumea de la până la .

i

unu

n

Atunci intervalul de incertitudine este , iar eroarea în determinarea punctului minim al funcției, respectiv, este : . $2{\frac {\left(ba\right)}{(n+1)))$ $x_{m}$ $F\stânga(x\dreapta)$ $\varepsilon ={\frac {\left(ba\right)}{n+1}}$

Modificare

Dacă numărul dat de dimensiuni este par ( ), atunci partiționarea se poate face într-un mod diferit, mai sofisticat: $n=2k$

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

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

, unde este o constantă din intervalul .

\delta

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

Apoi, în cel mai rău caz, intervalul de incertitudine are lungimea . ${\frac {(ba)}{(n/2+1)}}+\delta$

Combinatorică

Metoda de enumerare este una dintre cele mai simple metode combinatorice. [unu]

Literatură

Akulich I.L. Programare matematică în exemple și sarcini: Proc. indemnizație pentru economia studenților. specialist. universități. - M .: Mai sus. scoala, 1986.
Gill F., Murray W., Wright M. Optimizare practică. Pe. din engleza. — M .: Mir, 1985.
Maksimov Yu.A.,Filipovskaya E.A. Algoritmi pentru rezolvarea problemelor de programare neliniară. — M .: MEPhI, 1982.
Korn G., Korn T. Manual de matematică pentru oameni de știință și ingineri. - M . : Nauka, 1970. - S. 575-576.

Note

↑ Elemente de combinatorie. Metode de rezolvare a unor probleme

Metode de optimizare
Unidimensional	metoda secțiunii de aur Dihotomie Metoda parabolelor Căutare în grilă Metoda de căutare uniformă a blocurilor Metoda Fibonacci Căutare ternară metoda Piyavsky Metoda Strongin
Comanda zero	metoda Gauss Metoda Nelder-Mead Metoda Hook-Jeeves metoda Rosenbrock metoda Powell
Prima comanda	coborâre în gradient Metoda Zeutendijk Coordonarea coborârii Metoda gradientului conjugat Metode cvasi-newtoniene Algoritmul Levenberg-Marquardt
a doua comanda	metoda lui Newton Metoda Newton-Raphson Algoritmul Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastic	Metoda Monte Carlo Recoacere simulată Algoritmi evolutivi evolutie diferentiala Algoritmul furnicilor Metoda roiului de particule Algoritmul coloniilor de albine Metoda de mers aleatoriu
Metode de programare liniară	Metoda simplex algoritmul lui Gomori Metoda elipsoidă Metoda potențială
Metode de programare neliniară	Programare secvenţială pătratică