Merge branch 'AndreasFMueller:master' into master

2 files changed, 50 insertions, 43 deletions

diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex
index 363dc06..3bec61d 100644
--- a/buch/papers/munkres/teil1.tex
+++ b/buch/papers/munkres/teil1.tex
@@ -13,10 +13,10 @@ Um dieses Problem in einer einfachen, händischen Art und Weise zu lösen wurde
 
 \subsection{Zuordnungsproblem an einem konkreten Beispiel
 \label{munkres:subsection:bonorum}}
-Man hat 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
+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 von A nach B oder gar kein Kran verschoben werden. Also 1 oder 0.
+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.
 
 \begin{figure}
@@ -34,31 +34,39 @@ In einem Zuordnungsproblem sind alle Angebots- und Bedarfsmengen gleich 1
 \begin{equation}
 a_{i}=b_{j}=1
 \end{equation}
-Das Ziel ist es die Gesamtkosten zu minimieren. Mit Hilfe einer $n\times n$ Matrix $\mathbb{A}$ $\mathbb{\in}$ $\mathbb{R}^{n,n}$ kann der Faktor Kosten mit in die Rechnung eingebracht werden.
-In der Zelle dieser Matrix sind $a_{i,j}$ die Wege dargestellt, die entstehen, wenn man z.B. einem Kran $i$ den Einsatzort $j$ zuordnet.
-
-\begin{figure}
-\centering
-\includegraphics[width=5cm]{papers/munkres/figures/MatrixA.png}
-\caption{Darstellung einer Matrix $A$}
-\label{munkres:Vr2}
-\end{figure}
+Das Ziel ist es die Gesamtkosten zu minimieren. Mit Hilfe einer $n\times n$ Matrix 
+\[
+A
+=
+\begin{pmatrix}
+a_{11}&a_{12}&\dots &a_{1n}\\
+a_{21}&a_{22}&\dots &a_{2n}\\
+\vdots&\vdots&\ddots&\vdots\\
+a_{n1}&a_{n2}&\dots &a_{nn}
+\end{pmatrix}
+\]
+    
+$A$ $\mathbb{\in}$ $\mathbb{R}^{n,n}$ kann der Faktor Kosten mit in die Rechnung eingebracht werden.
+In der Zelle dieser Matrix sind $a_{i,j}$ Zahlen dargestellt, welche den Weg in z.B. Kilometer beschreiben.
+Sie entstehen, wenn man z.B. einem Kran $i$ den Einsatzort $j$ zuordnet.
 
+Die oben ersichtliche Matrix $A$ besitzt Matrix-Elemente. Die Elemente einer Matrix vom Typ $(n,n)$ mit Namen $A$ sind $a_{ij}$ wobei $i$ = 1,..., $n$ ist und $j$ = 1,...,$n$. $a_{ij}$ ist der Eintrag in der $i$-ten Zeile und $j$-ten Spalte der Matrix . Zum Beispiel ist a21 das Element der 2. Zeile und 1. Spalte. $i$ wird auch der Zeilenindex, $j$ der Spaltenindex genannt.
 
 \subsection{Alternative Darstellungen des Zuordnungsproblems
 \label{munkres:subsection:bonorum}}
-\begin{equation}
-Netzwerk
-\end{equation}
-\begin{equation}
-Matrix
-\end{equation}
-\begin{equation}
-Bitpartiter Graph
-\end{equation}
+\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 Arbeiter und in den eckigen Klammern rechts eine $[-1]$ für jede Tätigkeit. 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.
+\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 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.
+\begin{itemize}
+\item 3 = Anzahl der Knoten aus Menge A.
+\item 3 = Anzahl der Knoten aus Menge B.
+\end{itemize}
+
+
 \begin{figure}
 \centering
 \includegraphics[width=5cm]{papers/munkres/figures/Netzwerkdarstellung}
diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex
index 0d2c86e..964444c 100644
--- a/buch/papers/munkres/teil3.tex
+++ b/buch/papers/munkres/teil3.tex
@@ -45,45 +45,44 @@ Die ungarische Methode kann in einem einfachen händischen Beispiel erläutert w
 
 \begin{enumerate}
 \item Pro Zeile eruiert man die kleinste Zahl. Diese kleinste Zahl wird bei
-allen anderen Ziffern in der jeweiligen Zeile subtrahiert. Mit dieser Subtraktion zieht man die unvermeidbaren Kosten ab. 
+allen anderen Ziffern in der jeweiligen Zeile subtrahiert. Mit dieser Subtraktion zieht man die unvermeidbaren Kosten ab, die man hat, um eine Baustelle zu erreichen. 
 
-\item Auch in diesem Schritt werden die unvermeidbaren Kosten abgezogen. Man zieht die kleinste Zahl in jeder Spalte von allen Zahlen in der Spalte ab.
+\item Auch in diesem Schritt werden die unvermeidbaren Weg-Kosten abgezogen. Man zieht die kleinste Zahl in jeder Spalte von allen Zahlen in der Spalte ab.
 
 \item Bei den nachfolgenden Schritten bleiben dann nur noch die Kosten übrig, die man hat, wenn man eine andere Zuordnung wählt. Hierbei sollen möglichst viele Nullen markiert werden, welche freistehend sind.
 (Freistehend bedeutet, sowohl in der jeweiligen Zeile und Spalte nur
 eine markierte Null zu haben)
 
