Optimalizační metody 27.3.2019 1. záp. písemka

Uživatelský avatar
awk
Matfyz(ák|ačka) level II
Příspěvky: 56
Registrován: 21. 5. 2018 18:54
Typ studia: Informatika Bc.

Optimalizační metody 27.3.2019 1. záp. písemka

Příspěvek od awk »

1. 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 \max c^T x' za podmínek Ax'=b,x'\ge 0.
\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*}

Příklad druhý
Navrhněte celočíselný lineární program, který vyřeší problém Set Splitting:
Jsou dány podmnožiny S_1\ldots,S_m množiny \{ 1,\ldots,n \} a váhy w_1,\ldots,w_n prvků 1,\ldots,n. Cílem je nalézt množinu X \subseteq \{ 1,\ldots,n \} s co nejmenší váhou, která dělí každou množinu S_i (tedy pro každé S_i platí, že X \cap S_i \ne \emptyset a S_i \setminus X \ne \emptyset). 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 n míst, kde je pravděpodobně kriminální aktivita. Místa se nacházejí na souřadnicích (x_i,y_i) pro i \in \{ 1,2,\ldots,n \}.
  1. 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ů (x_1,y_1) a (x_2,y_2) je |x_1-x_2| + |y_1-y_2|.
  2. Jak by se změnil lineární program, pokud bychom minimalizovali maximální dojezdovou dobu?
Příklad čtvrtý
Nechť X_1,\ldots,X_n \subseteq \mathbb{R}^d jsou konvexní množiny. Dokažte, že pro libovolné \alpha_1,\ldots,\alpha_n \in \mathbb{R} je množina \textstyle{\sum_{i=1}^n \alpha_i X_i} konvexní, přičemž:
\sum_{i=1}^n \alpha_i X_i = \left\{ \sum_{i=1}^{n} \alpha_i x_i \colon x_i \in X_i \right\}

Příklad pátý
Máme mnohostěn v \mathbb{R}^4 určený jako konvexní obal vrcholů
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)
Pro čtveřici vrcholů v_1,v_2,v_3,v_4 spočtěte rovnicový popis \{ x \in \mathbb{R}^4 \colon c^T x = b \} 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 A \subseteq \mathbb{R}^4 je afinní prostor, pokud A je tvaru L + v pro nějaký vektorový prostor L \subseteq \mathbb{R}^d a vektor v \in \mathbb{R}^d. Dimenze afinního prostoru A je rovna dimenzi jeho přidruženého vektorového prostoru L.

D: Konvexní mnohostěn v \mathbb{R^d} je průnik konečně mnoha poloprostorů. Alternativně můžeme říci, že konvexní mnohostěn je množina bodů tvaru \{ x \in \mathbb{R}^d \colon Ax \le b \} pro nějakou reálnou matici A a reálný vektor b.

D: Dimenze mnohostěnu P \subseteq \mathbb{R}^d je rovna dimenzi nejmenšího afinního prostoru A, který obsahuje celý mnohostěn P.

D: Množina K \subseteq \mathbb{R}^d se nazývá konvexní množinou, pokud \forall x,y \in K, \forall t \in [0,1] \colon tx + (1-t)y \in K. Jinak rečeno, každá úsečka se dvěma konci v K musí mít každý bod obsažený v K.

D: Mějme mnohostěn P \subseteq \mathbb{R}^n a nadrovinu h. Podle průniku s mnohostěnem označujeme nadrovinu h jako
  • tečnou, pokud celé P leží v jednom z uzavřených poloprostorů určených h a průnik P \cap h je neprázdný,
  • sečnou, pokud je průnik P s každým z otevřených poloprostorů určených h neprázdný, a nebo
  • mimoběžnou, pokud h 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ď C \subseteq \mathbb{R}^n omezená uzavřená konvexní množina a D \subseteq \mathbb{R}^n uzavřená konvexní množina. Pokud C \cap D \ne \emptyset, tak existuje nadrovina h \colon c^T x = b taková, že c^T x < b \ \forall x \in C a c^T x > b \ \forall x \in D (tj. h odděluje C a D).
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
(801.83 KiB) Staženo 189 x
Odpovědět

Zpět na „Ostatní“