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

<{ForumPost(poster="awk", timestamp=2019-04-19 07:43:34)}>
 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|$.
1. 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ť $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



*Attachments:*

- *[další testy.zip](/NOPT048/Z%C3%A1po%C4%8Det%202019-03-27%201.%20p%C3%ADsemka/dal%C5%A1%C3%AD%20testy.zip)*

<{/ForumPost}>