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 From 4f9cf26c7802a163da6b18cec9db62e75a9730cb Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20K=C3=BChne?= Date: Tue, 27 Jul 2021 12:30:10 +0200 Subject: neue version --- buch/papers/munkres/teil4.tex | 31 ++----------------------------- 1 file changed, 2 insertions(+), 29 deletions(-) (limited to 'buch/papers/munkres/teil4.tex') diff --git a/buch/papers/munkres/teil4.tex b/buch/papers/munkres/teil4.tex index 3d76743..9a27227 100644 --- a/buch/papers/munkres/teil4.tex +++ b/buch/papers/munkres/teil4.tex @@ -3,34 +3,7 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{Matrix-Interpretation +\section{- \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} +\rhead{-} -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