Suche Algorithmus für Auswertung einer Wahl mit mehreren Wünschen

[jonnywalker_23331c]

Guten Abend,

ich hoffe, dass mir hier jemand evtl. einen geeigneten Algorithmus benennen kann, um mein Problem zu lösen.

Ich bin Lehrer und wir führen bei uns eine Projektwoche durch. Das bedeutet, dass wir insgesamt 15 Projekte (jeweils mit definierten Teilnehmerzahlen) anbieten und unsere rund 360 Schülerinnen optimal verteilen müssen. Die Summe der Teilnehmerplätze in den Projekten liegt mit rund 380 etwas höher, als die Schülerzahl.

Jetzt zum Problem. Die Schüler dürfen wählen und haben einen Erst- und einen Zweitwunsch. Zudem dürfen sie ein Projekt auswählen, welches sie auf gar keinen Fall wollen.

Gibt es hierfür einen Algorithmus, der mir bei der Verteilung hilft? Ich möchte also die gewichteten Wünsche nutzen.
Theoretisch müsste man ja vermutlich sämtliche Kombinationen durchspielen und gucken, wo das Gesamtergebnis am besten ist. Nur auf Papier ist das unmöglich und als PC-Programm bekomme ich es ohne Vorlage eines Algorithmus nicht gecodet.

Hoffe ihr habt eine Idee. Bei Rückfragen, bitte einfach schreiben

LG Jonny

[X_Strom]

Hallo,

kleiner Ansatz:
Zähle erst aus, welchem Projekt wieviele Erst-, Zweit- und Drittstimmen zuzuordnen sind.
Du hast dann ein Ranking der Beliebtheit der Projekte.
Fülle dann zuerst die unbeliebtesten Projekte mit Erststimmen auf.
Fülle dann die freien Plätze der unbeliebten Projekte mit Zweitstimmen auf, danach mit Drittstimmen.
Gehe dabei so vor, dass zu aller erst das Projekt aufgefüllt wird, in welchem am meisten Plätze frei sind.
Jedes gefüllte Projekt wird weggelegt.
Es geht dann so lange weiter, biss alle Projekte gefüllt sind.
Die beliebtesten Projekte werden dann wohl nicht belegt oder kaum belegt sein.
Diese füllst du nun mit Schülern voll auf, die eins der Projekte als Erstwunsch nannten, aber wegen des Drittwunsch woanders einsortiert wurden.

Na, irgendwie so sollte es klappen.

[Christa]

Hi,

das hier kennst du schon?

http://www.sjb.rv.bw.schule.de/schule/lehrer/ku/soft/pzt/pzt.htm

Es ist zwar nicht mehr ganz frisch, sondern schon 4 Jahre alt, aber wer weiß?!

Es geht in Richtung X-Stroms, mit Erstwunsch, Zweitwunsch, Drittwunsch (du wolltest ja Erstwunsch, Zweitwunsch, Ungewünscht), aber vielleicht hilft’s trotzdem. Und ansonsten kannst du den Autor kontaktieren, vielleicht findet ihr zusammen eine Lösung, die für dein Problem besser passt.

Gruß
Christa

[Christa]

Und noch eine Sache, falls ihr an der Schule Untis benutzen solltet, hilft vielleicht auch das:
https://www.untis.at/phpBB3/viewtopic.php?t=460

Vielleicht schreibst du, was ihr überhaupt für Software benutzt, möglicherweise gibt’s etwas Fertiges, und du musst nicht das Rad neu erfinden. Von IServ gibt’s z. B. auch ein Modul Kurswahl …

[jonnywalker_23331c]

Hallo,

vielen Dank für den Tipp. Das Programm scheint auf den ersten Blick ganz hilfreich zu sein. Leider steige ich da noch nicht ganz durch und muss erstmal mit kleinen Datenbeständen gucken, wie es funktioniert. Es gibt ja leider keine ausführliche Dokumentation.
Was meinst du mit „X-Stroms“ konnte mit Google dazu nichts finden.

LG Jonny

[jonnywalker_23331c]

Hallo,

wir benutzen tatsächlich Untis. Da wir aber eine Sek1-Schule sind nutzen wir nicht das Kurs-Modul und haben dies auch nicht bezahlt. Somit fällt das leider raus.
Für das Wahlproblem nutzen wir leider jedes Jahr nur Papierlisten und sitzen da eine ganze Woche um eine „ganz gute“ Verteilung zu finden.
Da würde ich es halt gerne beschleunigen.

LG Jonny

[Christa]

Was meinst du mit „X-Stroms“ konnte mit Google dazu nichts finden.

Uff, du solltest nicht googeln, und ich meinte X_Strom und nicht X-Strom, und das im Genitiv. Also das, was er dir geantwortet hat, mit den Wünschen, aber das hatte ich auch bereits geschrieben. Sorry, da habe ich dich wohl auf eine falsche Fährte gelockt.

muss erstmal mit kleinen Datenbeständen gucken, wie es funktioniert

Das wäre sowieso empfehlenswert.

Viel Erfolg!

[Christa]

haben dies auch nicht bezahlt

Ehrlich gesagt habe ich gar keine Idee, was für Kosten Untis verursacht. Wir haben es bei uns auch noch nicht so lange im Einsatz, und die Schulleitung ist nur am Fluchen, auch wenn sie sich langsam mit der einen oder anderen Macke abgefunden haben.

