\documentclass[12pt]{article}
\usepackage{german}
\usepackage{times}
\usepackage{din_a4}
\usepackage{epsf}

\usepackage{amsfonts}
\parindent=0pt
\parskip3mm
\def\qed{\vbox{\hrule
  \hbox{\vrule\hbox to 5pt{\vbox to 8pt{\vfil}\hfil}\vrule}\hrule}}
\def\theorem#1{\par\medbreak\noindent\bf#1\enspace\sl\nobreak}
\def\endtheorem{\par\medskip\rm}
\def\remark#1{\par\medbreak\noindent\bf#1\enspace\rm\nobreak}
\def\endremark{\par\medskip\rm}
\def\proof{\par\medbreak\noindent{\bf Proof.}\enspace}
\def\beweis{\par\medbreak\noindent{\bf Beweis :}\enspace}
\def\ME{\mathop{\rm ME}}
\def\GE{\mathop{\rm GE}}
%\def\endproof{\unskip \nobreak \hskip0pt plus 1fill \qquad \qed \par}
\def\endproof{\nobreak{\parskip0pt\par}\nobreak\rightline{\qed}}
 \newcommand{\N}{\mathbb{N}}
    \newcommand{\Q}{\mathbb{Q}}
    \newcommand{\R}{\mathbb{R}}
    \newcommand{\Z}{\mathbb{Z}}
    \newcommand{\K}{\mathbb{K}}
\def\ctr#1{\hfil#1\hfil}
\def\hhh{\hphantom{1}}

\newcommand{\ds}{\displaystyle}


\begin{document}
 

\hfuzz=3pt
 \def\conv{\mathop{\rm conv}}
\def\lin{\mathop{\rm lin}}
\def\diag{\mathop{\rm diag}}
\def\cone{\mathop{\rm cone}}
\def\L{\hbox{\stk L}}
\def\C{\hbox{\stroke C}}
%\def\K{\hbox{\rm I\kern-3.5pt.K}}
\def\F{\hbox{\Stroke F}}
\def\H{\hbox{\Stroke h}}
\def\lin{\mathop{\rm lin}}
\def\cone{\mathop{\rm cone}}
\def\CONE{\mathop{\rm CONE}}
\def\aff{\mathop{\rm aff}}
\def\rank{\mathop{\rm rank}}
\def\arank{\mathop{\rm arank}}
\def\L{{\rm L}}
\def\Ta{\parindent 20pt\parskip 5pt\par}
\def\Tb{\parskip 0pt\parindent 35pt\hangindent 45pt\par}
\def\Tc{\parskip 0pt\parindent 45pt\hangindent 55pt\par}
\def\Td{\parskip 0pt\parindent 55pt\hangindent 65pt\par}
\def\Te{\parskip 0pt\parindent 65pt\hangindent 75pt\par}
\def\Tf{\parskip 0pt\parindent 75pt\hangindent 85pt\par}
\def\Tg{\parskip 0pt\parindent 85pt\hangindent 95pt\par}
\def\Th{\parskip 0pt\parindent 95pt\hangindent 105pt\par}
\def\Ti{\parskip 0pt\parindent 105pt\hangindent 115pt\par}
\def\Tj{\parskip 0pt\parindent 115pt\hangindent 125pt\par}
\def\Tk{\parskip 0pt\parindent 125pt\hangindent 135pt\par}
\def\Tl{\parskip 0pt\parindent 135pt\hangindent 145pt\par}
\def\Tm{\parskip 0pt\parindent 145pt\hangindent 155pt\par}
\def\P{$\cal P$}
\def\I{$\cal I$}
\def\T{$\cal T$}
\def\CP{co-$\cal P$}
\def\MCP{{\hbox{co-}\cal P}}
\def\MP{{\cal P}}
\def\MI{{\cal I}}
\def\MT{{\cal T}}
\def\NP{${\cal N}\hskip-2pt{\cal P}$}
\def\MNP{{\cal N}\hskip-2pt{\cal P}}
\def\CNP{$\hbox{co-}{\cal N}\hskip-2pt{\cal P}$}
\def\MCNP{\hbox{co-}{\cal N}\hskip-2pt{\cal P}}
\def\NPh{${\cal N}\hskip-2pt{\cal P}$-hard}
\def\NPe{${\cal N}\hskip-2pt{\cal P}$-easy}
\def\NPeq{${\cal N}\hskip-2pt{\cal P}$-equivalent}
\def\NPc{${\cal N}\hskip-2pt{\cal P}$-complete}
\def\relv{\mathbin{|}\allowbreak}
\def\dt{\mathop{\rm dt}}

\def\cpunkt{\raise 1pt\hbox{.}}
\def\hh{\hphantom{-}}
\def\h{\hphantom{0}}
\def\vv{\hbox to 0pt{\vphantom{g}}}
\def\vl{\vrule}
\def\hline{\noalign{\hrule}}
\def\B{$\cal B$}
\def\MB{{\cal B}}
\def\C{$\cal C$}
\def\MC{{\cal C}}
\def\T{$\cal T$}
\def\MT{{\cal T}}
\def\Kr{\mathop{\rm Kr}}


 \def\lft#1{#1\hfil}
\def\rt#1{\hfil#1}



\def\cpunkt{\raise 1pt\hbox{.}}
\def\hh{\hphantom{-}}
\def\h{\hphantom{0}}
\def\vv{\hbox to 0pt{\vphantom{g}}}
\def\vl{\vrule}
\def\hline{\noalign{\hrule}}
\def\B{$\cal B$}
\def\MB{{\cal B}}
\def\C{$\cal C$}
\def\MC{{\cal C}}
\def\T{$\cal T$}
\def\MT{{\cal T}}
\def\Kr{\mathop{\rm Kr}}


 

%\vskip-2truecm


\setcounter{section}{1}


\section*{Polyedertheorie}

Prof. Dr. Martin Gr\"otschel  \hfill 3. Januar 2001

Der nachfolgende Text entspricht im wesentlichen Kapitel 2  des
Vorlesungsskripts zur Vorlesung ``Lineare Optimierung'', die von mir im
Wintersemester 2000/2001 gehalten wurde. In diesem Kapitel ist die Notation
zur Polyedertheorie zusammengefasst.

\section{Polyeder}




