From 6c2ea74f867d898626e5ef25c61814cd2aa49bbd Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Sat, 31 Jul 2021 11:57:23 +0200 Subject: neue version --- buch/papers/munkres/teil1.tex | 17 +++++++++++++---- buch/papers/munkres/teil2.tex | 4 ++-- buch/papers/munkres/teil3.tex | 9 +++++---- 3 files changed, 20 insertions(+), 10 deletions(-) (limited to 'buch/papers/munkres') diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex index c13732c..4532783 100644 --- a/buch/papers/munkres/teil1.tex +++ b/buch/papers/munkres/teil1.tex @@ -8,21 +8,30 @@ \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 -Ort transportiert, sondern es geht um die kostenminimale Zuordnung von z.B. Personen, oder Bau-Materialien auf bestimmte Orte, Stellen oder Aufgaben. +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 +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. \subsection{Zuordnungsproblem abstrakt \label{munkres:subsection:bonorum}} -Es sind alle Angebots- und Bedarfsmengen gleich 1 +In einem Zuordnungsproblem sind alle Angebots- und Bedarfsmengen gleich 1 \begin{equation} a_{i}=b_{j}=1 \end{equation} -\subsection{alternative Darstellungen des Zuordnungsproblems +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. + +\subsection{Alternative Darstellungen des Zuordnungsproblems \label{munkres:subsection:bonorum}} \begin{equation} Netzwerk @@ -35,7 +44,7 @@ Bitpartiter Graph \end{equation} Ein bipartiter Graph ist ein mathematisches Modell für Beziehungen zwischen den Elementen zweier Mengen. -Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen» +Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen. \begin{figure} \centering \includegraphics[width=5cm]{papers/munkres/figures/Netzwerkdarstellung} diff --git a/buch/papers/munkres/teil2.tex b/buch/papers/munkres/teil2.tex index 9a44cd4..a3b249e 100644 --- a/buch/papers/munkres/teil2.tex +++ b/buch/papers/munkres/teil2.tex @@ -7,7 +7,7 @@ \label{munkres:section:teil2}} \rhead{Schwierigkeit der Lösung (Permutationen)} -Eine Permutation ist eine Anordnung von Objekten in einer bestimmten Reihenfolge oder eine Umordnung von Objekten aus einer vorgegebenen Reihung. Ist eine maximale Zuordnung (maximales Matching) gefunden, so steht in jeder Zeile und jeder Spalte der Matrix genau ein Element, das zur optimalen Lösung gehört, eine solche Gruppe von Positionen wird auch als Transversale der Matrix bezeichnet. +Eine Permutation ist eine Anordnung von Objekten in einer bestimmten Reihenfolge oder eine Umordnung von Objekten aus einer vorgegebenen Reihung. Ist eine optimale Zuordnung gefunden, so steht in jeder Zeile und jeder Spalte der Matrix genau ein Element, das zur optimalen Lösung gehört, eine solche Gruppe von Positionen wird auch als Transversale der Matrix bezeichnet. -Die Problemstellung kann auch so formuliert werden, dass man die Zeilen- oder die Spaltenvektoren so umordnet soll, dass die Summe der Elemente in der Hauptdiagonale maximal wird. Hieraus wird sofort ersichtlich, dass es in einer n×n-Matrix genau so viele Möglichkeiten gibt, die Zeilen- bzw. Spaltenvektoren zu ordnen, wie es Permutationen von n Elementen gibt, also n!. Außer bei kleinen Matrizen ist es nahezu aussichtslos, die optimale Lösung durch Berechnung aller Möglichkeiten zu finden. Schon bei einer 10×10-Matrix gibt es nahezu 3,63 Millionen (3.628.800) zu berücksichtigender Permutationen. +Die Problemstellung kann auch so formuliert werden, dass man die Zeilen- oder die Spaltenvektoren so umordnet soll, dass die Summe der Elemente in der Hauptdiagonale maximal wird. Hieraus wird sofort ersichtlich, dass es in einer $n$×$n$-Matrix genau so viele Möglichkeiten gibt, die Zeilen- bzw. Spaltenvektoren zu ordnen, wie es Permutationen von $n$ Elementen gibt, also $n!$. Außer bei kleinen Matrizen ist es nahezu aussichtslos, die optimale Lösung durch Berechnung aller Möglichkeiten zu finden. Schon bei einer 10×10-Matrix gibt es nahezu 3,63 Millionen (3.628.800) zu berücksichtigender Permutationen. diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex index cd47c92..6307f55 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -7,7 +7,7 @@ \label{munkres:section:teil3}} \rhead{Der Munkres-Algorithmus (Ungarische Methode)} -Mit der ungarischen Methode können also lineare Optimierungsprobleme gelöst +Mit der ungarischen Methode können also Optimierungsprobleme gelöst werden, die bei gewichteten Zuordnungen in bipartiten Graphen entstehen. Mit ihr kann die eindeutige Zuordnung von Objekten aus zwei Gruppen so optimiert werden, dass die Gesamtkosten minimiert werden bzw.~der @@ -29,15 +29,16 @@ um eine $O(n^3)$-Laufzeit zu erreichen. \subsection{Besondere Leistung der Ungarischen Methode \label{munkres:subsection:malorum}} -Es ist ein kombinatorischer Optimierungsalgorithmus, der das Zuordnungsproblem +Die Ungarische Methode ist ein kombinatorischer Optimierungsalgorithmus, der das Zuordnungsproblem 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. - +wie $n^2$, $n^3$, $n^4$, etc.~wächst und vernünftig skaliert. $n$ ist hierbei die "Grösse" des Problems. \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. + \begin{figure} \centering \includegraphics[width=14cm]{papers/munkres/figures/beispiel_munkres} -- cgit v1.2.1 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') 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/teil1.tex | 24 +++++++++++++++--------- buch/papers/munkres/teil3.tex | 2 +- 2 files changed, 16 insertions(+), 10 deletions(-) (limited to 'buch/papers/munkres') diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex index 4532783..867830f 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{$K_{3,3}$ 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 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/teil1.tex | 2 +- buch/papers/munkres/teil3.tex | 22 ++++++++++++++++++++-- 2 files changed, 21 insertions(+), 3 deletions(-) (limited to 'buch/papers/munkres') diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex index 867830f..d22b57f 100644 --- a/buch/papers/munkres/teil1.tex +++ b/buch/papers/munkres/teil1.tex @@ -22,7 +22,7 @@ Für solche Optimierungsproblem für reelle Varianten sind verschiedene Verfahre \begin{figure} \centering \includegraphics[width=5cm]{papers/munkres/figures/ganzzahlige_punkte} -\caption{$K_{3,3}$ Problem der Ganzzahligkeit.} +\caption{Problem der Ganzzahligkeit.} \label{munkres:Vr2} \end{figure} 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 8feb90a7677b2c93493958c8a22008c293cca0db Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Mon, 2 Aug 2021 11:43:35 +0200 Subject: fehlendes bild --- .../munkres/figures/Ungarische_Methode_Beispiel.png | Bin 0 -> 1179631 bytes 1 file changed, 0 insertions(+), 0 deletions(-) create mode 100644 buch/papers/munkres/figures/Ungarische_Methode_Beispiel.png (limited to 'buch/papers/munkres') 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 Binary files /dev/null and b/buch/papers/munkres/figures/Ungarische_Methode_Beispiel.png differ -- cgit v1.2.1 From 97d2d95b6d2f50444221f060d986095c0129628f Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Mon, 2 Aug 2021 11:45:45 +0200 Subject: fehlendes bild --- .../figures/Ungarische_Methode_Beispiel_Zuw.png | Bin 0 -> 117508 bytes 1 file changed, 0 insertions(+), 0 deletions(-) create mode 100644 buch/papers/munkres/figures/Ungarische_Methode_Beispiel_Zuw.png (limited to 'buch/papers/munkres') 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 Binary files /dev/null and b/buch/papers/munkres/figures/Ungarische_Methode_Beispiel_Zuw.png differ -- cgit v1.2.1 From 2ce8b93410c15a7f4d72712d4e4a3e46e809bf71 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Mon, 2 Aug 2021 11:46:17 +0200 Subject: fehlendes bild --- buch/papers/munkres/figures/ganzzahlige_punkte.png | Bin 0 -> 257390 bytes 1 file changed, 0 insertions(+), 0 deletions(-) create mode 100644 buch/papers/munkres/figures/ganzzahlige_punkte.png (limited to 'buch/papers/munkres') 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 Binary files /dev/null and b/buch/papers/munkres/figures/ganzzahlige_punkte.png differ -- 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') 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 02cdfa6fcffe1df6f457c541aa05ff714bbf09d0 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Mon, 2 Aug 2021 21:01:34 +0200 Subject: fehlendes bild --- buch/papers/munkres/figures/MatrixA.png | Bin 0 -> 87794 bytes 1 file changed, 0 insertions(+), 0 deletions(-) create mode 100644 buch/papers/munkres/figures/MatrixA.png (limited to 'buch/papers/munkres') diff --git a/buch/papers/munkres/figures/MatrixA.png b/buch/papers/munkres/figures/MatrixA.png new file mode 100644 index 0000000..45a71a4 Binary files /dev/null and b/buch/papers/munkres/figures/MatrixA.png differ -- 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/teil1.tex | 16 ++++++++++++---- buch/papers/munkres/teil3.tex | 18 ++++++------------ 2 files changed, 18 insertions(+), 16 deletions(-) (limited to 'buch/papers/munkres') diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex index d22b57f..388a448 100644 --- a/buch/papers/munkres/teil1.tex +++ b/buch/papers/munkres/teil1.tex @@ -15,13 +15,13 @@ Um dieses Problem in einer einfachen, händischen Art und Weise zu lösen wurde \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 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 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. +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. +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} \centering -\includegraphics[width=5cm]{papers/munkres/figures/ganzzahlige_punkte} +\includegraphics[width=8cm]{papers/munkres/figures/ganzzahlige_punkte} \caption{Problem der Ganzzahligkeit.} \label{munkres:Vr2} \end{figure} @@ -37,6 +37,14 @@ a_{i}=b_{j}=1 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 Matrix $A$} +\label{munkres:Vr2} +\end{figure} + + \subsection{Alternative Darstellungen des Zuordnungsproblems \label{munkres:subsection:bonorum}} \begin{equation} 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/teil1.tex | 2 +- buch/papers/munkres/teil3.tex | 7 +++---- 2 files changed, 4 insertions(+), 5 deletions(-) (limited to 'buch/papers/munkres') diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex index 388a448..363dc06 100644 --- a/buch/papers/munkres/teil1.tex +++ b/buch/papers/munkres/teil1.tex @@ -40,7 +40,7 @@ In der Zelle dieser Matrix sind $a_{i,j}$ die Wege dargestellt, die entstehen, w \begin{figure} \centering \includegraphics[width=5cm]{papers/munkres/figures/MatrixA.png} -\caption{Darstellung Matrix $A$} +\caption{Darstellung einer Matrix $A$} \label{munkres:Vr2} \end{figure} 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 From 24a24cb7f6cb0a85bc136bbdb11ad52b7d7917f0 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Wed, 4 Aug 2021 10:27:27 +0200 Subject: neue version --- buch/papers/munkres/teil1.tex | 29 ++++++++++++++++++++++------- buch/papers/munkres/teil3.tex | 4 ++-- 2 files changed, 24 insertions(+), 9 deletions(-) (limited to 'buch/papers/munkres') diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex index 363dc06..07489e3 100644 --- a/buch/papers/munkres/teil1.tex +++ b/buch/papers/munkres/teil1.tex @@ -35,30 +35,45 @@ In einem Zuordnungsproblem sind alle Angebots- und Bedarfsmengen gleich 1 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. +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. \begin{figure} -\centering -\includegraphics[width=5cm]{papers/munkres/figures/MatrixA.png} +\[ +A += +\begin{pmatrix} +a_{11}&a_{12}&\dots &a_{1m}\\ +a_{21}&a_{22}&\dots &a_{2m}\\ +\vdots&\vdots&\ddots&\vdots\\ +a_{n1}&a_{n2}&\dots &a_{nm} +\end{pmatrix} +\] \caption{Darstellung einer Matrix $A$} -\label{munkres:Vr2} \end{figure} - +Eine Matrix, wie hier in Abbildung 21.2 ersichtlich, ist ein rechteckiges Schema, dessen Elemente üblicherweise Zahlen, aber auch andere mathematische Elemente wie Variablen oder Funktionen sein können. Sie besteht aus $n$ Zeilen und $m$ Spalten. D.h. die Elemente einer Matrix vom Typ $(n,m)$ mit Namen $A$ sind $a_{ij}$ wobei $i$ = 1,..., $m$ 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} +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.3 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. \begin{equation} Matrix \end{equation} +Im Bild 21.4 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. \begin{equation} Bitpartiter Graph \end{equation} 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. +\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..d2e8174 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -45,9 +45,9 @@ 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 -- cgit v1.2.1 From f06e1476cec724c47306967946f9dcb6d8be971e Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Thu, 5 Aug 2021 10:59:29 +0200 Subject: neue version --- buch/papers/munkres/teil1.tex | 43 ++++++++++++++++++------------------------- buch/papers/munkres/teil3.tex | 37 ++++++++++++++++++------------------- 2 files changed, 36 insertions(+), 44 deletions(-) (limited to 'buch/papers/munkres') diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex index 07489e3..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,40 +34,33 @@ 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}$ Zahlen dargestellt, welche den Weg in z.B. Kilometer beschreiben. -Sie entstehen, wenn man z.B. einem Kran $i$ den Einsatzort $j$ zuordnet. - -\begin{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_{1m}\\ -a_{21}&a_{22}&\dots &a_{2m}\\ +a_{11}&a_{12}&\dots &a_{1n}\\ +a_{21}&a_{22}&\dots &a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ -a_{n1}&a_{n2}&\dots &a_{nm} +a_{n1}&a_{n2}&\dots &a_{nn} \end{pmatrix} \] -\caption{Darstellung einer Matrix $A$} -\end{figure} -Eine Matrix, wie hier in Abbildung 21.2 ersichtlich, ist ein rechteckiges Schema, dessen Elemente üblicherweise Zahlen, aber auch andere mathematische Elemente wie Variablen oder Funktionen sein können. Sie besteht aus $n$ Zeilen und $m$ Spalten. D.h. die Elemente einer Matrix vom Typ $(n,m)$ mit Namen $A$ sind $a_{ij}$ wobei $i$ = 1,..., $m$ 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. + +$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} -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.3 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. -\begin{equation} -Matrix -\end{equation} -Im Bild 21.4 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. -\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 zwei Gruppen von Objekten wird hierbei eine eindeutige Zuordnung hergestellt. +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. diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex index d2e8174..964444c 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -53,37 +53,36 @@ allen anderen Ziffern in der jeweiligen Zeile subtrahiert. Mit dieser Subtraktio (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 -- cgit v1.2.1 From 0a784fbf3f8b5acf9103dc3587b4c1cfdcca688b Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Sun, 8 Aug 2021 11:43:48 +0200 Subject: neue version --- buch/papers/munkres/main.tex | 2 -- buch/papers/munkres/teil1.tex | 8 +++---- buch/papers/munkres/teil3.tex | 52 +++++++++++++------------------------------ 3 files changed, 19 insertions(+), 43 deletions(-) (limited to 'buch/papers/munkres') diff --git a/buch/papers/munkres/main.tex b/buch/papers/munkres/main.tex index e5282dc..201e70b 100644 --- a/buch/papers/munkres/main.tex +++ b/buch/papers/munkres/main.tex @@ -13,8 +13,6 @@ \input{papers/munkres/teil1.tex} \input{papers/munkres/teil2.tex} \input{papers/munkres/teil3.tex} -\input{papers/munkres/teil4.tex} -\input{papers/munkres/teil5.tex} \printbibliography[heading=subbibliography] \end{refsection} diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex index 3bec61d..a0cc739 100644 --- a/buch/papers/munkres/teil1.tex +++ b/buch/papers/munkres/teil1.tex @@ -45,13 +45,13 @@ a_{21}&a_{22}&\dots &a_{2n}\\ 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. + +$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}} \subsubsection{Netzwerk} diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex index 964444c..692bfdf 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -41,53 +41,28 @@ Es gibt Fälle, in welchen das Ausgangsproblem keine quadratische Form besitzt. \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. Das Vorgehen wird in den nachfolgenden Schritten 1-16 beschrieben und auch in der Abbildung 21.5 dargestellt. +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. Es gibt Situationen, in denen man nichts mehr tun muss, um eine optimale Zuordnung zu finden. Eine optimale Zuordnung ohne zusätzliche Kosten ist eine Auswahl genau eines Feldes in jeder Zeile und Spalte, welches 0 enthält. Das Ziel des Algorithmus ist also, die Matrix so zu ändern, dass genügend Nullen in der Matrix vorkommen. Es ist zudem wichtig, dass man nach jeder Modifikation der Matrix testet, ob man bereits eine Zuordnung machen kann, also genügend Nullen hat. +Das Vorgehen wird in den nachfolgenden Schritten 1-6 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. Mit dieser Subtraktion zieht man die unvermeidbaren Kosten ab, die man hat, um eine Baustelle zu erreichen. +\item Man beginnt mit der Zeilen-Reduktion. Pro Zeile eruiert man die kleinste Zahl. Diese kleinste Zahl, jeweils in rot markiert, wird bei 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. Man erkennt, dass die Nullen mit zwei Linien abdeckbar sind. Das heisst es gibt 2 Spalten bei denen noch keine Zuordnungen möglich sind. -\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 Auch im zweiten Schritt werden mittels der Spalten-Reduktion die unvermeidbaren Weg-Kosten abgezogen. Man zieht die kleinste Zahl, wiederum in rot markiert, in jeder Spalte von allen Zahlen in der Spalte ab. +Die Nullen können somit mit 3 Linien abgedeckt werden. Im Idealfall hat die Matrix in jeder Zeile und Spalte bereits genügend viele Nullen, so dass man bereits eine Zuordnung ohne Mehrkosten machen kann. Dies ist jedoch noch nicht der Fall. Es sollen weitere Nullen in die Matrix hineingebracht werden. -\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 Es bleiben jetzt einige Felder übrig, für die noch keine Zuordnung möglich ist. Die kleinste Ziffer wird dabei aus den noch nicht mit blau markierten Zahlen ausgewählt werden. Im Beispiel ist es die Zahl 1. Das Feld mit dem kleinsten Eintrag beinhaltet die Kosten, die unvermeidlich sind, wenn man für diese Felder auch noch eine Zuordnung machen will. Um neue Nullen zu bekommen, lagert man jetzt die Kosten auf die anderen Zeilen und Spalten um. Dies tut man, indem man in allen nicht abgedeckten Feldern die minimalen Kosten subtrahiert und in den blau markierten Kreuzungspunkten dazu addiert. -\item Weiter werden die jeweiligen Zeilen eruiert, bei welchen keine markierte Null vorhanden sind. Diese kennzeichnet man mit einer blauen Fläche. +\item in Schritt 4 sollen jetzt möglichst viele Nullen markiert werden, welche freistehend sind. +Freistehend bedeutet, dass sowohl in der jeweiligen Zeile und Spalte keine andere markierte Null vorhanden ist. -\item In der vorherigen, mit blauer Fläche markierten Zeile die 0 eruieren und dann die dazugehörige Spalte ebenfalls -blau markieren. +\item Alle markierten Nullen werden jetzt in eine 1 umgewandelt. Die restlichen Ziffern in der Matrix, exklusiv die einsen, sollen jetzt ignoriert und durch eine Null ersetzt werden. -\item Im der selben Spalte die markierte Null eruieren und die dazugehörige -Zeile ebenfalls blau kennzeichnen. - -\item Alle Zeilen mit einem gelben Balken durchstreichen, welche KEINE blauen Markierungen haben. - -\item Alle Spalten durchstreichen, welche eine Blaue Markierung besitzt! - -\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 der Nullen) - -\item Jeweilige Zahlen eruieren, welche vorgängig doppelt mit einer gelben Fläche durchgestrichen wurden. - -\item Kleinste eruierte Ziffer aus Schritt 9, soll nun auf die zwei in rot markierten Ziffern aus Schritt 11 dazu addiert werden. - -\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 Alle markierten Nullen werden jetzt in eine 1 umgewandelt. - -\item Die restlichen Ziffern in der Matrix, exklusiv die einsen, sollen jetzt ignoriert und durch eine Null ersetzt werden. - -\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. +\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. Man erhält den minimalsten Transportweg von total 13 Kilometer. \end{enumerate} \begin{figure} \centering -\includegraphics[width=14cm]{papers/munkres/figures/Ungarische_Methode_Beispiel.png} +\includegraphics[width=8cm]{papers/munkres/figures/Ungarische_Methode_Beispiel.png} \caption{Händisches Beispiel des Munkres Algorithmus, minimalster Transportweg.} \label{munkres:Vr2} \end{figure} @@ -95,6 +70,7 @@ welche freistehend sind. Es werden nur die markierten Nullen betrachtet. \subsection{Zuordnung der Kräne \label{munkres:subsection:malorum}} +Als Resultat des Munkres-Algorithmus kann man jetzt die folgende Zuordnung aus der Matrix ablesen: \begin{itemize} \item Der Kran von Baustelle A1 soll zur Baustelle B2. \item Der Kran von Baustelle A2 soll zur Baustelle B3. @@ -107,4 +83,6 @@ welche freistehend sind. Es werden nur die markierten Nullen betrachtet. \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} 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 +\end{figure} + +In Abbildung 21.6 ist nebst dem minimalsten Transportweg auch ersichtlich, wie die optimalste Zuweisung der Kräne auf die neuen Standorte erfolgen soll. \ No newline at end of file -- cgit v1.2.1 From 6824f0a18d2fe5aa999596b2ad72cc7ee186622a Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Sun, 8 Aug 2021 11:44:47 +0200 Subject: fehlendes bild --- .../figures/Ungarische_Methode_Beispiel.png | Bin 1179631 -> 485941 bytes 1 file changed, 0 insertions(+), 0 deletions(-) (limited to 'buch/papers/munkres') diff --git a/buch/papers/munkres/figures/Ungarische_Methode_Beispiel.png b/buch/papers/munkres/figures/Ungarische_Methode_Beispiel.png index fb4d061..242db77 100644 Binary files a/buch/papers/munkres/figures/Ungarische_Methode_Beispiel.png and b/buch/papers/munkres/figures/Ungarische_Methode_Beispiel.png differ -- cgit v1.2.1 From db34dc83135d3f17713279a0a7265f9381417e33 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Sun, 8 Aug 2021 18:02:12 +0200 Subject: neue version --- buch/papers/munkres/teil1.tex | 14 ++++++-------- buch/papers/munkres/teil2.tex | 2 +- buch/papers/munkres/teil3.tex | 15 ++++++++------- 3 files changed, 15 insertions(+), 16 deletions(-) (limited to 'buch/papers/munkres') diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex index a0cc739..6d8762e 100644 --- a/buch/papers/munkres/teil1.tex +++ b/buch/papers/munkres/teil1.tex @@ -8,14 +8,14 @@ \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 -Ort transportiert, sondern es geht um die kostenminimale Zuordnung von z.B. Personen, oder Bau-Maschinen auf bestimmte Orte, Stellen oder Aufgaben. +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}} 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. +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. @@ -45,17 +45,15 @@ a_{21}&a_{22}&\dots &a_{2n}\\ a_{n1}&a_{n2}&\dots &a_{nn} \end{pmatrix} \] - -$A$ $\mathbb{\in}$ $\mathbb{R}^{n,n}$ - +$\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. +In den Zellen 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$ 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 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. +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. \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} diff --git a/buch/papers/munkres/teil2.tex b/buch/papers/munkres/teil2.tex index a3b249e..9407c96 100644 --- a/buch/papers/munkres/teil2.tex +++ b/buch/papers/munkres/teil2.tex @@ -9,5 +9,5 @@ Eine Permutation ist eine Anordnung von Objekten in einer bestimmten Reihenfolge oder eine Umordnung von Objekten aus einer vorgegebenen Reihung. Ist eine optimale Zuordnung gefunden, so steht in jeder Zeile und jeder Spalte der Matrix genau ein Element, das zur optimalen Lösung gehört, eine solche Gruppe von Positionen wird auch als Transversale der Matrix bezeichnet. -Die Problemstellung kann auch so formuliert werden, dass man die Zeilen- oder die Spaltenvektoren so umordnet soll, dass die Summe der Elemente in der Hauptdiagonale maximal wird. Hieraus wird sofort ersichtlich, dass es in einer $n$×$n$-Matrix genau so viele Möglichkeiten gibt, die Zeilen- bzw. Spaltenvektoren zu ordnen, wie es Permutationen von $n$ Elementen gibt, also $n!$. Außer bei kleinen Matrizen ist es nahezu aussichtslos, die optimale Lösung durch Berechnung aller Möglichkeiten zu finden. Schon bei einer 10×10-Matrix gibt es nahezu 3,63 Millionen (3.628.800) zu berücksichtigender Permutationen. +Die Problemstellung kann auch so formuliert werden, dass man die Zeilen- oder die Spaltenvektoren so umordnet soll, dass die Summe der Elemente in der Hauptdiagonale maximal wird. Hieraus wird sofort ersichtlich, dass es in einer $n$×$n$-Matrix genau so viele Möglichkeiten gibt, die Zeilen- bzw. Spaltenvektoren zu ordnen, wie es Permutationen von $n$ Elementen gibt, also $n!$. Außer bei kleinen Matrizen ist es nahezu aussichtslos, die optimale Lösung durch Berechnung aller Möglichkeiten zu finden. Schon bei einer 10×10-Matrix gibt es nahezu 3,63 Millionen (3.628.800) zu berücksichtigende Permutationen. diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex index 692bfdf..2693185 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -11,7 +11,7 @@ Mit der ungarischen Methode können also Optimierungsprobleme gelöst werden, die bei gewichteten Zuordnungen in bipartiten Graphen entstehen. Mit ihr kann die eindeutige Zuordnung von Objekten aus zwei Gruppen so optimiert werden, dass die Gesamtkosten minimiert werden bzw.~der -Gesamtgewinn maximiert werden kann. +Gesamtgewinn maximiert werden kann. \subsection{Geschichte \label{munkres:subsection:malorum}} @@ -32,27 +32,28 @@ um eine $O(n^3)$-Laufzeit zu erreichen. Die Ungarische Methode ist ein kombinatorischer Optimierungsalgorithmus, der das Zuordnungsproblem 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. +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 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. +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 zu einem Quadrat 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. Es gibt Situationen, in denen man nichts mehr tun muss, um eine optimale Zuordnung zu finden. Eine optimale Zuordnung ohne zusätzliche Kosten ist eine Auswahl genau eines Feldes in jeder Zeile und Spalte, welches 0 enthält. Das Ziel des Algorithmus ist also, die Matrix so zu ändern, dass genügend Nullen in der Matrix vorkommen. Es ist zudem wichtig, dass man nach jeder Modifikation der Matrix testet, ob man bereits eine Zuordnung machen kann, also genügend Nullen hat. +Die ungarische Methode kann in einem einfachen händischen Beispiel erläutert werden. Wir gehen von der Kostenmatrix $A$ aus. Diese Matrix wird in mehreren Schritten immer weiter reduziert. Anschliessend erfolgen mehrere Zuordnungen. Hierbei ist zu beachten, dass jede Zeile und jede Spalte immer genau eine eindeutige Zuordnung ergibt. Es gibt Situationen, in denen man nichts mehr tun muss, um eine optimale Zuordnung zu finden. Eine optimale Zuordnung ohne zusätzliche Kosten ist eine Auswahl genau eines Feldes in jeder Zeile und Spalte, welches 0 enthält. Das Ziel des Algorithmus ist also, die Matrix so zu ändern, dass genügend Nullen in der Matrix vorkommen. Es ist zudem wichtig, dass man nach jeder Modifikation der Matrix testet, ob man bereits eine Zuordnung machen kann, also genügend Nullen hat. Das Vorgehen wird in den nachfolgenden Schritten 1-6 beschrieben und auch in der Abbildung 21.5 dargestellt. \begin{enumerate} -\item Man beginnt mit der Zeilen-Reduktion. Pro Zeile eruiert man die kleinste Zahl. Diese kleinste Zahl, jeweils in rot markiert, wird bei 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. Man erkennt, dass die Nullen mit zwei Linien abdeckbar sind. Das heisst es gibt 2 Spalten bei denen noch keine Zuordnungen möglich sind. +\item Man beginnt mit der Zeilen-Reduktion. Pro Zeile eruiert man die kleinste Zahl. Diese kleinste Zahl, jeweils in rot markiert, wird bei 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. Man erkennt, dass die Nullen mit zwei Linien abdeckbar sind. Das heisst es gibt zwei Spalten bei denen noch keine Zuordnungen möglich sind. \item Auch im zweiten Schritt werden mittels der Spalten-Reduktion die unvermeidbaren Weg-Kosten abgezogen. Man zieht die kleinste Zahl, wiederum in rot markiert, in jeder Spalte von allen Zahlen in der Spalte ab. -Die Nullen können somit mit 3 Linien abgedeckt werden. Im Idealfall hat die Matrix in jeder Zeile und Spalte bereits genügend viele Nullen, so dass man bereits eine Zuordnung ohne Mehrkosten machen kann. Dies ist jedoch noch nicht der Fall. Es sollen weitere Nullen in die Matrix hineingebracht werden. +Die Nullen können somit mit drei Linien abgedeckt werden. Im Idealfall hat die Matrix in jeder Zeile und Spalte bereits genügend viele Nullen, so dass man bereits eine Zuordnung ohne Mehrkosten machen kann. Dies ist jedoch noch nicht der Fall. Es sollen weitere Nullen in die Matrix hineingebracht werden. \item Es bleiben jetzt einige Felder übrig, für die noch keine Zuordnung möglich ist. Die kleinste Ziffer wird dabei aus den noch nicht mit blau markierten Zahlen ausgewählt werden. Im Beispiel ist es die Zahl 1. Das Feld mit dem kleinsten Eintrag beinhaltet die Kosten, die unvermeidlich sind, wenn man für diese Felder auch noch eine Zuordnung machen will. Um neue Nullen zu bekommen, lagert man jetzt die Kosten auf die anderen Zeilen und Spalten um. Dies tut man, indem man in allen nicht abgedeckten Feldern die minimalen Kosten subtrahiert und in den blau markierten Kreuzungspunkten dazu addiert. +Dieser Schritt 3 muss so oft wiederholt werden, bis genügend viele Nullen in der Matrix vorhanden sind. -\item in Schritt 4 sollen jetzt möglichst viele Nullen markiert werden, welche freistehend sind. +\item In Schritt 4 sollen jetzt möglichst viele Nullen markiert werden, welche freistehend sind. Freistehend bedeutet, dass sowohl in der jeweiligen Zeile und Spalte keine andere markierte Null vorhanden ist. \item Alle markierten Nullen werden jetzt in eine 1 umgewandelt. Die restlichen Ziffern in der Matrix, exklusiv die einsen, sollen jetzt ignoriert und durch eine Null ersetzt werden. -- cgit v1.2.1 From 3b4f8802c52ed799fc37d3c1338ac71905c2ed12 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Sun, 8 Aug 2021 20:13:10 +0200 Subject: neue version --- buch/papers/munkres/teil1.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'buch/papers/munkres') diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex index 6d8762e..97359fb 100644 --- a/buch/papers/munkres/teil1.tex +++ b/buch/papers/munkres/teil1.tex @@ -44,8 +44,8 @@ a_{21}&a_{22}&\dots &a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n1}&a_{n2}&\dots &a_{nn} \end{pmatrix} +\in \mathbb{R}^{n,n} \] -$\mathbb{\in}$ $\mathbb{R}^{n,n}$ kann der Faktor Kosten mit in die Rechnung eingebracht werden. In den Zellen 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$ dem Einsatzort $j$ zuordnet. -- cgit v1.2.1 From 7b66eb6617ad735754e009e3801aaa5acbcf2586 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Sun, 8 Aug 2021 20:34:58 +0200 Subject: neue version --- buch/papers/munkres/teil1.tex | 2 +- buch/papers/munkres/teil2.tex | 1 - buch/papers/munkres/teil3.tex | 7 +++---- 3 files changed, 4 insertions(+), 6 deletions(-) (limited to 'buch/papers/munkres') diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex index 97359fb..aad45cc 100644 --- a/buch/papers/munkres/teil1.tex +++ b/buch/papers/munkres/teil1.tex @@ -47,7 +47,7 @@ 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 $a_{i,j}$ Zahlen dargestellt, welche den Weg in z.B. Kilometer beschreiben. +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 diff --git a/buch/papers/munkres/teil2.tex b/buch/papers/munkres/teil2.tex index 9407c96..2fe24f8 100644 --- a/buch/papers/munkres/teil2.tex +++ b/buch/papers/munkres/teil2.tex @@ -8,6 +8,5 @@ \rhead{Schwierigkeit der Lösung (Permutationen)} Eine Permutation ist eine Anordnung von Objekten in einer bestimmten Reihenfolge oder eine Umordnung von Objekten aus einer vorgegebenen Reihung. Ist eine optimale Zuordnung gefunden, so steht in jeder Zeile und jeder Spalte der Matrix genau ein Element, das zur optimalen Lösung gehört, eine solche Gruppe von Positionen wird auch als Transversale der Matrix bezeichnet. - Die Problemstellung kann auch so formuliert werden, dass man die Zeilen- oder die Spaltenvektoren so umordnet soll, dass die Summe der Elemente in der Hauptdiagonale maximal wird. Hieraus wird sofort ersichtlich, dass es in einer $n$×$n$-Matrix genau so viele Möglichkeiten gibt, die Zeilen- bzw. Spaltenvektoren zu ordnen, wie es Permutationen von $n$ Elementen gibt, also $n!$. Außer bei kleinen Matrizen ist es nahezu aussichtslos, die optimale Lösung durch Berechnung aller Möglichkeiten zu finden. Schon bei einer 10×10-Matrix gibt es nahezu 3,63 Millionen (3.628.800) zu berücksichtigende Permutationen. diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex index 2693185..fd25a74 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -71,7 +71,8 @@ Freistehend bedeutet, dass sowohl in der jeweiligen Zeile und Spalte keine ander \subsection{Zuordnung der Kräne \label{munkres:subsection:malorum}} -Als Resultat des Munkres-Algorithmus kann man jetzt die folgende Zuordnung aus der Matrix ablesen: +Als Resultat des Munkres-Algorithmus werden in Abbildung 21.6 nebst dem minimalsten Transportweg auch die optimalste Zuweisung der Kräne auf die neuen Standorte ersichtlich. +Es können die folgenden Zuordnungen aus der Matrix abgelesen werden: \begin{itemize} \item Der Kran von Baustelle A1 soll zur Baustelle B2. \item Der Kran von Baustelle A2 soll zur Baustelle B3. @@ -84,6 +85,4 @@ Als Resultat des Munkres-Algorithmus kann man jetzt die folgende Zuordnung aus d \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} - -In Abbildung 21.6 ist nebst dem minimalsten Transportweg auch ersichtlich, wie die optimalste Zuweisung der Kräne auf die neuen Standorte erfolgen soll. \ No newline at end of file +\end{figure} \ No newline at end of file -- cgit v1.2.1