písemka z lineárního programování
Písemku vypracovávejte samostatně. Nezapoměňte všude uvádět postupy, může vás to zachránit v případě numerické chyby. Všechna tvrzení je třeba řádně zdůvodnit, věty z přednášky či cvičení však dokazovat nemusíte, vždy pouze uveďte, co a kde používáte.
Příklady mohou být rozdílně složité a proto doporučujeme nejdříve pročíst všechna zadání a začít od těch, které vám budou připadat jednodušší. Hodně štěstí!
Jméno/Přezdívka:
Příklad první
Převeďte následující lineární program do rovnicového tvaru, tj. do tvaru {: alt="\max c^T x'" type="image/"} za podmínek {: alt="Ax'=b" type="image/"},{: alt="x'\ge 0" type="image/"}.
{: alt="\begin{align*} \min \ &x_1 + 2x_5 \ 4x_1 + 5 &\ge 5x_3 + x_4 \ 3x_2 &\le 12 + x_3 + x_4 \ x_5 &= 9 - x_3 \ 4 &\ge 2x_1-x_4-x_6 \ x_1,x_2,x_3 &\ge 0 \ x_4,x_5,x_6 &\in \mathbb{R} \end{align*}" type="image/"}
Příklad druhý
Navrhněte celočíselný lineární program, který vyřeší problém Set Splitting:
Jsou dány podmnožiny {: alt="S_1\ldots,S_m" type="image/"} množiny {: alt="{ 1,\ldots,n }" type="image/"} a váhy {: alt="w_1,\ldots,w_n" type="image/"} prvků {: alt="1,\ldots,n" type="image/"}. Cílem je nalézt množinu {: alt="X \subseteq { 1,\ldots,n }" type="image/"} s co nejmenší váhou, která dělí každou množinu {: alt="S_i" type="image/"} (tedy pro každé {: alt="S_i" type="image/"} platí, že {: alt="X \cap S_i \ne \emptyset" type="image/"} a {: alt="S_i \setminus X \ne \emptyset" type="image/"}). Váha množiny je součet vah jejich prvků.
Příklad třetí
Newyorská radnice se pro zvýšení bezpečnosti rozhodla postavit novou policejní stanici. Za účelem určení vhodné polohy stanice vytipovala radnice {: alt="n" type="image/"} míst, kde je pravděpodobně kriminální aktivita. Místa se nacházejí na souřadnicích {: alt="(x_i,y_i)" type="image/"} pro {: alt="i \in { 1,2,\ldots,n }" type="image/"}.
Vaším úkolem je navrhnout lineární program, který určí umístění stanice minimalizující průměrnou dojezdovou dobu na tato místa. Dojezdová doba je přímo úměrná vzdálenosti bodů v Manhattanské metrice, tj. vzdálenost bodů {: alt="(x_1,y_1)" type="image/"} a {: alt="(x_2,y_2)" type="image/"} je {: alt="|x_1-x_2| + |y_1-y_2|" type="image/"}.
Jak by se změnil lineární program, pokud bychom minimalizovali maximální dojezdovou dobu?{: style="list-style-type:lower-alpha"}
Příklad čtvrtý
Nechť {: alt="X_1,\ldots,X_n \subseteq \mathbb{R}^d" type="image/"} jsou konvexní množiny. Dokažte, že pro libovolné {: alt="\alpha_1,\ldots,\alpha_n \in \mathbb{R}" type="image/"} je množina {: alt="\textstyle{\sum_{i=1}^n \alpha_i X_i}" type="image/"} konvexní, přičemž:
{: alt="\sum_{i=1}^n \alpha_i X_i = \left{ \sum_{i=1}^{n} \alpha_i x_i \colon x_i \in X_i \right}" type="image/"}
Příklad pátý
Máme mnohostěn v {: alt="\mathbb{R}^4" type="image/"} určený jako konvexní obal vrcholů
{: alt="v_1 = (-3,0,0,0), \quad v_2 = (-1,0,0,2), \quad v_3 = (0,2,0,0), \quad v_4 = (1,4,1,0), \quad v_5 = (3,0,0,0), \quad v_6 = (0,2,0,1)" type="image/"}
Pro čtveřici vrcholů {: alt="v_1,v_2,v_3,v_4" type="image/"} spočtěte rovnicový popis {: alt="{ x \in \mathbb{R}^4 \colon c^T x = b }" type="image/"} nadroviny, na které všechny 4 body leží. Rozhodněte také, zda je tato nadrovina sečná, tečná, nebo mimoběžná vůči zadanému mnohostěnu.
Užitečné definice a věty:
D: Množina {: alt="A \subseteq \mathbb{R}^4" type="image/"} je afinní prostor, pokud {: alt="A" type="image/"} je tvaru {: alt="L + v" type="image/"} pro nějaký vektorový prostor {: alt="L \subseteq \mathbb{R}^d" type="image/"} a vektor {: alt="v \in \mathbb{R}^d" type="image/"}. Dimenze afinního prostoru {: alt="A" type="image/"} je rovna dimenzi jeho přidruženého vektorového prostoru {: alt="L" type="image/"}.
D: Konvexní mnohostěn v {: alt="\mathbb{R^d}" type="image/"} je průnik konečně mnoha poloprostorů. Alternativně můžeme říci, že konvexní mnohostěn je množina bodů tvaru {: alt="{ x \in \mathbb{R}^d \colon Ax \le b }" type="image/"} pro nějakou reálnou matici {: alt="A" type="image/"} a reálný vektor {: alt="b" type="image/"}.
D: Dimenze mnohostěnu {: alt="P \subseteq \mathbb{R}^d" type="image/"} je rovna dimenzi nejmenšího afinního prostoru {: alt="A" type="image/"}, který obsahuje celý mnohostěn {: alt="P" type="image/"}.
D: Množina {: alt="K \subseteq \mathbb{R}^d" type="image/"} se nazývá konvexní množinou, pokud {: alt="\forall x,y \in K, \forall t \in [0,1] \colon tx + (1-t)y \in K" type="image/"}. Jinak rečeno, každá úsečka se dvěma konci v {: alt="K" type="image/"} musí mít každý bod obsažený v {: alt="K" type="image/"}.
D: Mějme mnohostěn {: alt="P \subseteq \mathbb{R}^n" type="image/"} a nadrovinu {: alt="h" type="image/"}. Podle průniku s mnohostěnem označujeme nadrovinu {: alt="h" type="image/"} jako
tečnou, pokud celé {: alt="P" type="image/"} leží v jednom z uzavřených poloprostorů určených {: alt="h" type="image/"} a průnik {: alt="P \cap h" type="image/"} je neprázdný,
sečnou, pokud je průnik {: alt="P" type="image/"} s každým z otevřených poloprostorů určených {: alt="h" type="image/"} neprázdný, a nebo
mimoběžnou, pokud {: alt="h" type="image/"} není ani tečná ani sečná.
T: Průnik libovolného počtu uzavřených množin je uzavřená množina. Speciálně mnohostěny a jednotlivé body jsou uzavřené množiny.
T: (Věta o oddělování) Buď {: alt="C \subseteq \mathbb{R}^n" type="image/"} omezená uzavřená konvexní množina a {: alt="D \subseteq \mathbb{R}^n" type="image/"} uzavřená konvexní množina. Pokud {: alt="C \cap D \ne \emptyset" type="image/"}, tak existuje nadrovina {: alt="h \colon c^T x = b" type="image/"} taková, že {: alt="c^T x < b \ \forall x \in C" type="image/"} a {: alt="c^T x > b \ \forall x \in D" type="image/"} (tj. {: alt="h" type="image/"} odděluje {: alt="C" type="image/"} a {: alt="D" type="image/"}).
V příloze jsou ještě nějaké další písemky, na které jsem narazil při učení na zápočtovou písemku.
další testy.zip
Attachments: