Zadání

Optimalizace: Optimalizační a příliš podmíněné problémy a jejich řešení. Lineární, celočíselné a dynamické programování.

Vypracování

Optimalizační a příliš podmíněné problémy

Optimalizační problém je 6-tice $U = (\Sigma_I, \Sigma_O, L, M, p, t)$ , kde:

$\Sigma_I, \Sigma_O$ je vstupní, resp. výstupní abeceda,
$L \subseteq \Sigma_I^*$ je množina vstupních instancí
$M: L \rightarrow 2^{\Sigma_O^*}$ je funkce, která každé vstupní instanci přiřadí množinu jejich přístupných řešení
$p$ je funkce, která dvojici $(u, x), x \in L, u \in M(x)$ přiřadí reálné číslo $p(u, x)$
$t \in \{max, min\}$

Optimalizační problémy je možné řešit pomocí CSP (constraint satisfactory problem) algoritmů, lineárního (celočíselného), nebo dynamického programování.

Příliš podmíněný problém je CSP problém, pro který řešení neexistuje. Tyto problémy se řeší pomocí stanovení ceny jednotlivých omezení a řešící program se snaží nalézt řešení, které minimalizuje celkovou cenu nesplněných omezení: MAX-CSP, omezení s váhami, fuzzy omezení, semiring-based (polookruhy).

MAX-CSP využívá součet cen nesplněných omezení jako optimalizační kritérium, omezení s váhami převádí cenu na váhu omezení, fuzzy CSP modeluje cenu pomocí fuzzy množin (čísla z intervalu <0, 1> pro vyjádření preference prvků). Polookruhy využívají $c$ -polokruh: $<\mathcal{A}, +, \times, 0, 1>$ :

$\mathcal{A}$ - množina polookruhu (množina preferencí)
$0 \in \mathcal{A}$ - úplné nesplnění
$1 \in \mathcal{A}$ - úplné splnění
$+$ - komutativní, idempotentní, asociativní operace s jednotkovým prvkem $0$ , s absorbujícím prvkem $1$
$\times$ - komutativní, asociativní operace, distributivní nad $+$ , s jednotkovým prvkem $1$ , s absorbujícím prvkem $0$ .

Lineární a celočíselné programování

Vstupem úlohy lineárního programování je lineární funkce (nazývá se taky účelová funkce) a sada lineárních ohraničení na proměnnými $x_1, ..., x_n$ . Cílem je najít takové hodnoty proměnných, které splňují lineární ohraničení a zároveň maximalizují (resp. minimalizují) hodnotu účelové funkce.

Variantou lineárního programování je celočíselné programování, ve kterém požadujeme navíc aby proměnné měli celočíselné hodnoty. Jinou variantou je 0/1-lineární programování, ve kterém můžou proměnné mít hodnoty pouze 0 nebo 1.

Pro řešení úloh lineárního programování nad $\mathbb{R}$ je možné využít nasledovné algoritmy:

simplexový algoritmus - v nejhorším případě má exponenciální složitost, ale v praxi má obvykle dobrý výkon
elipsoidový algoritmus - má polynomiální složitost, v praxi je pomalý kvůli vysokým konstantám
metody vnitřních bodů - pro velké vstupní instance je stejně rychlý nebo rychlejší než simplexový algoritmus

Celočíselné úlohy a 0/1-úlohy jsou NP těžké. Pro polynomiální řešení nad celými čísly se využívají techniky zaokrouhlování (aproximativní algoritmy) nebo schéma primární a duální úlohy (aproximace pomocí přibližování hodnot jejich účelových funkcí).

Schéma primární a duální úlohy obvykle pracuje se standardním tvarem úlohy LP: všechny lineární ohraničení mají tvar nerovnosti a hodnoty proměnných jsou nezáporné. Každá úloha LP se dá převést do standardního tvaru.

Dynamické programování

Dynamické programování je založeno na myšlence že optimální řešení problému obsahuje v sobě optimální řešení podproblémů.

Dynamické programování využívá následovný postup:

rekurzívně definuj hodnotu optimálního řešení
vypočítej hodnotu optimálního řešení zdola-nahoru
z vypočítaných hodnot sestav optimální řešení

Technika je vhodná pro řešení optimalizačních problémů, u kterých dochází k překrývání podproblémů. Dynamické programování „ořezává“ strom prohledávaného stavového prostoru od větví, které nemůžou vést k nalezení optimálního řešení.

Předměty

FI:IA101 Algoritmika pro těžké problémy (podzim 2011), prof. RNDr. Ivana Černá, CSc.

FI:PA163 Programování s omezujícími podmínkami (podzim 2011), doc. Mgr. Hana Rudová, Ph.D.

Použitá literatura

Vypracoval

DevelX - Martin Jurča

stav - 90 %