Opregningsmetode

Optællingsmetoden (ensartet søgemetode, gitteropregning) er den enkleste af metoderne til at finde værdierne af funktioner med reelle værdier i henhold til et hvilket som helst af sammenligningskriterierne (til maksimum , til minimum , til en vis konstant). Anvendt på ekstreme problemer er det et eksempel på en direkte metode til betinget endimensionel passiv optimering .

Beskrivelse

Lad os illustrere essensen af den ensartede søgemetode ved at overveje problemet med at finde minimum.

Lad en funktion gives . Og optimeringsproblemet ser således ud: . Lad også antallet af observationer oplyses . $f(x):\;[a,\;b]\til {\mathbb {R}}$ $f(x)\til \min _{{x\i [a,\;b]}}$ $n$

Derefter opdeles segmentet i lige store dele med divisionspunkter: $\venstre[a,b\højre]$ $(n+1)$

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

Efter at have beregnet værdierne ved punkter , finder vi ved sammenligning punktet , hvor er et tal fra til sådan, at $F\venstre(x\højre)$ $x_{i},\;i=1,\ldots ,n$ $x_{m}$ $m$ $en$ $n$

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

for alle fra til .

jeg

en

n

Så er usikkerhedsintervallet , og fejlen ved bestemmelse af funktionens minimumspunkt er henholdsvis : . $2{\frac {\left(ba\right)}{(n+1)))$ $x_{m}$ $F\venstre(x\højre)$ $\varepsilon ={\frac {\left(ba\right)}{n+1}}$

Ændring

Hvis det givne antal dimensioner er lige ( ), kan partitionering udføres på en anden, mere sofistikeret måde: $n=2k$

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

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

, hvor er en konstant fra intervallet .

\delta

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

Så har usikkerhedsintervallet i værste fald længde . ${\frac {(ba)}{(n/2+1)}}+\delta$

Combinatorics

Optællingsmetoden er en af de enkleste kombinatoriske metoder. [en]

Litteratur

Akulich I.L. Matematisk programmering i eksempler og opgaver: Proc. godtgørelse for studerendes økonomi. specialist. universiteter. - M . : Højere. skole, 1986.
Gill F., Murray W., Wright M. Praktisk optimering. Om. fra engelsk. — M .: Mir, 1985.
Maksimov Yu.A., Filipovskaya E.A. Algoritmer til løsning af problemer med ikke-lineær programmering. - M .: MEPhI, 1982.
Korn G., Korn T. Håndbog i matematik for videnskabsmænd og ingeniører. - M . : Nauka, 1970. - S. 575-576.

Noter

↑ Elementer af kombinatorik. Metoder til at løse nogle problemer

Optimeringsmetoder _
Endimensionel	gyldne snit metode Modsætning Parabel metode Netsøgning Ensartet bloksøgningsmetode Fibonacci metode Ternær søgning Piyavsky metode Strongin metode
Nul orden	Gauss metode Nelder-Mead metode Hook-Jeeves metode Rosenbrock metode Powell metode
Første ordre	gradient nedstigning Zeutendijk metode Koordinat nedstigning Konjugeret gradientmetode Kvasi-newtonske metoder Levenberg-Marquardt algoritme
anden orden	Newtons metode Newton-Raphson metode Broyden-Fletcher-Goldfarb-Shanno-algoritme (BFGS)
Stokastisk	Monte Carlo metode Simuleret udglødning Evolutionære algoritmer differentiel evolution Myre-algoritme Partikelsværmmetode Algorithme for bikoloni Tilfældig gå-metode
Lineære programmeringsmetoder _	Enkel metode Gomoris algoritme Ellipsoid metode Potentielle metode
Ikke-lineære programmeringsmetoder	Sekventiel kvadratisk programmering