\documentclass[a4paper,12pt]{scrartcl} % Papierformat
\usepackage[ngerman]{babel}
%\usepackage{ngerman} % Deusche Rechtschreibung
\usepackage{amssymb} % Paket für R-, N-, Q-Symbole
\usepackage[latin1]{inputenc}  % Zeichencodierung
%\usepackage[right]{eurosym}   % Das Euro-Zeichen ist hier drin
\usepackage{pst-pdf,pstricks,pst-plot,pst-node,pst-circ}
%\usepackage{wasysym}  % Isländische Zeichen
\usepackage{color}
\usepackage{ifpdf}    % "workaround" um Fehler in hyperref mit pstricks
\ifpdf                %
\usepackage{hyperref} %
\fi                   %
\setlength{\fboxrule}{1pt} % Breite der Umrandung
\usepackage{amsmath}
\usepackage{graphicx} % Einbinden von Grafik
\usepackage{wrapfig} % Paket für Umfließen der Grafik
%\usepackage{caption} % Bildunterschrift
%\captionsetup{labelformat=empty} % Keine Nummerierung der Bilder
\usepackage{units}     % Einheiten in Formeln
%\usepackage{rotating} % vertikales Beschriften in Tabelle
%\pagestyle{empty}    % ohne Seitennummerierung
\widowpenalty=10000
\clubpenalty=10000
\setlength{\parindent}{0pt} % kein Einrücken nach Abschnitt
\begin{document}

\title{Lineares Optimieren}
\author{W. Kippels}
\maketitle
\tableofcontents
\newpage

\section{Einleitung}
Hier soll das Verfahren des Linearen Optimierens an einem Beispiel in Kurzform
vor\-ge\-führt werden. Auf die Hintergründe soll an dieser Stelle nicht eingegangen
werden.\\

\section{Die Beispielaufgabe}
\begin{wrapfigure}{r}{10cm}
\psset{xunit=10mm,yunit=10mm}
\begin{pspicture}(-0.8,-0.8)(8.8,6.8)
  \psline*[linewidth=1.5pt,linecolor=lightgray]
     (0,0)(0,5.4)(2,5)(4,4)(6,2)(7,0)(0,0)
  \psgrid[subgriddiv=5,griddots=0,
          subgridwidth=0.1pt,
          subgridcolor=black!15,
          gridcolor=black!50,
          xunit=1,yunit=1]
  \psaxes[linewidth=1.8pt,Dx=1,Dy=1]{->}(0,0)(-0.8,-0.8)(8.8,6.8)
  \uput[-90](8.5,0){$x_1$}  \uput[180](0,6.5){$x_2$}
  \psline[linewidth=1pt](0,6)(12,0)
  \psline[linewidth=1pt](0,8)(8,0)
  \psline[linewidth=1pt](0,5.4)(27,0)
  \psline[linewidth=1pt](0,14)(7,0)
\end{pspicture}
\end{wrapfigure}

Die Zielfunktion, die \textbf{maximal} werden soll, lautet:
\[z=3x_1+2x_2\]

Die Bedingungen lauten:
\[\begin{array}{|rrcr|}
\hline
x_1&+2x_2&\leq&12 \\
2x_1&+2x_2&\leq&16 \\
x_1&+5x_2&\leq&27 \\
2x_1&+x_2&\leq&14 \\
\hline
\end{array}\]
\[ \textnormal{mit } x_1,x_2 \geq 0\]
\enlargethispage{10mm}
Nebenstehend ist der Bereich graphisch dargestellt, der sich aus den
Ungleichungen ergibt. Alle Werte, die zulässig sind, liegen in dem grau
unterlegten Bereich.\\

\section{Einführung von Schlupfvariablen}
Mit den Hilfsvariablen $x_4$, $x_5$ und $x_6$, den sogenannten
"`Schlupfvariablen"', die alle $\geq 0$ sein müssen, werden aus den
Ungleichungen Gleichungen. Sie kennzeichnen den "`Rest"', der bis zur
Obergrenze in der Ungleichung noch frei bleibt.
\[\begin{array}{|rrrcr|}
\hline
x_1&+2x_2&+\textcolor{red}{x_3}&=&12 \\
2x_1&+2x_2&+\textcolor{red}{x_4}&=&16 \\
x_1&+5x_2&+\textcolor{red}{x_5}&=&27 \\
2x_1&+x_2&+\textcolor{red}{x_6}&=&14 \\
\hline
\end{array}\]
\[ \textnormal{mit } x_1,x_2,x_3,x_4,x_5,x_6 \geq 0\]
Hierdurch hat sich zwar die Zahl der Variablen erhöht, aber anstelle der
Ungleichungen haben wir nun die einfacher zu handhabenden
Vorzeichenbeschränkungen der Variablen erhalten.\\

