Uppräkningsmetod

Uppräkningsmetoden (enhetlig sökmetod, rutnätsuppräkning) är den enklaste av metoderna för att hitta värdena för funktioner med verkligt värde enligt något av jämförelsekriterierna (till maximalt , till minimum , till en viss konstant). Tillämpat på extrema problem är det ett exempel på en direkt metod för villkorad endimensionell passiv optimering .

Beskrivning

Låt oss illustrera kärnan i den enhetliga sökmetoden genom att överväga problemet med att hitta minimum.

Låt en funktion ges . Och optimeringsproblemet ser ut så här: . Låt också antalet observationer anges . $f(x):\;[a,\;b]\to {\mathbb {R}}$ $f(x)\till \min _{{x\i [a,\;b]}}$ $n$

Sedan delas segmentet in i lika delar med divisionspunkter: $\vänster[a,b\höger]$ $(n+1)$

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

Efter att ha beräknat värdena vid punkter , finner vi genom jämförelse punkten , där är ett tal från till så att $F\vänster(x\höger)$ $x_{i},\;i=1,\ldots ,n$ $x_{m}$ $m$ $ett$ $n$

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

för alla från till .

i

ett

n

Då är osäkerhetsintervallet , och felet vid bestämning av funktionens minimipunkt är : . $2{\frac {\left(ba\right)}{(n+1)))$ $x_{m}$ $F\vänster(x\höger)$ $\varepsilon ={\frac {\left(ba\right)}{n+1}}$

Ändring

Om det givna antalet dimensioner är jämnt ( ), kan partitionering göras på ett annat, mer sofistikerat sätt: $n=2k$

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

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

, där är någon konstant från intervallet .

\delta

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

Då har osäkerhetsintervallet i värsta fall längd . ${\frac {(ba)}{(n/2+1)}}+\delta$

Combinatorics

Uppräkningsmetoden är en av de enklaste kombinatoriska metoderna. [ett]

Litteratur

Akulich I.L. Matematisk programmering i exempel och uppgifter: Proc. bidrag för studenters ekonomi. specialist. universitet. - M . : Högre. skola, 1986.
Gill F., Murray W., Wright M. Praktisk optimering. Per. från engelska. — M .: Mir, 1985.
Maksimov Yu.A., Filipovskaya E.A. Algoritmer för att lösa problem med icke-linjär programmering. — M .: MEPhI, 1982.
Korn G., Korn T. Handbok i matematik för vetenskapsmän och ingenjörer. - M . : Nauka, 1970. - S. 575-576.

Anteckningar

↑ Inslag av kombinatorik. Metoder för att lösa vissa problem

Optimeringsmetoder _
En-dimensionell	gyllene snittmetoden Dikotomi Parabolmetoden Rutnätssökning Enhetlig blocksökningsmetod Fibonacci-metoden Ternär sökning Piyavsky-metoden Strongin metod
Noll ordning	Gauss metod Nelder-Mead metod Hook-Jeeves metod Rosenbrock-metoden Powell metod
Första beställning	lutning nedstigning Zeutendijk-metoden Koordinera nedstigning Konjugerad gradientmetod Kvasi-newtonska metoder Levenberg-Marquardts algoritm
andra beställning	Newtons metod Newton-Raphson-metoden Broyden-Fletcher-Goldfarb-Shanno-algoritm (BFGS)
Stokastisk	Monte Carlo metoden Simulerad glödgning Evolutionära algoritmer differentiell evolution Myralgoritm Partikelsvärmmetod Algoritm för bikoloni Random walk-metod
Linjära programmeringsmetoder _	Enkel metod Gomoris algoritm Ellipsoid metod Potentiell metod
Icke -linjära programmeringsmetoder	Sekventiell kvadratisk programmering