diff options
Diffstat (limited to 'buch/papers/munkres/teil0.tex')
| -rw-r--r-- | buch/papers/munkres/teil0.tex | 19 |
1 files changed, 4 insertions, 15 deletions
diff --git a/buch/papers/munkres/teil0.tex b/buch/papers/munkres/teil0.tex index 1ef0538..0578429 100644 --- a/buch/papers/munkres/teil0.tex +++ b/buch/papers/munkres/teil0.tex @@ -3,19 +3,8 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{Geschichte\label{munkres:section:teil0}} -\rhead{Geschichte} -Die Ungarische Methode wurde 1955 von Harold Kuhn entwickelt und veröffentlicht. -Der Name ``Ungarische Methode'' ergab sich, weil der Algorithmus -weitestgehend auf den früheren Arbeiten zweier ungarischer Mathematiker -basierte: Dénes Kőnig und Jenő Egerváry. -James Munkres überprüfte den Algorithmus im Jahr 1957 und stellte fest, -dass der Algorithmus (stark) polynomiell ist. -Seitdem ist der Algorithmus auch als Kuhn-Munkres oder -Munkres-Zuordnungsalgorithmus bekannt. -Die Zeitkomplexität des ursprünglichen Algorithmus war $O(n^4)$, -später wurde zudem festgestellt, dass er modifiziert werden kann, -um eine $O(n^3)$-Laufzeit zu erreichen. - - +\section{Einleitung\label{munkres:section:teil0}} +\rhead{Einleitung} +Im Bereich der Unternehmensplanung (Operations Research) gibt es verschiedene Fragestellungen. Eine davon ist das sogenannte Transportproblem. Zum Transport einheitlicher Objekte von mehreren Angebots- zu mehreren Nachfrageorten ist ein optimaler, d. h. kostenminimaler Plan zu finden, wobei die vorhandenen und zu liefernden Mengen an den einzelnen Standorten gegeben sowie die jeweiligen Transportkosten pro Einheit zwischen allen Standorten bekannt sind. +Nun gibt es im Bereich des klassischen Transportproblems Sonderfälle. Ein Sonderfall ist z.B. das Zuordnungsproblem. |