Wir ordnen das Ganze und bringen es in die \emph{kanonische} Form.
\[\begin{array}{|rrrrrrrrcr|}
\hline
z&=&3x_1&+2x_2&&&&&\rightarrow&\textnormal{max}\\
&&x_1&+2x_2&+x_3&&&&=&12 \\
&&2x_1&+2x_2&&+x_4&&&=&16 \\
&&x_1&+5x_2&&&+x_5&&=&27 \\
&&2x_1&+x_2&&&&+x_6&=&14 \\
\hline
\end{array}\]
\[ \textnormal{mit } x_1,x_2,x_3,x_4,x_5,x_6 \geq 0\]

\section{Die Simplex-Methode}
Der optimale Wert der Zielfunktion liegt auf einem Eckpunkt des zulässigen
Bereiches, der als Schnittpunkt zweier Begrenzungsgeraden des Systems
dargestellt werden kann, wenn man es graphisch veranschaulicht.\footnote{Die
Veranschaulichung klappt leider nur im $\mathbb{R}^2$ und im $\mathbb{R}^3$. Im
$\mathbb{R}^3$ schneiden sich drei Ebenen, im $\mathbb{R}^4$ würden sich vier
dreidimensionale Räume schneiden, was mit unserer Vorstellung nicht kompatibel
ist.} Dazu gehört immer eine \emph{Basislösung} des Li\-ne\-ar\-glei\-chungs\-sys\-tems.\\

Es gibt stets nur \textbf{endlich viele} Basislösungen des
Li\-ne\-ar\-glei\-chungs\-sys\-tems. Man könnte die nun einfach \textbf{alle} durchrechnen,
was aber um so aufwändiger wird, je mehr Gleichungen und Variablen vorhanden
sind. Der Trick der \emph{Simplex-Methode} besteht nun darin, sich von einem
beliebigen Startpunkt aus so durch die Basis-Lösungen zu "`hangeln"', dass sich
der Wert der Zielfunktion jeweils verbessert. Damit muss man weniger
Basislösungen durchrechnen.\\

Zunächst muss die Zielfunktion noch in das Li\-ne\-ar\-glei\-chungs\-sys\-tem eingefügt
werden. Dazu müssen alle Variablen auf die linke Seite gebracht werden.
\[\begin{array}{rcll}
z&=&3x_1+2x_2 &|-3x_1-2x_2 \\
-3x_1-2x_2+z&=&0 \\
\end{array}\]
Fügt man dieses Ergebnis in das Li\-ne\-ar\-glei\-chungs\-sys\-tem ein, erhält man
folgendes System:
\[\begin{array}{|rrrrrrrcr|}
\hline
x_1&+2x_2&+x_3&&&&&=&12 \\
2x_1&+2x_2&&+x_4&&&&=&16 \\
x_1&+5x_2&&&+x_5&&&=&27 \\
2x_1&+x_2&&&&+x_6&&=&14 \\
-3x_1&-2x_2&&&&&+z&=&0 \\
\hline
\end{array}\]

Die Ba\-sis\-va\-ri\-ab\-len sind die Variablen in der Diagonale in diesem
Li\-ne\-ar\-glei\-chungs\-sys\-tem. Alle Nicht-Ba\-sis\-va\-ri\-ab\-len -- das sind die Variablen in
den vorderen Spalten, die in jeder Gleichung vorkommen -- nehmen den Wert 0 an.
Setzt man diese Nullen im
Li\-ne\-ar\-glei\-chungs\-sys\-tem ein (hier für $x_1$ und $x_2$), dann erkennt man sofort,
dass die Werte auf den rechten Seiten der Gleichungen unmittelbar die Werte der
Ba\-sis\-va\-ri\-ab\-len (hier $x_3$, $x_4$, $x_5$, $x_6$ und $z$) darstellen.\\

