od Thomyy » 15. 1. 2010 19:43
Ahojte lidi,
Lachout avizoval, že předtermín bude těžší, a podle mě se tak i stalo:
1) Nechť
je konvexní a uzavřená. Nechť
je konvexní. Dokažte, že
je buď prázdná, nebo celý prostor
nebo uzavřený poloprostor.
2) Nechť
je konečná množina. Sestrojte duální úlohu k úloze
za podmínek:
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)
za podmínek:
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
je uzavřená, je
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
za podmínek
kde množina indexů pro
je
pro které existuje
takové, že buď
nebo
4) stačí je převést maximum na minumum vztahem
s řešit klasicky.
Ahojte lidi,
Lachout avizoval, že předtermín bude těžší, a podle mě se tak i stalo:
1) Nechť [latex]C\in\mathbb{R}^n[/latex] je konvexní a uzavřená. Nechť [latex]\mathbb{R}^n\setminus C[/latex] je konvexní. Dokažte, že [latex]C[/latex] je buď prázdná, nebo celý prostor [latex]\mathbb{R}^n[/latex] nebo uzavřený poloprostor.
2) Nechť [latex]\Gamma\in\mathbb{N}^2[/latex] je konečná množina. Sestrojte duální úlohu k úloze
[latex]\min \sum_{(i,j)\in\Gamma} c_{ij}x_{ij}[/latex]
za podmínek:
[latex]\sum_{i:(i,k)\in\Gamma}x_{ik}-\sum_{j:(k,j)\in\Gamma}x_{kj}=0\quad \forall k\in\mathbb{N}[/latex]
[latex]0\leq x_{ij}\leq d_{ij}\quad \forall (i,j)\in\Gamma[/latex]
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)
[latex]\max x_1+2x_2-\frac{1}{2}x_1^2-\frac{1}{2}x_2^2[/latex]
za podmínek:
[latex]x_1+4x_2\leq 5[/latex]
[latex]2x_1+3x_2\leq 6[/latex]
[latex]x_1\leq 0,x_2\in\mathbb{R}[/latex]
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 [latex]C[/latex] je uzavřená, je [latex]C[/latex] 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
[latex]\max \sum_{(i,j)\in\Gamma}d_{ij}y_{ij}[/latex]
za podmínek
[latex]u_i-u_j+y_{ij}\leq c_{ij}\quad (i,j)\in\Gamma[/latex]
[latex]y_{ij}\geq 0, u_k\in\mathbb{R}[/latex]
kde množina indexů pro [latex]u_.[/latex] je [latex]\{k:[/latex]pro které existuje [latex]r\in\mathbb{N}[/latex] takové, že buď [latex](k,r)\in\Gamma[/latex] nebo [latex](r,k)\in\Gamma\}[/latex]
4) stačí je převést maximum na minumum vztahem [latex]\max f(x)=-\min -f(x)[/latex] s řešit klasicky.