Zkouška 15.1. 2010 (předtermín)

Thomyy
Matfyz(ák|ačka) level I
Příspěvky: 9
Registrován: 23. 12. 2006 22:41
Typ studia: Matematika Bc.
Kontaktovat uživatele:

Zkouška 15.1. 2010 (předtermín)

Příspěvek od Thomyy »

Ahojte lidi,

Lachout avizoval, že předtermín bude těžší, a podle mě se tak i stalo:

1) Nechť C\in\mathbb{R}^n je konvexní a uzavřená. Nechť \mathbb{R}^n\setminus C je konvexní. Dokažte, že C je buď prázdná, nebo celý prostor \mathbb{R}^n nebo uzavřený poloprostor.

2) Nechť \Gamma\in\mathbb{N}^2 je konečná množina. Sestrojte duální úlohu k úloze
\min \sum_{(i,j)\in\Gamma} c_{ij}x_{ij}
za podmínek:
\sum_{i:(i,k)\in\Gamma}x_{ik}-\sum_{j:(k,j)\in\Gamma}x_{kj}=0\quad \forall k\in\mathbb{N}
0\leq x_{ij}\leq d_{ij}\quad \forall (i,j)\in\Gamma

3) byla klasická úloha na lineární progamování, které se řešilo graficky přes duální úlohu a pomocí komplementarity se dopočetlo primární řešení. Zadání si nepamatuju.
4) Rešte pomocí podmínek (LPO) optimální řešení úlohy (chtěl i vysvětlení, proč to, co jsme spočítali je globální nebo lokální maximum)
\max x_1+2x_2-\frac{1}{2}x_1^2-\frac{1}{2}x_2^2
za podmínek:
x_1+4x_2\leq 5
2x_1+3x_2\leq 6
x_1\leq 0,x_2\in\mathbb{R}


Hint:
1) Stačí tyto dvě množiny oddělit nadrovinou a jelikož dohromady ty dvě množiny dávají celý prostor, musí každý být poloprostor (které odděluje ta nadrovina). A protože C je uzavřená, je C uzavřený poloprostor.
2)Přes tabulku to skoro není možný, ale když se jí člověk snaží nějak vymyslet, tak dostane aspoň pár bodů. Výsledek je
\max \sum_{(i,j)\in\Gamma}d_{ij}y_{ij}
za podmínek
u_i-u_j+y_{ij}\leq c_{ij}\quad (i,j)\in\Gamma
y_{ij}\geq 0, u_k\in\mathbb{R}
kde množina indexů pro u_. je \{k:pro které existuje r\in\mathbb{N} takové, že buď (k,r)\in\Gamma nebo (r,k)\in\Gamma\}
4) stačí je převést maximum na minumum vztahem \max f(x)=-\min -f(x) s řešit klasicky.
Veni, vidi, a někdy možná vici :-P
Odpovědět

Zpět na „Optimalizace“