Merge pull request #60 from Kuehnee/master

Pull Request Munkres - 21-08-02

5 files changed, 89 insertions, 12 deletions

diff --git a/buch/papers/munkres/figures/Ungarische_Methode_Beispiel.png b/buch/papers/munkres/figures/Ungarische_Methode_Beispiel.png
new file mode 100644
index 0000000..fb4d061
--- /dev/null
+++ b/buch/papers/munkres/figures/Ungarische_Methode_Beispiel.png
diff --git a/buch/papers/munkres/figures/Ungarische_Methode_Beispiel_Zuw.png b/buch/papers/munkres/figures/Ungarische_Methode_Beispiel_Zuw.png
new file mode 100644
index 0000000..73217d3
--- /dev/null
+++ b/buch/papers/munkres/figures/Ungarische_Methode_Beispiel_Zuw.png
diff --git a/buch/papers/munkres/figures/ganzzahlige_punkte.png b/buch/papers/munkres/figures/ganzzahlige_punkte.png
new file mode 100644
index 0000000..5689825
--- /dev/null
+++ b/buch/papers/munkres/figures/ganzzahlige_punkte.png
diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex
index 4532783..d22b57f 100644
--- a/buch/papers/munkres/teil1.tex
+++ b/buch/papers/munkres/teil1.tex
@@ -7,17 +7,25 @@
 \label{munkres:section:teil1}}
 \rhead{Problemstellung}
 
-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
+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.
 
 \subsection{Zuordnungsproblem an einem konkreten Beispiel
 \label{munkres:subsection:bonorum}}
-Man hat der 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
+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
 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 angenommen werden.$\mathbb{R}$. 
-Beim Beispiel mit den Kräne gib es aber ein Problem. Bei der Suche nach der optimalen Lösung darf  nur die Methode der ganzzahligen Optimierung gewählt werden.$\mathbb{Z}$. 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.
-Doch das Problem bleibt, mit ganzzahligen Punkten kann kein Optimum erzielt werden und ist eine träge, langsame Angelegenheit.
+Die Frage lautet, wie sind die Kräne umzusetzen, damit deren Transportstrecke minimal wird? Bei der normalen Optimierung dürfen normalerweise beliebige reelle Werte angenommen werden $\mathbb{R}$. 
+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 $\mathbb{Z}$. 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.
+Für solche Optimierungsproblem für reelle Varianten sind verschiedene Verfahren entwickelt worden, die im Allgemeinen auch sehr effizient sind. Das reelle Problem ist also in einer einfachen Art uns 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}
+\centering
+\includegraphics[width=5cm]{papers/munkres/figures/ganzzahlige_punkte}
+\caption{Problem der Ganzzahligkeit.}
+\label{munkres:Vr2}
+\end{figure}
+
 
 \subsection{Zuordnungsproblem abstrakt
 \label{munkres:subsection:bonorum}}
@@ -26,10 +34,8 @@ 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 dann auch der Faktor Kosten mit in die Rechnung eingebracht werden. 
-
-In der Zelle dieser Matrix sind $a_{i,j}$ die Kosten dargestellt, die entstehen, wenn man z.B. einem Arbeiter $i$ die Aufgabe $j$ zuordnet.
+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.
 
 \subsection{Alternative Darstellungen des Zuordnungsproblems
 \label{munkres:subsection:bonorum}}
diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex
index 6307f55..874baae 100644
--- a/buch/papers/munkres/teil3.tex
+++ b/buch/papers/munkres/teil3.tex
@@ -34,14 +34,85 @@ in polynomieller Zeit löst.
 Der Begriff polynomielle Laufzeit bedeutet, dass die Laufzeit des Programms
 wie $n^2$, $n^3$, $n^4$, etc.~wächst und vernünftig skaliert. $n$ ist hierbei die "Grösse" des Problems.
 
