Oblast přípustných řešení
V teorii optimalizace je proveditelná doména , proveditelná množina , vyhledávací prostor nebo prostor řešení množina všech možných bodů (hodnot proměnných) optimalizačního problému, které splňují omezení problému. Tato omezení mohou zahrnovat nerovnosti , rovnosti a požadavek, aby řešení bylo celé číslo [1] [2] . Oblast proveditelných řešení je počáteční oblastí hledání kandidátů na řešení problému a tuto oblast lze během vyhledávání zúžit.
Například vzít úkol
Minimalizovat
s omezeními na proměnné a
a
V tomto případě je oblastí proveditelných řešení množina dvojic ( x 1 , x 2 ), pro které hodnota x 1 není menší než 1 a ne větší než 10 a hodnota x 2 není menší než 5 a ne více než 12. Všimněte si, že množina možných řešení je uvažována odděleně od účelové funkce, která určuje kritérium optimalizace a která se ve výše uvedeném příkladu rovná
U mnoha problémů přípustný rozsah řešení zahrnuje omezení, že jedna nebo více proměnných musí být nezáporné. V problémech čistě celočíselného programování se množina možných řešení skládá z celých čísel (nebo nějaké podmnožiny). V problémech lineárního programování je doménou proveditelných řešení konvexní polytop - oblast ve vícerozměrném prostoru, jejíž hranice jsou tvořeny nadrovinami [1] .
Spokojenost s omezením je proces hledání bodu v doméně proveditelných řešení.
Související definice
Při omezení nerovností může být bod buď vnitřní bod (platný bod), hraniční bod (platný bod) nebo vnější bod (neplatný bod). Aktivní neboli závazné omezení je takové, které se v daném bodě změní na rovnost [1] . Některé algoritmy mohou používat pojem aktivního omezení k vytvoření efektivnějšího algoritmu (viz metoda proměnné báze .
Pokud pro úlohu neexistuje platný bod, je úloha považována za neplatnou .
Podmíněné optimum je lokální optimum ležící na hranici přípustné oblasti [1] .
Konvexní doména proveditelných řešení
Konvexní doména proveditelných řešení je množina řešení, ve kterých segment spojující dvě proveditelná řešení obsahuje pouze platné body a neprochází žádným neplatným bodem. Konvexní množina možných řešení vzniká u mnoha typů problémů, včetně problémů lineárního programování, a je zvláště zajímavá, protože pokud je problémem optimalizovat konvexní účelovou funkci , v obecném případě je takový problém snadněji řešitelný na konvexní množina řešení a jakékoli lokální optimum bude také globálním optimem .
Nedostatek přípustných řešení
Pokud jsou omezení optimalizačního problému společně nekonzistentní, neexistuje žádný bod, který by vyhovoval všem omezením, a pak je doména proveditelných řešení prázdná . V tomto případě problém nemá řešení a je prý nepřijatelný [1] .
Ohraničené a neohraničené domény přípustných řešení
Množina přípustných řešení může být omezená nebo neomezená . Například množina proveditelných řešení definovaných omezeními { x ≥ 0, y ≥ 0} je neomezená, protože se lze v některých směrech ubírat donekonečna a přitom zůstat v doméně proveditelných řešení. Naproti tomu množina proveditelných řešení tvořená omezeními { x ≥ 0, y ≥ 0, x + 2 y ≤ 4} je omezená, protože pohyb v libovolném směru je omezený. V úlohách lineárního programování s n proměnnými je nezbytnou, ale ne postačující podmínkou pro ohraničenost oboru proveditelných řešení přítomnost alespoň n + 1 omezení.
Pokud je množina proveditelných řešení neomezená, optimální řešení může nebo nemusí existovat v závislosti na chování účelové funkce. Pokud je například množina definována omezeními { x ≥ 0, y ≥ 0}, pak optimalizační problém x + y nemá řešení, protože kteréhokoli kandidáta lze zlepšit zvýšením x nebo y , ale minimalizace x + y problém má optimální řešení (a totiž v bodě ( x , y ) = (0, 0)).