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 - 5393 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.

fed-Code einblenden

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.
fed-Code einblenden
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.

fed-Code einblenden

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.

fed-Code einblenden

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:
fed-Code einblenden

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:
fed-Code einblenden
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.

fed-Code einblenden

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.
fed-Code einblenden
Das Gesamtgewicht hat also abgenommen, es bleibt aber stets nichtnegativ. Da alle Matrixeinträge ganzzahlig sind, folgt daraus, dass dieses Verfahren, endlich oft angewendet, schließlich zum Ziel führt und eine 0-Diagonale der Länge n erzeugt!

Was heißt das für unsere Beispielmatrix?
Wir überdecken die 5te, 7te und 8te Zeile sowie die 5te und 7te Spalte. In der Restmatrix befinden sich keine Nullen.
fed-Code einblenden
Bild
Durch Subtraktion der 1 von allen unbedeckten Zeilen und Addition zu allen bedeckten Spalten erhält man eine neue Matrix:
fed-Code einblenden
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
fed-Code einblenden






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
fed-Code einblenden

Solange nicht erklärt ist, wofür A, b, e und x stehen, wird das noch niemanden aus den Schuhen hauen.

fed-Code einblenden

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.
fed-Code einblenden

Ü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:
fed-Code einblenden
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
fed-Code einblenden
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?

fed-Code einblenden

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.
fed-Code einblenden

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.

fed-Code einblenden


Jetzt kommt der Knackpunkt Nummer 1!
fed-Code einblenden

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.

fed-Code einblenden

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:

fed-Code einblenden


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...

fed-Code einblenden
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 5393
 
Aufrufstatistik des Artikels
Insgesamt 135 externe Seitenaufrufe zwischen 2012.01 und 2021.03 [Anzeigen]
DomainAnzahlProz
http://google.de10174.8%74.8 %
http://stefan.koerner-familie.de85.9%5.9 %
https://google.de107.4%7.4 %
https://google.com32.2%2.2 %
http://google.hu21.5%1.5 %
http://images.google.de21.5%1.5 %
http://google.com21.5%1.5 %
http://www.ecosia.org21.5%1.5 %
http://www.bing.com21.5%1.5 %
https://www.bing.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 74 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
201203-06 (8x)http://stefan.koerner-familie.de/mathe/matching.pdf
202005-11 (7x)https://google.de/
201206-06 (7x)http://google.de/url?sa=t&rct=j&q=unimodular genau dann wenn bipartit
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]