Das Li\-ne\-ar\-glei\-chungs\-sys\-tem liegt in kanonischer Form vor. Deshalb kann es in
ein Tableau geschrieben werden, wie es auch im Basis-Austausch-Verfahren
verwendet wird. In diesem Lösungsverfahren nennen wir es
\emph{Simplex-Tableau}. Der Zweck dieses Tableaus ist ein ganz einfacher: Der
Mathematiker ist von Natur aus faul. Deshalb versucht er gern, Sachverhalte so
aufzuschreiben, dass es möglichst wenig Arbeit macht. Deshalb enthält das
Tableau nur die unverzichtbaren Werte in geordneter Form, möglichst ohne jede
Redundanz.\\

Zur Anfangsbasislösung $x^{(0)}$ gehört folgendes Tableau:
\[\begin{array}{|c|rr|r|}
\hline
x^{(0)} & x_1 & x_2 & \textbf{1}\\
\hline
x_3 & 1 & 2 & 12 \\
x_4 & 2 & 2 & 16 \\
x_5 & 1 & 5 & 27 \\
x_6 & 2 & 1 & 14 \\
\hline
z   & -3& -2 & 0 \\
\hline
\end{array}\]

Zu diesem Tableau gehört die Anfangsbasislösung:
\[x^{(0)}=(0;0|12;16;27;14)^\tau \]

Zunächst muss erläutert werden, wie dieses Tableau aufgebaut ist. Oben links
ist die Bezeichnung der Basislösung angegeben. Auf diese Bezeichnung kann man
sich im Folgenden beziehen. (Nach und nach werden verschiedene Basislösungen
erstellt, bei denen einfach der Index (0) schrittweise hochgezählt wird.) \\

Die Ba\-sis\-va\-ri\-ab\-len -- das sind wie gesagt die Variablen in der Diagonale im
Li\-ne\-ar\-glei\-chungs\-sys\-tem -- stehen in der ersten Spalte. Die zugehörigen Lösungen
-- also die Werte aus den rechten Gleichungsseiten -- stehen in der letzten
Spalte unter der sym\-bo\-li\-schen \textbf{1} als Überschrift. In den Spalten
dazwischen stehen die Koeffizienten der Nicht-Ba\-sis\-va\-ri\-ab\-len unter den
zugehörigen Überschriften. In der letzten Spalte stehen die entsprechenden
Parameter der Zielfunktion, wobei ganz unten der Wert (das Ergebnis) der
Zielfunktion steht -- hier zunächst der Wert 0, denn wenn man \mbox{$x_1=0$}
und \mbox{$x_2=0$} in die Zielfunktion einsetzt, ergibt sich:
\[z^{(0)}=z \left( x^{(0)} \right) =0\]

\section{Das Basis-Austauschverfahren}
Bevor wir im Beispiel weiterarbeiten können, möchte ich zunächst das
Ba\-sis-Aus\-tausch\-ver\-fah\-ren erläutern. Hierbei wird schlicht eine Ba\-sis\-va\-ri\-ab\-le
zu ei\-ner Nicht-Ba\-sis\-va\-ri\-ab\-le und umgekehrt. Sie tauschen also sozusagen ihre
Rollen. Zum Algorithmus gehören vier Schritte, die ich hier an einem anderen
Beispiel erläutern möchte.\\

Gegeben sei ein Li\-ne\-ar\-glei\-chungs\-sys\-tem, das sich mit dieser Matrix darstellen
lässt:
\[ \left( \begin{array}{cccc|c}
1 & 0 & 0 &\frac{3}{2} & 5 \\
0 & 1 & 0 &-\frac{5}{2}& 6 \\
0 & 0 & 1 &-\frac{1}{2}& 9 \\
\end{array}\right) \]

Das Li\-ne\-ar\-glei\-chungs\-sys\-tem lässt sich kürzer mit diesem Tableau darstellen:

\[\begin{array}{|c|c|c|}
\hline
& x_4 & \textbf{1}\\
\hline
x_1 & \frac{3}{2} & 5 \\
x_2 & -\frac{5}{2} & 6 \\
x_3 & -\frac{1}{2} & 9 \\
\hline
%\hline
%& \uparrow & -2 \\
%\hline
\end{array}\]

