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 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 , pak v úloze minimalizace hledáme takové , že pro všechna . V úloze maximalizace naopak hledáme takové , že pro všechna .
Nalezený prvek je nazýván optimálním řešením, který pro obecnou úlohu optimalizace nemusí být jednoznačný. Množina se nazývá množinou přípustných řešení. Přípustná množina často bývá podmnožinou vektorového prostoru , 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í lineární programování kvadratické programování nelineární programování konvexní programování dynamické programování celočíselné programování parametrické programování vícekriteriální programování infinitní programování semi-infinitní programování semi-definitní programování
Algoritmy matematického programování: metoda větví a mezí horolezecký algoritmus simplexový algoritmus gradientní sestup metoda Lagrangeových multiplikátorů
Heuristické algoritmy zakázané prohledávání hladový algoritmus genetický algoritmus simulované žíhání Hopfieldova neuronová síť
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
http://www.uai.fme.vutbr.cz/~jdvorak/vyuka/tsoa/tsoa.htm https://web.archive.org/web/20090131041525/http://home.eunet.cz/berka/o/
Optimalizace Kategorie:Matematické problémy