Das Hauptanliegen dieser Vorlesung ist die Behandlung von Problemen der
linearen Programmierung. Man kann die Verfahren zur L\"osung derartiger
Probleme rein algebraisch darstellen als Manipulation von linearen Gleichungs-
und Ungleichungssystemen. Die meisten Schritte dieser Algorithmen haben jedoch
auch eine geometrische Bedeutung; und wenn man erst einmal die geometrischen
Prinzipien und Regeln verstanden hat, die hinter diesen Schritten liegen,
ist es viel einfacher, die Algorithmen und ihre Korrektheitsbeweise zu
verstehen. Wir wollen daher in dieser  Vorlesung einen geometrischen Zugang
w\"ahlen und zun\"achst die L\"osungsmengen linearer Programme studieren.
Speziell wollen wir unser Augenmerk auf geometrische Sachverhalte und ihre
algebraische Charakterisierung legen. Dies wird uns helfen, aus geometrischen
Einsichten algebraische Verfahren abzuleiten.

\theorem{(2.1) Definition.}

\begin{itemize}
\item[(a)]
Eine Teilmenge $G\subseteq\K^n$ hei\ss t {\bf Hyperebene}, falls es einen
Vektor $a\in\K^n\setminus\{0\}$ und $\alpha\in\K$ gibt mit
$$G=\{x\in\K^n\mid a^Tx=\alpha\}.$$
Der  Vektor $a$ hei\ss t {\bf Normalenvektor} zu $G$.

\item[(b)]
Eine Teilmenge $H\subseteq\K^n$ hei\ss t {\bf Halbraum}, falls es einen
Vektor $a\in\K^n\setminus\{0\}$ und $\alpha\in\K$ gibt mit
$$H=\{x\in\K^n\mid a^Tx\le\alpha\}.$$
Wir nennen $a$ den {\bf Normalenvektor} zu $H$. Die Hyperebene
$G=\{x\in\K^n\mid a^Tx=\:\alpha\}$ hei\ss t die zum Halbraum $H$ geh\"orende
Hyperebene oder die $H$ berandende Hyperebene, und $H$ hei\ss t der zu $G$
geh\"orende Halbraum.

\item[(c)]
Eine Teilmenge $P\subseteq\K^n$ hei\ss t {\bf Polyeder},
falls es ein $m\in\Z_+$, eine Matrix $A\in\K^{(m,n)}$ und einen Vektor
$b\in\K^m$ gibt mit
$$P=\{x\in\K^n\mid Ax\le b\}.$$
Um zu betonen, da\ss\ $P$ durch $A$ und $b$ definiert ist, schreiben wir
auch
$$P=P(A,b):=\{x\in\K^n\mid Ax\le b\}.$$

\item[(d)]
Ein Polyeder $P$ hei\ss t {\bf Polytop}, wenn es beschr\"ankt ist,
d.~h.~wenn es ein $B\in\K$, $B>0$ gibt mit
$P\subseteq\{x\in\K^n\mid \|x\|\le B\}.$
\end{itemize}
\endtheorem
\endproof

Polyeder k\"onnen wir nat\"urlich auch in folgender Form schreiben
$$P(A,b)=\bigcap^m_{i=1}\{x\in\K^n\mid A_{i\cpunkt}x\le b_i\}.$$
Halbr\"aume sind offensichtlich Polyeder. Aber auch die leere Menge ist
ein Polyeder, denn $\emptyset=\{x\mid0^Tx\le-1\}$, und der gesamte
Raum ist ein Polyeder, denn $\K^n=\{x\mid0^Tx\le0\}$. Sind alle
Zeilenvektoren $A_{i\cpunkt}$ von $A$ vom Nullvektor verschieden, so sind
 die bei der obigen Durchschnittsbildung beteiligten Mengen Halbr\"aume.
Ist ein Zeilenvektor von $A$ der Nullvektor, sagen wir $A_{1\cpunkt}=0^T$,
so ist $\{x\in\K^n\mid A_{1\cpunkt}x\le b_1\}$ entweder leer (falls
$b_1<0$) oder der gesamte Raum $\K^n$ (falls $b_1\ge0$). Das hei\ss t,
entweder ist $P(A,b)$ leer oder die Mengen $\{x\mid A_{i\cpunkt}\le b_i\}$
mit $A_{i\cpunkt}=0$ k\"onnen bei der obigen Durchschnittsbildung
weggelassen werden. Daraus folgt

\medskip

