Přeskočit na obsah

Optimalizace (matematika)

Z Wikipedie, otevřené encyklopedie

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.

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í

[editovat | editovat zdroj]

Algoritmy matematického programování:

Heuristické algoritmy

[editovat | editovat zdroj]

Metaheuristické algoritmy

[editovat | editovat zdroj]

Literatura

[editovat | editovat zdroj]
  • Miroslav Maňas: Optimalizační metody, Státní nakladatelství technické literatury, Praha 1979, 1. vydání.

Související články

[editovat | editovat zdroj]

Externí odkazy

[editovat | editovat zdroj]