Die Mathe-Redaktion - 22.10.2018 10:07 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 573 Gäste und 16 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Optimalen Spielplan erstellen
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich Optimalen Spielplan erstellen
stirni
Junior Letzter Besuch: im letzten Monat
Dabei seit: 23.09.2018
Mitteilungen: 5
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-09-23


Hallo liebe Community,

ich hoffe, ihr könnt mir weiterhelfen.

Ich habe folgendes Problem:

Ich muss einen Spielplan erstellen, der folgendes leistet:
(Es geht um einen Seilzieh-Wettkampf)
- 14 Teams ( Soll variabel sein)
- jeder gegen jeden (an einem Tag)
- 2 Zugfelder (2 Seile zum Ziehen)
- möglichst lange Regenerationspausen

Ich habe schon diesen Thread gefunden, leider sieht man die Buchseite, auf der im genanntem Topic eingegangen wird nicht mehr, deshalb brauchte ich dringend eure Hilfe.

Die Anzahl der ganzen Partien zu berechnen ist nicht das Problem, aber wie schaffe ich es, die größt mögliche Ruhepause einfließen zu lassen?
Und dann das Ganze auf 2 Zugfelder aufzuteilen?!

Ich habe breits versucht, über lokale Suche so etwas zu gestalten, auch mithilfe dieser Seite,
komme allerdings nicht auf einen grünen Zweig, bzw. habe noch nie etwas derart komplexes gemacht (zumindest nicht mathematisch gesehen)

Ich nutze Excel VBA.

Es wäre hilfreich, erstmal das Problem der längst möglichen Regenerationspausen zu lösen.

Ich hoffe wirklich, dass Ihr mir weiterhelfen könnt.

Vielen lieben Dank.

-Stirni



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5489
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-09-24 15:47


Zunächst mal ein Hinweis:
Die _durchschnittliche_ Pause zwischen zwei Wettkämpfen lässt sich durch Veränderung der Ansetzungen nicht (wesentlich) beeinflussen. Von 14 Mannschaften sind 4 jeweils im Wettkampf. Die Pausenzeiten sind also 3,5mal so lang, wie die Wettkampfzeiten.

Optimieren lässt sich die Anzahl der Pausen, die weniger als drei Wettkämpfe lang sind, ggf. auch die, die länger als vier Wettkämpfe lang sind.

Ich habe mal folgenden heuristischen Ansatz probiert:
Bei jeder Paarung, die noch nicht gegeneinander angetreten ist, schaut man, welche Mannschaft die kürzere Pause hatte. Gewählt wird das Paar, bei dem diese Pause maximal ist. Gibt es mehrere solche Paare, dann wird das Paar gewählt, bei dem die Pause der zweiten Mannschaft maximal ist.
Gibt es hier immer noch einen Gleichstand, so werden die Paare priorisiert, die bisher zusammen die wenigsten Wettkämpfe hatten.
Auch damit ist die Auswahl noch nicht eindeutig, ich habe aber noch keine gute Idee, was man als weitere Kriterien benutzen sollte.

Mit diesem Ansatz komme ich aber immerhin zu Ergebnissen, bei denen es nur vier Fälle gibt, in denen eine Mannschaft eine Pause von 2 Wettkämpfen hat. Ich weiß zwar nicht, ob es besser geht, der Ansatz lässt sich aber verhältnismäßig leicht implementieren.

Hier eine Ansetzung für 14 Mannschaften. In der 1. Zeile und Spalte stehen die Nummern der Mannschaften. In den Zellen steht die Position, an der diese Paarung im Turnierverlauf erfolgt.
Tabelle
    |	 1	 2	 3	 4	 5	 6	 7	 8	 9	10	11	12	13	14
----+-------------------------------------------------------------------------------------------------------------
 1  |	--	 1	 4	15	22	42	39	29	33	36	25	11	 7	18
 2  |	 1	--	15	 5	 8	22	43	36	40	33	28	25	18	11
 3  |	 4	15	--	 1	12	19	23	26	37	40	34	29	43	 8
 4  |	15	 5	 1	--	19	12	 9	23	26	30	37	41	45	32
 5  |	22	 8	12	19	--	 2	 5	16	30	27	41	44	34	38
 6  |	42	22	19	12	 2	--	16	 6	 9	44	31	38	27	35
 7  |	39	43	23	 9	 5	16	--	 2	13	20	46	35	31	28
 8  |	29	36	26	23	16	 6	 2	--	20	13	10	32	39	42
 9  |	33	40	37	26	30	 9	13	20	--	 3	 6	17	24	45