-\item Weiter werden die jeweiligen Zeilen eruiert, bei welchen keine markierte Null vorhanden sind. Diese kennzeichnet man.
+\item Weiter werden die jeweiligen Zeilen eruiert, bei welchen keine markierte Null vorhanden sind. Diese kennzeichnet man mit einer blauen Fläche.
 
-\item In der vorherigen Zeile die 0 eruieren und die Spalte ebenfalls
-kennzeichnen (*2)
+\item In der vorherigen, mit blauer Fläche markierten Zeile die 0 eruieren und dann die dazugehörige Spalte ebenfalls
+blau markieren.
 
-\item Im der selben Spalte die Markierte Null eruieren und die dazugehörige
-Zeile kennzeichnen (*3)
+\item Im der selben Spalte die markierte Null eruieren und die dazugehörige
+Zeile ebenfalls blau kennzeichnen.
 
-\item Alle Zeilen durchstreichen, welche KEINE Kennzeichnungen (*) haben
+\item Alle Zeilen mit einem gelben Balken durchstreichen, welche KEINE blauen Markierungen haben.
 
-\item Alle Spalten durchstreichen, welche EINE Kennzeichnung besitzt! (hier, *2)
+\item Alle Spalten durchstreichen, welche eine Blaue Markierung besitzt!
 
-\item Kleinste Ziffer auswählen, welche nicht schon durchgestrichen sind.
-(Im Beispiel ist es die Zahl 1. (Egal welche 1)
+\item In den übrigen Zahlen soll nun die kleinste Ziffer ausgewählt werden, welche nicht schon durchgestrichen sind.
+(Im Beispiel ist es die Zahl 1 in rot markiert. (Bei diesem Schritt ist es egal, welche 1 man wählt)
 
 \item Die eruierte kleinste Ziffer, wird von den nicht durchgestrichenen Ziffern
-subtrahiert. Danach muss die Matrix wieder komplettiert werden. (inkl. Unterstreichen)
+subtrahiert. Danach muss die Matrix wieder komplettiert werden. (inkl. Unterstreichen der Nullen)
 
-\item Jeweilige Zahlen eruieren, welche vorgängig doppelt durchgestrichen wurden.
+\item Jeweilige Zahlen eruieren, welche vorgängig doppelt mit einer gelben Fläche durchgestrichen wurden.
 
-\item Kleinste eruierte Ziffer von vorhin auf die zwei markierten Ziffern addieren.
+\item Kleinste eruierte Ziffer aus Schritt 9, soll nun auf die zwei in rot markierten Ziffern aus Schritt 11 dazu addiert werden. 
 
-\item Es sollen wiederum von neuem möglichst viele Nullen markiert werden,
-welche freistehend sind. In diesem Schritt werden nur die markierten Nullen betrachtet.
+\item In diesem Schritt sollen wiederum von neuem möglichst viele Nullen markiert werden,
+welche freistehend sind. Es werden nur die markierten Nullen betrachtet.
 
-\item Aus allen markierten Nullen in eine eins umwandeln.
+\item Alle markierten Nullen werden jetzt in eine 1 umgewandelt.
 
-\item Die restlichen Ziffern, durch eine Null ersetzen.
+\item Die restlichen Ziffern in der Matrix, exklusiv die einsen, sollen jetzt ignoriert und durch eine Null ersetzt werden.
 
-\item Zu guter letzt soll überall wo eine 1 steht, in der Ausgangsmatrix die
-dazugehörige Ziffer ausgewählt werden. Nach Einsetzen und Eruieren der Zahlen ergeben sich nach Summieren der Zahlen der minimalste Transportweg. Im erwähnten Beispiel sind es total 13 Kilometer.
+\item Zu guter Letzt werden überall wo eine 1 steht, die Zahlen aus der Ausgangsmatrix eingefügt. Nach Einsetzen der Zahlen können die in rot markierten Zahlen aufsummiert werden. Es ergibt der minimalste Transportweg. Im erwähnten Beispiel sind es total 13 Kilometer.
 \end{enumerate}
 
 \begin{figure}
@@ -108,4 +107,4 @@ dazugehörige Ziffer ausgewählt werden. Nach Einsetzen und Eruieren der Zahlen
 \includegraphics[width=3cm]{papers/munkres/figures/Ungarische_Methode_Beispiel_Zuw.png}
 \caption{Händisches Beispiel des Munkres Algorithmus, Zuweisung der Kräne }
 \label{munkres:Vr2}
-\end{figure} Somit konnte danke der Ungarischen Methode sowohl der minimalste Transportweg als auch die optimalste Zuweisung der Kräne auf die neuen Standorte ermittelt werden.
\ No newline at end of file
+\end{figure} Wie in Abbildung 21.6 ersichtlich, kann somit dank der Ungarischen Methode sowohl der minimalste Transportweg als auch die optimalste Zuweisung der Kräne auf die neuen Standorte ermittelt werden.
\ No newline at end of file