Optimizacija (matematika): Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
m robot Dodajanje: pt:Otimização |
m robot Dodajanje: ur:کاملیت (ریاضیات); kozmetične spremembe |
||
Vrstica 3:
V matematiki se izraz '''optimizacija''' ali '''matematično programiranje''' nanaša na iskanje minimuma ali maksimuma dane realne [[Funkcija|funkcije]] na dovoljeni množici točk. Problem predstavimo na sledeči način:
:Pri dani '''namenski funkciji''' ''f'' : ''A'' <math>\to</math> '''R''' iz [[množica (matematika)|
:''Iščemo'' takšen element ''x''<sub>0</sub> v ''A'', da je ''f''(''x''<sub>0</sub>) ≤ ''f''(''x'') za vse ''x'' v ''A'' (''minimizacija'') ali da je ''f''(''x''<sub>0</sub>) ≥ ''f''(''x'') ya vse ''x'' v ''A'' (''maksimizacija'').
Vrstica 15:
:min ''f''(''x'') = ''x''<sub>1</sub><sup>2</sup>+''x''<sub>2</sub><sup>2</sup>
pri pogojih
:''x''<sub>1</sub>
in
:''x''<sub>2</sub> = 1
Vrstica 21:
V prvi vrstici je definirana ''namenska funkcija'' ''f''(''x''), ki jo minimiziramo. druga in tretja vrstica predstavljata [[omejitev (matematika)|omejitvi]], ki določata množico dopustnih rešitev ''A''. Druga vrstica predstavlja ''neeenakostno omejitev'', tretja pa ''enakostno''. Po dogovoru navadno omejitve pišemo tako, da je na eni strani enačaja ali neenačaja ničla:
:''c'' <sub>1</sub> ('''x''') = 1-''x''<sub>1</sub>
in
:''c'' <sub>2</sub> ('''x''') = 1 - ''x''<sub>2</sub> = 0
Vrstica 31:
* [[Linearno programiranje]] se ukvarja s problemi, kjer je namenska funkcija ''f'' linearna, dovoljeno območje ''A'' pa je določeno le z linearnimi enačbami in neenačbami.
* [[Celo programiranje]] se ukvarja z linearnimi programi, kjer lahko nekatere ali vse spremenljivke zavzamejo le [[celo število|cele]] vrednosti.
* [[Kvadratično programiranje]] - namenska funkcija lahko vsebuje kvadratne člene,
* [[Nelinearno programiranje]] - splošen primer, ko namenska funkcija ali omejitve ali oboji vsebujejo nelinearne člene.
* [[Konveksno programiranje]] - namenska funkcija je konveksna, prav tako dovoljeno območje.
* [[Semidefinitno programiranje]] je podpodročje konveksne optimizacije, jer so spremenljivke [[defintna bilinearna forma
* [[Stohastično programiranje]] se ukvarja s primeri, kjer so nekatere od omejitev ali parametrov odvisne od [[naključno število
* [[Robustno programiranje]] - pri tem podobno kot pri stohastičnem programiranju poskušamo zajeti negotovost v podatkih, na katerih temelji optimizacijski problem.
* [[Dinamično programiranje]] se ukvarja z reševanjem problemov, kjer strategija reševanja temelji na razcepu na manjše podprobleme.
Vrstica 43:
== Metode reševanja ==
Pri dvakrat zvezno diferenciabilnih funkcijah lahko probleme brez omejitev (enostavna [[minimizacija]] ali [[maksimizacija]]) rešujemo z iskanjem stacionarnih točk, v katerih je [[gradient]] namenske funkcije nič. Pri tem uporabimo [[Hessova matrika|Hessovo matriko]] za dolo;itev tipa stacionarne točke. Če je Hessova matrika [[defintna bilinearna forma
Obstoj odvodov ni vedno zagotovljen ali pa jih je težko izračunati (na primer, kadar je namenska funcija definirana preko rešitve zapletenega sistema diferencialnih enačb). Zato delimo metode reševanja optimizacijskih problemov na razrede glede na potrebno glaskost namenske in omejitvenih funkcij, ki so:
* Kombinatorične metode
* Metode brez uporabe odvodov
* Metode prvega reda
* Metode drugega reda
Spodaj je naštetih nekaj ožjih skupin metod:
* [[Metoda najstrmejšega sestopa]] (oz. dvigovanja pri maksimizaciji)
* [[Nelder-Meadova]] metoda ali nelinearna simpleksna metoda
* [[Simpleksna metoda]] za linearno programiranje
* [[Newtonova metoda]]
* [[Kvazi-Newtonova metoda]]
* [[Metode notranje točke]]
* [[Metoda konjugiranih gradientov]]
* [[Metoda konjugiranih smeri]] - ekvivalent metodi knjugiranih gradientov v primeru, ko nimamo na voljo odvdov funkcije
* [[Metoda aktivne množice]]
* [[Zaporedno kvadratično programiranje]]
* [[Metoda zaporednih aproksimacij]]
* [[Evolucijske metode]], na primer [[genetski algoritmi]]
* [[Stohastično tuneliranje]]
* [[Metoda jate delcev]]
* [[Diferencialna evolucija]]
* [[Optimizacija s kolonijo mravelj]]
Pri [[Gradientna metoda|gradientnih metodah]] v glavnem uporabljamo dva osnovna pristopa reševanja optimizacijskih problemov (imenujemo ju tudi [[prototipni algoritem|prototipna algoritma]]): [[minimizacija v dani smeri]] in [[Metoda omejenega koraka
Probleme z omejitvami pogosto prevedemo na problem iskanja ekstremov funkcije brez omejitev s pomočjo [[Lagrangeov množitelj|Lagrangeovih množiteljev]].
== Glej tudi ==
* [[arg min]]
* [[Operacijske raziskave]]
* [[Variacijski račun]]
* [[
* [[
* [[IOptLib]]
* [[Inverse]]
== Zunanje povezave ==
* [http://www-fp.mcs.anl.gov/otc/Guide/index.html NEOS Guide (vodič po programju za optimizacijo)]
* [http://www.mathprog.org/ Mathematical Programming Society]
* [http://www-unix.mcs.anl.gov/otc/Guide/faq/ Optimization FAQ] - pogosta vprašanja s področja optimizacije
* [http://www.ipp.mpg.de/de/for/bereiche/stellarator/Comp_sci/CompScience/csep/csep1.phy.ornl.gov/mo/mo.html Mathematical optimization]
Vrstica 91:
; Modelski jeziki za optimizacijo:
* [http://www.gams.com/ GAMS]
* [http://www.ampl.com/ AMPL]
* [http://www.maximal-usa.com/mpl/ MPL]
* [http://www.c3m.si/Inverse/ Inverse]
; Programi za reševanje optimizacijskih problemov:
* [http://www.ilog.com/products/cplex/ CPLEX]
* [http://www.mosek.com/ Mosek]
* [http://www.sas.com/technologies/analytics/optimization/ SAS OR]
* [http://www.conopt.com/ CONOPT]
* [http://www.dashoptimization.com/ Xpress-MP - Optimizacijski program, ki je prost za študente]
* [http://projects.coin-or.org/Ipopt IPOPT] - metoda notranje točke za reševanje problemov nelinearnega programiranja, odprta koda.
* [http://www.stanford.edu/group/SOL/software.html Free Optimization Software by Systems Optimization Laboratory, Stanford University]
; Optimizacijske knjižnice:
* [http://ool.sourceforge.net/ OOL (Open Optimization library)] - zbirka optimizacijskih rutin v jeziku C.
* [http://www2.arnes.si/~ljc3m2/igor/ioptlib/ IOptLib (Investigative Optimization Library)] - knjižica za razvoj optimizacijskih algoritmov (ANSI C, odprta koda).
[[Kategorija:Operacijske raziskave]]
Vrstica 144:
[[tr:Optimizasyon]]
[[uk:Задача оптимізації]]
[[ur:کاملیت (ریاضیات)]]
[[vi:Tối ưu hóa (toán học)]]
[[zh:最优化]]
|