Optimalizace (matematika)

Matematická úloha optimalizace je snahou o nalezení takových hodnot proměnných, pro které účelová funkce nabývá minimální nebo maximální hodnoty. Mnoho teoretických úloh i úloh z reálného světa vede na řešení úlohy optimalizace. Často se vyskytuje při modelování fyzikálních jevů, kde cílová funkce $f$ má význam energie fyzikálního systému, která má v rovnovážném stavu systému být minimální. Úloha optimalizace představuje teoretický základ pro operační výzkum.

Definice

Je-li účelová funkce $f:A\to \mathbb {R}$ , pak v úloze minimalizace hledáme takové $x_{0}\in A$ , že $f(x_{0})\leq f(x)$ pro všechna $x\in A$ . V úloze maximalizace naopak hledáme takové $x_{0}\in A$ , že $f(x_{0})\geq f(x)$ pro všechna $x\in A$ .

Nalezený prvek $x_{0}$ je nazýván optimálním řešením, který pro obecnou úlohu optimalizace nemusí být jednoznačný. Množina $A$ se nazývá množinou přípustných řešení. Přípustná množina často bývá podmnožinou vektorového prostoru $\mathbb {R} ^{n}$ , vydělenou omezujícími podmínkami ve formě rovností či nerovností. Optimalizační úlohu někdy pomáhají řešit tzv. podmínky optimality. Úloha optimalizace je někdy nazývána též úlohou matematického programování (tento termín nemá přímý vztah k programování).

Kromě deterministického matematického programování se někdy užívají stochastické (meta)heuristické algoritmy k nalezení dostatečně kvalitního řešení optimalizačních úloh v dostatečně krátkém čase, inspirované přírodou. Tyto algoritmy můžeme popsat jako zkratkovitý postup prohledávání prostoru řešení bez záruky správného výsledku, nicméně jsou zbaveny celé řady neduhů konvenčních optimalizačních metod, jako např. požadavek spojitosti či diferencovatelnosti objektivní resp. vazební funkce, respektování omezujících podmínek, uvíznutí v mělkém lokálním minimu atd. Na druhou stranu však je při jejich aplikaci zapotřebí nastavení jistých volných parametrů, které je nutné „naladit“ v závislosti na konkrétním optimalizačním problému.

Pro řešení optimalizačních problémů lze mj. užít aproximační algoritmus, který na rozdíl od heuristického algoritmu poskytuje záruku na odchylku vypočteného řešení od optimálního řešení, či pravděpodobnostní algoritmus, který na rozdíl od heuristického algoritmu určuje pravděpodobnost optimality řešení.

Matematické programování

Algoritmy matematického programování:

Heuristické algoritmy

Metaheuristické algoritmy

Multiagentní systém
Optimalizace včelím rojem (Bee colony optimization)
Optimalizace mravenčí kolonií (Ant colony optimization)
Optimalizace hejnem světlušek (Glowworm Swarm Optimization)
Optimalizace hejnem částic (Particle swarm optimization)

Odkazy

Literatura

Miroslav Maňas: Optimalizační metody, Státní nakladatelství technické literatury, Praha 1979, 1. vydání.

Související články

Extrém funkce

Externí odkazy

Obrázky, zvuky či videa k tématu optimalizace na Wikimedia Commons
http://www.uai.fme.vutbr.cz/~jdvorak/vyuka/tsoa/tsoa.htm Archivováno 31. 5. 2009 na Wayback Machine.
https://web.archive.org/web/20090131041525/http://home.eunet.cz/berka/o/