OR 2019 Quiz Teil B

1. Seien $x_1,\ldots,x_N\in\mathbb{R}^n$ und sei $y=\sum_{i=1}^N \alpha_i x_i$. Unter welchen der folgenden Bedingungen ist $y$ eine Konvexkombination der $x_i$?

(a) $\sum_{i=1}^N\alpha_i=1$ und $\alpha_i\geq 0$ für alle $i=1,\ldots,N$

(b) $\sum_{i=1}^N\alpha_i=1$

(c) $\alpha_i\geq 0$ für alle $i=1,\ldots,N$

(d) $\alpha_i\in [0,1]$ für alle $i=1,\ldots,N$

(e) $\alpha_i = 1/N$ für alle $i=1,\ldots,N$

(f) $\binom{1}{y}=\binom{1 \cdots 1}{x_1 \cdots x_N}\alpha$ mit $\alpha=(\alpha_1,\ldots,\alpha_N)^T\geq 0$

(g) $\alpha_i= 0$ für alle $i=1,\ldots,N$

2. Welche der folgenden Mengen sind konvex?

(a) $\Big\{x\in\mathbb{R}^2 : \begin{pmatrix}1&1\\0&0\end{pmatrix}x=\begin{pmatrix}5\\1\end{pmatrix}\Big\}$

(b) $B(0,1) \setminus \{e_1\} \subseteq \mathbb{R}^n$

(c) $B(0,1) \setminus \{0\}\subseteq \mathbb{R}^n$

(d) $\operatorname{conv}\{1,2,3\}\subseteq \mathbb{R}$

(e) $\{(x,y)\in \mathbb{R}^2 : y\geq x^3\}$

3. Welche der folgenden Funktionen sind konvex?

4. Gegeben sei die Menge $A=\operatorname{conv}\left\{\begin{pmatrix}0\\1\\-1\end{pmatrix},\begin{pmatrix}-1\\0\\1\end{pmatrix},\begin{pmatrix}0\\-1\\1\end{pmatrix},\begin{pmatrix}1\\0\\-1\end{pmatrix}\right\}\subseteq \mathbb{R}^3$.

Was ist $\operatorname{dim}(A)$?

5. Welche der folgenden Aussagen sind wahr?

(a) Sei $C\subseteq \mathbb{R}^n$ konvex, abgeschlossen und nicht leer. Falls $z\not\in C$, dann gibt es eine strikte Trennhyperebene von $\{z\}$ und $C$.

(b) Sei $C\subseteq \mathbb{R}^n$ abgeschlossen und nicht leer. Falls $z\not\in C$, dann gibt es eine Trennhyperebene von $\{z\}$ und $C$.

(c) Sei $C\subseteq \mathbb{R}^n$ konvex und nicht leer. Falls $z\not\in C$, dann gibt es eine Trennhyperebene von $\{z\}$ und $C$.

(d) Sei $C\subseteq \mathbb{R}^n$ konvex und nicht leer. Falls $z\not\in C$, dann gibt es eine strikte Trennhyperebene von $\{z\}$ und $C$.

6. Für welche der folgenden Mengen $P$ gilt $P=\operatorname{conv}(\operatorname{ext}(P))$?

7. Wieviele Ecken hat das Polyeder $P=\{x\in\mathbb{R}^3 : Ax\leq b\}$, wobei

$$ A=\begin{pmatrix} -1&0&0\\0&-1&0\\0&0&-1\\1&0&0\end{pmatrix},b=\begin{pmatrix}0\\0\\0\\5\end{pmatrix}$$

8. Seien $A\in\mathbb{R}^{m\times n}$ und $b\in\mathbb{R}^m$ gegeben.

Welche der folgenden Aussagen sind wahr?

(a) Es gibt einen Vektor $x\in\mathbb{R}^n$ mit $x\geq 0$ und $Ax=b$ genau dann, wenn es keinen Vektor $y\in\mathbb{R}^m$ gibt, der $A^Ty\geq 0$ und $b^Ty<0$ erfüllt.

(b) Es gibt einen Vektor $x\in\mathbb{R}^n$ mit $Ax\leq b$ genau dann, wenn es keinen Vektor $y\in\mathbb{R}^m$ gibt, der $y\geq 0$,  $A^Ty= 0$ und $b^Ty= 2019$ erfüllt.

(c) Es gibt einen Vektor $x\in\mathbb{R}^n$ mit $Ax\leq b$ genau dann, wenn es keinen Vektor $y\in\mathbb{R}^m$ gibt, der $y\geq 0$,  $A^Ty= 0$ und $b^Ty= -2019$ erfüllt.

9. Seien $c\in\mathbb{R}^n$, $A\in\mathbb{R}^{m\times n}$ und $b\in\mathbb{R}^m$ gegeben. Sei
$$p^*=\sup\{c^Tx : x\in\mathbb{R}^n, Ax\leq b\}$$
und
$$d^*=\inf\{b^Ty : y\in\mathbb{R}^m, y\geq 0, A^Ty=c\}.$$

Welche der folgenden Aussagen ist wahr?

(a) $p^*\leq d^*$.

(b) $p^*\geq d^*$.

(c) Falls es für beide Programme zulässige Vektoren gibt, dann ist $p^*=d^*$.

(d) Falls es für beide Programme zulässige Vektoren gibt, dann ist $p^* \geq d^*$.

(e) Es ist $d^*=-\infty$, falls es keine zulässigen Vektoren für das obige Maximierungsprogramm gibt.

10. Gegeben seien folgende lineare Programme:
\begin{equation}p^*=\sup\left\{(5,8)x : \begin{pmatrix}1 & 2 \\ 3 & 4 \end{pmatrix}x\leq \begin{pmatrix}3\\3\end{pmatrix}\right\}\qquad (PLP)\end{equation}
und
\begin{equation}d^*=\inf\left\{(3,3)y : y\geq 0, \begin{pmatrix}1 & 3 \\ 2 & 4 \end{pmatrix}y=\begin{pmatrix}5\\8\end{pmatrix}\right\}.\qquad (DLP)\end{equation}

Welche der folgenden Aussagen ist wahr?

(a) $p^*= d^*$.

(b) $p^*\leq \inf\left\{(3,3)y : y\geq 0, \begin{pmatrix}1 & 3 \\ 2 & 4 \\5 & 6\end{pmatrix}y=\begin{pmatrix}5\\8\\10\end{pmatrix}\right\}$.

(c) $p^*=\inf\left\{(3,3)y : y\geq 0, \begin{pmatrix}1 & 3 \\ 2 & 4 \\5 & 6\end{pmatrix}y=\begin{pmatrix}5\\8\\10\end{pmatrix}\right\}$.

(d) Seien $x^*$ optimal für (PLP) und $y^*$ optimal für (DLP), dann gilt:
$$\begin{pmatrix}3 & 4 \end{pmatrix}x^*-3\neq 0 \Rightarrow y^*_2=0.$$

(e) Seien allgemein $x^*$ optimal für ein primales LP $\sup\{c^Tx : x\in\mathbb{R}^n, Ax\leq b\}$ und $y^*$ optimal für das zugehörige duale LP, dann gilt für alle Zeilen $i$:
$$\left(Ax^*-b\right)_i= 0 \Rightarrow y^*_i\neq 0.$$

11. Mit dem Verfahren von Fourier und Motzkin kann man:

12. Welche Aussagen zum Simplex-Verfahren sind korrekt?