10  |	36	33	40	30	27	44	20	13	 3	--	17	 7	10	24
11  |	25	28	34	37	41	31	46	10	 6	17	--	 3	14	21
12  |	11	25	29	41	44	38	35	32	17	 7	 3	--	21	14
13  |	 7	18	43	45	34	27	31	39	24	10	14	21	--	 4
14  |	18	11	 8	32	38	35	28	42	45	24	21	14	 4	--



  Profil  Quote  Link auf diesen Beitrag Link
stirni
Junior Letzter Besuch: im letzten Monat
Dabei seit: 23.09.2018
Mitteilungen: 5
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2018-09-27 11:15


Danke Kitaktus,

Hast du mir evtl. den Quellcode zur Hand, wie du die Tabelle erstellt hast? Ich komm' nicht drauf.

Habe es bisher mit dem Link nur geschaft, 6x 2 Spiele Pause und 1x 1 Spiel Pause. Das ist natürlich zuwenig.

Vielen Dank!



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5489
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2018-09-27 11:43


Die Daten habe ich halbautomatisiert mit Excel erzeugt.
Ich benutze zwei Tabellen. In der einen steht, in welchem Spiel Mannschaft i (Zeile) gegen Mannschaft j (Spalte) antritt. Am Anfang ist die Tabelle leer.

In der anderen Tabelle steht in Zelle (i,j) eine Bewertung mit folgender Bedeutung:
Wann war das letzte Spiel von Mannschaft i (Maximum der Zeile i aus der 1. Tabelle) und wann war das letzte Spiel von Mannschaft j (Maximum der Spalte j aus der 1. Tabelle). Nimm den größeren der beiden Werte mal 100, addiere den kleineren der beiden Werte und addiere die Gesamtzahl der Spiele von i und j geteilt durch 100 dazu, wenn i schon gegen j gespielt hat, dann schreibe in die Zelle 9999 (*).
In dieser Tabelle hebe ich den niedrigsten Wert farbig hervor. Das wird die nächste Paarung. Ich trage in der ersten Tabelle in die Zellen (i,j) und (j,i) die Nummer der Paarung ein (wobei ich jede Nummer zweimal vergebe, da du ja zwei parallele Wettkämpfe ausführst(**).
Nach dem Eintragen der neuen Paarung ändern sich in der zweiten Tabelle die Bewertungen und es wird ein neues Minimum angezeigt.
In vielen Fällen gibt es mehrere Paarungen, die die gleiche Bewertung haben, dann habe ich versucht, von Hand eine günstige Kombination auszuwählen.

In Matlab könnte ich dazu auch einen Code schreiben, aber ich weiß nicht, ob Du den lesen kannst.


(*) Diese Bewertung bewirkt folgendes:
Angenommen es gibt zwei mögliche Paarungen (A,B) und (C,D) und von diesen vier Mannschaften hat C (alleine) als letztes gespielt. Dann ist die Bewertung von (C,D) auf jeden Fall höher als die von (A,B). C muss also nicht spielen, wenn es noch Mannschaften gibt, die schpn länger Pause haben und gegeneinander spielen könnten.
Angenommen A und C haben zusammen als letztes gespielt. Dann entscheidet wer von den Mannschaften B und D länger pausiert hat. Damit wird (in gewissem Maße) verhindert, dass Mannschaften zu lange pausieren.

(**) Es ist überlegenswert, ob man nicht trotz der zwei Wettkampfplätze die Paarungen einzeln durchnummeriert. Die nächste Paarung wäre dann auf dem nächsten freien Platz.
Das erscheint mir zumindest sinnvoll, wenn die Plätze nahe beisammen liegen. Ansonsten muss man natürlich schon im Voraus festlegen, wer auf welchem Platz anzutreten hat.



  Profil  Quote  Link auf diesen Beitrag Link
stirni
Junior Letzter Besuch: im letzten Monat
Dabei seit: 23.09.2018
Mitteilungen: 5
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2018-09-27 12:53


Danke für deine Ausführungen,

ich komme allerdings immer noch nicht so recht dahinter, wie du die Paarungen ansetzt.
Könntest du mir das mit den 2 Tabellen anschaulich machen?
Wie sehen diese aus? (Bin leider etwas unter Zugzwang, da die Tabelle morgen Abend stehen sollte)

Danke Dir auf jeden Fall vielmals!!!



  Profil  Quote  Link auf diesen Beitrag Link
stirni
Junior Letzter Besuch: im letzten Monat
Dabei seit: 23.09.2018
Mitteilungen: 5
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2018-09-27 13:26


Vielleicht ein kleiner Nachtrag:

Ich werde deine Gepostete Tabelle nun mal händisch übernehmen, das reicht mir Mal zum Anfang.

Ich habe allerdings ein weiteres Problem:

Jeder zieht gg. jeden ja nur ein Mal.
Dieses Match besteht allerdings aus 2 Zügen:
Wenn beide einen Zug gewinnen, bekommt jeder einen Punkt
Gewinnt einer beide Züge, bekommt der Gewinner 3 Punkte und der Verlierer keinen Punkt.

Dies habe ich in eine Kreuztabelle geschrieben,
an deren letzten Spalte der Rang ausgewertet wird.
Nun soll bei Punktgleichstand der direkte Vergleich herangezogen werden.
Wenn Mannschaft A gleiche Punktzahl wie Man. B,
dann soll nachgeschaut werden, wie das direkte Duell der beiden ausgegangen ist. Wenn A beide Züge gewonnen, dann ist A einen Rang vor B, wenn beide jew. einen Zug gewonnen haben bleiben beide auf dem gleichen Rang (gibt Entscheidungsmatch mit Best-Of 3) ansonsten   hat B beide gewonnen und ist einen Rang vor A.

Die momentane Spalte Rang wertet nur die Punkte aus.
Hier ein Bild
Wie zu sehen ist haben Team 1 und 2 gleiche Punktzahl, aber Team 1 hat gegen Team 2 gewonnen also muss Team 1 den Rang 1 haben und Team 2 den Rang 2.

Ich hoffe du kannst ein weiteres Mal helfen :)
Danke Dir!

