Laskentamenetelmä

Luettelomenetelmä (yhtenäinen hakumenetelmä, ruudukkolaskenta) on yksinkertaisin menetelmistä reaaliarvoisten funktioiden arvojen löytämiseksi minkä tahansa vertailukriteerin mukaan ( maksimiin , minimiin , tiettyyn vakioon). Äärimmäisiin ongelmiin sovellettu se on esimerkki suorasta menetelmästä ehdolliseen yksiulotteiseen passiiviseen optimointiin .

Kuvaus

Havainnollistetaan yhtenäisen hakumenetelmän olemusta pohtimalla minimin löytämisen ongelmaa.

Olkoon funktio annettu . Ja optimointiongelma näyttää tältä: . Ilmoitetaan myös havaintojen määrä . $f(x):\;[a,\;b]\to {\mathbb {R}}$ $f(x)\to \min _{{x\in [a,\;b]}}$ $n$

Sitten segmentti jaetaan yhtä suuriin osiin jakopisteillä: $\vasen[a,b\oikea]$ $(n+1)$

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

Laskettuamme arvot pisteissä , löydämme vertailuna pisteen , jossa on luku alkaen sellaiseen , että $F\vasen(x\oikea)$ $x_{i},\;i=1,\ldots ,n$ $x_{m}$ $m$ $yksi$ $n$

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

kaikille alkaen - .

i

yksi

n

Tällöin epävarmuusväli on , ja virhe funktion minimipisteen määrittämisessä on vastaavasti: . $2{\frac {\left(ba\right)}{(n+1)))$ $x_{m}$ $F\vasen(x\oikea)$ $\varepsilon ={\frac {\left(ba\right)}{n+1}}$

Muutos

Jos annettu määrä mittoja on parillinen ( ), osiointi voidaan tehdä toisella, hienostuneemmalla tavalla: $n = 2k$

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

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

, missä on jokin vakio väliltä .

\delta

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

Silloin epävarmuusvälillä on pahimmassa tapauksessa pituus . ${\frac {(ba)}{(n/2+1)}}+\delta$

Kombinatoriikka

Luettelomenetelmä on yksi yksinkertaisimmista kombinatorisista menetelmistä. [yksi]

Kirjallisuus

Akulich I.L. Matemaattinen ohjelmointi esimerkeissä ja tehtävissä: Proc. opiskelijatalouden tuki. asiantuntija. yliopistot. - M . : Korkeampi. koulu, 1986.
Gill F., Murray W., Wright M. Käytännön optimointi. Per. englannista. - M .: Mir, 1985.
Maksimov Yu.A., Filipovskaya E.A. Algoritmit epälineaarisen ohjelmoinnin ongelmien ratkaisemiseen. - M .: MEPhI, 1982.
Korn G., Korn T. Matematiikan käsikirja tutkijoille ja insinööreille. - M .: Nauka, 1970. - S. 575-576.

Muistiinpanot

↑ Kombinatorian elementit. Menetelmät joidenkin ongelmien ratkaisemiseksi

Optimointimenetelmät _
Yksiulotteinen	kultaisen leikkauksen menetelmä Dikotomia Paraabeli menetelmä Verkkohaku Yhtenäinen lohkohakumenetelmä Fibonaccin menetelmä Kolminkertainen haku Piyavsky menetelmä Vahva menetelmä
Nolla järjestys	Gaussin menetelmä Nelder-Meadin menetelmä Hook-Jeeves -menetelmä Rosenbrockin menetelmä Powellin menetelmä
Ensimmäinen tilaus	gradienttilasku Zeutendijkin menetelmä Koordinaattilasku Konjugaattigradienttimenetelmä Kvasi-Newtonilaiset menetelmät Levenberg-Marquardt-algoritmi
toinen tilaus	Newtonin menetelmä Newton-Raphsonin menetelmä Broyden-Fletcher-Goldfarb-Shanno-algoritmi (BFGS)
Stokastinen	Monte Carlon menetelmä Simuloitu hehkutus Evoluutioalgoritmit differentiaalinen evoluutio Ant algoritmi Hiukkasparvimenetelmä Mehiläisyhdyskunnan algoritmi Satunnainen kävelymenetelmä
Lineaariset ohjelmointimenetelmät _	Yksinkertainen menetelmä Gomorin algoritmi Ellipsoidi menetelmä Potentiaalinen menetelmä
Epälineaariset ohjelmointimenetelmät	Jaksottainen neliöllinen ohjelmointi