Da würde ich es halt gerne beschleunigen.

Das glaube ich dir gerne.

Sind die 360 SuS alle aus einem Jahrgang? Bzw., was eigentlich wichtiger wäre: muss die Klasse auch in der Liste enthalten sein, oder hast du nur eine Namensliste? Wird evtl. auch das Geschlecht mit gespeichert? Sind es immer 15 Projekte, oder können es auch mehr sein? Oder kann auch mal ein Projekt wegfallen, weil sich nicht genug Leute dafür interessieren? Und was meinst du mit

jeweils mit definierten Teilnehmerzahlen

genau? Gibt es eine Mindest- und eine Maximalgröße, evtl. auch nur eine der beiden? Denn ganz wird die Rechnung nie aufgehen.

Vielleicht mag sich einer unserer angehenden Anwendungsentwickler damit beschäftigen, wenn einer meiner Kollegen das interessant genug finden. Aber versprechen will und kann ich nichts!

[Juli_d3e3b8]

Hi,

das klingt für mich nach einem Linearen Optimierungsproblem wie es im Operations Research gelöst wird. Hier gibt es dazu eine Erklärung; schau dir besonders die Beispiele weiter unten an (z.B. das Produktionsproblem): https://www.mathebibel.de/lineare-optimierung

Genau so könnte man auch dein Problem aufstellen und dann von einem Computer lösen lassen; der benutzte Algorithmus heißt Simplex-Algorithmus.

Ein solches Optimierungsproblem besteht aus einem Dateninput (bei dir der Input, welcher Schüler welche Präferenzen hat), Entscheidungsvariablen (welcher Schüler welches Projekt bearbeitet), einer Zielfunktion (Anzahl der „Päferenzpunkte“ (s.u.) zu maximieren) und Nebenbedingungen (bspw. dass Projekt 1 maximal 20 Schüler aufnehmen kann). Da das mit den Indizes per Hand einfacher ist, habe ich es eben auf Papier geschrieben. So könnte dein Optimierungsproblem aussehen:

Zur Erklärung: Der Algorithmus versucht nun, den Zielfunktionswert zu maximieren. Das geht, indem möglichst viele x auf 1 gesetzt werden, wenn das c davor möglichst hoch (also eine 2 oder zumindest eine 1) ist und das x auf jeden Fall auf 0 zu setzen, wenn das c davor -1 ist. Die Nebenbedingungen darunter verhindern, dass einfach alle x mit c=2 oder c=1 davor auf eins gesetzt werden, sondern dass eben die Projekte gefüllt werden und jeder Schüler nur ein Projekt bearbeitet.

Da hier viele Nebenbedingungen und Variablen per Indizes zusammengefasst werden, ist das Problem etwas komplexer als die aus dem Beispiel oben. Ich habe es auch nicht implementiert und ausprobiert, könnte mir aber vorstellen, dass das schon ein guter Ansatz ist.

Implementieren kann man solche Probleme prinzipiell auch mit Excel (Stichwort Excelerweiterung Excel Solver), allerdings könnte ich mir vorstellen, dass das eben wegen den Indices nicht funktioniert, da man alles ausformulieren müsste. Ein Programm, das dafür eher ausgelegt ist, wäre IBM CPLEX (https://www.ibm.com/de-de/marketplace/ibm-ilog-cplex).

Ich denke, dass das Einlesen in das Alles etwas Zeit beanspruchen würde, aber dafür wärst du natürlich hinterher auch der King im Lehrerzimmer

Viel Erfolg!
Juli

[Juli_d3e3b8]

Hallo nochmal,

habe das Problem aus Interesse eben implementiert; und zwar so:

1. Excel-Datei mit den Präferenzen der Schüler (hier nur 5 Projekte, aber auch 280 Schüler):
   

2. Datei mit CPLEX aus Excel einlesen. Das geht so:
   

3. Problem implementieren. Variablen:

• projectMax legt die verfügbaren Plätze je Projekt fest
• pref sind die aus der Excel importieren Präferenzen
• pupils und projects sind sogenannte ranges: Man könnte auch jedes Mal 1…5 (also von 1 bis 5) schreiben, aber wenn man mal was
  ändern will, geht das so leichter
• x sind die Entscheidungsvariablen (in boolean, also entweder 0 oder 1).
  Dann steht da noch die Zielfunktion und die Nebenbedingungen (letztere in der „subject to“-Klammer). Die erste Nebenbedingung sorgt für die Einhaltung der Obergrenzen, die zweite, dass jeder Schüler ein Projekt bearbeitet.

4.Problem lösen (lassen). Hier ist die erste Zeile zugegebenermaßen etwas komisch dargestellt. Jede Zeile entspricht einem Schüler. Der erste Schüler bearbeitet Projekt 1, der zweite Schüler Projekt 3, der dritte Projekt 5 usw.

Anmerkung: Falls nicht genügend Plätze für alle Schüler verfügbar sind, hat das Problem keine Lösung, da immer mindestens eine Nebenbedingung verletzt ist.

Scheint alles ganz gut zu klappen! Falls dein Problem also noch aktuell ist und du dabei Hilfe brauchst, sag Bescheid

Grüße!
Juli