Nelineární programování

Nelineární program s možným rozsahem a optimem

Jako nelineární programování nebo též nelineární optimalizace se označuje subdisciplína matematického programování, která řeší problém nalezení minima nebo maxima nelineární funkce.

Jejími speciálními typy jsou konvexní programování a kvadratické programování.

Úloha

Úlohou nelineárního programování je následující optimalizační úloha

${\displaystyle \min _{x\in M}f(x),}$

přičemž:

• f (x) je obecně nelineární funkce
• množina přípustných řešení M je popsána soustavou nerovnic

  ${\displaystyle g_{i}(x)\leq 0,\quad i=1,\ldots ,m,}$

  kde g_i (x) jsou reálné funkce.

Metody řešení

Úlohy nelineárního programování dělíme na dva základní typy:

• optimalizace bez vazeb, kdy M = Rⁿ. Používané algoritmy:
  • metoda největšího spádu
  • metoda sdružených gradientů
  • DFP (Davidon-Fletcher-Powell)

• optimalizace s vazbami, kdy M ⊂ Rⁿ. Používané algoritmy:
  • metody přípustných směrů: Zoutendijk, Frank a Wolf, Topkis-Veinott,…
  • Veinottovy opěrné nadroviny
  • penalizační algoritmy
  • bariérové algoritmy

Tyto metody jsou většinou iterační a založeny na následujícím algoritmickém schématu: Sestrojíme nejprve výchozí přípustné řešení (tj. bod z množiny M). Potom se postupně pohybujeme k dalším přípustným bodům, ve kterých je hodnota účelové funkce nižší. Takto pokračujeme, dokud je patrná změna účelové funkce, pokud již patrná není, tak výsledný bod prohlásíme za kandidáta na optimum. Tyto metody konvergují pouze k lokálnímu minimu. Proto je nutné celý proces opakovat s různými volbami výchozích přípustných řešení. Velkou výhodou proto je úloha tzv. konvexního programování, neboť tam je každé lokální minimum zároveň minimem globálním.

Pro řešení se používají také podmínky optimality.

Odkazy

Literatura

• Milan Hamala: Nelineárne programovanie, ALFA, Bratislava 1972, 1. vydání.
• Miroslav Maňas: Optimalizační metody, Státní nakladatelství technické literatury, Praha 1979, 1. vydání.
• Miroslav Maňas: Nelineární programování, Státní pedagogické nakladatelství, Praha 1983, 1. vydání

Související články

• Matematické programování
• Lineární programování

Externí odkazy

• https://web.archive.org/web/20050210045848/http://home.eunet.cz/berka/o/matempr1.htm
• http://www.uai.fme.vutbr.cz/~jdvorak/vyuka/tsoa/tsoa.htm Archivováno 31. 5. 2009 na Wayback Machine.

Portály: Matematika