courses:a4b33opt:poazadavky_ke_zkousce [OI-Wiki]

Tato stránka je pouze pro čtení. Můžete si pouze prohlédnout zdrojový kód, ale ne ho měnit. Zeptejte se správce, pokud si myslíte, že něco není v pořádku.
====== Požadavky ke zkoušce z A4B33OPT ======

  * Co zkusit společnými silami vypracovat některé otázky z materiálů ke zkoušce.
  * Seznam s otázkami a okruhy ke zkoušce zde: [[http://cw.felk.cvut.cz/lib/exe/fetch.php/courses/a4b33opt/zkouska-pozadavky.pdf?id=courses%3Aa4b33opt%3Astart&cache=cache|Požadavky ke zkoušce]]

__Hodí se:__
  * http://www.vscht.cz/mat/sbirka/KapitolaII6.pdf - sbírka příkladů (i s podrobným řešením) k analýze funkcí více proměnných
  * http://math.feld.cvut.cz/prucha/m3bc/3tru.pdf - příklady na tečné roviny
===== Základy =====

4. sup{ x + y | (x, y) ∈ R2 , x^2 + y^2 < 1 } = sqrt(2)

  * Nemela by byt nejnizsi horni mez, tedy supremum v tomto pripade 1? Je to rovnice neohraniceneho kruhu s polomerem 1, cili sup = 1 mi prijde logictejsi...
  * Myslim, ze ne. Resime sup{ x + y } za podminek x^2 + y^2 < 1. Tedy soucet souradnic na kruhu a ten je maximalni pokud x = y ; x > 0 (I. kvadrant). Z podminky pak:
    
    x^2 + x^2 = 1
    x = sqrt(1 / 2) = sqrt(2) / 2
    f(x, y) = x + y = sqrt(2) / 2 + sqrt(2) / 2 = sqrt(2) = sup{ f(x,y) }
 

===== Převody různých forem LP na sebe =====

Priklady:\\

==== 1. ====
min c*x, A*x >= b převedeme na rovnost přidáním skluzové proměnné.

min c*x, A1*x + ... + Ak*x + z = b, z >= 0 přicemž "z" je vektor velikosti stejné jako "x".

<code>
Podle me je to A*x - z = b, z >= 0.
</code>

Může to být oboje - musíme totiž navíc specifikovat, jakých hodnot mohou nabývat ty skluzové proměnné. Pokud připustíme, že z může být menší než 0, tak platí i první případ. Pokud budeme požadovat z nezáporné, tak platí ten druhý způsob.

==== 2. ====
min max(ck*x + dk), A*x >= b, nahradíme minimalizací skluz. prom.

min z, ck*x + dk <= z, A*x >= b

==== 3. ====
min sum(|ck*x + dk|), A*x >= b, převedeme na  minimalizaci skluzové prom.

min z, A*x >= b, sum(|ck*x + dk|) <= z, následně "z" parametrizujeme

min z1+z2+...+zn, A*x >= b, |ck*x + dk| <= zk, odstraníme absolutní hodnotu

min z1+z2+...+zn, A*x >= b, ck*x + dk <= zk, -ck*x - dk <= zk (k=1...n)

==== 4. ====
min c*x, max(dk*x + ek) <= f, A*x >= b, pokud ma byt max. prvek mnoziny mensi nez f, musi byt vsechny mensi nez f

min c*x, dk*x + ek <= f, A*x >= b

==== 5. ====
min c*x, min(dk*x + ek) >= f, A*x >= b, pokud ma byt min. prvek mnoziny vetsi nez f, musi byt vsechny vetsi nez f

min c*x, dk*x + ek >= f, A*x >= b

==== 6. ====
min sum(max(ckl*x + dkl)), A*x >= b, převedeme na minimalizaci skluz. prom.

min z, sum(max(ckl*x + dkl)) <= z, A*x >= b, parametrizujeme "z"

min z1+...+zn, max(ckl*x + dkl) <= zl, pokud max. mensi nez "zl", pak vsechny mensi

min z1+...+zn, ckl*x + dkl <= zl

==== 7. ====
min |c*x|, A*x >=b, prevedem na min. skluz. prom.

min z, |c*x| <= z, A*x >= b, odstraníme abs. hodnotu (|x| = max(x, -x); pokud max(x, -x) <= z, pak x i -x musi byt <= z)

min z, c*x <= z, -c*x <= z, A*x >= b

==== 8. ====
min c*x, |d*x + e| <= f, A*x >= b, odstranime abs. stejne jako vyse (zde detailneji)

min c*x, max(d*x+e, -d*x-e) <= f, A*x >= b, pokud max. prvek mensi nez f, pak vsechny mensi nez f

min c*x, d*x + e <= f, -d*x - e <= f, A*x >= b

==== 9. ====
min f(x), A*x >= b, f(x) lze prevest na max ze tri funkci

min max(-x-2, 0, 1/2*x-1), A*x >= b, prevedeme na min. skluz. prom.

min z, max(-x-2, 0, 1/2*x-1) <= z, A*x >= b

min z, -x - 2 <= z, 0 <= z, 1/2*x - 1 <= z, A*x >= b

==== 10. ====
min ||Ax - b|| (norma 1) = min |A1*x - b1| + |A2*x - b2| +...+|Ak*x - bk|

min sum(|Ai*x - bi|), prevedeme na min. skluz. prom.

min z, sum(|Ai*x - bi|) <= z, parametrizujeme z

min x1 +...+ zk, |Ai*x - bi| <= zi, odstranime abs.

min x1+...+zk, Ai*x - bi <= zi, bi - Ai*x <= zi


==== 11. ====
min||Ax - b|| (norma nekonecno) = min max |Ai*x - bi|, nahradime min. skluz. prom.

min z, max(|Ai*x - bi|) <= z, kdyz max mensi, tak vsechny mensi

min z, |Ai*x - bi| <= z, odstrnanime abs.

min z, Ai*x - bi <= z, bi - Ai*x <= z

==== 12. ====
Lze minimalizovat min min(ck*x + dk), A*x >= b?

Nelze. Minimum z nekolika polynomu je konkavni fce. U konkavni fce minimum pomoci LP nenajdeme.


==== 13. ====
Jde prevest max |c*x|, A*x >= b na LP? Ne. Na LP to nelze prevest, protoze vznikne problem max max. Pokud si vzpomenete, na ilustraci pridane promenne (z) jakozto klandru pod ostatnimi promennymi, tak je zrejme, ze by odletel do nekonecna.

Prevodem by vzniklo:

max z, c*x >= z, -c*x >= z, A*x >= b

Tlacime tedy odspodu klandr "z" tak, aby byl mensi roven podminkam (cili pohybujeme se po puvodni kriterialni funkci). Jelikoz ale podminky omezujici "z" vytvareji konvexni funkci a "z" se snazime maximalizovat, utece nam "z" nahoru do nekonecna.

==== 14. ====
Jde prevest min c*x, |d*x + e| >= f, A*x >= b na LP? Nejde.

 |d*x + e| = max(d*x + e, -d*x - e)

Ze max. prvek je vetsi nez f ale nezmamena, ze vsechny prvky jsou vetsi nez f, a proto nemuzeme prevest na dve nerovnice.

**Prosím o kontrolu všech příkladů. U některých si nejsem správností jistý (např. u 13)** --- //[[milded1@fel.cvut.cz|Daniel Milde]] 2010/01/09 14:52//






~~DISCUSSION~~
courses/a4b33opt/poazadavky_ke_zkousce.1263630176.txt.gz · Poslední úprava: 2025/01/03 18:24 (upraveno mimo DokuWiki)
Nahoru