-Stirni



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5489
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2018-09-27 13:49


Du könntest mir ja sagen, wieviele Mannschaften dabei sind, dann könnte ich vielleicht selbst eine Lösung erzeugen... ;-)

Mal am Beispiel von fünf Mannschaften. Wir betrachten den Zeitpunkt, nachdem (A,B) und (C,D) schon eingeplant sind:
Tabellen
	 A	 B	 C	 D	 E	letztes Match
 A	--	01	..	..	..	01
 B	01	--	..	..	..	01
 C	..	..	--	02	..	02
 D	..	..	02	--	..	02
 E	..	..	..	..	--	00
letztes
Match	01	01	02	02	00
 
Bewertung
	 A	 B	 C	 D	 E
 A	--	9999	0201.02	0201.02	0100.01
 B	9999	--	0201.02	0201.02	0100.01
 C	0201.02	0201.02	--	9999	0200.01
 D	0201.02	0201.02	9999	--	0200.01
 E	0100.01	0100.01	0200.01	0200.01	--

Die niedrigste Bewertung (0100.01) haben die Paarung AE und BE. Wir legen AE als nächste Paarung fest und jetzt sieht es so aus:
	 A	 B	 C	 D	 E	letztes Match
 A	--	01	..	..	03	03
 B	01	--	..	..	..	01
 C	..	..	--	02	..	02
 D	..	..	02	--	..	02
 E	03	..	..	..	--	03
letztes
Match	03	01	02	02	03
 
	 A	 B	 C	 D	 E
 A	--	9999	0302.03	0302.03	9999
 B	9999	--	0201.02	0201.02	0301.02
 C	0302.03	0201.02	--	9999	0302.02
 D	0302.03	0201.02	9999	--	0302.02
 E	9999	0301.02	0302.02	0302.02	--

Die niedrigste Bewertung (0201.02) haben die Paarung BC und BD. Wir legen BC als nächste Paarung fest und jetzt sieht es so aus:
Tabelle
	 A	 B	 C	 D	 E	letztes Match
 A	--	01	..	..	03	03
 B	01	--	04	..	..	04
 C	..	04	--	02	..	04
 D	..	..	02	--	..	02
 E	03	..	..	..	--	03
letztes
Match	03	04	04	02	03
 
	 A	 B	 C	 D	 E
 A	--	9999	0302.03	0302.03	9999
 B	9999	--	9999	0402.03	0403.03
 C	0403.04	9999	--	9999	0403.03
 D	0302.03	0402.03	9999	--	0302.02
 E	9999	0403.03	0403.03	0302.02	--

Hier greift mal das dritte Kriterium. In Frage kommen die Paarungen AD und DE, da A, D und E schon mehr Pause haben als B und C. A und E haben die gleiche Wartezeit, ich nehme aber E statt A, da E erst ein Spiel hatte, A aber schon zwei.


Die nächsten Paarungen wären dann AC, BD (oder BE), CE, AD, und BE.
[Ich hoffe, ich habe keinen Fehler drin, ich habe das von Hand gemacht.]

[Die Antwort wurde nach Beitrag No.4 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
stirni
Junior Letzter Besuch: im letzten Monat
Dabei seit: 23.09.2018
Mitteilungen: 5
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2018-09-27 14:04


14 Mannschaften sind dabei. :)

Ist ja Wahnsinn, wieviel Mühe du dir jedes Mal gibt :) Danke.

Bin gerade dabei das händisch zu übernehmen, besser wäre natürlich wenn ich das durch einen Code machen könnte :)
Les ich mir alles durch wenn ich das händisch übernommen habe :)

