\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{german}
\usepackage{graphicx}
\usepackage{fullpage}
\usepackage[utf8x]{inputenc}

\newcommand{\ZETTELNUMMER}{10}
\newcommand{\ABGABEDATUM}{am 23.\@ Juni 2015 vor der Vorlesung in die
  Mitarbeiterschachteln}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe~\arabic{AUFGNR}]\stepcounter{AUFGNR}
  #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}
\newcommand{\eps}{\varepsilon}


\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}

\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}

\usepackage{xspace}
\newcommand{\OPT}{\ensuremath{\mathsf{{OPT}}}\xspace}

\usepackage{amsthm}
\theoremstyle{plain}
\newtheorem*{thm}{Satz}

\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER.\ Aufgabenblatt zur Vorlesung \hfill SoSe 2015

\smallskip
\noindent
\large
\textbf{H\"ohere Algorithmik II}\\[0.5ex]
\normalsize
Wolfgang Mulzer, Lena Schlipf, Yannik Stein
\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm


\begin{description}

\AUFGABE{Beweis von Farkas' Lemma: Induktionsanfang}{10 Punkte}

Zeigen Sie:
Seien $A \in \R^{m \times 1}$ und $\mathbf{b} \in \R^m$.
Angenommen, es gibt kein $x \in \R$ mit $x \geq 0$ 
und $Ax \leq \mathbf{b}$.
Dann existiert ein $\mathbf{y} \in \R^m$ mit $\mathbf{y} \geq \mathbf{0}$, 
$\mathbf{y}^T A \geq \mathbf{0}^T$ und $\mathbf{y}^T \mathbf{b} < 0$.

\AUFGABE{Farkas' Lemma: Varianten}{10 Punkte}

In der Vorlesung haben wir folgende
Variante von Farkas' Lemma bewiesen:
Seien $A \in \R^{m \times n}$ und $\mathbf{b} \in \R^m$.
Dann gibt es \emph{entweder} ein $\mathbf{x} \in \R^n$ mit
$\mathbf{x} \geq \mathbf{0}$ und $A\mathbf{x} \leq \mathbf{b}$,
\emph{oder} es gibt ein
$\mathbf{y} \in \R^m$ mit $\mathbf{y} \geq \mathbf{0}$, 
$\mathbf{y}^T A \geq \mathbf{0}^T$ und 
$\mathbf{y}^T\mathbf{b} < 0$.

Beweisen Sie, dass die beiden folgenden Aussagen 
zum Lemma aus der Vorlesung \"aquivalent sind:

\begin{enumerate}
  \item Seien $A \in \R^{m \times n}$ und $\mathbf{b} \in \R^m$.
    \emph{Entweder} es existiert ein $\mathbf{x} \in \R^n$ mit 
    $\mathbf{x} \geq \mathbf{0}$ und 
    $A\mathbf{x} = \mathbf{b}$, 
    \emph{oder} es existiert ein $\mathbf{y} \in \R^m$ mit
       $\mathbf{y}^T A \geq \mathbf{0}^T$ und 
       $\mathbf{y}^T \mathbf{b} < 0$.
  \item Seien $A \in \R^{m \times n}$ und $\mathbf{b} \in \R^m$.
    \emph{Entweder} es existiert ein $\mathbf{x} \in \R^m$ mit 
    $A\mathbf{x} \leq \mathbf{b}$, 
    \emph{oder} es existiert ein $\mathbf{y} \in \R^m$ mit
       $\mathbf{y} \geq \mathbf{0}$,
       $\mathbf{y}^T A = \mathbf{0}^T$ und 
       $\mathbf{y}^T \mathbf{b} < 0$.
\end{enumerate}

\AUFGABE{Dualit\"at von LPs}{10 Punkte}

Sei $G = (V, E)$ ein bipartiter Graph.
Eine \emph{Paarung} ist eine Menge $M \subseteq E$ von
Kanten, so dass jeder Knoten von $G$ h\"ochstens eine inzidente
Kante in $M$ hat. Eine \emph{Maximum-Paarung} ist eine Paarung
mit der gr\"o\ss{}tm\"oglichen Anzahl von Kanten.

\begin{enumerate}
  \item Zeichnen Sie einen bipartiten Graphen mit
    $10$ Knoten, der eine Maximum-Paarung mit $5$ Kanten enth\"alt.
    Ihr Graph soll auch eine \emph{maximale} Paarung mit $4$ Kanten
    enthalten, die keine Maximum-Paarung ist. (Eine Paarung $M$ hei\ss{}t
    \emph{maximal}, falls es keine Paarung $M'$ mit $M' \supset M$ und
    $M' \neq M$ gibt).
  \item Formulieren Sie das Problem, zu einem gegebenen bipartiten
    Graphen $G$ eine Maximum-Paarung zu finden, als lineares Programm.
    Erkl\"aren Sie Ihr lineares Programm kurz in Worten.
  \item
    Formulieren Sie das duale lineare Programm zu Ihrem linearen Programm 
    aus (b). Interpretieren Sie das Ergebnis.
  \item
    Informieren Sie sich \"uber den \emph{Satz von K\"onig}.
    Folgt der Satz schon aus (b) und (c)? Begr\"unden Sie Ihre Antwort.
\end{enumerate}

\end{description}
\end{document}