Hierbei sind $x_1$, $x_2$ und $x_3$ die Ba\-sis\-va\-ri\-ab\-len, $x_4$ ist eine
Nicht-Ba\-sis\-va\-ri\-ab\-le. Im nun folgenden Schritt soll $x_4$ eine Ba\-sis\-va\-ri\-ab\-le
werden. Im Beispiel soll dafür $x_3$ zu ei\-ner Nicht-Ba\-sis\-va\-ri\-ab\-len werden.
$x_3$ und $x_4$ tauschen also ihre Rollen. Hierzu sind \textbf{vier} Schritte
notwendig.\\

\paragraph{Schritt 1:} Ein Pivot-Element wird ausgewählt und markiert. Das ist
das Element, das am Schnittpunkt der Zeile und der Spalte der Variablen steht,
die gegeneinander ausgetauscht werden. Wichtig: Hier darf keine Null stehen!\\

Ein neues Tableau wird angelegt. Hierin sind die Variablennamen entsprechend
ausgetauscht (hier also $x_3$ gegen $x_4$). Anstelle des markierten
Pivot-Elementes wird hier sofort sein \textbf{Kehrwert} eingetragen.\\

\begin{tabular}{|c|c|c|}
\hline
& $x_4$ & \textbf{1}\\
\hline
$x_1$ & $\frac{3}{2}$ & 5 \\
$x_2$ & $-\frac{5}{2}$ & 6 \\
$x_3$ & \fcolorbox{red}{yellow}{$-\frac{1}{2}$} & 9 \\
\hline
\end{tabular}\quad $\Longrightarrow$ \quad \begin{tabular}{|c|c|c|}
\hline
& $x_3$ & \textbf{1}\\
\hline
$x_1$ &  &  \\
$x_2$ &  &  \\
$x_4$ & $-2$ &  \\
\hline
\end{tabular}\\

\paragraph{Schritt 2:}
Eine Arbeitszeile wird unter dem ursprünglichen Tableau angelegt. Dazu
dividiert man jedes Element der Pivot-Zeile (mit Ausnahme des Pivot-Elementes
selbst) durch das Pivot-Element (hier: $-\frac{1}{2}$). In unserem Beispiel ist
das nur ein einziges Element in der letzten Spalte. Ein Pfeil $\uparrow$ als
Platzhalter zeigt auf des Pivot-Element.\\

Diese Arbeitszeile stellt gleichzeitig die neuen Elemente in der Pivot-Zeile
dar. Die Werte (in unserem Beispiel nur ein einziger Wert) werden in die neue
Pivot-Zeile eingetragen.\\

\[\cfrac{9}{-\frac{1}{2}}=-18\]

\begin{tabular}{|c|c|c|}
\hline
& $x_4$ & \textbf{1}\\
\hline
$x_1$ & $\frac{3}{2}$ & 5 \\
$x_2$ & $-\frac{5}{2}$ & 6 \\
$x_3$ & \fcolorbox{red}{yellow}{$-\frac{1}{2}$} & 9 \\
\hline
\end{tabular}\quad $\Longrightarrow$ \quad \begin{tabular}{|c|c|c|}
\hline
& $x_3$ & \textbf{1}\\
\hline
$x_1$ &  &  \\
$x_2$ &  &  \\
$x_4$ & $-2$ & $-18$\\
\hline
\end{tabular}\\
\textcolor{white}{.}\hspace{11mm} $\uparrow$ \hspace{2mm} $-18$ \\

\paragraph{Schritt 3:}
Nach dem gleichen Verfahren werden nun die Elemente der neuen Pivot-Spalte
berechnet. Diese müssen jedoch zusätzlich mit dem Faktor $(-1)$ multipliziert
werden.\\
\[-\cfrac{\frac{3}{2}}{-\frac{1}{2}}=3\]
\[-\cfrac{-\frac{5}{2}}{-\frac{1}{2}}=-5\]

