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

<{ForumPost(poster="Thomyy", timestamp=2010-01-15 19:43:39)}>
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.
<{/ForumPost}>