Stern Mathematik: kleine mathematische Hilfe für potentielle Schwiegermütter
Released by matroid on Mi. 23. November 2005 20:31:34 [Statistics]
Written by N-man - 5435 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\) BildSehr geehrte potentielle Schwiegermütter, dieser kleine Artikel soll Ihnen helfen die liebreizende Tochter bzw. den werten Sohn endlich zufriedenstellend unter die Haube zu bringen. Dabei wird nur erklärt werden, wie man solch ein zufriedenstellendes Schwiegerkind findet. Die Aufgabe, das eigene Kind von dieser Wahl anschließend zu überzeugen, obliegt Ihnen und den Früchten Ihrer dominanten Erziehung.



Zunächst möchten wir zwei kleine Einschränkungen treffen:

Wir wollen annehmen, dass nur potentielle Schwiegermütter aus Dörfern diesen Artikel wirklich interessiert lesen.
Wir wollen annehmen, dass jeweils das zukünftige Schwiegerkind aus dem gleichen Dorf kommt.

Dies sind natürlich keine wirklichen Einschränkungen, denn: Wie man weiß, ist die Stadt ein Sündenpfuhl. Hurerei, Drogen und die Spaßgesellschaft führen in der Stadt zu einem Werteverlust, dem auch die Ehe zum Opfer gefallen ist. Die städtische Gesellschaft ist eine Singlegesellschaft, die städtische Schwiegermutter stirbt aus! Und vernünftigerweise kann das zukünftige Schwiegerkind nur aus dem gleichen Dorf kommen, denn wie alle Dörfler wissen, ist aus dem Nachbardorf (geschweige von noch weiter weg) noch nie etwas Gutes gekommen. Eine Ehe, in die das Schwiegerkind neue Sitten und Bräuche einführt, ist zum Scheitern verurteilt! Die Frage lautet nun, wie finden Sie, werte potentielle Schwiegermutter, aus den Unverheirateten Ihres Dorfes den zufriedenstellendsten Partner für Ihr Kind? Aus einer subjektiven Sicht ist diese Frage oftmals leicht zu beantworten. Natürlich ist der ledige Dorfarzt dem Trinkerhannes vorzuziehen; die Müller Edith mit ihrer hohen Austeuer allen anderen Jungfern. Leider bringt eine Ehe, die nach solch subjektiven Kriterien gestiftet wurde, oftmals Neid und Gerede im Dorf mit sich. Die positiven Eigenschaften des Schwiegerkindes werden dann mit jahrelangem Nachbarschaftsstreit aufgewogen. Das ist natürlich nicht wünschenswert. Uns stellt sich also die Aufgabe: Wie findet man das optimale Schwiegerkind und erhält gleichzeitig den Dorffrieden? Zur Lösung dieser heiklen Aufgabe schlagen wir vor, regelmäßig eine Konferenz der potentiellen Schwiegermütter des Dorfes (kurz: Koschwi) abzuhalten. Die Beratungen der Koschwi legen die Grundlage, um anschließend mit ein paar mathematischen Tricks festlegen zu können, wer mit wem zu verheiraten ist, um alle relativ glücklich zu machen und so den Dorffrieden zu wahren. Die Koschwi hat die Aufgabe alle denkbaren potentiellen Paarungen zwischen einem unverheirateten Mann und einer unverheirateten Frau des Dorfes zu bewerten. Die Bewertung sollte objektiv erfolgen. Um dies zu gewährleisten ist zu Sitzungsbeginn ein Punktekatalog zu verabschieden. Die Bewertung jeder Paarung erfolgt nach diesem Katalog. Beispielsweise könnten für soziale Stellung, eingebrachtes Vermögen, erlernte Berufe, Ausbildung, Kochkünste, ... Pluspunkte; für zu großen Altersunterschied, zu nahen Verwandtschaftsgrad usw. Minuspunkte vergeben werden. Eine progressive Dorfgemeinschaft könnte vielleicht auch "Liebe" bepunkten und Paarungen in Betracht ziehen, in denen die Frau älter als der Mann ist. Machen wir es an einem Beispiel fest. Nach der Bewertung der Koschwi kann das Ergebnis in einer Tabelle festgehalten beispielsweise so aussehen:
Bernd Fred Hans Horst Hugo Karl Otto Peter
Anna 12 43 -32 - 13 2 45 -11
Brit - 57 -10 - 39 59 60 3
Edith 60 62 9 - - 65 71 21
Franzi 0 12 -50 19 20 -23 44 30
Moni 28 43 - -22 13 - 34 -
Uta 13 -2 -41 -11 15 5 8 4

Die ganzen "-" in der Tabelle zeigen, bei welchen Paaren unsere Beispiel-Koschwi sich einfach keine Ehe vorstellen kann, z.B. weil die beiden potentiellen Eheleute Geschwister sind oder es gesellschaftlich einfach unmöglich ist. Wir möchten den Dorffrieden wahren, indem wir durch geschickte Eheschließungen alle möglichst zufriedenstellen. Sie, liebe Schwiegermutter, sind zufrieden, falls die Heirat Ihres Sprösslings eine möglichst hohe Punktzahl laut Tabelle bringt. Das Dorf ist zufrieden, wenn die Summe der Punktzahlen aller Eheschließungen möglichst hoch ist. Das heißt aber, dass Paare mit einer negativen Punktzahl ebenfalls nicht in Betracht kommen. Eine negative Punktzahl macht weder Sie als Schwiegermutter glücklich, noch hilft eine zum Scheitern verurteilte Ehe dem Dorffrieden weiter. Es ergibt sich also sinnvollerweise eine neue modifizierte Tabelle:
Bernd Fred Hans Horst Hugo Karl Otto Peter
Anna 12 43 - - 13 2 45 -
Brit - 57 - - 39 59 60 3
Edith 60 62 9 - - 65 71 21
Franzi - 12 - 19 20 - 44 30
Moni 28 43 - - 13 - 34 -
Uta 13 - - - 15 5 8 4

