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

\newcommand{\ZETTELNUMMER}{13}
\newcommand{\ABGABEDATUM}{bis zum 3. Februar 2017, 12 Uhr, in den
Briefkasten neben Raum 111}

\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}}



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


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

\smallskip
\noindent
\large
\textbf{H\"ohere Algorithmik}\hfill WiSe 2016/17 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Boris Klemz

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM\\
Dies ist das letzte regul\"are Aufgabenblatt.

\vskip 0.5cm

\begin{description}
\AUFGABE{Simplex}{10 Punkte}

L\"osen Sie die folgenden beiden LPe der Form
\begin{align*}
\max c^T x&, \text{ wobei}\\
Ax &\leq b\\
x &\geq 0
\end{align*}
mit dem Simplex-Algorithmus.

\begin{enumerate}
\item \[
   A =  \left( \begin{matrix}
      1 & 1 & 2 \\ 
      2 & 0 & 3 \\
      2 & 1 & 3
      \end{matrix}\right),
    b = \left( \begin{matrix}  
      4 \\ 5 \\ 7 
    \end{matrix}\right),
    c = \left( \begin{matrix}  
      3 \\ 2 \\ 4
    \end{matrix}\right).
   \]
\item  \[
   A =  \left( \begin{matrix}
      1 & 2 & 3 & 1 \\ 
      1 & 1 & 2 & 3 
      \end{matrix}\right),
    b = \left( \begin{matrix}  
      5 \\ 3
    \end{matrix}\right),
    c = \left( \begin{matrix}  
      5 \\ 6 \\ 9 \\ 8
    \end{matrix}\right).
   \]
\end{enumerate}


\AUFGABE{L\"osbarkeit von LPen}{10 Punkte}

F\"ur welche Werte von $s$ und $t$ gilt f\"ur das lineare Programm 
\begin{align*}
\max x_1 + x_2&, \text{ wobei}\\
sx_1 + tx_2 &\leq 1\\
x_1, x_2 &\geq 0
\end{align*}

\begin{enumerate}
\item es gibt eine optimale L\"osung, 
\item es gibt keine zul\"assige L\"osung,
\item die Zielfunktion ist unbeschr\"ankt?
\end{enumerate}
\newpage
\AUFGABE{Modellieren mit LPen}{10 Punkte}
\begin{enumerate}
\item Bei der \emph{Berliner Luftbr\"ucke} ging es darum,
  das blockierte West-Berlin aus der Luft zu versorgen.
  Dabei wurde auch lineares Programmieren verwendet. In dieser
  Aufgabe sollen Sie sich ein einfaches Beispiel ansehen.

  Das Ziel ist es, die gesamte Transportkapazit\"at nach West-Berlin
  pro Woche zu maximieren. Dabei m\"ussen folgende Rahmenbedingungen 
  beachtet werden:
  \begin{itemize}
    \item Insgesamt k\"onnen h\"ochstens 44 Fl\"uge pro Woche stattfinden.
    \item Es gibt zwei Flugzeugtypen A und B. Flugzeuge vom Typ A
      sind gr\"o\ss{}er und ben\"otigen zwei volle Besatzungen f\"ur einen
      Flug, w\"ahrend Flugzeuge vom Typ B mit einer vollen Besatzung auskommen.
      Insgesamt stehen 64 Besatzungen pro Woche zur Verf\"ugung.
    \item Ein Flug vom Typ A kostet 9.000 Dollar, ein Flug vom Typ B kostet
      5.000 Dollar. Das w\"ochentliche Budget betr\"agt 300.000 Dollar.
    \item Flugzeuge vom Typ A k\"onnen 30.000 Tonnen transportieren.
      Bei Flugzeugen vom Typ B sind es 20.000 Tonnen
  \end{itemize}
  Formulieren Sie das Problem als lineares Programm und finden Sie eine optimale
  L\"osung mit einer Methode Ihrer Wahl. Erkl\"aren Sie Ihr Vorgehen.
\item Modellieren Sie das Maximum-Fluss Problem
  als lineares Programm.
\end{enumerate}
\end{description}

\end{document}
