Soziale Graphentheorie angewendet: Tischplanung bei einer Hochzeitsfeier

Question

Für unsere Hochzeitparty würde möchte ich auf mathematischem Weg die optimale Tischbesetzung finden. 

Ich habe bereits eine Datengrundlage geschaffen, die die Beziehungsgraphen zwischen den Gästen darstellt. Nachfolgend ein abstrahiertes Beispiel.

Es gibt eine Tabelle aus Personen:

ID	Person
1	Ulf
2	Tanja
3	Ulfs Vater
4	Ulfs Mutter

Ulf heiratet Tanja und Ulf's Eltern sind geschieden. Damit sieht die Beziehungsmatrix wie folgt aus:

	Ulf	Tanja	Ulfs Vater	Ulfs Mutter
Ulf	-	100	90	80
Tanja	-	-	50	30
Ulfs Vater	-	-	-	0
Ulfs Mutter	-	-	-	-

 

Der Score skaliert von 0(hassen sich) über 50 (neutral zueinander) zu 100 (lieben sich)

Es gibt folgende Rahmenbedingungen:

100er Scores: sollen zwangweise zusammensitzen

0er: sollen zwangweise getrennt sitzen

Es sind 65 Gäste geladen

10 Tische mit einer Besetzung zwischen 5 und 8 Personen

Mit welchen mathematischen Verfahren finde ich die optimale Besetzung?

Comments

Heisst Zusammensitzen am gleichen Tisch oder nebeneinander?

Gibt es bei den übrigen Gästen keine 'Probleme'?

---

Ich denke mal am gleichen Tisch und Nebeneinander. Oder würdest du das Hochzeitspaar nur am selben Tisch einplanen :)

Bei den übrigen Gästen gibt es vermutlich auch eine Scoretabelle, die die Beziehung untereinander wiederspiegelt.

Hier geht es ja in erster Linie um eine Methode, wie man so etwas lösen kann.
Zunächst würde ich die Tischaufteilung machen. D.h. nach 5er bis 8er Gruppen suchen, die Zusammen einen Möglichst hohen Score haben.

Z.B. wird die Familie Mütterlicherseits keine so große Verbindung zur Familie Väterlicherseits haben. D.h. die kann man meist getrennt setzen weil da meist keine großen Scorewerte existieren.

Ich weiß aber nicht ob es für ein Computerprogramm nicht eventuell einfacher ist das alles auszuprobieren.

---

An den Hochzeitstisch sollten benen Ulf und Tanja mind. noch die Eltern sitzen. Also Ufs Eltern und Tanjas Eltern. Tanjas Eltern sind oben allerdings nicht aufgeführt. Werden aber vermutlich auch nebeneinander zu platzieren sein.

---

Danke für eure Kommentare.

Wie Mathecoach richtig erkannt hat, geht es hauptsächlich um eine Methodensuche, nicht um die Problemlösung selbst.
Oben stehend ist nur ein Auszug aus den Daten. In "echt" erstelle ich zur Zeit noch die 65:65 Matrix aller zugesagten Gäste.

Ich habe mich entschieden, als erstes verschiedene Clustering Methoden, die der SPSS Modeller so bietet anzutesten. Keiner der in diesem Tool verprogrammierten Algorithmen bietet die Möglichkeit, die oben erwähnten Constraints von vornherein abzufangen.

Dennoch lasse ich es auf einen Versuch ankommen und poste hier die Ergebnisse.

Sollten jemand dennoch ein Ansatz einfallen, bin ich für Ideen dankbar.

Answer 1

Unabhängig von einer rein mathematischen Lösung. Sind unter den 65 Gästen auch Kinder jüngeren alters. Dann kann es z.b. gut sein Kinder extra zu setzen auch wenn diese neutral gegeneinander sind und nicht die Kinder zu den jeweiligen Eltern zu setzen, nur weil das einen höheren Score gibt.
Also eine Mathematische Lösung kann, soweit sie nicht alles berücksichtigt selbst auch eher suboptimal sein.
Auch kann es rechnerisch besser sein zwei die sich nicht mögen an verschiedenen Tischen zu platzieren. Allerdings gehören z.B. an den Brauttisch einfach die eltern dazu. Da ist es unklug dann ein Elternteil nur aus mathematischer Sicht an einen anderen Tisch zu verbannen. Aber sicher sollten sie nicht nebeneinander sitzen. Dann ist die Frage wie man es gewichtet Personen die am Gleichen Tisch sitzen zu bewerten als Personen die an verschiedenen Tischen sitzen. Und letztlich sitze ich dann vielleicht nicht mit meinem Cousin den ich nich mag an einem Tisch aber dafür sitzen wir dann Rücken an Rücken an zwei verschiedenen Tischen.
Letztendlich sind da so viele Möglichkeiten zu berücksichtigen das meist es einfacher ist selber einen Sitzplan zu erstellen als probieren das mit einem Computerprogramm zu machen :)