Skúška 31.1.2012

Príklad 1: Nech $\mathrm{C}\subset \mathrm{R}^{n}$ je uzavretá a konvexná, $\mathrm{R}^{n}\setminus \mathrm{C}$ je konvexná. Dokážte, že potom buď $\mathrm{C}$ je prázdna množina alebo uzavretý priestor alebo celý priestor $\mathrm{R}^{n}$.

Príklad 2: Určiť duálnu úlohu k úlohe LP
$$\begin{align} \textrm{min} \sum_{i=1}^{n} \sum_{j=1}^{m}i^2x_{ij} otag \\ \textrm{za podmienok} \quad \sum_{j=1}^{m} x_{ij} \leq \textrm{b}_{i}, \quad \forall i=1,...,n otag \\ \sum_{j=1}^{m} \sum_{i=1}^{n} x_{ij}= 1 otag \\ x_{ij} \geq 0,\quad i=1,...,n,\quad j=1,...,m otag \\ \textrm{parametre spĺňajú} \quad \sum_{i=1}^{n} b_{i} \geq 1,\quad b_{i} \geq 0,\quad \forall i=1,...,n otag \end{align}$$

Príklad 3: Uvažujme maticovú hru s výplatnou maticou

$$\left( {\begin{array}{ccc} 1 & 1 & 0 \\ 4 & 5 & 0 \\ 1 & 0 & 2 \\ 0 & 4 & -1 \end{array} } \right)$$

Určite cenu tejto hry a optimálne stratégie oboch hráčov.

Príklad 4: Vyriešením (LPO) nájsť optimálne riešenie úlohy
$$\begin{align} \textrm{min} \quad x+y otag \\ \textrm{za podmienok} \quad \frac{1}{x^{2}} + \frac{1}{y^{2}} \leq \frac{1}{a^{2}} otag \\ x \geq \epsilon, \quad x \geq \epsilon, \quad > 0, \quad \epsilon > 0 otag \end{align}$$

"Návod" k riešeniu:

1. Nezabudnúť prediskutovať prípady, keď je C prázdna alebo celý prostor, inak môžeme obe množiny neostro oddeliť.

2. Štandartný príklad, do duálnej úlohy nepísať omezenia na parametre, nemá to zmysel.

3. $\hat{x}=\left(0,\frac{2}{7},\frac{5}{7},0\right)^{T},\quad \hat{y}=\left(0,\frac{2}{7},\frac{5}{7}\right)^{T},\quad v=\frac{10}{7}$

4. Učelová funkcia je lineárna, množina prípustných riešení je konvexná, teda vyriešením LPO dostane optimálne riešenie úlohy. Pri riešení treba diskutovať vzťah $\epsilon$ a $\sqrt{2}a$, z toho dostaneme optimálne riešenie.

PS: Ak by niekto vedel, ako odstrániť to <br/>, tak mi, prosím, napíšte :)