EDIT: Du kannst ja mal den Matlab Code schicken, vllt. kapier ichs ja ;) (Kenn mich in C# aus, kP wie man in MATLAB programmiert)

-Stirni



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5489
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2018-09-27 14:10


2018-09-27 13:26 - stirni in Beitrag No. 5 schreibt:
Nun soll bei Punktgleichstand der direkte Vergleich herangezogen werden.
Wenn Mannschaft A gleiche Punktzahl wie Man. B,
dann soll nachgeschaut werden, wie das direkte Duell der beiden ausgegangen ist.

Ehrlich gesagt, für ein einzelnes Turnier würde ich nicht versuchen, dass automatisiert umzusetzen.
Wenn es nur so wäre, wie von Dir beschrieben, dann könnte man das in Excel noch einigermaßen übersichtlich umsetzen. Man sortiert nach Punkten, schaut dann nach, ob Punktgleichheit mit dem Vorgänger oder Nachfolger besteht, vergibt eine zusätzliche Feinwertung und sortiert nochmal.

Das Problem ist aber komplexer. Was machst Du, wenn sieben Mannschaften die gleiche Punktzahl haben?
Naheliegend wäre dann nur die Ergebnisse dieser sieben Mannschaften untereinander heranzuziehen. Wenn es schlecht läuft hast Du dann Punktgleichheit (jeder drei Siege, drei Niederlagen, oder ...). Wer soll dann die Entscheidungsmatches austragen?

Schau Dir mal hier an, wie das im Schach gemacht wird.
Bei Gleichstand auch bzgl. der Feinwertung ist dann vielleicht ein Stichkampf sinnvoll. Das kommt aber wesentlich seltener vor als ein Gleichstand nur nach Punkten.

[Die Antwort wurde nach Beitrag No.6 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5489
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2018-09-27 14:37


Ich habe das jetzt mal schnell in Matlab geschrieben, aber nur mäßig getestet:
Matlab
n=14;
A=zeros(n); % eine nxn-Matrix mit lauter Nullen
a1=max(A);  % Zeitpunkt des letzten Spiels
a2=sum(A>0);% Anzahl der Spiele bisher
 
B=zeros(n)+diag(ones(1,n)*inf,0); % eine nxn-Matrix mit lauter Nullen, auf der Diagonale stehen lauter "Unendlich"
 
for k=1:n*(n-1)/2
    [wer,wo]=min(B);
%   [wer,wo]=min(B+rand(n)); % Variante: Bei Gleichstand wird zufällig
%   ausgewählt, damit kam ich auf Lösungen ohne 2er-Pausen
    [wer2,wo2]=min(wer);
    x=wo2; y=wo(x); % x und y sind die Mannschaften, deren Paarung den niedrigsten Score ergibt.
 
    A(x,y)=ceil(k/2);
    A(y,x)=ceil(k/2);
    a1=max(A);
    a2=sum(A>0);
    for s=1:n
        for t=s+1:n
            B(s,t)=max(a1(s),a1(t))*10000 + min(a1(s),a1(t))*100 + a2(s)+a2(t);
            if A(s,t)>0
                B(s,t)=999999;
            end
            B(t,s)=B(s,t);
        end
    end
%    A,B,[x,y],pause
end
 
A % Enthät die Nummern aller Paarungen
As=sort(A); % sortier Spaltenweise
d=diff(As(2:end,:)) % bildet paarweise die Differenzen = Wartezeit zwischen zwei Spielen
sum(sum(d==2)) % bestimmt, wie oft der Abstand zwischen zwei Spielen genau 2 ist.

Hier noch eine Lösung ohne 2er Pause, kannst Du bitte kontrolliern, ob die i.O. ist?
Das wäre dann auch gleich ein Softwaretest für mich :-)

     0    11    14    30    37    18    34    40    43    24    27    21     3     7
    11     0    18    44     1    15    22     7    25    39     4    29    36    33
    14    18     0    41    31    11    45     4    21    28     8    35    24    38
    30    44    41     0     9    26     5    16    37     2    23    13    33    20
    37     1    31     9     0     5    15    44    34    12    19    41    27    23
    18    15    11    26     5     0     8    22    40    36     1    32    43    29
    34    22    45     5    15     8     0    19     2    42    12    38    30    26
    40     7     4    16    44    22    19     0    28    32    35    25    13    10
    43    25    21    37    34    40     2    28     0     6    31    17    10    14
    24    39    28     2    12    36    42    32     6     0    16     9    20    46
    27     4     8    23    19     1    12    35    31    16     0    45    39    42
    21    29    35    13    41    32    38    25    17     9    45     0     6     3
     3    36    24    33    27    43    30    13    10    20    39     6     0    17
     7    33    38    20    23    29    26    10    14    46    42     3    17     0
 



  Profil  Quote  Link auf diesen Beitrag Link
stirni hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]