Oblast přípustných řešení

Oblast přípustných řešení (OPŘ) (také množina přípustných řešení, angl. Feasible region, feasible set) — v operačním výzkumu, optimalizaci a matematickém modelování je to množina všech možných řešení (souborů hodnot proměnných), která splňují všechna omezení uložená na úlohu.

OPŘ představuje podprostor, ve kterém se hledá optimální řešení. Jakékoli řešení ležící mimo tuto oblast je nepřípustné.

Definice a formování

Oblast přípustných řešení se formuje jako průnik množin definovaných každým jednotlivým omezením úlohy. Omezení mohou být vyjádřena ve formě:

• Nerovností: Stanovují horní nebo dolní hranice pro hodnoty proměnných nebo jejich kombinací (například „spotřeba zdroje A nesmí překročit 100 jednotek", „množství vyrobené produkce musí být nejméně 50 kusů").
• Rovností: Vyžadují přesné splnění podmínky (například „celkový objem přepravy musí být roven 1000 tunám", „bilance vstupních a výstupních toků je rovna nule").
• Podmínek na znaménko proměnných: Proměnné musí být často nezáporné, celočíselné nebo náležet určité diskrétní množině.

Bod (nebo vektor hodnot proměnných) náleží OPŘ tehdy a jen tehdy, pokud současně splňuje všechna tato omezení.

Geometrická interpretace

OPŘ má často názornou geometrickou interpretaci, zejména v úlohách s malým počtem proměnných:

• V dvourozměrném prostoru (2 proměnné): Každé lineární omezení-nerovnost definuje polorovinu. OPŘ představuje průnik těchto polorovin — konvexní mnohoúhelník (případně neomezený nebo prázdný).
• V trojrozměrném prostoru (3 proměnné): Každé lineární omezení-nerovnost definuje poloprostor. OPŘ je průnikem těchto poloprostorů — konvexním mnohostěnem (polyedrem).
• Ve vícerozměrném prostoru: OPŘ definovaná lineárními omezeními je konvexní mnohostěn (polytop).

V případě nelineárních omezení může mít OPŘ složitější tvar a nemusí být konvexní.

Role v optimalizaci

Oblast přípustných řešení hraje zásadní roli v optimalizaci:

1. Definice prostoru hledání: Optimální řešení úlohy (pokud existuje) se vždy nachází uvnitř OPŘ nebo na její hranici. Optimalizační algoritmy hledají extrém účelové funkce právě v této oblasti. 2. Ověření existence řešení: Pokud je OPŘ prázdná množina (tj. omezení si navzájem odporují), pak úloha nemá přípustná řešení, a tedy ani optimální řešení. 3. Vliv na optimální řešení: Tvar a velikost OPŘ přímo ovlivňují možnost dosažení extrému účelové funkce a hodnotu tohoto extrému.

Vlastnosti OPŘ (v úlohách lineárního programování)

V úlohách lineárního programování (LP), kde jsou všechna omezení i účelová funkce lineární, má OPŘ důležité vlastnosti:

• Konvexita: Patří-li dva body do OPŘ, pak celá úsečka spojující tyto body také náleží do OPŘ. Tato vlastnost zaručuje, že optimální řešení (pokud existuje a je jedinečné) bude ležet v jednom z vrcholů mnohostěnu OPŘ.
• Uzavřenost: OPŘ zahrnuje své hranice (z důvodu neostrých nerovností ≤, ≥ a rovností).

OPŘ může být:

• Omezená: Má konečné rozměry.
• Neomezená: Sahá do nekonečna v jednom nebo více směrech.
• Prázdná: Neobsahuje ani jeden bod.

Literatura

• Ventcell E. S. Operační výzkum: úlohy, principy, metodologie. — M.: Nauka, 1988.
• Ackoff R., Sasieni M. Základy operačního výzkumu. — M.: Mir, 1971.
• 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
• Omezení
• Přípustné řešení
• Optimální řešení
• Účelová funkce
• Lineární programování
• Konvexní množina