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: 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

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

Nejnižší horní mez bude jednička, ne?

Řešíme sup{ x + y } za podmínek x^2 + y^2 < 1 . Tedy součet druhých mocnin souřadnic na kruhu a ten je maximální, pokud |x| = |y|. Tedy:

x = y

Potom platí x^2 + x^2 = 1 Z toho zjistime, ze x musi byt sqrt(1/2)… ale supremum je urceno eukleidovskou metrikou… tedy sqrt(sqrt(1/2)^2 + sqrt(1/2)^2) = 1

Co na to ostatní? Já teda pořádnou definici suprema a infima pro R^n nenašel.

• no, v nějaký starší verzi přednášek od Wernera byla na slidu 3 věta, která tam už teď koukám není: „Uvědomte si, že abychom mohli hovořit o maximu (minimu, supremu, infimu) z X, množina X musí být úplně uspořádaná (jako jsou např. reálná čísla). Je-li např. X z C či X z R^2, nelze o maximu mluvit.“ na základě toho bych řekla, že ten otazník jako výsledek příkladu je tam schválně, protože supremum R^2 neexistuje, respektive nelze ho určit.

Priklady:

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“.

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

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.

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

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

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)

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

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

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

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

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

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

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

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

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

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 z1 +…+ zk, |Ai*x - bi| ⇐ zi, odstranime abs.

min z1+…+zk, Ai*x - bi ⇐ zi, bi - Ai*x ⇐ zi

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

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.

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.

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) — Daniel Milde 2010/01/09 14:52