From 5c98f91bd4bc2b88c5ee0c746951c91f38963459 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Sun, 1 Aug 2021 14:19:47 +0200 Subject: neue version --- buch/papers/munkres/teil3.tex | 57 +++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 55 insertions(+), 2 deletions(-) (limited to 'buch/papers/munkres/teil3.tex') diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex index 6307f55..557d179 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -34,14 +34,67 @@ 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} +\includegraphics[width=14cm]{papers/munkres/figures/Ungarische Methode Beispiel} \caption{Händisches Beispiel des Munkres Algorithmus.} \label{munkres:Vr2} \end{figure} -- cgit v1.2.1 From 65966d22f384fa01a8db10b7fd47857efde92a81 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Mon, 2 Aug 2021 11:06:30 +0200 Subject: neue version --- buch/papers/munkres/teil3.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'buch/papers/munkres/teil3.tex') diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex index 557d179..7faf958 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -94,7 +94,7 @@ dazugehörige Ziffer ausgewählt werden. Nach Einsetzen und Eruieren der Zahlen \begin{figure} \centering -\includegraphics[width=14cm]{papers/munkres/figures/Ungarische Methode Beispiel} +\includegraphics[width=14cm]{papers/munkres/figures/Ungarische_Methode_Beispiel} \caption{Händisches Beispiel des Munkres Algorithmus.} \label{munkres:Vr2} \end{figure} -- cgit v1.2.1 From a8df39c46bc2ac0e92fc36d14d9d320d748bdf70 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Mon, 2 Aug 2021 11:37:31 +0200 Subject: neue version --- buch/papers/munkres/teil3.tex | 22 ++++++++++++++++++++-- 1 file changed, 20 insertions(+), 2 deletions(-) (limited to 'buch/papers/munkres/teil3.tex') diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex index 7faf958..6dadf32 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -94,7 +94,25 @@ dazugehörige Ziffer ausgewählt werden. Nach Einsetzen und Eruieren der Zahlen \begin{figure} \centering -\includegraphics[width=14cm]{papers/munkres/figures/Ungarische_Methode_Beispiel} -\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 Zuweisung.png} +\caption{Händisches Beispiel des Munkres Algorithmus, Zuweisung der Kräne } +\label{munkres:Vr2} +\end{figure} + -- cgit v1.2.1 From cbd9a9d63f0dfcd3141a9a420dac959e554f9b57 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Mon, 2 Aug 2021 11:49:47 +0200 Subject: neue version --- buch/papers/munkres/teil3.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'buch/papers/munkres/teil3.tex') diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex index 6dadf32..874baae 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -111,7 +111,7 @@ dazugehörige Ziffer ausgewählt werden. Nach Einsetzen und Eruieren der Zahlen \begin{figure} \centering -\includegraphics[width=3cm]{papers/munkres/figures/Ungarische Methode Beispiel Zuweisung.png} +\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} -- cgit v1.2.1 From 8e6efdb02d8e35d9a3749a377a80de679a8b3ba2 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Mon, 2 Aug 2021 21:06:43 +0200 Subject: neue version --- buch/papers/munkres/teil3.tex | 18 ++++++------------ 1 file changed, 6 insertions(+), 12 deletions(-) (limited to 'buch/papers/munkres/teil3.tex') diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex index 874baae..2a8f4a7 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -36,30 +36,24 @@ wie $n^2$, $n^3$, $n^4$, etc.~wächst und vernünftig skaliert. $n$ ist hierbei \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. +Es gibt Fälle, in welchen das Ausgangsproblem keine quadratische Form besitzt. Das ist z.B. dann der Fall, wenn 3 Mitarbeiter vier verschiedene Eignungstests absolvieren 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 wird eine $3\times 4$ 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. Das Vorgehen wird in den nachfolgenden Schritten 1-16 beschrieben und auch in der Abbildung 21.5 dargestellt. \begin{enumerate} \item Pro Zeile eruiert man die kleinste Zahl. Diese kleinste Zahl wird bei -allen anderen Ziffern in der jeweiligen Zeile subtrahiert. +allen anderen Ziffern in der jeweiligen Zeile subtrahiert. Mit dieser Subtraktion zieht man die unvermeidbaren Kosten ab. -\item Danach zieht man wiederum die kleinste Zahl in jeder Spalte von allen -Zahlen in der Spalte ab. +\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 Es sollen möglichst viele Nullen markiert werden, welche freistehend sind. +\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 Jeweilige Zeilen eruieren, bei welchen keine markierte Null vorhanden sind und kennzeichnen. +\item Weiter werden die jeweiligen Zeilen eruiert, bei welchen keine markierte Null vorhanden sind. Diese kennzeichnet man. \item In der vorherigen Zeile die 0 eruieren und die Spalte ebenfalls kennzeichnen (*2) -- cgit v1.2.1 From 5ee4a25b3a02fa12de47dd1dad1b8b1be2d7c7ae Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Tue, 3 Aug 2021 10:52:13 +0200 Subject: neue version --- buch/papers/munkres/teil3.tex | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) (limited to 'buch/papers/munkres/teil3.tex') diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex index 2a8f4a7..0d2c86e 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -36,7 +36,7 @@ wie $n^2$, $n^3$, $n^4$, etc.~wächst und vernünftig skaliert. $n$ ist hierbei \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 3 Mitarbeiter vier verschiedene Eignungstests absolvieren 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 wird eine $3\times 4$ zu einer $4\times 4$-Matrix. +Es gibt Fälle, in welchen das Ausgangsproblem keine quadratische Form besitzt. Das ist z.B. dann der Fall, wenn drei Mitarbeiter vier verschiedene Eignungstests absolvieren 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 wird eine $3\times 4$ zu einer $4\times 4$-Matrix. \subsection{Beispiel eines händischen Verfahrens \label{munkres:subsection:malorum}} @@ -83,7 +83,7 @@ welche freistehend sind. In diesem Schritt werden nur die markierten Nullen betr \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. +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. \end{enumerate} \begin{figure} @@ -108,5 +108,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} - +\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 -- cgit v1.2.1