\begin{tabular}{|c|c|c|}
\hline
& $x_4$ & \textbf{1}\\
\hline
$x_1$ & $\frac{3}{2}$ & 5 \\
$x_2$ & $-\frac{5}{2}$ & 6 \\
$x_3$ & \fcolorbox{red}{yellow}{$-\frac{1}{2}$} & 9 \\
\hline
\end{tabular}\quad $\Longrightarrow$ \quad \begin{tabular}{|c|c|c|}
\hline
& $x_3$ & \textbf{1}\\
\hline
$x_1$ & $3$ &  \\
$x_2$ & $-5$ &  \\
$x_4$ & $-2$ & $-18$\\
\hline
\end{tabular}\\
\textcolor{white}{.}\hspace{11mm} $\uparrow$ \hspace{2mm} $-18$ \\

\paragraph{Schritt 4:}
Nun müssen noch alle übrigen Elemente des neuen Tableaus berechnet werden. Als
Rechenhilfe dazu wurde die Arbeitszeile unter dem alten Tableau angelegt. Man
sucht sich zunächst für jedes neu zu bildende Element aus dem alten Tableau das
zugehörige Element aus der Pivot-Spalte (gleiche Zeile, aber in der Spalte mit
dem Pfeil $\uparrow$) und multipliziert es mit dem Wert in der Arbeitszeile,
der senkrecht unter dem zu ersetzenden Element steht. Dieses Produkt wird nun
von dem alten Element subtrahiert und man erhält das neue Element.

\begin{center}
$5-\frac{3}{2} \cdot (-18)=5+27=32$\\
$6- \left(-\frac{5}{2}\right) \cdot (-18)=6-45=-39$
\end{center}

\begin{tabular}{|c|c|c|}
\hline
& $x_4$ & \textbf{1}\\
\hline
$x_1$ & $\frac{3}{2}$ & 5 \\
$x_2$ & $-\frac{5}{2}$ & 6 \\
$x_3$ & \fcolorbox{red}{yellow}{$-\frac{1}{2}$} & 9 \\
\hline
\end{tabular}\quad $\Longrightarrow$ \quad \begin{tabular}{|c|c|c|}
\hline
& $x_3$ & \textbf{1}\\
\hline
$x_1$ & $3$ & 32 \\
$x_2$ & $-5$ & $-39$ \\
$x_4$ & $-2$ & $-18$\\
\hline
\end{tabular}\\
\textcolor{white}{.}\hspace{11mm} $\uparrow$ \hspace{2mm} $-18$ \\

Damit ist der Austausch komplett durchgeführt.

\section{Fortsetzung der Simplex-Methode}
Nachdem wir uns das Verfahren des Basisaustausches in Erinnerung gerufen haben,
können wir zu unserem ursprünglichen Problem zurückkehren.\\

Wir erinnern uns: Es kommt nun darauf an, mehrfach einen Basisaustausch
durch\-zu\-füh\-ren, \textbf{so dass der Wert der Zielfunktion dabei jedes mal
zunimmt}, und ohne dass eine Basislösung \textbf{negativ} wird, wodurch der
zulässige Bereich verlassen würde. Es dürfen also nicht "`blind"' irgendwelche
Austausche durchgeführt werden, man muss \textbf{vorher} prüfen, welcher
Austausch vorteilhaft ist. Ohne hier näher auf die Hintergründe einzugehen kann
gesagt werden, dass diese Bedingungen erfüllt sind, wenn man folgendermaßen
vorgeht. Schaun wir uns dazu noch einmal das zuvor erstellte Simplex-Tableau
an.\\

Zur Anfangsbasislösung $x^{(0)}$ gehört folgendes Tableau:
\[\begin{array}{|c|rr|r|}
\hline
x^{(0)} & x_1 & x_2 & \textbf{1}\\
\hline
x_3 & 1 & 2 & 12 \\
x_4 & 2 & 2 & 16 \\
x_5 & 1 & 5 & 27 \\
x_6 & 2 & 1 & 14 \\
\hline
z   & -3& -2 & 0 \\
\hline
\end{array}\]

Zunächst sucht man sich eine Nicht-Ba\-sis\-va\-ri\-ab\-le aus, die man tauschen möchte.
Kriterium ist dabei, dass sich nur dann der Wert der Zielfunktion vergrößert,
wenn der $z$-Wert unter der Nicht-Ba\-sis\-va\-ri\-ab\-len \textbf{negativ} ist. In der
Anfangsbasislösung ist das in unserem Beispiel sowohl für $x_1$ als auch für
$x_2$ gegeben. Das ist auch logisch so, denn in der Anfangsbasislösung ist der
Wert der Zielfunktion noch Null. Bei späteren Schritten wird das nicht so
sein.\\