Nach Fertigstellung der Tabelle ist die Aufgabe der Koschwi eigentlich schon beendet. Vielleicht trinkt man jetzt ein Tässchen Kaffee und tauscht die neuesten Neuigkeiten aus. Natürlich kann man auch ein wenig über die Planlosigkeit der Eheschließungen in Nachbardörfern herziehen. Klüger als die war man ja schon allemal! Ab jetzt wird es mathematischer... Die Arbeit geht also auf einen Zahlenmenschen über. Natürlich kann das auch weiterhin eine potentielle Schwiegermutter sein.

Die graphentheoretische Darstellung
Das hier dargestellte Heiratsproblem ist ein spezielles Matchingproblem. "Match" kommt aus dem Englischen und bedeutet in diesem Fall "Paar". Gegeben ist ein Graph G=(V,E) mit einer Knotenmenge V und einer Kantenmenge E. Ein Matching ist eine Auswahl M der Kanten von G, so dass keine zwei Kanten von M adjazent sind, d.h. keine zwei Kanten besitzen einen gemeinsamen Knoten. Bild Dies ist ein Beispiel für ein Matching. Aus dem linken Graphen werden die roten Kanten ausgewählt, diese bilden ein Matching. Für die Modellierung als Matchingproblem abstrahieren wir nun unsere Dorfunverheirateten zu Knoten eines Graphen. Eine Kante symbolisiert die Denkbarkeit der Eheschließung und jede Kante ist mit einem sogenannten Gewicht (=der von der Koschwi zugesprochenen Punktzahl) versehen. Der so entstandene Graph gehört einer besonderen Sorte von Graphen an, denn unsere Knoten können wir in zwei Klassen aufteilen (Männlein und Weiblein). Jede Kante verbindet nur Knoten verschiedener Klassen. Einen Graphen mit dieser Eigenschaft nennt man bipartiten Graphen. Für unser Beispiel ist die Darstellung auf Grund der nicht ganz niedrigen Knotenanzahl doch etwas unübersichtlich. Deswegen ein etwas kleineres Beispiel für die Darstellung eines bipartiten Graphen: Bild Auf einem solchen Graphen suchen wir nun ein Matching. Die Bipartität liefert uns nur Paare aus Mann und Frau, die Eigenschaften eines Matchings garantieren uns, dass wir niemanden doppelt verheiraten. Jedes Matching beschreibt also einen zulässigen "Verheiratungsplan". Für unser Dorffriedensoptimum benötigen wir das Matching mit maximalem Kantengewicht. Dieser Abschnitt bringt keine neuen Erkenntnisse, er zeigt nur, wie man das gestellte Problem verallgemeinert darstellen kann. In der Literatur wird die Suche eines gewichtsmaximalen Matchings auf einem bipartiten Graph oft durch das Beispiel Arbeiter-Maschine illustriert. Jeder Arbeiter (=die erste Knotenklasse) hat gewisse Erfahrungen (=Kantengewichte) mit der Bedienung einer Maschine (=andere Knotenklasse). Welcher Arbeiter sollte jetzt welche Maschine bedienen? Oftmals ist man nicht auf der Suche nach einem gewichtsmaximalen Matching, sondern einfach nach einem maximalen Matching: Man sucht die maximale Kantenanzahl, aus denen ein Matching bestehen kann. Das ist aber kein neues Problem. Setzt man alle Kantengewichte auf 1, liefert das gewichtsmaximale Matching ein maximales Matching und der Wert des gewichtsmaximalen Matchings verrät, wieviele Kanten ein maximales Matching bilden. Genug der Vorrede, es wird langsam Zeit für eine Lösung! Es sollen hier zwei Lösungswege angegeben werden. Der erste Lösungsweg wird nur der Vollständigkeit halber dargestellt... er hat so einen Informatik-Touch an sich... nicht, dass das etwas Schlechtes wäre. Der zweite Lösungsweg ist der eigentliche Grund für diesen Artikel. Als ich vor mehr als einem Jahr damit in Berührung kam, war ich ganz fasziniert davon... vielleicht kann das jemand nachvollziehen.



Ein Lösungsalgorithmus für das Problem des gewichtsmaximalen Matchings

