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

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