Metoda výčtu

Metoda výčtu (metoda jednotného vyhledávání, výčet mřížky) je nejjednodušší z metod pro nalezení hodnot reálně hodnotných funkcí podle libovolného srovnávacího kritéria (na maximum , na minimum , na určitou konstantu). Při aplikaci na extremální problémy je příkladem přímé metody podmíněné jednorozměrné pasivní optimalizace .

Popis

Ukažme si podstatu jednotné vyhledávací metody tím, že se zamyslíme nad problémem hledání minima.

Nechť je dána funkce . A optimalizační problém vypadá takto: . Uveďme také počet pozorování . $f(x):\;[a,\;b]\to {\mathbb {R}}$ $f(x)\to \min _{{x\in [a,\;b]}}$ $n$

Poté je segment rozdělen na stejné části pomocí dělicích bodů: $\left[a,b\right]$ $(n+1)$

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

Po výpočtu hodnot v bodech najdeme porovnáním bod , kde je číslo od do takové, že $F\left(x\right)$ $x_{i},\;i=1,\ldots ,n$ $x_{m}$ $m$ $jeden$ $n$

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

pro všechny od do .

i

jeden

n

Potom je interval nejistoty , a chyba při určování minimálního bodu funkce je : . $2{\frac {\left(ba\right)}{(n+1)))$ $x_{m}$ $F\left(x\right)$ $\varepsilon ={\frac {\left(ba\right)}{n+1}}$

Úprava

Pokud je zadaný počet dimenzí sudý ( ), pak lze rozdělení provést jiným, sofistikovanějším způsobem: $n=2k$

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

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

, kde je nějaká konstanta z intervalu .

\delta

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

V nejhorším případě má interval nejistoty délku . ${\frac {(ba)}{(n/2+1)}}+\delta$

Kombinatorika

Výčtová metoda je jednou z nejjednodušších kombinatorikových metod. [jeden]

Literatura

Akulich I.L. Matematické programování v příkladech a úlohách: Proc. příspěvek na studentské hospodářství. specialista. vysoké školy. - M .: Vyšší. škola, 1986.
Gill F., Murray W., Wright M. Praktická optimalizace. Za. z angličtiny. — M .: Mir, 1985.
Maksimov Yu.A., Filipovskaya E.A. Algoritmy pro řešení problémů nelineárního programování. — M. : MEPhI, 1982.
Korn G., Korn T. Příručka matematiky pro vědce a inženýry. - M .: Nauka, 1970. - S. 575-576.

Poznámky

↑ Prvky kombinatoriky. Metody řešení některých problémů

Optimalizační metody
Jednorozměrný	metoda zlatého řezu Dichotomie Parabolová metoda Vyhledávání v mřížce Jednotná metoda vyhledávání bloků Fibonacciho metoda Ternární hledání Piyavského metoda Stronginovou metodou
Nulové pořadí	Gaussova metoda Metoda Nelder-Mead Hook-Jeevesova metoda Rosenbrockova metoda Powellova metoda
První objednávka	gradientní sestup Zeutendijkova metoda Souřadnicový sestup Metoda konjugovaného gradientu Kvazi-newtonské metody Levenberg-Marquardtův algoritmus
druhá objednávka	Newtonova metoda Newton-Raphsonova metoda Algoritmus Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastické	Metoda Monte Carlo Simulované žíhání Evoluční algoritmy diferenciální evoluce Algoritmus mravenců Metoda roje částic Algoritmus včelstva Metoda náhodné chůze
Metody lineárního programování	Simplexní metoda Gomoriho algoritmus Elipsoidní metoda Potenciální metoda
Metody nelineárního programování	Sekvenční kvadratické programování