Superpočítání pro průmysl www.it4i.cz

Metody optimalizace

Metody optimalizace se zabývají hledáním minima funkcí více proměnných, které jsou všude nebo téměř všude spojité i s některými derivacemi, a to na množině, která je typicky popsána pomocí rovností a nerovností. Optimalizační úlohy vznikají typicky při řešení praktických úloh, když chceme dosáhnout co nejlepšího výsledku v rámci našich možností. Co je nejlepší posuzujeme pomocí cenové funkce či cenového funkcionálu, což je v obecném případě zobrazení definované na množině prvků vhodného vektorového prostoru. Extrémy cenového funkcionálu často hledáme na přípustné množině.

Příkladem takové optimalizační úlohy je třeba problém nalezení rovnovážné polohy kuličky hmotnosti m zavěšené na pružině nad překážkou. Tento problém můžeme vyjádřit jako minimalizaci funkce potenciální energie tohoto systému. Přípustná množina nám popisuje nepronikání kuličky do překážky.

Odkazy na obecně formulované optimalizační úlohy najdeme již v minulosti. Ať už jde o úlohu nalezení pozemku o největší rozloze při daném obvodu (dle mytologie vyřešená princeznou Didó) nebo pozorování učiněné Keplerem při koupi vína. Keplera zajímal tvar sudu, který má při použití daného množství materiálu největší objem. S obdobnými úlohami se setkáváme i v současnosti. Např. jaký tvar má mít článek řetězu, aby byl nejpevnější či jak má vypadat křídlo letadla tak, aby bylo dostatečně pevné a přitom lehké. Některé jednodušší úlohy lze vyřešit analytickými metodami. Pro naprostou většinou optimalizačních úloh je nutné použít numerické metody a to z toho důvodu, že většinu praktických úloh analyticky řešit nelze. Vhodnou numerickou metodu je nutno zvolit dle typu cenové funkce a popisu přípustné množiny.

Lineární algebra

Většinu praktických úloh je výhodné zapsat pomocí nástrojů lineární algebry, například tzv. úlohu lineárního programování. První metody řešení úloh lineárního programování byly navrženy před druhou světovou válkou pro účely plánování. Řešení speciální úlohy lineárního programování, tzv. dopravní úlohy, sehrálo významnou roli při plánování invaze v Normandii.

Úlohy kvadratického programování

V optimalizačních úlohách pocházejících z mechaniky hledáme stav s minimální potenciální energií (rovnovážný stav) nějakého systému. To vede na úlohy tzv. kvadratického programování, tj. úlohy minimalizace kvadratické funkce.

Úlohy s omezením

U řady optimalizačních úloh je navíc kladeno omezení na množinu, ze které vybíráme řešení. Takové omezení nazýváme přípustnou množinou. Vraťme se k úloze hledání rovnovážného stavu kuličky zavěšené nad překážkou. Omezení nám v tomto případě popisuje překážku, kterou kulička nesmí proniknout. Přípustná množina je tedy prostor nad překážkou.

Efektivní implementace

Pro numerické řešení optimalizačních úloh lze využít řady metod. V případě řešení rozsáhlých úloh, které řešíme pomocí výkonného superpočítače, je třeba se pečlivě zaměřit na výběr metody i její implementaci. V takovém případě je rozumné upřednostnit metody, které umožňují paralelizaci řešení úlohy.

Využití

Partneři