Mathematische Crewverteilungsfrage
Juergen Ernst Guenther
Ein Wochentörn mit zwei Booten.
Diesmal B44, aber das ändert sich jedes Jahr.
Auch die Teilnehmerstärke variiert incl. Skipper
von 13 bis 16 Teilnehmern.
Die Samstagscrew belegt die Schlafkojen und übergibt auch am
folgenden Freitag wieder das Boot.
Von Sonntag bis Donnerstag wird tagsüber mit leichtem Gepäck
durchgewechselt. Jeder soll mal mit jedem segeln und bei
jedem der beiden Skipper ungefähr gleich häufig. Die beiden
Skipper bleiben jeweils auf ihrem Boot.
Der erste Ansatz war eine einfache Permutation: Erst wechselte
die erste Hälfte der Crew, dann die zweite, dann alle geraden,
dann alle ungeraden.
Es zeigte sich jedoch, dass es dabei Gruppierungen gab, die
sich nie trafen und Leute, die ständig zusammen waren.
Idee: Ein Auszählverfahren. Beide Skipper wählen virtuell jeden
Tag abwechselnd die Crewmitglieder. Dabei werden die bevorzugt,
die nach Gewichtung besonders selten auf dem eigenen Boot und
mit den schon vorausgewählten Crewmitgliedern zusammen waren,
bei gleicher Wertung die, die besonders viel mit den vorausgewählten
Crewmitgliedern der Gegencrew anzutreffen waren, bei gleicher Wertung
die mit der niedrigsten Losnummer.
Bei rein kubischer Gewichtung der Treffen erreicht man eine
Gleichverteilung der Skipper (3,3) für jeden der Restcrew.
(Samstag und Freitag werden wegen der Übergabe als ein Tag
gewertet). Dafür gibt es jede Menge Nullen in der Treffermatrix.
Vergibt man für (Skipper,Crew) und (Crew,Crew) unterschiedliche
Gewichtungsvektoren lassen sich durch Parametrisierung die Nullen
eliminieren, dafür treten anscheinend zwangsläufig bei der
Skipperzuordnung auch (4,2) und (2,4) auf. Ausserdem kommt es
je nach Crewstärke und Parameter wieder zu Sechser-Klüngeln.
Das Problem ist wohl, dass zum Ende der jeweiligen Auszählung
genommen werden muss, was noch am Steg steht, zum anderen,
dass dann die Skipper sich gelegentlich bessere Treffer
wegschnappen.
Gibt es ein besseres Verfahren?
Backtracking funktioniert ja leider nur, wenn es eine optimale
Lösung gibt.
.m.
--
Jürgen Ernst Günther
Die Wege des Herrn sind unergründlich, die Wege seiner Schäfchen
mitunter schwankend. -- Christoph Süß, quer 2007-09-27
Christian Fette
"Juergen Ernst Guenther" <muf...@rrr.de> schrieb im Newsbeitrag news:slrnfvau0l...@news.rrr.de...
>
> Ein Wochentörn mit zwei Booten.
> Diesmal B44, aber das ändert sich jedes Jahr.
> Auch die Teilnehmerstärke variiert incl. Skipper
> von 13 bis 16 Teilnehmern.
> Bei rein kubischer Gewichtung der Treffen erreicht man eine
> Gleichverteilung der Skipper (3,3) für jeden der Restcrew.
> (Samstag und Freitag werden wegen der Übergabe als ein Tag
> gewertet). Dafür gibt es jede Menge Nullen in der Treffermatrix.
> Vergibt man für (Skipper,Crew) und (Crew,Crew) unterschiedliche
> Gewichtungsvektoren lassen sich durch Parametrisierung die Nullen
> eliminieren, dafür treten anscheinend zwangsläufig bei der
> Skipperzuordnung auch (4,2) und (2,4) auf. Ausserdem kommt es
> je nach Crewstärke und Parameter wieder zu Sechser-Klüngeln.
Sonst noch Probleme? :-) :-) :-)
Vielleicht ist die Frage in de.sci.mathematik besser aufgehoben...
Oder sind hier ausgewachsene Statistiker unter uns?
(Aber je länger ich darüber nachdenke, desto interessanter ist die Frage... :-) )
Gruß
Chr.
Matthias Luczak
Ich habe unten mal eine Verteilung für 6 Personen bzw 8 Pers.
(AS+BS Skipper und A1,A2,A3,B1,B2,B3 = Crews) aufgestellt. Schon
dabei schaffe ich es gerade mal die Segler an den 5 Tagen
einigermaßen gleichmäßig untereinander und auf die Schiffe zu
verteilen. Wenn Du mehr Segler planen willst gar 13 - 16 ist es
meines Erachtens unmöglich.
Mein Vorschlag einfach 2-3 Monate Segeln, dann wird Du die Verteilung
auch einigermaßen gleichmäßig hin bekommen.
Habe gerade noch eine zweite Idee: An einem Tag alle auf ein Boot,
dann ist wenigsten jeder mal mit
jedem anderen gesegelt. ;-)
Tag 1
AS A1 A2
BS B1 B2
Tag 2
AS B1 A1
BS A2 B2
Tag 3
AS A1 B2
BS A2 B1
Tag 4
AS B1 B2
BS A1 A2
Tag 5
AS A2 B2
BS A1 B1
Tag 1
AS A1 A2 A3
BS B1 B2 B3
Tag 2
AS B1 A2 B3
BS A1 B2 A3
Tag 3
AS B1 B2 A3
BS A1 A2 B3
Tag 4
AS A1 B2 A2
BS B1 B3 A3
Tag 5
AS A1 B1 B3
BS A2 B2 A3
Marc Heusser
"Christian Fette" <chf...@gmx.de> wrote:
> Vielleicht ist die Frage in de.sci.mathematik besser aufgehoben...
Oder in comp.soft-sys.math.mathematica nachfragen auf Englisch -
Mathematica hätte ich falls nötig.
Gruss
Marc
--
remove bye and from mercial to get valid e-mail
<http://www.heusser.com>
Tobias Crefeld
Wenn alle Crewstücke gleich sind, also keine Vorkenntnisse oder
körperlichen Vorteile zu berücksichtigen sind, würde ich losen. (Nicht das
ich den Sinn dieser permanenten Verwürfelungsstrategie begreifen würde...)
--
Gruss,
Tobias.
Juergen Ernst Guenther
Welchen Sinn hat es, wenn man gemeinsam segeln geht,
aber einander nie trifft? Dann ist es mitunter recht
aufschlussreich, die verschiedenen Stile der beiden
Skipper kennen zu lernen, zudem wenn beide Boote mit
unterschiedlichem Spielzeug ausgestattet sind und sich
etwas anders verhalten. Schliesslich hast du beim
Flottiliensegeln immer früher oder später gewisse
Animositäten zwischen den Crews. Und das ist blöd,
wenn es Zweck des Törns war, dass die Leute sich
mal treffen und kennenlernen wollten.
Das Losen ist an sich eine sehr gute Strategie.
Nur muss man da mitunter sehr viele Auslosungen
wegwerfen, bis eine dabei ist, in der keine
unnötigen Härten vorkommen.
Juergen Ernst Guenther
> Vielleicht ist die Frage in de.sci.mathematik besser aufgehoben...
Dort stand sie ja auch.
Ich hab nur das Followup-To: wieder auf diese Gruppe gesetzt.
Sorry, hab vergessen darauf hinzuweisen.
Juergen Ernst Guenther
> Ich habe unten mal eine Verteilung für 6 Personen bzw 8 Pers.
> (AS+BS Skipper und A1,A2,A3,B1,B2,B3 = Crews) aufgestellt. Schon
> dabei schaffe ich es gerade mal die Segler an den 5 Tagen
> einigermaßen gleichmäßig untereinander und auf die Schiffe zu
> verteilen. Wenn Du mehr Segler planen willst gar 13 - 16 ist es
> meines Erachtens unmöglich.
Nun, es gibt ja eine Lösung.
Niemand hat gesagt, das sie perfekt sein muss.
Ich hatte nur gehofft, dass es eventuell eine Lösung gibt,
die besser als unsere bisherigen Ideen ist.
1. Jeder trifft jeden mindestens einmal (bis auf die beiden
Skipper, die auf ihren Booten bleiben): Hab ich geschafft.
2. Jeder sollte nach Möglichkeit auf beiden Booten gleich
häufig sein: Ging bisher nur unter Verletzung von Regel 1.
3. Nett wäre, wenn es keine Dauerpäärchen gäbe: geht manchmal.
4. Blöd, wenn jemand seine Koje auf einem Boot hat, aber
ständig auf dem anderen segelt: passiert manchmal, wenn
Regel 2 nicht klappt.
5. Schön, wenn auch die Crewverteilung möglichst gleichmässig
wird.
1 und 2 schafft man, nur leider nicht gleichzeitig. Es reicht aber
auch, wenn 2 halbwegs passt. 3 kann man hinbekommen. Nur 4 kann
ich bislang nicht steuern. Passiert aber selten.
Tobias Crefeld
> etwas anders verhalten. Schliesslich hast du beim
> Flottiliensegeln immer früher oder später gewisse
> Animositäten zwischen den Crews. Und das ist blöd,
> wenn es Zweck des Törns war, dass die Leute sich
> mal treffen und kennenlernen wollten.
Mei, Konkurrenz belebt das Geschäft! :-)
Wenn ich beim Yachtsegeln überhaupt einen soziologisch interessanten
Aspekt sehe, dann den der Teambildung. Das beinhaltet natürlich auch immer
eine Abgrenzung nach außen. Außerdem beinhaltet es nach meinem Verständnis
auch eine Zuordnung von Verantwortlichkeiten für bestimmte Bereiche an
Bord. Das was Ihr da praktiziert, ist dann wohl so ne Art Teambildung mit
permanent praktizierter Exit-Strategie. Was es nicht alles gibt.
So eine Art des Flottillensegelns würde mich eh wahnsinnig machen. Wenn
man als Crew nicht mehr selbst entscheiden kann, wohin man als nächstes
fährt, weil ja immer noch die Wünsche der anderen Boote berücksichtigt
werden müssen. Das ist ja dann wie Kreuzfahrt mit Hapag, nur für
Selbstkocher und ohne Kaptain.
> Das Losen ist an sich eine sehr gute Strategie.
> Nur muss man da mitunter sehr viele Auslosungen
> wegwerfen, bis eine dabei ist, in der keine
> unnötigen Härten vorkommen.
Was ist denn eine "unnötige Härte" beim Segeln?
Aber das heißt dann wohl auch, Du hast doch noch weitere Konditionen, die
bei dem Auswahlverfahren zum Tragen kommen sollen, die Du bislang nicht
genannt hattest.
--
Gruss,
Tobias.
Joachim Reinke
> Das was Ihr da praktiziert, ist dann wohl so ne Art Teambildung mit
> permanent praktizierter Exit-Strategie.
Die Phrase gefällt mir. Die nehme ich in mein "Business-Vokabular" auf.
Unsere Marketing-Abteilung praktiziert das übrigens durchgehend. Jeder
Kundenanruf ist ein "Projekt" und jedes neue "Projekt" erfordert
natürlich eine komplette Neu-Verteilung aller Marketing-Mitarbeiter auf
alle "Projekte" (da würde man hipperweise natürlich besser "Re-staffing"
zu sagen). Man sollte nicht glauben, daß man bei denen für dieselben
Fragestellungen eine Woche später noch dieselben Ansprechpartner hat
oder daß die neuen Ansprechpartner von den alten eine Übergabe erhalten
hätten. Aber ich glaube, ich schwiff(tm) ab.
> Was ist denn eine "unnötige Härte" beim Segeln?
> Aber das heißt dann wohl auch, Du hast doch noch weitere Konditionen, die
> bei dem Auswahlverfahren zum Tragen kommen sollen, die Du bislang nicht
> genannt hattest.
Optimierungsaufgaben ohne explizit formulierte Optimalitätsfunktion, auf
deren Zielmenge eine Ordnungsrelation wohldefiniert ist, ist schwierig.
Sag ich jetzt mal mit meinem halben Mathe-Vordiplom, um das man als
Bonner Informatiker nicht drumrumkommt...
--
Der Preis, den die Freiheit kostet, heißt Verantwortung.
Florian Laws
>
> Optimierungsaufgaben ohne explizit formulierte Optimalitätsfunktion, auf
> deren Zielmenge eine Ordnungsrelation wohldefiniert ist, ist schwierig.
> Sag ich jetzt mal mit meinem halben Mathe-Vordiplom, um das man als
> Bonner Informatiker nicht drumrumkommt...
Das Aufstellen der Optimalitätsfunktion ist ja gerade die Aufgabe hier.
Grüße,
Florian
Thomas Erstfeld
Klar ist das Wetter scheiße, aber stellt euch doch einfach den optimalen
Saisonanfang vor. ;-))
Für eine Woche Segeln lohnt sich das Theater mit dem Crewwechsel nicht
wirklich. Und wer trotzdem damit nicht zurecht kommt, sollte sich eine
andere Freizeitbeschäftigung oder andere Mitsegler suchen.
Gruß
Thomas
Ignatios Souvatzis
[...]
> Ich hatte nur gehofft, dass es eventuell eine Lösung gibt,
> die besser als unsere bisherigen Ideen ist.
>
> 1. Jeder trifft jeden mindestens einmal (bis auf die beiden
> Skipper, die auf ihren Booten bleiben): Hab ich geschafft.
> 2. Jeder sollte nach Möglichkeit auf beiden Booten gleich
> häufig sein: Ging bisher nur unter Verletzung von Regel 1.
> 3. Nett wäre, wenn es keine Dauerpäärchen gäbe: geht manchmal.
> 4. Blöd, wenn jemand seine Koje auf einem Boot hat, aber
> ständig auf dem anderen segelt: passiert manchmal, wenn
> Regel 2 nicht klappt.
> 5. Schön, wenn auch die Crewverteilung möglichst gleichmässig
> wird.
>
> 1 und 2 schafft man, nur leider nicht gleichzeitig.
Kein Problem. Eine triviale Möglichkeit ist: Nimm eine Lösung, die 1.
erfüllt, und lass die Crews (bis auf den Skipper) zur Halbzeit das
Schiff tauschen. Voilà - Regel 2 (und als Folge Regel 4) sind auch
erfüllt.
-is
--
seal your e-mail: http://www.gnupg.org/
Tobias Crefeld
> Kein Problem. Eine triviale Möglichkeit ist: Nimm eine Lösung, die 1.
> erfüllt, und lass die Crews (bis auf den Skipper) zur Halbzeit das
> Schiff tauschen. Voilà - Regel 2 (und als Folge Regel 4) sind auch
> erfüllt.
Diese Makro-Crew muss ein Pendant zu meinem Segelverein zu sein. Da
erkennt man die universitäre Herkunft auch immer wieder daran, dass
einfache Lösungen zumindest erstmal grundsätzlich in Frage gestellt und
lange diskutiert werden müssen, um dann doch wieder auf sie zurück zu
kommen. =:)
Zeit zum Ansegeln, wie mir scheint. Meines habe ich schon hinter mir.
Single-handed Flottille am Gardasee. Auch da kann man lange diskutieren,
wer wann warum mit welchem Boot und welchem Rigg und welcher
Schutzbekleidung ablegt... muss man aber nicht. ;)
--
Gruss,
Tobias.
Joachim Reinke
> hier.
...und zwar die desjenigen, der das Problem hat bzw. eine Lösung haben
möchte. Schließlich weiß ja sonst keiner so genau, was für denjenigen
eine Lösung ist. Mag in Prosa geschehen.
Florian Laws
>> Das Aufstellen der Optimalitätsfunktion ist ja gerade die Aufgabe
>> hier.
>
> ...und zwar die desjenigen, der das Problem hat bzw. eine Lösung haben
> möchte.
... bei der er das geneigte Publikum um Hilfe gebeten hatte.
> Schließlich weiß ja sonst keiner so genau, was für denjenigen
> eine Lösung ist. Mag in Prosa geschehen.
Die Prosa steht da.
Grüße,
Florian