Nun muss festgelegt werden, gegen welche Ba\-sis\-va\-ri\-ab\-le getauscht wird. Nachdem
man die Nicht-Ba\-sis\-va\-ri\-ab\-le nach vorstehendem Punkt festgelegt hat (im Beispiel
habe ich dazu willkürlich $x_1$ ausgewählt), fügt man sinnvollerweise eine
weitere Spalte an das Tableau an. Die Überschrift $Q$ deutet an, es ist ein
Quotient. Man dividiert den Wert aus der letzten Spalte durch den Wert in der
Spalte der auszutauschenden Nicht-Ba\-sis\-va\-ri\-ab\-len. In dieser Hilfsspalte sucht
man nun den kleinsten Wert. Der gehört zur auszutauschenden Ba\-sis\-va\-ri\-ab\-len.

\textbf{Wichtig: Wählt man nicht den -- bzw. einen der gleich kleinen --
kleinsten Werte aus, wird beim nächsten Schritt ein Wert negativ, und man
verlässt dadurch den Definitionsbereich ei\-ner Variablen!}\\

\newpage
\begin{center}
\begin{tabular}{|c|cc|c|}
\hline
$x^{(0)}$ & $x_1$ & $x_2$ & \textbf{1}\\
\hline
$x_3$ & 1 & 2 & 12 \\
$x_4$ & 2 & 2 & 16 \\
$x_5$ & 1 & 5 & 27 \\
$x_6$ & \fcolorbox{red}{yellow}{2} & 1 & 14 \\
\hline
$z$  & $-3$& $-2$ & 0 \\
\hline
\end{tabular}\begin{tabular}{cc}
$Q$ \\
12 \\
8 \\
27 \\
7 & $\leftarrow$ min \\
\\
\end{tabular}\\
$\uparrow$\hspace{30mm}\textcolor{white}{.}\\
\end{center}

In unserem Beispiel steht damit fest, dass $x_1$ gegen $x_6$ getauscht werden
muss. Führen wir das nun durch.\\

\begin{tabular}{|c|cc|c|}
\hline
$x^{(0)}$ & $x_1$ & $x_2$ & \textbf{1}\\
\hline
$x_3$ & 1 & 2 & 12 \\
$x_4$ & 2 & 2 & 16 \\
$x_5$ & 1 & 5 & 27 \\
$x_6$ & \fcolorbox{red}{yellow}{2} & 1 & 14 \\
\hline
$z$  & $-3$& $-2$ & 0 \\
\hline
\end{tabular} \quad $\Longrightarrow$ \quad
\begin{tabular}{|c|cc|c|}
\hline
$x^{(1)}$ & $x_6$ & $x_2$ & \textbf{1}\\
\hline
$x_3$ & $-0{,}5$ & 1,5 & 5 \\
$x_4$ & $-1$ & 1 & 2 \\
$x_5$ & $-0{,}5$ & 4,5 & 20 \\
$x_1$ & 0,5 & 0,5 & 7 \\
\hline
$z$  & 1,5 & $-0{,}5$ & 21 \\
\hline
\end{tabular}\begin{tabular}{cc}
$Q$ \\
3,33 \\
2& $\leftarrow$ \\
4,44 \\
14 & \\
\\
\end{tabular}\\
\textcolor{white}{.}\hspace{12mm} $\uparrow$ \hspace{3mm} 0,5 \hspace{3mm} 7
 \hspace{48mm} $\uparrow$ \\

Man sieht, dass bei diesem Schritt der Wert der Zielfunktion auf 21 angewachsen
ist. Weiterhin sieht man, dass nur $x_2$ als Nicht-Ba\-sis\-va\-ri\-ab\-le getauscht
werden kann, da nur hier in der $z$-Zeile ein \textbf{negativer} Wert steht.
Die Hilfsspalte mit den Quotienten steht schon dahinter. Hier ergibt sich, dass
bei $x_4$ der kleinste Wert steht. Der nächste Tausch muss also $x_4$ gegen
$x_2$ sein. \textbf{Steht jetzt in der Spalte der Basislösungen (unter der 1)
ein negativer Wert, dann hat man zuvor irgendetwas falsch gemacht!}\\

