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

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}$

2. stačí je převést maximum na minumum vztahem $\max f(x)=-\min -f(x)$ s řešit klasicky.