Optimální řešení (optimalizace)

Optimální řešení — v operačním výzkumu, optimalizaci a teorii rozhodování je to takové přípustné řešení (tj. splňující všechna omezení úlohy), které zajišťuje extremální (maximální nebo minimální, v závislosti na formulaci úlohy) hodnotu účelové funkce.

Hledání optimálního řešení je hlavním cílem řešení většiny optimalizačních úloh.

Podstata a charakteristiky

Optimální řešení má dvě klíčové charakteristiky:

1. Přípustnost: Musí splňovat všechna omezení uložená na proměnné modelu. Jinými slovy, optimální řešení vždy náleží do oblasti přípustných řešení (OPŘ). 2. Extremálnost vzhledem k účelové funkci: Ze všech přípustných řešení zajišťuje nejlepší (maximální nebo minimální) hodnotu účelové funkce, která formalizuje kritérium optimality.

Ne každé přípustné řešení je optimální, ale každé optimální řešení musí být nutně přípustné.

Vztah k oblasti přípustných řešení

Oblast přípustných řešení (OPŘ) představuje množinu všech alternativ (souborů hodnot proměnných), které splňují omezení úlohy. Optimální řešení je bod (nebo body) v této oblasti, kde účelová funkce dosahuje svého extrému. Je-li OPŘ prázdná, úloha nemá žádná přípustná, a tedy ani optimální řešení.

Role účelové funkce a omezení

• Omezení určují množinu možných řešení (OPŘ).
• Účelová funkce určuje, které z těchto možných řešení je nejlepší (optimální).

Bez účelové funkce nelze určit, které z přípustných řešení je optimální. Bez omezení může být úloha triviální nebo nemusí mít konečné optimální řešení (například maximalizace lineární funkce bez omezení).

Jednoznačnost optimálního řešení

Optimální řešení není vždy jediné. V některých úlohách (například v lineárním programování, je-li účelová funkce rovnoběžná s jedním z aktivních omezení) může existovat nekonečně mnoho optimálních řešení se stejnou hodnotou účelové funkce. Hodnota účelové funkce v bodě (bodech) optima je však vždy jedinečná (existuje-li optimum).

Metody hledání

Pro hledání optimálních řešení v operačním výzkumu se používají různé matematické metody v závislosti na typu modelu:

• Simplexová metoda (pro lineární programování)
• Metody gradientního sestupu a další numerické metody (pro nelineární programování)
• Metoda větví a mezí, metody řezů (pro celočíselné programování)
• Metody dynamického programování

Závislost na modelu

Je důležité chápat, že řešení je optimální pouze v rámci přijatého matematického modelu. Pokud model nedostatečně odráží reálnou situaci (nesprávně zvolená účelová funkce, nezohledněná důležitá omezení nebo závislosti), může formálně nalezené optimální řešení být v praxi neefektivní nebo dokonce chybné.

Optimalita ve vícekriteríálních úlohách

V úlohách s více účelovými funkcemi (vícekriteríální optimalizace) je pojem jediného optimálního řešení často nahrazen pojmem Pareto-optimality. Pareto-optimální řešení je takové přípustné řešení, u něhož nelze zlepšit hodnotu jedné účelové funkce, aniž by se zhoršila hodnota alespoň jedné jiné.

Literatura

• Ventcel E. S. Issledovanije operacij: zadači, principy, metodologija. — M.: Nauka, 1988.
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)

Viz také

• Operační výzkum
• Optimalizace
• Matematický model
• Účelová funkce
• Omezení
• Oblast přípustných řešení
• Přípustné řešení
• Kritérium
• Teorie rozhodování
• Vícekriteríální optimalizace
• Pareto-optimalita
• Extrém