+\subsection{Unterschiedliche Anzahl von Quellen und Zielen
+\label{munkres:subsection:malorum}}
+Es gibt Fälle, in welchen das Ausgangsproblem keine quadratische Form besitzt. Das ist z.B dann der Fall, wenn eine 3 Mitarbeiter 4 Eignungstests abdsolvieren müssen. In diesem Fall wird in der Ungarischen Methode die Matrix künstlich mittels einer Dummy Position quadratisch ergänzt. Dummy-Positionen werden dann mit der größten vorhandenen Zahl aus der Matrix besetzt. Beispielsweise eine $4\times 3$ wird zu einer $4\times 4$ Matrix.
+
 \subsection{Beispiel eines händischen Verfahrens
 \label{munkres:subsection:malorum}}
 
-Die ungarische Methode kann in einem einfachen händischen Beispiel
erläutert werden. Es gibt eine Ausgangsmatrix. Diese Matrix wird in mehreren Schritten immer
weiter reduziert. Anschließend erfolgen mehrere Zuordnungen. Hierbei ist zu beachten, dass
jede Zeile und jede Spalte immer genau eine eindeutige Zuordnung ergibt.
Die optimale Lösung ist erreicht, wenn genau $n$ Zuordnungen gefunden
sind.
+Die ungarische Methode kann in einem einfachen händischen Beispiel
+erläutert werden. Es gibt eine Ausgangsmatrix. Diese Matrix wird in mehreren Schritten immer
+weiter reduziert. Anschließend erfolgen mehrere Zuordnungen. Hierbei ist zu beachten, dass
+jede Zeile und jede Spalte immer genau eine eindeutige Zuordnung ergibt.
+Die optimale Lösung ist erreicht, wenn genau $n$ Zuordnungen gefunden
+sind.
+
+\begin{enumerate}
+\item Pro Zeile eruiert man die kleinste Zahl. Diese kleinste Zahl wird bei
+allen anderen Ziffern in der jeweiligen Zeile subtrahiert.
+
+\item Danach zieht man wiederum die kleinste Zahl in jeder Spalte von allen
+Zahlen in der Spalte ab.
+
+\item Es 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 Jeweilige Zeilen eruieren, bei welchen keine markierte Null vorhanden sind und kennzeichnen.
+
+\item In der vorherigen Zeile die 0 eruieren und die Spalte ebenfalls
+kennzeichnen (*2)
+
+\item Im der selben Spalte die Markierte Null eruieren und die dazugehörige
+Zeile kennzeichnen (*3)
+
+\item Alle Zeilen durchstreichen, welche KEINE Kennzeichnungen (*) haben
+
+\item Alle Spalten durchstreichen, welche EINE Kennzeichnung besitzt! (hier, *2)
+
+\item Kleinste Ziffer auswählen, welche nicht schon durchgestrichen sind.
+(Im Beispiel ist es die Zahl 1. (Egal welche 1)
+
+\item Die eruierte kleinste Ziffer, wird von den nicht durchgestrichenen Ziffern
+subtrahiert. Danach muss die Matrix wieder komplettiert werden. (inkl. Unterstreichen)
+
+\item Jeweilige Zahlen eruieren, welche vorgängig doppelt durchgestrichen wurden.
+
+\item Kleinste eruierte Ziffer von vorhin auf die zwei markierten Ziffern addieren.
+
+\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 Aus allen markierten Nullen in eine eins umwandeln.
+
+\item Die restlichen Ziffern, durch eine Null ersetzen.
+
+\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.
+\end{enumerate}
 
 \begin{figure}
 \centering
-\includegraphics[width=14cm]{papers/munkres/figures/beispiel_munkres}
-\caption{Händisches Beispiel des Munkres Algorithmus.}
+\includegraphics[width=14cm]{papers/munkres/figures/Ungarische_Methode_Beispiel.png}
+\caption{Händisches Beispiel des Munkres Algorithmus, minimalster Transportweg.}
 \label{munkres:Vr2}
 \end{figure}
+
+\subsection{Zuordnung der Kräne
+\label{munkres:subsection:malorum}}
+
+\begin{itemize}
+\item Der Kran von Baustelle A1 soll zur Baustelle B2.
+\item Der Kran von Baustelle A2 soll zur Baustelle B3.
+\item Der Kran von Baustelle A3 soll zur Baustelle B4.
+\item Der Kran von Baustelle A4 soll zur Baustelle B1.
+\end{itemize}
+
+\begin{figure}
+\centering
+\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}
+