\centerline{{\sl Jedes Polyeder $P\ne\K^n$ ist Durchschnitt von endlich vielen
Halbr\"aumen.}}
\medskip

Gilt $P=P(A,b)$, so nennen wir das Ungleichungssystem $Ax\le b$ ein
{\bf P definierendes System} (von linearen Ungleichungen). Sind $\alpha>0$ und
$1\le i<j\le m$, so gilt  offensichtlich
$$P(A,b)=P(A,b)\cap\{x\mid\alpha A_{i\cpunkt}x\le\alpha b_i\}
\cap\{x\mid(A_{i\cpunkt}+A_{j\cpunkt})x\le b_i+b_j\}.$$
Daraus folgt, da\ss\ $A$ und $b$ zwar $P=P(A,b)$ eindeutig bestimmen,
da\ss\ aber $P$ unendlich viele Darstellungen der Form $P(D,d)$ hat.

\remark{(2.2) Beispiel.}
Wir betrachten das Ungleichungssystem
$$\vcenter{\halign{\ctr{#}\qquad&\rt{$#$}$\,$&\rt{$#$}$\;$&\rt{$#$}\cr
(1) & 2x_1 &            \;\le  & 5 \cr
(2) &      & -\;2x_2    \;\le  & 1 \cr
(3) & -x_1 & -\;\hhh x_2\;\le  & -1\cr
(4) & 2x_1 & +\;9x_2    \;\le  & 23\cr
(5) & 6x_1 & -\;2x_2    \;\le  & 13\cr
}}$$
Hieraus erhalten wir die folgende Matrix $A$  und den Vektor $b$:
$$A=\pmatrix{\hh2&\hh0\cr\hh0&-2\cr-1&-1\cr\hh2&\hh9\cr\hh6&-2\cr}
\qquad b=\pmatrix{\hh5\cr \hh1\cr -1\cr 23\cr 13\cr}$$
Das Polyeder $P=P(A,b)$ ist die L\"osungsmenge des obigen
Ungleichungssystems (1),$\ldots$,(5) und ist in Abbildung 2.1 graphisch
dargestellt.
\endremark
\endproof


\vbox{
$$\epsffile{2.1.eps}$$
\centerline{\bf Abb.~2.1}
}

 


Die Mengen zul\"assiger L\"osungen linearer Programme treten nicht immer
in der Form $Ax\le b$ auf. H\"aufig gibt es auch Gleichungen und
vorzeichenbeschr\"ankte Variable. Vorzeichenbeschr\"ankungen sind nat\"urlich
auch lineare Ungleichungssysteme, und ein Gleichungssytem $Dx=d$ kann in der
Form von zwei Ungleichungssystemen $Dx\le d$ und $-Dx\le-d$ geschrieben
werden. Allgemeiner gilt

\vbox{%
\theorem{(2.3) Bemerkung.}
Die L\"osungsmenge des Systems
$$\begin{array}{lr}
Bx+Cy & =c\cr
Dx+Ey & \le d\cr
x     & \ge0\cr
x\in\K^p, &y \in\K^q\cr
\end{array}$$
ist ein Polyeder.
\endtheorem
}

\beweis
Setze $n:=p+q$ und
$$A:=\pmatrix{\hh B&\hh C\cr-B&-C\cr\hh D&\hh E\cr-I&\hh0\cr},
\qquad b:=\pmatrix{\hh c\cr-c\cr\hh d\cr\hh0\cr},$$
dann ist $P(A,b)$ die L\"osungsmenge des vorgegebenen Gleichungs- und
Ungleichungssystems.
\endproof

Ein spezieller Polyedertyp wird uns h\"aufig begegnen, weswegen wir f\"ur
ihn eine besondere Bezeichnung w\"ahlen wollen. F\"ur $A\in\K^{(m,n)}$,
$b\in\K^m$ setzen wir
$$P^{=}(A,b):=\{x\in\K^n\mid Ax=b,x\ge0\}.$$
Nicht alle Polyeder k\"onnen in der  Form $P^{=}(A,b)$ dargestellt werden,
z.~B.~nicht $P=\{x\in\K\mid x\le1\}$.

Wir werden sp\"ater viele S\"atze \"uber Polyeder $P$ beweisen, deren
Aussagen {\bf darstellungsabh\"angig} sind, d.~h.~die Art und  Weise, wie
$P$ gegeben ist, geht explizit in die Satzaussage ein. So werden sich
z.~B.~die Charakterisierungen gewisser Polyedereigenschaften von $P(A,b)$
(zumindest formal) von den entsprechenden Charakterisierungen von
$P^{=}(A,b)$ unterscheiden. Darstellungsabh\"angige S\"atze wollen wir
jedoch nur einmal beweisen (normalerweise f\"ur Darstellungen, bei denen
die Resultate besonders einpr\"agsam oder einfach sind), deshalb werden wir
uns nun Transformationsregeln \"uberlegen, die angeben, wie man von einer
Darstellungsweise zu einer anderen und wieder zur\"uck kommt.

\remark{(2.4) Transformationen.}

\medskip
\noindent
{\bf Regel I:\quad Einf\"uhrung von Schlupfvariablen}

Gegeben seien $a\in\K^n$, $\alpha\in\K$. Wir schreiben
die Ungleichung

(i)
$a^Tx\le\alpha$

in der Form  einer Gleichung und einer Vorzeichenbeschr\"ankung

(ii)
$a^Tx+y=\alpha$,\quad $y\ge0$.

$y$ ist eine neue Variable, genannt {\bf Schlupfvariable}.

\noindent
Es gilt:
$$\vcenter{\halign{\ctr{$#$}\quad&\lft{#}\quad&\ctr{$#$}\quad&\lft{#}\cr
x & erf\"ullt (i) &\Longrightarrow &${x\choose y}\;$ erf\"ullt (ii) f\"ur
$y=\alpha-a^Tx$.\cr
{x\choose y} & erf\"ullt (ii) &\Longrightarrow &$x\;$ erf\"ullt (i).\cr
}}$$

\noindent
Allgemein: Ein Ungleichungssystem $Ax\le b$ kann durch Einf\"uhrung  eines
Schlupfvariablenvektors $y$ transformiert werden in ein Gleichungssystem mit
Vorzeichenbedingung $Ax+y=b$, $y\ge0$. Zwischen den L\"osungsmengen dieser
beiden Systeme bestehen die oben angegebenen Beziehungen. $P(A,b)$ und
$\{{x\choose y}\in\K^{n+m}\mid Ax+Iy=b,y\ge0\}$ sind jedoch zwei durchaus
verschiedene Polyeder in verschiedenen Vektorr\"aumen.

\medskip
\noindent
{\bf Regel II:\quad Einf\"uhrung von vorzeichenbeschr\"ankten Variablen}

\noindent

Ist $x$ eine (eindimensionale) nicht vorzeichenbeschr\"ankte Variable, so
k\"onnen wir zwei vorzeichenbeschr\"ankte Variablen $x^+$ und $x^-$
einf\"uhren, um $x$ darzustellen. Wir setzen
$$x:=x^+-x^-\quad\hbox{ mit }\quad x^+\ge0,\;x^-\ge0.$$
\endproof

\noindent
Mit den  Regeln I und II aus (2.4) k\"onnen wir z.~B.~jedem Polyeder
$P(A,b)\subseteq\K^n$ ein Polyeder $P^=(D,d)\subseteq\K^{2n+m}$ wie
folgt zuordnen. Wir setzen
$$D:=(A,-A,I_m),\;d:=b,$$
d.~h.~es gilt
$$P^=(D,d)=\left\{\pmatrix{x\cr y\cr z\cr}\in\K^{2n+m}\mid Ax-Ay+z=b,
\;x,y,z\ge0\right\}
.$$
Es ist \"ublich, die oben definierten Polyeder $P(A,b)$ und $P^=(D,d)$
{\bf \"aquivalent} zu nennen. Hierbei hat ``\"Aquivalenz'' folgende
Bedeutung.

\noindent
F\"ur $x\in\K^n$ sei
$$\vcenter{\halign{\rt{$#$}&\lft{$#$}\quad&\ctr{#}\quad&\lft{$#$}\cr
x^+\;:= &\;(x^+_1,\ldots,x^+_n)^T & mit & x^+_i=\max\{0,x_i\},\cr
x^-\;:= &\;(x^-_1,\ldots,x^-_n)^T & mit & x^-_i=\max\{0,-x_i\},\cr
}}$$
dann gilt:


$$\begin{array}{lcl}
x\in P(A,b)\quad &\Longrightarrow\quad\pmatrix{x^+\cr x^-\cr z\cr}
\in P^=(D,d)\;\hbox{ f\"ur } z=b-Ax\cr
\pmatrix{u\cr v\cr w\cr}\in P^=(D,d)\quad &\Longrightarrow\quad
x:=u-v\in P(A,b).
\end{array}$$



Besonders einfache Polyeder, auf die sich jedoch fast alle Aussagen der
Polyedertheorie zur\"uckf\"uhren lassen, sind polyedrische Kegel.

\theorem{(2.5) Definition.}
Ein Kegel $C\subseteq\K^n$ hei\ss t {\bf polyedrisch} genau dann, wenn
$C$ ein Polyeder ist.
\endtheorem
\endproof

\theorem{(2.6) Bemerkung.}
Ein Kegel $C\subseteq\K^n$ ist genau dann polyedrisch, wenn es eine
Matrix $A\in\K^{(m,n)}$ gibt mit
$$C=P(A,0).$$
\endtheorem

\beweis
Gilt $C=P(A,0)$, so ist $C$ ein Polyeder und offensichtlich ein Kegel.

Sei $C$ ein polyedrischer Kegel, dann existieren nach Definition (2.1) (c)
eine Matrix $A$ und ein Vektor $b$ mit $C=P(A,b)$.
Da jeder Kegel den Nullvektor enth"alt, gilt $0=A0 \le b$.Angenommen, es
existiert ein $\overline x\in C$ mit $A\overline x\not\le0$, d.~h.~es existiert
eine Zeile von $A$, sagen wir $A_{i\cpunkt}$, mit $t:=A_{i\cpunkt}
\overline x>0$. Da $C$ ein Kegel ist, gilt $\lambda\overline x\in C$ f\"ur
alle $\lambda\in\K_+$. Jedoch f\"ur $\overline\lambda:={b_i\over t}+1$
gilt einerseits $\overline\lambda\overline x\in C$ und andererseits
$A_{i\cpunkt}(\overline\lambda\overline x)=\overline\lambda t>b_i$, ein
Widerspruch. Daraus folgt, f\"ur alle $x\in C$ gilt $Ax\le0$.
Hieraus ergibt sich $C=P(A,0)$.
\endproof

\pagebreak


\vbox{%
%\baselineskip=14.4pt
In der folgenden Tabelle 2.1 haben wir alle m\"oglichen Transformationen
aufgelistet. Sie soll als ``Nachschlagewerk'' dienen.

\begin{tabular}{|p{38mm}|p{36mm}|p{34mm}|p{45mm}|}
  \hline
& & & \mbox{}\newline \\
  \multicolumn{1}{|c|}{Transformation} & & & \\
                 
 
  \multicolumn{1}{|r|}{nach} 
  & \centerline{$\ds By \leq d$}
 
  & \centerline{$\ds
  \begin{array}{rcl}
    By &=& d\\[3mm]
    y  & \geq & 0
  \end{array}
  $}
  & \centerline{$\ds \begin{array}{rcl}
    By &\leq& d\\[3mm]
     y  & \geq & 0
  \end{array}$} \\
  \multicolumn{1}{|c|}{von} & & &\\
& & & \mbox{}\newline \\
  \hline
  \mbox{}\newline

  \centerline{$\ds  Ax=b$}
 \mbox{}\newline
  \centerline{hierbei ist}
 \mbox{}\newline
  $\ds\begin{array}{rcl}
    x_i^+ &=&\max\{ 0,x_i\}\\[3mm]
    x_i^- &=&\max\{ 0,-x_i\}
  \end{array}$


  & 

 $$\pmatrix{\hh A\cr-A\cr}y\le
                        \pmatrix{\hh b\cr-b\cr}$$
           $$y=x$$ 
 &

 $$\begin{array}{r@{\hspace*{-0mm}}l} (A,-A)\;y&=b\\[2mm]
                    y &  \ge0\\[3mm]
           y=\pmatrix{x^+\cr x^-\cr}\end{array}$$   
& 
  $$\begin{array}{r@{\hspace*{-0mm}}l}\pmatrix{\hh A&-A\cr-A&\hh A\cr}y&\le
                        \pmatrix{\hh b\cr-b\cr}\cr
                      y&\ge0\\[2mm]
           y=\pmatrix{x^+\cr x^-\cr}\end{array}$$ \mbox{}\newline \\
\hline 
& & & \mbox{}\newline \\
  \mbox{}\newline 
 \centerline{$\ds \begin{array}{rcl}
    Ax &\leq& b
    \end{array}$} 
 &  \mbox{}\newline  \centerline{$\ds \begin{array}{rcl}
    Ay &\leq& b\\[3mm]
     y  & = & x
  \end{array}$}  

 & \mbox{}\newline 
 $\ds \begin{array}{rcl}(A,-A,I)\;y=b\\[2mm]
                       y\ge0   \\[2mm]
           y=\pmatrix{x^+\cr x^-\\b-Ax}
\end{array}$
 \mbox{}\newline 
    
 &  \mbox{}\newline 
 $\ds \begin{array}{rcl}
(A,-A)\;y\le b\\[2mm]
                       y\ge0   \\[2mm]
           y=\pmatrix{x^+\cr x^-}
\end{array}$   
 \mbox{}\newline \\

\hline 
& & & \mbox{}\newline \\
  $$\begin{array}{cc}Ax&=b\\[3mm]
                       x&\ge 0\cr\end{array}$$
 &  \mbox{}\newline 
\centerline{$\ds \begin{array}{rcl}\pmatrix{\hh A\cr-A\cr-I\cr}y
                  &\le\pmatrix{\hh b\cr-b\cr\hh0\cr}\cr\end{array}$}

                 \centerline{     $y=x$}

 &   $$\begin{array}{cc}Ay&= b\\[3mm]
                       y&\ge 0\\[3mm]
           y&=x\end{array}$$

& $$\begin{array}{rll}\pmatrix{\hh A\cr-A\cr}y
                  &\le\pmatrix{\hh b\cr-b\cr}\\[3mm]
                       y&\ge0&\\[3mm]
                       y & =x& \end{array}$$ \\
\hline 
 \mbox{}\newline 
  $$\begin{array}{cc}Ax\le b\\[3mm]
                      x\ge0\cr\end{array}$$
  &  $$\pmatrix{\hh A\cr-I\cr}y
                   \le\pmatrix{b \cr 0 \cr } $$
           $$y=x$$


 &  $$\begin{array}{rl}(A,I)\;y&=b\\[3mm]
                       y&\ge0\end{array}$$
          $$ y=\pmatrix{x\cr b-Ax}$$


 & \mbox{}\newline $$\begin{array}{cc}Ay&\le b\\[3mm]
                       y&\ge 0\cr\end{array}$$
           $$y=x$$
 \mbox{}\newline \\
\hline


\end{tabular}
}

\vfill

\end{document}


\theorem{(2.1) Definition.}

\begin{itemize}
\item[(a)]
Eine Teilmenge $G\subseteq\K^n$ hei\ss t {\bf Hyperebene}, falls es einen
Vektor $a\in\K^n\setminus\{0\}$ und $\alpha\in\K$ gibt mit
$$G=\{x\in\K^n\mid a^Tx=\alpha\}.$$
Der  Vektor $a$ hei\ss t {\bf Normalenvektor} zu $G$.

\item[(b)]
Eine Teilmenge $H\subseteq\K^n$ hei\ss t {\bf Halbraum}, falls es einen
Vektor $a\in\K^n\setminus\{0\}$ und $\alpha\in\K$ gibt mit
$$H=\{x\in\K^n\mid a^Tx\le\alpha\}.$$
Wir nennen $a$ den {\bf Normalenvektor} zu $H$. Die Hyperebene
$G=\{x\in\K^n\mid a^Tx=\:\alpha\}$ hei\ss t die zum Halbraum $H$ geh\"orende
Hyperebene oder die $H$ berandende Hyperebene, und $H$ hei\ss t der zu $G$
geh\"orende Halbraum.

\item[(c)]
Eine Teilmenge $P\subseteq\K^n$ hei\ss t {\bf Polyeder},
falls es ein $m\in\Z_+$, eine Matrix $A\in\K^{(m,n)}$ und einen Vektor
$b\in\K^m$ gibt mit
$$P=\{x\in\K^n\mid Ax\le b\}.$$
Um zu betonen, da\ss\ $P$ durch $A$ und $b$ definiert ist, schreiben wir
auch
$$P=P(A,b):=\{x\in\K^n\mid Ax\le b\}.$$

\item[(d)]
Ein Polyeder $P$ hei\ss t {\bf Polytop}, wenn es beschr\"ankt ist,
d.~h.~wenn es ein $B\in\K$, $B>0$ gibt mit
$P\subseteq\{x\in\K^n\mid \|x\|\le B\}.$
\end{itemize}
\endtheorem
\endproof

Polyeder k\"onnen wir nat\"urlich auch in folgender Form schreiben
$$P(A,b)=\bigcap^m_{i=1}\{x\in\K^n\mid A_{i\cpunkt}x\le b_i\}.$$
Halbr\"aume sind offensichtlich Polyeder. Aber auch die leere Menge ist
ein Polyeder, denn $\emptyset=\{x\mid0^Tx\le-1\}$, und der gesamte
Raum ist ein Polyeder, denn $\K^n=\{x\mid0^Tx\le0\}$. Sind alle
Zeilenvektoren $A_{i\cpunkt}$ von $A$ vom Nullvektor verschieden, so sind
 die bei der obigen Durchschnittsbildung beteiligten Mengen Halbr\"aume.
Daraus folgt:  $P(A,b)$ ist der Durchschnitt von  endlich vielen Halbr\"aumen.
Ist ein Zeilenvektor der Nullvektor, sagen wir $A_{1\cpunkt}=0^T$, so ist
$\{x\in\K^n\mid A_{1\cpunkt}x\le b_1\}$ entweder leer (falls $b_1<0$) oder
der gesamte Raum $\K^n$ (falls $b_1\ge0$). Das hei\ss t, entweder is
$P(A,b)$ leer oder die Mengen $\{x\mid A_{i\cpunkt}\le b_i\}$ mit
$A_{i\cpunkt}=0$ k\"onnen bei der obigen Durchschnittsbildung weggelassen
werden. Daraus folgt

\medskip

\centerline{{\sl Jedes Polyeder $P\ne\K^n$ ist Durchschnitt von endlich vielen
Halbr\"aumen.}}
\medskip

Gilt $P=P(A,b)$, so nennen wir das Ungleichungssystem $Ax\le b$ ein
{\bf P definierendes System} (von linearen Ungleichungen). Sind $\alpha>0$ und
$1\le i<j\le m$, so gilt  offensichtlich
$$P(A,b)=P(A,b)\cap\{x\mid\alpha A_{i\cpunkt}x\le\alpha b_i\}
\cap\{x\mid(A_{i\cpunkt}+A_{j\cpunkt})x\le b_i+b_j\}.$$
Daraus folgt, da\ss\ $A$ und $b$ zwar $P=P(A,b)$ eindeutig bestimmen,
da\ss\ aber $P$ unendlich viele Darstellungen der Form $P(D,d)$ hat.

\remark{(2.2) Beispiel.}
Wir betrachten das Ungleichungssystem
$$\vcenter{\halign{\ctr{#}\qquad&\rt{$#$}$\,$&\rt{$#$}$\;$&\rt{$#$}\cr
(1) & 2x_1 &            \;\le  & 5 \cr
(2) &      & -\;2x_2    \;\le  & 1 \cr
(3) & -x_1 & -\;\hhh x_2\;\le  & -1\cr
(4) & 2x_1 & +\;9x_2    \;\le  & 23\cr
(5) & 6x_1 & -\;2x_2    \;\le  & 13\cr
}}$$
Hieraus erhalten wir die folgende Matrix $A$  und den Vektor $b$:
$$A=\pmatrix{\hh2&\hh0\cr\hh0&-2\cr-1&-1\cr\hh2&\hh9\cr\hh6&-2\cr}
\qquad b=\pmatrix{\hh5\cr \hh1\cr -1\cr 23\cr 13\cr}$$
Das Polyeder $P=P(A,b)$ ist die L\"osungsmenge des obigen
Ungleichungssystems (1),$\ldots$,(5) und ist in Abbildung 2.1 graphisch
dargestellt.
\endremark
\endproof


\vbox{
$$\epsffile{2.1.eps}$$
\centerline{\bf Abb.~2.1}
}

 


Die Mengen zul\"assiger L\"osungen linearer Programme treten nicht immer
in der Form $Ax\le b$ auf. H\"aufig gibt es auch Gleichungen und
vorzeichenbeschr\"ankte Variable. Vorzeichenbeschr\"ankungen sind nat\"urlich
auch lineare Ungleichungssysteme, und ein Gleichungssytem $Dx=d$ kann in der
Form von zwei Ungleichungssystemen $Dx\le d$ und $-Dx\le-d$ geschrieben
werden. Allgemeiner gilt

\vbox{%
\theorem{(2.3) Bemerkung.}
Die L\"osungsmenge des Systems
$$\begin{array}{lr}
Bx+Cy & =c\cr
Dx+Ey & \le d\cr
x     & \ge0\cr
x\in\K^p,y &\in\K^q\cr
\end{array}$$
ist ein Polyeder.
\endtheorem
}

\beweis
Setze $n:=p+q$ und
$$A:=\pmatrix{\hh B&\hh C\cr-B&-C\cr\hh D&\hh E\cr-I&\hh0\cr},
\qquad b:=\pmatrix{\hh c\cr-c\cr\hh d\cr\hh0\cr},$$
dann ist $P(A,b)$ die L\"osungsmenge des vorgegebenen Gleichungs- und
Ungleichungssystems.
\endproof

Ein spezieller Polyedertyp wird uns h\"aufig begegnen, weswegen wir f\"ur
ihn eine besondere Bezeichnung w\"ahlen wollen. F\"ur $A\in\K^{(m,n)}$,
$b\in\K^m$ setzen wir
$$P^{=}(A,b):=\{x\in\K^n\mid Ax=b,x\ge0\}.$$
Nicht alle Polyeder k\"onnen in der  Form $P^{=}(A,b)$ dargestellt werden,
z.~B.~nicht $P=\{x\in\K\mid x\le1\}$.

Wir werden sp\"ater viele S\"atze \"uber Polyeder $P$ beweisen, deren
Aussagen {\bf darstellungsabh\"angig} sind, d.~h.~die Art und  Weise, wie
$P$ gegeben ist, geht explizit in die Satzaussage ein. So werden sich
z.~B.~die Charakterisierungen gewisser Polyedereigenschaften von $P(A,b)$
(zumindest formal) von den entsprechenden Charakterisierungen von
$P^{=}(A,b)$ unterscheiden. Darstellungsabh\"angige S\"atze wollen wir
jedoch nur einmal beweisen (normalerweise f\"ur Darstellungen, bei denen
die Resultate besonders einpr\"agsam oder einfach sind), deshalb werden wir
uns nun Transformationsregeln \"uberlegen, die angeben, wie man von einer
Darstellungsweise zu einer anderen und wieder zur\"uck kommt.

\remark{(2.4) Transformationen.}

\medskip
\noindent
{\bf Regel I:\quad Einf\"uhrung von Schlupfvariablen}

Gegeben seien $a\in\K^n$, $\alpha\in\K$. Wir schreiben
die Ungleichung

(i)
$a^Tx\le\alpha$

in der Form  einer Gleichung und einer Vorzeichenbeschr\"ankung

(ii)
$a^Tx+y=\alpha$,\quad $y\ge0$.

$y$ ist eine neue Variable, genannt {\bf Schlupfvariable}.

\noindent
Es gilt:
$$\vcenter{\halign{\ctr{$#$}\quad&\lft{#}\quad&\ctr{$#$}\quad&\lft{#}\cr
x & erf\"ullt (i) &\Longrightarrow &${x\choose y}\;$ erf\"ullt (ii) f\"ur
$y=\alpha-a^Tx$.\cr
{x\choose y} & erf\"ullt (ii) &\Longrightarrow &$x\;$ erf\"ullt (i).\cr
}}$$

\noindent
Allgemein: Ein Ungleichungssystem $Ax\le b$ kann durch Einf\"uhrung  eines
Schlupfvariablenvektors $y$ transformiert werden in ein Gleichungssystem mit
Vorzeichenbedingung $Ax+y=b$, $y\ge0$. Zwischen den L\"osungsmengen dieser
beiden Systeme bestehen die oben angegebenen Beziehungen. $P(A,b)$ und
$\{{x\choose y}\in\K^{n+m}\mid Ax+Iy=b,y\ge0\}$ sind jedoch zwei durchaus
verschiedene Polyeder in verschiedenen Vektorr\"aumen.

\medskip
\noindent
{\bf Regel II:\quad Einf\"uhrung von vorzeichenbeschr\"ankten Variablen}

\noindent

Ist $x$ eine (eindimensionale) nicht vorzeichenbeschr\"ankte Variable, so
k\"onnen wir zwei vorzeichenbeschr\"ankte Variablen $x^+$ und $x^-$
einf\"uhren, um $x$ darzustellen. Wir setzen
$$x:=x^+-x^-\quad\hbox{ mit }\quad x^+\ge0,\;x^-\ge0.$$
\endproof

\noindent
Mit den  Regeln I und II aus (2.4) k\"onnen wir z.~B.~jedem Polyeder
$P(A,b)\subseteq\K^n$ ein Polyeder $P^=(D,d)\subseteq\K^{2n+m}$ wie
folgt zuordnen. Wir setzen
$$D:=(A,-A,I_m),\;d:=b,$$
d.~h.~es gilt
$$P^=(D,d)=\left\{\pmatrix{x\cr y\cr z\cr}\in\K^{2n+m}\mid Ax-Ay+z=b,
\;x,y,z\ge0\right\}
.$$
Es ist \"ublich, die oben definierten Polyeder $P(A,b)$ und $P^=(D,d)$
{\bf \"aquivalent} zu nennen. Hierbei hat ``\"Aquivalenz'' folgende
Bedeutung.

\noindent
F\"ur $x\in\K^n$ sei
$$\vcenter{\halign{\rt{$#$}&\lft{$#$}\quad&\ctr{#}\quad&\lft{$#$}\cr
x^+\;:= &\;(x^+_1,\ldots,x^+_n)^T & mit & x^+_i=\max\{0,x_i\},\cr
x^-\;:= &\;(x^-_1,\ldots,x^-_n)^T & mit & x^-_i=\max\{0,-x_i\},\cr
}}$$
dann gilt:


$$\begin{array}{lcl}
x\in P(A,b)\quad &\Longrightarrow\quad\pmatrix{x^+\cr x^-\cr z\cr}
\in P^=(D,d)\;\hbox{ f\"ur } z=b-Ax\cr
\pmatrix{u\cr v\cr w\cr}\in P^=(D,d)\quad &\Longrightarrow\quad
x:=u-v\in P(A,b).
\end{array}$$



Besonders einfache Polyeder, auf die sich jedoch fast alle Aussagen der
Polyedertheorie zur\"uckf\"uhren lassen, sind polyedrische Kegel.

\theorem{(2.5) Definition.}
Ein Kegel $C\subseteq\K^n$ hei\ss t {\bf polyedrisch} genau dann, wenn
$C$ ein Polyeder ist.
\endtheorem
\endproof

\theorem{(2.6) Bemerkung.}
Ein Kegel $C\subseteq\K^n$ ist genau dann polyedrisch, wenn es eine
Matrix $A\in\K^{(m,n)}$ gibt mit
$$C=P(A,0).$$
\endtheorem

\beweis
Gilt $C=P(A,0)$, so ist $C$ ein Polyeder und offensichtlich ein Kegel.

Sei $C$ ein polyedrischer Kegel, dann existieren nach Definition (2.1) (c)
eine Matrix $A$ und ein Vektor $b$ mit $C=P(A,b)$.
Da jeder Kegel den Nullvektor enth"alt, gilt $0=A0 \le b$.Angenommen, es
existiert ein $\overline x\in C$ mit $A\overline x\not\le0$, d.~h.~es existiert
eine Zeile von $A$, sagen wir $A_{i\cpunkt}$, mit $t:=A_{i\cpunkt}
\overline x>0$. Da $C$ ein Kegel ist, gilt $\lambda\overline x\in C$ f\"ur
alle $\lambda\in\K_+$. Jedoch f\"ur $\overline\lambda:={b_i\over t}+1$
gilt einerseits $\overline\lambda\overline x\in C$ und andererseits
$A_{i\cpunkt}(\overline\lambda\overline x)=\overline\lambda t>b_i$, ein
Widerspruch. Daraus folgt, f\"ur alle $x\in C$ gilt $Ax\le0$.
Daraus folgt $C=P(A,0)$.
\endproof

\pagebreak
\pagestyle{empty}

\vbox{%
%\baselineskip=14.4pt
In der folgenden Tabelle 2.1 haben wir alle m\"oglichen Transformationen
aufgelistet. Sie soll als ``Nachschlagewerk'' dienen.

\begin{tabular}{|p{38mm}|p{36mm}|p{34mm}|p{45mm}|}
  \hline
& & & \mbox{}\newline \\
  \multicolumn{1}{|c|}{Transformation} & & & \\
                 
 
  \multicolumn{1}{|r|}{nach} 
  & \centerline{$\ds By \leq d$}
 
  & \centerline{$\ds
  \begin{array}{rcl}
    By &=& d\\[3mm]
    y  & \geq & 0
  \end{array}
  $}
  & \centerline{$\ds \begin{array}{rcl}
    By &\leq& d\\[3mm]
     y  & \geq & 0
  \end{array}$} \\
  \multicolumn{1}{|c|}{von} & & &\\
& & & \mbox{}\newline \\
  \hline
  \mbox{}\newline

  \centerline{$\ds  Ax=b$}
 \mbox{}\newline
  \centerline{hierbei ist}
 \mbox{}\newline
  $\ds\begin{array}{rcl}
    x_i^+ &=&\max\{ 0,x_i\}\\[3mm]
    x_i^- &=&\max\{ 0,-x_i\}
  \end{array}$


  & 

 $$\pmatrix{\hh A\cr-A\cr}y\le
                        \pmatrix{\hh b\cr-b\cr}$$
           $$y=x$$ 
 &

 $$\begin{array}{r@{\hspace*{-0mm}}l} (A,-A)\;y&=b\\[2mm]
                    y &  \ge0\\[3mm]
           y=\pmatrix{x^+\cr x^-\cr}\end{array}$$   
& 
  $$\begin{array}{r@{\hspace*{-0mm}}l}\pmatrix{\hh A&-A\cr-A&\hh A\cr}y&\le
                        \pmatrix{\hh b\cr-b\cr}\cr
                      y&\ge0\\[2mm]
           y=\pmatrix{x^+\cr x^-\cr}\end{array}$$ \mbox{}\newline \\
\hline 
& & & \mbox{}\newline \\
  \mbox{}\newline 
 \centerline{$\ds \begin{array}{rcl}
    Ax &\leq& b
    \end{array}$} 
 &  \mbox{}\newline  \centerline{$\ds \begin{array}{rcl}
    Ay &\leq& b\\[3mm]
     y  & = & x
  \end{array}$}  

 & \mbox{}\newline 
 $\ds \begin{array}{rcl}(A,-A,I)\;y=b\\[2mm]
                       y\ge0   \\[2mm]
           y=\pmatrix{x^+\cr x^-\\b-Ax}
\end{array}$
 \mbox{}\newline 
    
 &  \mbox{}\newline 
 $\ds \begin{array}{rcl}
(A,-A)\;y\le b\\[2mm]
                       y\ge0   \\[2mm]
           y=\pmatrix{x^+\cr x^-}
\end{array}$   
 \mbox{}\newline \\

\hline 
& & & \mbox{}\newline \\
  $$\begin{array}{cc}Ax&=b\\[3mm]
                       x&\ge 0\cr\end{array}$$
 &  \mbox{}\newline 
\centerline{$\ds \begin{array}{rcl}\pmatrix{\hh A\cr-A\cr-I\cr}y
                  &\le\pmatrix{\hh b\cr-b\cr\hh0\cr}\cr\end{array}$}

                 \centerline{     $y=x$}

 &   $$\begin{array}{cc}Ay&= b\\[3mm]
                       y&\ge 0\\[3mm]
           y&=x\end{array}$$

& $$\begin{array}{rll}\pmatrix{\hh A\cr-A\cr}y
                  &\le\pmatrix{\hh b\cr-b\cr}\\[3mm]
                       y&\ge0&\\[3mm]
                       y & =x& \end{array}$$ \\
\hline 
 \mbox{}\newline 
  $$\begin{array}{cc}Ax\le b\\[3mm]
                      x\ge0\cr\end{array}$$
  &  $$\pmatrix{\hh A\cr-I\cr}y
                   \le\pmatrix{b \cr 0 \cr } $$
           $$y=x$$


 &  $$\begin{array}{rl}(A,I)\;y&=b\\[3mm]
                       y&\ge0\end{array}$$
          $$ y=\pmatrix{x\cr b-Ax}$$


 & \mbox{}\newline $$\begin{array}{cc}Ay&\le b\\[3mm]
                       y&\ge 0\cr\end{array}$$
           $$y=x$$
 \mbox{}\newline \\
\hline


\end{tabular}
}

\vfill

\end{document}



%\end{document}

%\scrollmode
%\pageno=24
%\font\aa=amr10 scaled \magstep1
%\font\bb=ambx10 scaled \magstep1
%\footline={\hfil{\aa\folio}\hfil}

\def\hh{\hphantom{-}}

\setbox1=\vbox to 40truemm{\hsize34truemm%
           \vfil
           \centerline{Transformation}
           \vfil
           \rightline{nach\quad}
           \vfil
           \centerline{von}
           \vfil}
\setbox2=\vbox to 40truemm{\hsize38truemm%
           \vfil
           $$By\le d$$
           \vfil}
\setbox3=\vbox to 40truemm{\hsize34truemm%
           \vfil
           $$\begin{array}{cc}By&= d\cr
                       y&\ge 0
\end{array}$$
           \vfil}
\setbox4=\vbox to 40truemm{\hsize50truemm%
           \vfil
           $$\begin{array}{cc}By&\le d\cr
                       y&\ge 0\cr
\end{array}$$
           \vfil}

\setbox5=\vbox to 40truemm{\hsize34truemm%
           \vfil
           $$Ax=b$$
           \centerline{hierbei ist}
           $$\begin{array}{l@{\hspace*{-1mm}}l}x^+_i&=\max\{0,x_i\}\cr
                      x^-_i&=\max\{0,-x_i\}\cr\end{array}$$
           \vfil}
\setbox6=\vbox to 40truemm{\hsize38truemm%
           \vfil
           $$\pmatrix{\hh A\cr-A\cr}y\le
                        \pmatrix{\hh b\cr-b\cr}$$
           $$y=x$$
           \vfil}
\setbox7=\vbox to 40truemm{\hsize34truemm%
           \vfil
           $$\begin{array}{r@{\hspace*{-0mm}}l} (A,-A)\;y&=b\\
                    y &  \ge0\\[2mm]
           y=\pmatrix{x^+\cr x^-\cr}\end{array}$$
           \vfil}

\setbox8=\vbox to 40truemm{\hsize50truemm%
           \vfil
           $$\begin{array}{rl}\pmatrix{\hh A&-A\cr-A&\hh A\cr}y&\le
                        \pmatrix{\hh b\cr-b\cr}\cr
                      y&\ge0\\[2mm]
           y=\pmatrix{x^+\cr x^-\cr}\end{array}$$
           \vfil}

\setbox9=\vbox to 40truemm{\hsize34truemm%
           \vfil
           $$Ax\le b$$
           \vfil}

\setbox10=\vbox to 40truemm{\hsize38truemm%
           \vfil
           $$Ay\le b$$
           $$y=x$$
           \vfil}

\setbox11=\vbox to 40truemm{\hsize34truemm%
           \vfil
           $$\begin{array}{l}(A,-A,I)\;y=b\\[2mm]
                       y\ge0   \\[2mm]
           y=\pmatrix{x^+\cr x^-\\b-Ax}
\end{array}$$       
\vfil}

\setbox12=\vbox to 40truemm{\hsize50truemm%
           \vfil
           $$\begin{array}{l}(A,-A)\;y\le b\\[2mm]
                       y\ge0   \\[2mm]
           y=\pmatrix{x^+\cr x^-}
\end{array}$$
           \vfil}

\setbox13=\vbox to 40truemm{\hsize34truemm%
           \vfil
           $$\begin{array}{cc}Ax&=b\cr
                       x&\ge 0\cr\end{array}$$
           \vfil}
\setbox14=\vbox to 40truemm{\hsize38truemm%
           \vfil
           $$\begin{array}{cc}\pmatrix{\hh A\cr-A\cr-I\cr}y
                  &\le\pmatrix{\hh b\cr-b\cr\hh0\cr}\cr
                       y&=x\cr\end{array}$$
           \vfil}

\setbox15=\vbox to 40truemm{\hsize34truemm%
           \vfil
           $$\begin{array}{cc}Ay&= b\cr
                       y&\ge 0\cr
           y&=x\end{array}$$
           \vfil}

\setbox16=\vbox to 40truemm{\hsize50truemm%
           \vfil
           $$\begin{array}{cc}\pmatrix{\hh A\cr-A\cr}y
                  &\le\pmatrix{\hh b\cr-b\cr}\cr
                       y&\ge0\cr
                       y & x \end{array}$$
           \vfil}

\setbox17=\vbox to 40truemm{\hsize34truemm%
           \vfil
           $$\begin{array}{cc}Ax\le b\cr
                      x\ge0\cr\end{array}$$
           \vfil}
\setbox18=\vbox to 40truemm{\hsize38truemm%
           \vfil
           $$\pmatrix{\hh A\cr-I\cr}y
                   \le\pmatrix{b \cr 0 \cr } $$
           $$y=x$$
           \vfil}
\setbox19=\vbox to 40truemm{\hsize34truemm%
           \vfil
           $$\begin{array}{cc}(A,I)\;y&=b\cr
                       y&\ge0\cr
           y=\pmatrix{x\cr b-Ax} \end{array}$$
           \vfil}

\setbox20=\vbox to 40truemm{\hsize50truemm%
           \vfil
           $$\begin{array}{cc}Ay&\le b\cr
                       y&\ge 0\cr\end{array}$$
           $$y=x$$
           \vfil}

\vbox{%
\baselineskip=14.4pt
In der folgenden Tabelle 2.1 haben wir alle m\"oglichen Transformationen
aufgelistet. Sie soll als ``Nachschlagewerk'' dienen.}

$$\vbox{\offinterlineskip
  \halign
    {&\vrule width 1.42truept#&#&
      \vrule width 1.42truept#&#&
      \vrule #&#&
      \vrule #&#&
      \vrule width 1.42truept#\cr
  \noalign{\hrule height 1.42truept}
  &\box1  &&\box2  &&\box3  &&\box4  &\cr
  \noalign{\hrule height 1.42truept}
  &\box5  &&\box6  &&\box7  &&\box8  &\cr
  \noalign{\hrule}
  &\box9  &&\box10 &&\box11 &&\box12 &\cr
  \noalign{\hrule}
  &\box13 &&\box14 &&\box15 &&\box16 &\cr
  \noalign{\hrule}
  &\box17 &&\box18 &&\box19 &&\box20 &\cr
\noalign{\hrule height 1.42truept}
}
\vskip 10truemm
\centerline{\bf Tabelle 2.1}
}$$