Operations Research – 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 Aussagen sind wahr?

(a) Sei $C\subseteq \mathbb{R}^n$ konvex und abgeschlossen, und sei $z\not\in C$. Dann gibt es eine Trennhyperebene von $\{z\}$ und $C$.

(b) Sei $C\subseteq \mathbb{R}^n$ konvex, und sei $z\not\in C$. Dann gibt es eine Trennhyperebene von $\{z\}$ und $C$.

(c) Falls $A$ und $B$ konvexe und abgeschlossene Mengen sind, mit $A\cap B=\emptyset$, dann gibt es eine Trennhyperebene von $A$ und $B$.

(d) Falls $A$ und $B$ konvexe und abgeschlossene Mengen sind, mit $A\cap B=\emptyset$, dann gibt es eine strikte Trennhyperebene von $A$ und $B$.
4. Für welche der folgenden Mengen $P$ gilt $P=\operatorname{conv}(\operatorname{ext}(P))$?
5. 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}$$
6. 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= 2017$ 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= -2017$ erfüllt.
7. 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 $p^*=-\infty$, falls es keine zulässigen Vektoren für das obige Maximierungsprogramm gibt.
8. Mit dem Verfahren von Fourier und Motzkin kann man:
9. Welche der folgenden Aussagen sind wahr?
10. Sei $G$ ein ungerichteter bipartiter Graph und $A$ seine Inzidenzmatrix. Welche der folgenden Programme berechnet die Matchingzahl von $G$?

(a) $\max\{1^Tx : x\in\mathbb{R}^E_{\geq 0}, Ax\leq 1\}$.

(b) $\min\{1^Ty : y\in\mathbb{Z}^V_{\geq 0}, A^Ty\geq 1\}$.

(c) $\max\{1^Tx : x\in\mathbb{Z}^E_{\geq 0}, Ax\geq 1\}$.

(d) $\min\{1^Ty : y\in\mathbb{R}^V_{\geq 0}, A^Ty\leq 1\}$.