Optimizacija (matematika): Razlika med redakcijama

Izbrisana vsebina Dodana vsebina
TXiKiBoT (pogovor | prispevki)
m robot Dodajanje: pt:Otimização
Xqbot (pogovor | prispevki)
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)| množice]] ''A'' v [[realno število|realna števila]]
:''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> &ge; 1
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> &le; 0
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, območje ''A'' pa je določeno le z linearnimi enačbami in neenačbami.
* [[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 |semidefinitne]] [[matrika | matrike]]
* [[Stohastično programiranje]] se ukvarja s primeri, kjer so nekatere od omejitev ali parametrov odvisne od [[naključno število | naključnih spremenljivk]].
* [[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 |pozitivno definitna]], je točka lokalni minimum, če je negativno definitna, je lokalni maksimum, če pa je nedefinitna, je to sedelna točka.
 
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 | minimizacija z omejenim korakom]]. Oba pristopa pogosto kombiniramo z [[Metoda množice aktivnih omejitev | metodo aktivne množice]].
 
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]]
* [[Optimizacijske metode | Optimizacijske metode]]
* [[Optimizacijski programi | Optimizacijski programi]]
* [[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] &mdash; General Algebraic Modeling System
* [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:最优化]]