\begin{tabular}{|c|cc|c|}
\hline
$x^{(1)}$ & $x_6$ & $x_2$ & \textbf{1}\\
\hline
$x_3$ & $-0{,}5$ & 1,5 & 5 \\
$x_4$ & $-1$ & \fcolorbox{red}{yellow}{1} & 2 \\
$x_5$ & $-0{,}5$ & 4,5 & 20 \\
$x_1$ & 0,5 & 0,5 & 7 \\
\hline
$z$  & 1,5 & $-0{,}5$ & 21 \\
\hline
\end{tabular} \quad $\Longrightarrow$ \quad
\begin{tabular}{|c|cc|c|}
\hline
$x^{(2)}$ & $x_6$ & $x_4$ & \textbf{1}\\
\hline
$x_3$ & 1 & $-1{,}5$ & 2 \\
$x_2$ & $-1$ & 1 & \textcolor{red}{2} \\
$x_5$ & 4 & $-4{,}5$ & 11 \\
$x_1$ & 1 & $-0{,}5$ & \textcolor{red}{6} \\
\hline
$z$  & 1 & 0,5 & \textcolor{red}{22} \\
\hline
\end{tabular}\\
\textcolor{white}{.}\hspace{13mm}$-1$ \hspace{7mm} $\uparrow$ \hspace{5mm} 2 \\

In der $z$-Zeile stehen jetzt nur noch positive Werte. Das bedeutet, wir haben
den optimalen Wert der Zielfunktion mit 22 erreicht. Auch in der Spalte unter
der sym\-bo\-li\-schen \textbf{1} stehen -- wie erforderlich -- ausschließlich
positive Werte. Die Ergebnisse für $x_1$ und $x_2$ können abgelesen werden.
\begin{center}
\fcolorbox{red}{yellow}{$x_1=6$}\qquad  \fcolorbox{red}{yellow}{$x_2=2$}
\end{center}

Schaut man in die Grafik, dann kann man diese Lösung als Eckpunkt im Polygonzug
erkennen.
\begin{center}
\psset{xunit=10mm,yunit=10mm}
\begin{pspicture}(-0.8,-0.8)(8.8,6.8)
  \psline*[linewidth=1.5pt,linecolor=lightgray]
     (0,0)(0,5.4)(2,5)(4,4)(6,2)(7,0)(0,0)
  \psgrid[subgriddiv=5,griddots=0,
          subgridwidth=0.1pt,
          subgridcolor=black!15,
          gridcolor=black!50,
          xunit=1,yunit=1]
  \psaxes[linewidth=1.8pt,Dx=1,Dy=1]{->}(0,0)(-0.8,-0.8)(8.8,6.8)
  \uput[-90](8.5,0){$x_1$}  \uput[180](0,6.5){$x_2$}
  \psline[linewidth=1pt](0,6)(12,0)
  \psline[linewidth=1pt](0,8)(8,0)
  \psline[linewidth=1pt](0,5.4)(27,0)
  \psline[linewidth=1pt](0,14)(7,0)
  \pscircle*[linecolor=red](6,2){2pt}
   \uput[-10](6,2){\textcolor{red}{Maximum}}
\end{pspicture}
\end{center}

\end{document}
%\begin{wrapfigure}{r}{9cm}
%\includegraphics[width=\linewidth]{Bilddatei}
%\caption{Bildunterschrift}
%\end{wrapfigure}
%\pagecolor{yellow}    % setzt Hintergrundfarbe für die Seite
%\color{red}           % Schreibt ab hier mit Farbe
%\color[rgb]{0,0.5,0}  % Farbe aus Anteilen zusammensetzen; Anteile: 0..1
%\textcolor{red}{text} % Schreibt vorübergehend mit Farbe
%\fcolorbox{red}{yellow}{Text} % Umrandet Text auf gelb mit rot
%\ifpdf \htmladdnormallink{text}{URL}\fi
%\rput{Winkel}(Drehpunkt){Objekt} % Drehen eines Objektes
%\ifpdf \hyperlink{label}{Text}\fi
%\ifpdf \hypertarget{label}{Text}\fi
%\begin{sideways}Beschriftung \end{sideways} % vertikale Schrift in Tabelle
%\EUR{185}
% \^=                  % "entspricht"
