From cecdcdb230662af594ce68715c61f1263bff9ace Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Mon, 26 Jul 2021 07:57:58 +0200 Subject: add munkres files --- buch/papers/munkres/teil4.tex | 36 ++++++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) create mode 100644 buch/papers/munkres/teil4.tex (limited to 'buch/papers/munkres/teil4.tex') diff --git a/buch/papers/munkres/teil4.tex b/buch/papers/munkres/teil4.tex new file mode 100644 index 0000000..3d76743 --- /dev/null +++ b/buch/papers/munkres/teil4.tex @@ -0,0 +1,36 @@ +% +% teil4.tex -- Beispiel-File für Teil 4 +% +% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\section{Matrix-Interpretation +\label{munkres:section:teil4}} +\rhead{Matrix-Interpretation} +Gegeben ist die quadratische Matrix $C=(c_{ij})$ der Grösse $n\times n$. +Ohne Beschränkung der Allgemeinheit werden eine Zuordnung $j +\rightarrow s_j$, $j = 1, \dots, n$ mit minimaler Gesamtsumme +$\sum_{j=1}^{n}c_{s_j,j}$ gesucht, wobei die $s_j$ eine Permutation +von $\{1,\ldots ,n\}$ sind. +Soll die Summe maximiert werden, dann kann $C$ durch $-C$ ersetzt werden. +Die Grundlage dieses Verfahrens ist, dass sich die optimale Zuordnung +unter bestimmten Änderungen der Matrix nicht ändert, sondern nur +der Optimalwert. +Diese Änderungen sind durch Knotenpotentiale bzw.~duale Variablen +\begin{equation} +u_1 u_2,{\dots}, u_n +\end{equation} + +für die Zeilen und + +\begin{equation}v_1,v_2,\dots,v_n \end{equation} fuer die Spalten angegeben. +Die modifizierte Matrix hat dann die Komponenten $\tilde{c}_{i,j} += c_{ij} - u_j - v_j$. + +In der Summe über jede kantenmaximale Zuordnung kommt jedes +Knotenpotential genau einmal vor, so dass die Änderung der Zielfunktion +eine Konstante ist. +Sind die Einträge von $C$ nichtnegativ, und sind alle Knotenpotentiale +ebenfalls nichtnegativ, so nennt man die modifizierte Matrix \~{C} +auch eine Reduktion. +Ziel ist, in der reduzierten Matrix möglichst viele Komponenten auf +den Wert Null zu bringen und unter diesen die Zuordnung zu konstruieren. -- cgit v1.2.1