Um besser arbeiten zu können, müssen wir jetzt ein wenig Notation einführen. Gegeben sind ein bipartiter Graph G=(V_1+V_2|,E) mit den beiden Knotenklassen V_1 und V_2| und der Kantenmenge E\subseteq V_1 x V_2 sowie eine Gewichtsfunktion w: E->\IR^+. Gesucht wird ein gewichtsmaximales Matching M. Wir motzen unseren Graphen G nun noch etwas auf. Wir möchten erreichen, dass abs(V_1)=abs(V_2)=n ist. Durch Einführung neuer künstlicher Knoten kann diese Bedingung sichergestellt werden. Desweiteren fordern wir, dass ein vollständiger bipartiter Graph vorliegt, d.h. jeder Knoten aus V_1 ist mit allen Knoten aus V_2 verbunden (und dementsprechend auch jeder Knoten aus V_2 mit allen aus V_1). Um diese Bedingung zu erfüllen, werden gegebenenfalls neue künstliche Kanten eingeführt und mit einem Kantengewicht von 0 versehen. Den so entstandenen Graphen nennen wir G'. Man kann sich leicht überlegen, dass ein gewichtsmaximales Matching auf dem aufgemotzten Graphen G' einem gesuchten Matching auf dem Originalgraphen G entspricht, da die neuen 0-Kantengewichte das Gesamtgewicht nicht verändern. Ebenfalls kann man sich unschwer überlegen, dass es in einem maximalen gewichtsmaximalen Matching für jeden Knoten eine Kante gibt, die zu diesem Knoten inzident ist. Für unserer Heiratsproblem heißt das nichts anderes, als dass wir bei gleicher Anzahl von Männern und Frauen im Optimalfall auch alle verheiratet haben. War es notwendig künstliche Knoten einzuführen, dann ist die Heirat mit einem solchen Knoten leider die Ehelosigkeit. Es gibt ja auch Nonnen, die mit ihrem Kloster verheiratet sind... Vielleicht hilft diese Vorstellung für das Verständnis. Bevor wir zum eigentlichen Algorithmus kommen können, müssen wir noch etwas rumbasteln. Es ist notwendig aus unserem Maximierungsproblem ein Minimierungsproblem zu machen. Ist v das größte Gewicht einer Kante im Graph G', dann ersetzen wir für jede Kante k von G' ihr ursprüngliches Gewicht w(k) durch w'(k):=v-w(k). Ein maximales Matching minimalen Gewichts in G' liefert uns das gesuchte gewichtsmaximale Matching in G. Auch das kann man leicht einsehen. Durch die Transformation der Gewichte erhält man neue nichtnegative Gewichte, wobei aus dem größten Gewicht das kleinste geworden ist usw. Aus dem maximalen gewichtsmaximalen Matching wird das maximale gewichtsminimale. Am Besten ist wohl wir versuchen das an unserem Beispiel nachzuvollziehen. In unserem Dorf leben acht unverheiratete Männer, allerdings nur sechs Frauen. Wir führen also zwei künstliche, "weibliche" Knoten ein. Den bipartiten Graphen machen wir nun noch vollständig, indem wir die von der Koschwi nicht vorgesehenen Paarungen mit 0 bewerten. Es ergibt sich analog zur Tabelle die folgende Gewichtsmatrix. ((array(12,43,0,0,13,2,45,0;0,57,0,0,39,59,60,3;60,62,9,0,0,65,71,21;0,12,0,19,20,0,44,30;28,43,0,0,13,0,34,0;13,0,0,0,15,5,8,5;0,0,0,0,0,0,0,0;0,0,0,0,0,0,0,0))) Die größte Punktzahl haben Edith und Otto mit 71 Punkten erreicht, also ist v=71. Um auf unser Minimierungsproblem zu transformieren, werden nun alle Gewichte jeweils von 71 subtrahiert. ((array(59,28,71,71,58,69,26,71;71,14,71,71,32,12,11,68;11,9,62,71,71,6,0,50;71,59,71,52,51,71,27,41;43,28,71,71,58,71,37,71;58,71,71,71,56,66,63,66;71,71,71,71,71,71,71,71;71,71,71,71,71,71,71,71))) Was können wir mit dieser Matrix nun anfangen? Wir suchen ein maximales Matching, d.h. in diesem Falle sollen 8 Paare vor den Traualtar treten. Eine Zeile symbolisiert eine Frau, eine Spalte einen Mann. Wählt man ein Matrixelement aus, ist damit auch ein Brautpaar ausgewählt. Natürlich darf aus jeder Zeile und aus jeder Spalte nur je ein Element gewählt werden. Eine Auswahl, die diese Bedingung erfüllt, soll Diagonale der Länge n heißen. Es gibt n! solche Diagonalen. Für n=8 macht das 40320 Kombinationsmöglichkeiten. Unter all diesen Kombinationsmöglichkeiten suchen wir diejenige, bei der die Summe der ausgewählten Elemente minimal ist. Die Auswahl der n konkreten Paarungen lässt sich mit einer Permutationsmatrix X verdeutlichen: X=menge(x_ij)_(i,j=1..n) wobei x_ij =fdef(1, (i,j)\el M;0, sonst) Es gilt die praktische Eigenschaft, dass das Abziehen einer Konstanten p von jedem Element einer Zeile oder von jedem einer Spalte das optimale Matching nicht verändert, sondern nur dessen Gewicht um p verringert. Der Beweis ist ein Einzeiler: Von jedem Element der h-ten Zeile der Matrix W wird p_h abgezogen. Es ergibt sich eine neue Matrix W' mit Einträgen w'_ij=w_ij für alle i!=h sowie w'_hj=w_hj-p_h. Für das Gesamtgewicht des von der Permutationsmatrix X repräsentierten Matchings M gilt: w'(M)=sum(w'_ij|x_ij,i und j)=sum(w_ij|x_ij,i und j)-p_h |sum(x_hj,j)=sum(w_ij|x_ij, i und j)-p_h=w(M)-p_h Eine analoge Aussage ergibt sich für die Addition eines festen Wertes zu einer Zeile oder einer Spalte. Ein gewichtsminimales maximales Matching findet man natürlich besonders gut, wenn es eines gibt, das nur Kanten mit Gewicht Null enthält. Damit ist die Hauptidee dieses Lösungsalgorithmus verraten: Durch Subtraktion in einer Zeile bzw. Spalte werden Nullen erzeugt. Dabei ist darauf zu achten, dass keine Einträge negativ werden. Dies wird solange wiederholt, bis eine Diagonale der Länge n ausgewählt werden kann, für deren Elemente das Gewicht jeweils 0 ist. Die zugehörigen Paarungen bilden offensichtlich das maximale Matching minimalen Gewichtes. Wenden wir das auf unsere Matrix W an. Zunächst ziehen wir von allen Elementen einer Zeile h das jeweilige Zeilenminimum p_h ab. Also konkret: p_1=26, p_2=11, p_3=0, p_4=27, p_5=28, p_6=56, p_7=p_8=71. Damit ergibt sich die neue Matrix ((array(33,2,45,45,32,43,0,45;60,3,60,60,21,1,0,57;11,9,62,71,71,6,0,50;44,32,44,25,24,44,0,14;15,0,43,43,30,43,9,43;2,15,15,15,0,10,7,10;0,0,0,0,0,0,0,0;0,0,0,0,0,0,0,0))) Nun könnte man ebenfalls von den Spalten einen entsprechenden Wert q_h abziehen. Da sich aber in jeder Spalte schon bereits eine 0 befindet, ist q_h stets 0. Damit kommen wir also nicht weiter. Wir benötigen eine neue Idee. Halten wir zunächst einmal fest, dass man in unserer aktuellen Matrix eine 0-Diagonale höchstens der Länge 5 finden kann, z.B. durch w_17, w_52, w_65, w_71, w_73 . Es gilt: Falls eine Matrix eine 0-Diagonale der maximalen Länge m hat, existieren e Zeilen und f Spalten mit e+f=m, so dass alle(!) Nullen der Matrix durch diese Zeilen und Spalten abgedeckt werden. Der Beweis soll jetzt nur kurz skizziert werden. Wer sich für Graphentheorie interessiert, weiß, dass die Größe des minimalen Trägers gleich der Größe eines maximalen Matchings eines Graphen ist. Wir konstruieren einen Hilfsgraphen, der alle Knoten des ursprünglichen Graphen enthält und Kanten dort, wo der entsprechende Matrixeintrag 0 ist. Ein Matching in diesem Graphen entspricht einer 0-Diagonale in der Matrix, ein Träger entspricht einer Auswahl von Zeilen und Spalten. In unserem Beispiel decken beispielsweise die 5te, 7te und 8te Zeile sowie die 5te und 7te Spalte alle Nullen der Matrix. Da wir noch keine vollständige 0-Diagonale haben, können durch die ausgewählten Zeilen und Spalten nicht alle Matrixelemente abgedeckt werden. Sei w^- das kleinste nichtabgedeckte Matrixelement. Wir subtrahieren w^- von allen Elementen nicht abgedeckter Zeilen, anschließend addieren wir w^- zu allen abgedeckten Spalten. Dieses Subtrahieren und Addieren verändert ein optimales Matching wiederum nicht, nur sein Gewicht. Für die neuen Matrixelemente w'_ij gilt: w'_ij=fdef(w_ij-w^-, w_ij ist unbedeckt; w_ij, w_ij von Zeile oder Spalte bedeckt; w_ij+w^- , w_ij von Zeile und Spalte bedeckt Nach dieser Transformation liegt also wiederum eine Matrix mit nichtnegativen Einträgen vor. Insgesamt gibt es ef doppelt bedeckte und n^2-n(e+f)+ef gar nicht bedeckte Einträge. Sei W_g = sum(w_ij,i und j,) das Gesamtgewicht der alten Matrix und W'_g analog das der neuen, dann gilt mit Vorüberlegungen: W'_g -W_g=(ef)|w^- -(n^2-n(e+f)+ef)|w^- =(n(e+f)-n^2)|w^- <0 da ja laut Annahme e+f Durch Subtraktion der 1 von allen unbedeckten Zeilen und Addition zu allen bedeckten Spalten erhält man eine neue Matrix: ((array(32,1,44,44,32,42,0,44;59,2,59,59,21,0,0,56;10,8,61,70,71,5,0,49;43,31,43,24,24,21,0,13;15,0,43,43,21,43,10,43;1,14,14,14,0,9,7,9;0,0,0,0,1,0,1,0;0,0,0,0,1,0,1,0))) Im nächsten Schritt kann man nun zusätzlich die zweite Zeile oder die sechste Spalte abdecken. Anders gesagt, man hat nun schon eine 0-Diagonale der Länge 6 innerhalb der Matrix. Man kommt nach zwei weiteren Iterationen zum Ziel, falls man in der ersten Iteration zusätzlich die 6te Spalte abdeckt und w^- =w_31 =10 wählt. Im letzten Schritt lassen sich die ersten sieben Spalten abdecken und w^- =w_47 =3 wählen. Man erhält: Bild Das Problem ist ENDLICH gelöst! Wir geben hiermit die Vermählung von Edith und Bernd (60 Punkte) Moni und Fred (43 Punkte) Uta und Hugo (15 Punkte) Brit und Karl (59 Punkte) Anna und Otto (45 Punkte) Franzi und Peter (30 Punkte) bekannt. Hans und Horst gehen leider leer aus. Sie werden wohl auf die Priesterschule gehen müssen. Ist doch auch schön! Der Algorithmus kurz und knapp Gegeben sei eine nxn-Matrix der Gewichte w_ij \el \IN_0|. \big Erstens Subtrahiere für i=1..n von allen Elementen der i-ten Zeile das kleinste Element p_i = min(j,w_ij) dieser Zeile. Subtrahiere für j=1..n von allen Elementen der j-ten Spalte das kleinste Element q_j = min(i,w_ij) dieser Spalte. \big Zweitens Suche eine minimale Überdeckung der Nullen. Hat die Überdeckung weniger als n Zeilen und Spalten, gehe zu Drittens, sonst zu Viertens. \big Drittens Sei w^- der kleinste unbedeckte Eintrag. Subtrahiere w^- von allen unbedeckten Einträgen, addiere w^- zu Einträgen, die von einer Zeile und einer Spalte bedeckt werden. Gehe zu Zweitens. \big Viertens Bestimme 0-Diagonale der Länge n.


Ein zweiter (schönerer?) Lösungsweg
Nun gut... Schönheit ist relativ. Vielleicht ist dieser Lösungsweg nicht schöner, aber (für mich) ist überraschend, dass es überhaupt so funktioniert. Unser Heiratsproblem ist optimierungstechnisch gesehen ein Maximierungsproblem. Wir möchten schließlich das Glück des Dorfes maximieren. Vielleicht gelingt es uns ja, das Ganze als 0815-Optimierungsaufgabe darzustellen, d.h. eine schöne Zielfunktion, ein paar nette Nebenbedingungen, alles möglichst linear. Wenn uns das gelingt, haben wir die Hilfsmittel der linearen Optimierung zur Verfügung um das Problem zu lösen. Oh Wunder, oh Wunder... es geht tatsächlich und ist sogar recht unkompliziert. Wir betrachten die lineare Optimierungsaufgabe max(x,w^T|x) Ax<=e x>=0 Solange nicht erklärt ist, wofür A, b, e und x stehen, wird das noch niemanden aus den Schuhen hauen. Wir stellen uns vor, wir haben alle Kanten des bipartiten Graphen, der aus der Koschwi hervorgeht, von 1 bis m nummeriert. Das heißt, jede potentiell denkbare Eheschließung bekommt eine Nummer zwischen 1 und m. x ist nun ein m-dimensionaler Vektor, dessen Komponenten nur die Werte 0 oder 1 annehmen sollen, also x\el menge(0,1)^m|. Der Wert 0 wird angenommen, wenn wir die entsprechende Kante nicht in unser Matching aufnehmen, der Wert 1, wenn dieses Paar den Segen der Koschwi erhält. MOMENT! Das geht doch nicht! Wir wollen die Lösung einfach finden, z.B. mit dem Simplexalgorithmus, denn das ist das erste, was man in der linearen Optimierung kennenlernt. Doch wir schränken unsere zulässigen Lösung von vornherein nur auf ganzzahlige Werte ein! Das ist etwas, was der Simplexalgorithmus nicht verträgt. Wir können uns zwar wünschen, dass unsere Optimallösung ganzzahlig sein soll, aber der Simplexalgorithmus wird sich darum einen Dreck scheren, er liefert uns i.A. irgendeine reelle, nicht ganze Lösung. Das Optimum unter den ganzzahligen zulässigen Lösungen zu finden, wird schwieriger sein und nicht so billig, wie wir es uns erhofft haben. Verschieben wir dieses Problem auf später. Ich verspreche (und das ist das überraschende an diesem Weg), alles wird sich in Wohlgefallen auflösen. Definieren wir also weiter. Der Vektor w\el\IR^m versammelt die Kantengewichte, d.h. die Punktzahlen, die die Koschwi vergeben hat. Die oben geforderten Eigenschaften unseres Lösungsvektors x vorausgesetzt, beschreibt die Zielfunktion das Gewicht des Matchings... eben die Summe der Gewichte der Kanten, die das Matching bilden. Angenommen unser bipartiter Graph besteht aus n Knoten, d.h wir haben n Unverheiratete im Dorf. Dann ist A eine nxm-Matrix und heißt die Knoten-Kanten-Inzidenzmatrix des Graphen. Dabei gehen wir davon aus, dass wiederum alle Knoten von 1 bis n durchnummeriert sind. Es ist also A=menge(a_ij)_(i=1..n, j=1..m) mit a_ij=fdef(1, Knoten i gehört zu Kante j; 0, sonst) Überlegen wir uns einmal, was passiert wenn wir nun A und x multiplizieren. Es wird ein n-elementiger Spaltenvektor entstehen. Beispielsweise ist das erste Element dieses Vektors das Produkt aus erster Zeile der Matrix A und dem Vektor x. Die erste Zeile von A "gehört" zum ersten Knoten, diese Zeile besteht aus Einsen und Nullen, je nachdem ob der erste Knoten zur entsprechenden Kante gehört oder nicht. Machen wir ein einfaches Beispiel für das Produkt einer Matrixzeile mit dem Vektor x: define(w1,\blue\1) define(w2,\red\1) define(w3,\green\1) define(n2,\red\O) define(n3,\green\O) define(n4,\darkgreen\O) (\w1,\n2,\w3,\n4)*(\w1;\w2;\n3;\n4)=\w1+\n2+\n3+\n4=1 Wir erhalten einen Summanden 1, falls der Knoten zur aktuellen Kante gehört und die Kante ins Matching aufgenommen wird (blau); eine Null erhält man in allen anderen Fällen, d.h. falls die Kante ausgewählt wird, aber der Knoten gar nicht zur aktuellen Kante gehört (rot) oder falls zwar der Knoten zur Kante gehört, aber diese Kante kommt nicht ins Matching (hellgrün), oder falls die Kante nicht ausgewählt wird und der Knoten ihr auch nicht angehört (dunkelgrün). Falls wir ein Matching suchen, heißt das aber auch, dass unser Produkt aus Matrixzeile und x-Vektor nur 0 oder 1 ergeben darf. Ist das Ergebnis größer, befinden sich mehrere Kanten in der Auswahl, die von ein und demselben Knoten ausgehen, damit liegt aber kein Matching mehr vor. Folglich ist e ein Vektor, der komplett aus Einsen besteht. Damit sind alle Komponenten des linearen Programms erklärt. Die Nebenbedingungen stellen sicher, dass ein Matching vorliegt, falls x außerdem ganzzahlig ist; die Zielfunktion beschreibt das zu maximierende Gewicht des Matchings. Es bleibt die Frage, warum die Simplexmethode nur ganzzahlige Lösungen von max(x,w^T|x) Ax<=e x>=0 erzeugt. Das ist nicht sofort einzusehen, hängt aber damit zusammen, dass die Knoten-Kanten-Inzidenzmatrix eines bipartiten Graphen eine sehr spezielle Struktur hat. Holen wir etwas weiter aus... Allerdings fangen wir jetzt nicht ganz von vorn an, d.h. ein paar Grundkenntnisse aus der linearen Optimierung und der linearen Algebra werden vorausgesetzt. Also warum müssen (optimale) Basislösungen ganzzahlig sein? \big Definition: Eine Matrix A\el\IZ^mxn mit vollem Zeilenrang heißt unimodular, falls die Determinante jeder aus m linear unabhängigen Spalten bestehenden Submatrix betragsmäßig gleich 1 ist. \big Satz 1: Sei A\el\IZ^mxm regulär. Dann ist A^(-1)|b für alle b\el\IZ^m ganzzahlig genau dann, wenn A unimodular ist. \big Beweis: Hinrichtung: Zu zeigen ist, dass die Determinante von A betragsmäßig 1 ist. Sei e_i ein m-dimensionaler Vektor, dessen i-te Komponente 1, alle anderen Komponenten 0 sind. A^(-1)|e_i liefert die i-te Spalte von A^(-1) und ist laut Voraussetzung ganzzahlig, somit ist A^(-1) eine ganzzahlige Matrix. Desweiteren gilt: 1=det(I)=det(A)*det(A^(-1)) Da die Determinanten ganzzahliger Matrizen ganzzahlig sind, muss die Determinante von A (und auch die von A^(-1)) betragsmäßig 1 sein. Rückrichtung: Die Cramersche Regel liefert sofort die Ganzzahligkeit. \big Satz 2: A\el\IZ^mxn habe vollen Zeilenrang und es sei b\el\IZ^m . Alle zulässigen Basislösungen von menge(x>=0: Ax=b) sind ganzzahlig genau dann, wenn A unimodular ist. \big Beweis: Hinrichtung: Wir müssen zeigen, dass A unimodular ist. Sei B eine beliebige Basis von A, dann genügt es wegen Satz 1 zu zeigen, dass A_B^(-1)|b für alle ganzzahligen b ganzzahlig ist. Sei also b\el\IZ^m. Wir wählen c\el\IZ^m so, dass c+(A_B)^(-1)|b>=0. Dann ist b^- =A_B|(c+(A_B)^(-1)|b) = A_B|c + b \el\IZ^m. Setzen wir x^-_B :=c+(A_B)^(-1)|b und x^-_N=0, dann ist x^- = (x^- _B , x^- _N) zulässige Basislösung von menge(x>=0, Ax=b^-). Also ist x^- nach Voraussetzungen ganzzahlig und damit auch (A_B)^(-1)|b =x^-_B-c. Rückrichtung: Ist A unimodular, b\el\IZ^m und x^- eine zulässige Basislösung vom menge(x>=0: Ax=b), dann gibt es eine Basis B mit x^- = (x^- _B , x^- _N) =((A_B)^(-1)|b,0). Nach Satz 1 ist x^-_B ganzzahlig. Daraus folgt, dass x^- \el\IZ^n. Nun gut, wir haben nachgewiesen, dass, falls A unimodular ist, die Basislösungen des Systems Ax=b für ganzzahlige b ganzzahlig sind. Das ist ja schon was. Es gibt aber noch zwei kleine Haken. Zum einen wissen wir noch nicht, ob unsere Knoten-Kanten-Inzidenzmatrix irgendetwas mit Unimodularität zu tun hat, zum anderen treten in unserem Matching-Problem keine Gleichungsnebenbedingungen, sondern Ungleichungsnebenbedingungen auf. Wenden wir uns zuerst dem zweiten Haken zu. Der Simplexalgorithmus verlangt sowieso Gleichungsnebenbedingungen oder einfache Ungleichungsbedingungen in Form von Vorzeichenbeschränkungen der Variablen. Aus allgemeinen Ungleichungen werden Gleichungen durch Einführen von Schlupfvariablen s. Aus Ax<=b entsteht also ein neues System Ax+s=(A,I)*(x;s)=b mit der Vorzeichenbeschränkung s >= 0. Nach Satz 2 muss (A,I) unimodular sein, damit dieses System nur ganzzahlige Basislösungen hat. Was bedeutet nun die Unimodularität der erweiterten Matrix (A,I)? Mit Hilfe des Laplaceschen Entwicklungssatzes kann man leicht zeigen, dass die Determinante jeder quadratischen Untermatrix von A, gleich welcher Dimension, den Wert 0, 1 oder -1 haben muss. Das ist offensichtlich eine stärkere Forderung und Anlass zu einer weiteren Definition. \big Definition Eine Matrix A\el\IZ^mxn heißt total unimodular, wenn jede quadratische Untermatrix die Determinante 0, 1, -1 hat. Eine triviale Folgerung ist, dass eine total unimodulare Matrix A\el menge(0,1,-1)^mxn sein muss. Desweiteren ist folgendes leicht einzusehen: A ist total unimodular genau dann, wenn (A,I) unimodular ist. Jetzt kommt der Knackpunkt Nummer 1! \big Satz von Hoffman und Kruskal Sei A\el\IZ^mxn total unimodular und b\el\IZ^m. Dann sind alle (optimalen) Basislösungen von max(x,c^t|x) unter den Nebenbedingungen Ax<=b, x>=0 ganzzahlig. \big Beweis Die Nebenbedingungen sind äquivalent zu (A,I)*(x;s)=b mit x, s >=0. (A,I) ist aufgrund der vorangegangenen Bemerkungen unimodular. Wegen Satz 2 sind die Basislösungen des neuen Optimierungsproblems mit den Variablen x und s ganzzahlig, und der x-Anteil ist optimal für das Ausgangsproblem. Juhu! Wir sind fast fertig. Uns fehlt noch ein einfacher Weg herauszufinden, ob unsere Inzidenzmatrix total unimodular ist. Es existiert zwar eine Definition für totale Unimodularität, aber es ist unpraktikabel für eine Matrix die Determinanten aller quadratischen Submatrizen nachzuprüfen. Abhilfe schafft folgender Satz, der unbewiesen bleiben soll. \big Satz von Heller und Tompkins Sei A\el menge(0,1,-1)^mxn mit höchstens zwei von Null verschiedenen Einträgen pro Spalte. A ist genau dann total unimodular, wenn sich die Zeilen von A in zwei Klassen einteilen lassen, so dass zwei Zeilen, die in einer Spalte beide eine +1 oder beide eine -1 haben, zur gleichen Klasse gehören und zwei Zeilen, von denen die eine in einer Spalte eine +1 und die andere in der gleichen Spalte eine -1 haben, zu verschiedenen Klassen gehören. Man überzeugt sich leicht, dass unsere Inzidenzmatrix diese Bedingung erfüllt: Die Spalten der Matrix symbolisieren jeweils eine Kante. An genau zwei Stellen jeder Spalte steht eine 1, sonst Nullen. Alle Zeilen lassen sich also in die erste Klasse einordnen. Wenden wir dieses Verfahren auf unser Beispieldorf. Wir nummerieren zunächst die Knoten (=die Unverheirateten) von 1 bis 14 und die Kanten (=potentielle Paarungen) von 1 bis 30:
Bernd
7
Fred
8
Hans
9
Horst
10
Hugo
11
Karl
12
Otto
13
Peter
14
Anna
1
12
1
43
2
- - 13
3
2
4
45
5
-
Brit
2
- 57
6
- - 39
7
59
8
60
9
3
10
Edith
3
60
11
62
12
9
13
- - 65
14
71
15
21
16
Franzi
4
- 12
17
- 19
18
20
19
- 44
20
30
21
Moni
5
28
22
43
23
- - 13
24
- 34
25
-
Uta
6
13
26
- - - 15
27
5
28
8
29
4
30

Damit ergibt sich die folgende gaaaanz ausführlich aufgeschriebene Gestalt für das lineare Programm: max 12x_1+43x_2+13x_3+2x_4+45x_5+57x_6+39x_7+59x_8+60x_9+3x_10+60x_11+ 62x_12+9x_13+65x_14+71x_15+21x_16+12x_17+19x_18+20x_19+44x_20+ 30x_21+28x_22+43x_23+13x_24+34x_25+13x_26+15x_27+5x_28+8x_29+4x_30 \small((array(\ 1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0;\ 0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0;\ 0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0;\ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0;\ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0;\ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1;\ 1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0;\ 0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0;\ 0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0;\ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0;\ 0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,1,0,0,0;\ 0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0;\ 0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,1,0;\ 0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,1)))*x<=e x>=0
Dieses lineare Problem ist nun also mittels Simplexmethode zu lösen. Wer schon mal die Simplexmethode von Hand gerechnet hat, wird zusammenzucken: Das sieht nach einer verdammt mühsamen und langwierigen Rechnung aus! Aber auch hier gibt es Entwarnung. Die Unimodularität der Systemmatrix bewirkt, dass alles immer schön ganzzahlig bleibt. Und die vielen Nullen in der Matrix sorgen außerdem dafür, dass in jeder Iteration nur ganz wenige Zeilen neu berechnet werden müssen. Nichtsdestotrotz, die Koschwi wartet ungeduldig auf die Bestätigung der mit der ersten Methode gefundenen Lösung. Deshalb sollte vielleicht doch lieber ein Computer und geeignete Software zum Einsatz kommen... Mit welchen Mitteln auch immer, der Simplexalgorithmus liefert die eindeutig bestimmte optimale Lösung x=(0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0). Die zur Erzeugung der Normalform eingefügten Schlupfvariablen haben im Optimum die Werte s=(0,0,0,0,0,0,0,0,1,1,0,0,0,0). Die beiden positiven Schlupfvariablen gehören zu den zu Hans und Horst gehörenden Zeilen im Ungleichungssystem Ax<=e. Sie zeigen an, dass das Produkt Ax in diesen beiden Zeilen den Wert Null hat: Partnerlosigkeit! Die Priesterschule ruft... Die Einsen im x-Vektor geben die Kanten bzw. Paarungen an, die ins optimale Matching aufzunehmen sind. Schließlich kann die Koschwi also das Resultat ihrer Bemühungen verkünden: Wissenschaftliche Untersuchungen haben ergeben, dass für eine bestmögliche Weiterentwicklung unserer Dorfgemeinschaft die Eheschließungen Anna+Otto, Brit+Karl, Edith+Bernd, Franzi+Peter, Moni+Fred, Uta+Hugo zu erfolgen haben. Wir danken allen Betroffenen für die unverzügliche Umsetzung dieses Beschlusses. Sehr geehrte potentielle Schwiegermütter, mit dem neu erworbenen Wissen werden Sie und Ihr Dorf hoffentlich ebenso zielstrebig die optimalen Paare zusammenstellen können. Viel Erfolg! Und Sie, liebe Schwiegermütter, die schon immer mit der oder dem Erwählten Ihres Nachwuchses unzufrieden waren, werden sich jetzt ärgern, dass dieser Artikel nicht schon eher verfasst wurde...
by Hume
[Edit]

 
Dieser Artikel ist enthalten in unserem Buch
Mathematisch für fortgeschrittene Anfänger
Mathematisch für fortgeschrittene Anfänger

\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Mathematik :: Graphentheorie :: Optimierung :: Sonstige Mathematik :
kleine mathematische Hilfe für potentielle Schwiegermütter [von N-man]  
Ein humorvoller Artikel über das Finden maximaler Matchings.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 5435
 
Aufrufstatistik des Artikels
Insgesamt 149 externe Seitenaufrufe zwischen 2012.01 und 2021.08 [Anzeigen]
DomainAnzahlProz
http://google.de10167.8%67.8 %
https://google.de1610.7%10.7 %
http://stefan.koerner-familie.de85.4%5.4 %
https://google.com74.7%4.7 %
https://www.bing.com32%2 %
http://google.hu21.3%1.3 %
http://images.google.de21.3%1.3 %
http://google.com21.3%1.3 %
https://duckduckgo.com10.7%0.7 %
http://www.ecosia.org21.3%1.3 %
http://www.bing.com21.3%1.3 %
https://r.search.yahoo.com10.7%0.7 %
http://de.search.yahoo.com10.7%0.7 %
http://google.ch10.7%0.7 %

Häufige Aufrufer in früheren Monaten
Insgesamt 87 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2013-2016 (24x)http://google.de/url?sa=t&rct=j&q=
201205-05 (14x)http://google.de/url?sa=t&rct=j&q=totale unimodularität prüfen
2020-2021 (13x)https://google.de/
201203-06 (8x)http://stefan.koerner-familie.de/mathe/matching.pdf
201206-06 (7x)http://google.de/url?sa=t&rct=j&q=unimodular genau dann wenn bipartit
2020-2021 (7x)https://google.com/
201305-05 (5x)http://google.de/url?sa=t&rct=j&q=bipartiter graph mit knoten gewichten besti...
201401-01 (5x)http://google.de/imgres?sa=X&rlz=2C1GTPM_deDE0537DE0537&espv=210&es_sm=93&biw...
201408-08 (4x)http://google.de/url?sa=t&rct=j&q=matching matheplanet

[Top of page]

"Stern Mathematik: kleine mathematische Hilfe für potentielle Schwiegermütter" | 6 Comments
The authors of the comments are responsible for the content.

Re: kleine mathematische Hilfe für potentielle Schwiegermütt
von: Bilbo am: Mi. 23. November 2005 22:00:22
\(\begingroup\)Hi N-Man, ein sehr schöner und kurzweiliger (Einstands-?)Artikel, aus dem einiges lernen konnte (wobei mir das persönlich - wohl auch mangels Kenntnissen der linearen Optimierung - die erste Beweismethode besser gefallen hat). Vor allem die Anwendung aus dem wirklichen Leben, die du als Beispiel gefällt hast, gefällt mir; damit sollte es doch eigentlich machbar sein, der zunehmenden Kinderlosigkeit in Deutschland Einhalt zu gebieten!? 😄 Hoffentlich sehen wir bald weitere solch lesenswerte Artikel von dir! Gruß, Bilbo\(\endgroup\)
 

Re: kleine mathematische Hilfe für potentielle Schwiegermütt
von: N-man am: Do. 24. November 2005 17:45:53
\(\begingroup\)Danke Bilbo für das Lob. Und ja das war mein Einstandsartikel, ich lasse mir eben gerne etwas Zeit. Die Idee zu diesem Artikel wurde vor zwei Jahren (!) geboren. Vor einem Jahr habe ich diesen Artikel an einem Wochenende fast vollständig geschrieben. Es blieb eigentlich nur ein kleiner Rest zu schreiben, manches musste noch besser formuliert werden und dringend musste Korrektur gelesen werden. Nur konnte ich mich dazu nie richtig aufraffen. Dass der Artikel jetzt fertig ist, ist zum einen Matroid zu verdanken, der festgestellt hat, dass ich seid "geraumer" Zeit einen Artikel in Bearbeitung habe. Und vorallem hat HUME das Ende geschrieben, vieles besser formuliert... überhaupt alles besser gemacht, da ich hier von Toulouse aus weder die Möglickeiten noch die die Zeit dazu hatte. Also Danke an Hume, dass er bereit war diese Arbeit zu übernehmen.\(\endgroup\)
 

Re: kleine mathematische Hilfe für potentielle Schwiegermütter
von: SchuBi am: Do. 24. November 2005 19:01:17
\(\begingroup\)Hallo, Manuel! Für mich als Vater zweier Söhne ist jetzt noch das einzige Problem, die geeigneten Schwiegermütter zu finden, die diesen Artikel lesen und verstehen 😉\(\endgroup\)
 

Re: kleine mathematische Hilfe für potentielle Schwiegermütter
von: Gockel am: Do. 24. November 2005 20:00:17
\(\begingroup\)Frag doch mal dirgis 😉 mfg Kuppler-Gockel.\(\endgroup\)
 

Re: kleine mathematische Hilfe für potentielle Schwiegermütter
von: FlorianM am: Fr. 25. November 2005 20:16:42
\(\begingroup\)@N-Man Herrlicher Artikel!!\(\endgroup\)
 

Re: kleine mathematische Hilfe für potentielle Schwiegermütter
von: Goswin am: Mi. 31. August 2016 23:45:18
\(\begingroup\)Wer jetzt denkt, dass so ein Paarshipping daran scheitert, dass die Kandidaten romantischen Vorstellungen anhängen, oder die potentiellen Schwiegermütter zu wenig Mathematik können, der irrt sich gewaltig: ich könnte mir so ein Szenario in einem (ehemaligen) sowjetischen Schtetl sehr gut ausmalen! Nein, eine Umsetzung scheitert an der fehlenden dynamischen Komponente des Modells: manche der Schwiegermütter wird es vorziehen ein Jahr zu warten, bis Alternativkandidaten auf dem Heiratsmarkt auftreten.\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]