1 files changed, 47 insertions, 20 deletions
diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex
index aad45cc..0c23c7c 100644
--- a/buch/papers/munkres/teil1.tex
+++ b/buch/papers/munkres/teil1.tex
@@ -3,21 +3,28 @@
 %
 % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
 %
-\section{Beschrieb des Zuordnungsproblems
+\section{Das Zuordnungsproblems
 \label{munkres:section:teil1}}
-\rhead{Problemstellung}
+\rhead{Zuordnungsproblem}
 
 Das Spezielle an einem Zuordnungsproblem ist, dass es an jedem Ort nur eine Einheit angeboten bzw. nachgefragt wird. Es werden hier nicht Mengen möglichst kostenminimal von einem zum anderen
-Ort transportiert, sondern es geht um die kostenminimale Zuordnung von z.B. Personen oder Bau-Maschinen auf bestimmte Orte, Stellen oder Aufgaben.
-Um dieses Problem in einer einfachen, händischen Art und Weise zu lösen wurde der Munkres-Algorithmus, auch die Ungarische Methode genannt, entwickelt. Diese Methode ist ein weiteres Hauptthema dieses Kapitels.
+Ort transportiert, sondern es geht um die kostenminimale Zuordnung von z.~B.~Personen oder Bau-Maschinen auf bestimmte Orte, Stellen oder Aufgaben.
+Um dieses Problem in einer einfachen, händischen Art und Weise zu lösen wurde der Munkres-Algorithmus, auch die ungarische Methode genannt, entwickelt. Diese Methode ist ein weiteres Hauptthema dieses Kapitels.
+\index{Munkres-Algorithmus}%
+\index{ungarische Methode}%
 
 \subsection{Zuordnungsproblem an einem konkreten Beispiel
 \label{munkres:subsection:bonorum}}
 Als Beispiel betrachten wir den Fall, wo ein Bauunternehmer einen Bauingenieur beauftragt, eine optimale Transportroute für die Umplatzierung seiner Kräne zu eruieren. Das heisst, die Transportstrecke für die Umplatzierung seine Kräne
 soll möglichst klein werden. 
 Die Frage lautet: Wie sind die Kräne umzusetzen, damit deren Transportstrecke minimal wird? Bei der normalen Optimierung dürfen normalerweise beliebige reelle Werte $\mathbb{R}$ angenommen werden. 
-Beim Beispiel mit den Kräne gibt es aber ein Problem. Bei der Suche nach der optimalen Lösung darf  nur die Methode der ganzzahligen Optimierung gewählt werden. Materialien kann man aufteilen, jedoch Maschinen nicht. Die Bauarbeiter auf der neuen Baustelle benötigen einen ganzen Kran und nicht nur einen halben Kran. Es muss immer ein ganzer Kran (Anzahl 1) von A nach B oder gar kein Kran (Anzahl 0) verschoben werden. 
-Für solche Optimierungsprobleme für reelle Variablen sind verschiedene Verfahren entwickelt worden, die im Allgemeinen auch sehr effizient sind. Das reelle Problem ist also in einer einfachen Art und Weise lösbar. Doch das Problem bleibt, wie in der Illustration oben ersichtlich. Es kann mit ganzzahligen Punkten kein Optimum erzielt werden. Das Ziel ist es an das Optimum so nah wie möglich heranzukommen und dies ist eine vergleichsweise träge und langsame Angelegenheit.
+\index{Optimierung}%
+Für solche Optimierungsprobleme für reelle Variablen sind verschiedene Verfahren entwickelt worden, die im Allgemeinen auch sehr effizient sind. Das reelle Problem ist also in einer einfachen Art und Weise lösbar.
+
+Beim Beispiel der Kräne gibt es aber ein Problem. Bei der Suche nach der optimalen Lösung darf  nur die Methode der ganzzahligen Optimierung gewählt werden. Materialien kann man aufteilen, jedoch Maschinen nicht. Die Bauarbeiter auf der neuen Baustelle benötigen einen ganzen Kran und nicht nur einen halben Kran. Es muss immer ein ganzer Kran (Anzahl 1) von $A$ nach $B$ oder gar kein Kran (Anzahl 0) verschoben werden. 
+\index{ganzzahlige Optimierung}%
+\index{Optimierung, ganzzahlig}%
+Es entsteht das Problem, wie in der Illustration~\ref{munkres:Vr2} ersichtlich. Es kann mit ganzzahligen Punkten kein Optimum erzielt werden. Das Ziel ist es an das Optimum so nah wie möglich heranzukommen und dies ist eine vergleichsweise träge und langsame Angelegenheit.
 
 \begin{figure}
 \centering
@@ -30,11 +37,11 @@ Für solche Optimierungsprobleme für reelle Variablen sind verschiedene Verfahr
 \subsection{Zuordnungsproblem abstrakt
 \label{munkres:subsection:bonorum}}
 
-In einem Zuordnungsproblem sind alle Angebots- und Bedarfsmengen gleich 1 
+In einem Zuordnungsproblem sind alle Angebots- und Bedarfsmengen gleich 1:
 \begin{equation}
-a_{i}=b_{j}=1
+a_{i}=b_{j}=1.
 \end{equation}
-Das Ziel ist es die Gesamtkosten zu minimieren. Mit Hilfe einer $n\times n$ Matrix 
+Das Ziel ist, die Gesamtkosten zu minimieren. Mit Hilfe einer $n\times n$ Matrix 
 \[
 A
 =
@@ -47,21 +54,41 @@ a_{n1}&a_{n2}&\dots &a_{nn}
 \in \mathbb{R}^{n,n}
 \]
 kann der Faktor Kosten mit in die Rechnung eingebracht werden.
-In den Zellen dieser Matrix sind die Zahlen $a_{i,j}$ dargestellt, welche den Weg in z.B. Kilometer beschreiben.
-Sie entstehen, wenn man z.B. einem Kran $i$ dem Einsatzort $j$ zuordnet.
+In den Zellen dieser Matrix sind die Zahlen $a_{i,j}$ dargestellt, welche den Weg in z.~B.~Kilometer beschreiben.
+Sie entstehen, wenn man z.~B.~einem Kran $i$ dem Einsatzort $j$ zuordnet.
 
 \subsection{Alternative Darstellungen des Zuordnungsproblems
 \label{munkres:subsection:bonorum}}
 \subsubsection{Netzwerk}
-Ein (Fluss- oder Transport-) Netzwerk (engl. network) ist ein zusammenhängender Graph, bei dem jede Kante einen Fluss aufnehmen kann und jede Kante eine Kapazität für den Fluss hat. Die Menge des Flusses auf einer Kante kann die Kapazität der Kante nicht überschreiten. Ein Fluss muss die Einschränkung erfüllen, dass die Menge des Flusses in einen Knoten gleich der Menge des Flusses aus ihm heraus ist. Ein Fluss-Netzwerk (engl. flow network) ist ein Netzwerk, dessen Kanten zusätzlich Kosten pro Mengeneinheit des Flusses zugeordnet sind. Typischerweise will man einen Fluss durch die Kanten bestimmen, der den Einschränkungen des Netzwerks genügt und dessen Gesamtkosten minimal sind. Im Bild 21.2 dargestellt sind in den eckigen Klammern links die externen Flüsse $[1]$ für jeden Kran und in den eckigen Klammern rechts eine $[-1]$ für jeden Baustellenort. Die Kosten sind entlang der Kanten als Zahlen in Klammern dargestellt.  
+Ein Fluss- oder Transportnetzwerk (engl.~network) ist ein zusammenhängender Graph, bei dem jede Kante einen Fluss aufnehmen kann und jede Kante eine Kapazität für den Fluss hat.
+\index{Flussnetzwerk}%
+\index{Transportnetzwerk}%
+\index{zusammenhängend}%
+\index{Fluss}%
+\index{Kapazität}%
+Die Menge des Flusses auf einer Kante kann die Kapazität der Kante nicht überschreiten.
+Ein Fluss muss die Einschränkung erfüllen, dass die Menge des Flusses
+in einen Knoten gleich der Menge des Flusses aus ihm heraus ist.
+Ein Flussnetzwerk (engl.~flow network) ist ein Netzwerk, dessen Kanten zusätzlich Kosten pro Mengeneinheit des Flusses zugeordnet sind.
+\index{Flussnetzwerk}%
+Typischerweise will man einen Fluss durch die Kanten bestimmen, der den Einschränkungen des Netzwerks genügt und dessen Gesamtkosten minimal sind.
+Im Bild~\ref{munkres:netzwerkdarstellung}
+dargestellt sind in den eckigen Klammern links die externen Flüsse $[1]$ für jeden Kran und in den eckigen Klammern rechts eine $[-1]$ für jeden Baustellenort. Die Kosten sind entlang der Kanten als Zahlen in Klammern dargestellt.  
 \subsubsection{Matrix}
-Im Bild 21.3 ist eine typische $4\times 4$ Matrix dargestellt. Die Zeilen A1 bis A4 betreffen z.B. vier bestehende Maschinenlager eines Unternehmers. In den Spalten B1 bis B4 sind vier neue Baustellenorte zugewiesen. Die Zahlen in der Matrix bedeuten z.B. die Distanz in Kilometer von dem jeweiligen Lager zur jeweiligen Baustelle.
+Im Bild~\ref{munkres:matrixdarstellung}
+ist eine typische $4\times 4$ Matrix dargestellt. Die Zeilen A1 bis A4 betreffen z.~B.~vier bestehende Maschinenlager eines Unternehmers. In den Spalten B1 bis B4 sind vier neue Baustellenorte zugewiesen. Die Zahlen in der Matrix bedeuten z.~B.~die Distanz in Kilometer von dem jeweiligen Lager zur jeweiligen Baustelle.
 \subsubsection{Bitpartiter Graph}
 Ein bipartiter Graph ist ein mathematisches Modell für Beziehungen
-zwischen den Elementen zweier Mengen. Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen. Zwischen zwei Gruppen von Objekten wird hierbei eine eindeutige Zuordnung hergestellt. Der Graph ist in Abbildung 21.4 ersichtlich.
+zwischen den Elementen zweier Mengen.
+\index{bipartit}%
+\index{Graph, bipartit}%
+Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen.
+Zwischen zwei Gruppen von Objekten wird hierbei eine eindeutige Zuordnung hergestellt.
+Der Graph ist in Abbildung~\ref{munkres:bipartit}
+ersichtlich.
 \begin{itemize}
-\item 3 = Anzahl der Knoten aus Menge A.
-\item 3 = Anzahl der Knoten aus Menge B.
+\item $3 =\mathstrut$Anzahl der Knoten aus Menge $A$.
+\item $3 =\mathstrut$Anzahl der Knoten aus Menge $B$.
 \end{itemize}
 
 
@@ -69,19 +96,19 @@ zwischen den Elementen zweier Mengen. Es eignet sich sehr gut zur Untersuchung v
 \centering
 \includegraphics[width=5cm]{papers/munkres/figures/Netzwerkdarstellung}
 \caption{Typische Netzwerkdarstellung eines Zuordnungsproblems.}
-\label{munkres:Vr2}
+\label{munkres:netzwerkdarstellung}
 \end{figure}
 
 \begin{figure}
 \centering
 \includegraphics[width=5cm]{papers/munkres/figures/Matrixdarstellung}
-\caption{Typische 4x4 Matrixdarstellung eines Zuordnungsproblems.}
-\label{munkres:Vr2}
+\caption{Typische $4\times 4$ Matrixdarstellung eines Zuordnungsproblems.}
+\label{munkres:matrixdarstellung}
 \end{figure}
 
 \begin{figure}
 \centering
 \includegraphics[width=5cm]{papers/munkres/figures/bipartiter_graph}
 \caption{$K_{3,3}$ vollständig bipartiter Graph mit 3 Knoten pro Teilmenge.}
-\label{munkres:Vr2}
+\label{munkres:bipartit}
 \end{figure}