Problém s optimalizací - Optimization problem

v matematika, počítačová věda a ekonomika, an optimalizační problém je problém hledání nejlepší řešení ze všech proveditelná řešení.

Problémy s optimalizací lze rozdělit do dvou kategorií podle toho, zda proměnné jsou kontinuální nebo oddělený:

Optimalizační problém s diskrétními proměnnými je znám jako a diskrétní optimalizace, ve kterém objekt jako je celé číslo, permutace nebo graf musí být nalezen z spočetná sada.
Problém se spojitými proměnnými se označuje jako a průběžná optimalizace, ve kterém je optimální hodnota z a spojitá funkce musí být nalezen. Mohou zahrnovat omezené problémy a multimodální problémy.

Problém s průběžnou optimalizací

The standardní forma a kontinuální optimalizační problém je^[1]

{ displaystyle { begin {aligned} & { underset {x} { operatorname {minimalizovat}}} && f (x) & operatorname {subject ; to} && g_ {i} (x) leq 0, quad i = 1, dots, m &&& h_ {j} (x) = 0, quad j = 1, dots, p end {zarovnáno}}}

kde

$F : ℝ n \to ℝ$ je Objektivní funkce být minimalizován přes $n$ -variační vektor $X$ ,
$G i (X) \leq 0$ jsou nazývány nerovnost omezení
$h j (X) = 0$ jsou nazývány omezení rovnosti, a
$m \geq 0$ a $p \geq 0$ .

Li $m = p = 0$ , problém je neomezený optimalizační problém. Podle konvence standardní formulář definuje a problém s minimalizací. A problém s maximalizací lze léčit negovat objektivní funkce.

Problém kombinatorické optimalizace

Formálně, a kombinatorická optimalizace problém $A$ je čtyřnásobek^{[Citace je zapotřebí ]} $(Já, F, m, G)$ , kde

$Já$ je soubor případů;
daný případ $X \in Já$ , $F (X)$ je soubor proveditelných řešení;
daný případ $X$ a proveditelné řešení $y$ z $X$ , $m (X, y)$ označuje opatření z $y$ , což je obvykle a pozitivní nemovitý.
$G$ je branková funkce a je $min$ nebo $max$ .

Cílem je pak pro nějaký případ najít $X$ an optimální řešení, tj. proveditelné řešení $y$ s

{ displaystyle m (x, y) = g { bigl {} m (x, y ') střední y' ve f (x) { bigr }}.}

Pro každý problém kombinatorické optimalizace existuje odpovídající rozhodovací problém to se ptá, zda existuje proveditelné řešení pro určité konkrétní opatření $m 0$ . Například pokud existuje graf $G$ který obsahuje vrcholy $u$ a $proti$ , optimalizačním problémem může být „najít cestu z $u$ na $proti$ který používá nejmenší počet hran ". Tento problém může mít odpověď, řekněme, 4. Odpovídající rozhodovací problém by byl" existuje cesta z $u$ na $proti$ který používá 10 nebo méně hran? “Na tento problém lze odpovědět jednoduchým„ ano “nebo„ ne “.

V oblasti aproximační algoritmy, jsou algoritmy navrženy tak, aby nacházely téměř optimální řešení těžkých problémů. Obvyklá rozhodovací verze je pak neadekvátní definicí problému, protože specifikuje pouze přijatelná řešení. I když bychom mohli zavést vhodné rozhodovací problémy, problém je přirozenější charakterizován jako optimalizační problém.^[2]

Viz také

Problém počítání (složitost)
Optimalizace designu
Funkční problém
Problém s rukavicemi
Operační výzkum
Spokojený: nemusí být nalezeno optimální řešení, pouze „dost dobré“ řešení.
Problém s vyhledáváním
Polo nekonečné programování

Reference

^ Boyd, Stephen P .; Vandenberghe, Lieven (2004). Konvexní optimalizace (pdf). Cambridge University Press. str. 129. ISBN 978-0-521-83378-3.
^ Ausiello, Giorgio; et al. (2003), Složitost a aproximace (Opraveno) Springer, ISBN 978-3-540-65431-5

externí odkazy

„Jak Traffic Shaping optimalizuje šířku pásma sítě“. IPC. 12. července 2016. Citováno 13. února 2017.

[1] Boyd, Stephen P .; Vandenberghe, Lieven (2004). Konvexní optimalizace (pdf). Cambridge University Press. str. 129. ISBN 978-0-521-83378-3.

[Ausiello03-2] Ausiello, Giorgio; et al. (2003), Složitost a aproximace (Opraveno) Springer, ISBN 978-3-540-65431-5

[1]

[2]