Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Lineare Optimierung - Projekttage

Lineare Optimierung - Projekttage

Schüler

Tags: Lineare Optimierung, Prioritäten, Projekttage

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
Markus18

Markus18 aktiv_icon

15:35 Uhr, 17.02.2017

Antworten
Hallo,

ich habe von meinem Lehrer die Aufgabe bekommen, ein Programm in Java zu schreiben welches eine Lineare Optimierung durchführt. Es geht nicht um das Java Programm, sondern erstmal um die rein schriftliche rechnerische Lösung.

Jedes Jahr gibt es bei uns an der Schule Projekttage. Dieses Jahr soll jeder Schüler bis zu 10 Prioritäten für unterschiedliche Projekte angeben können. Nach Ablauf der Anmeldefrist, soll mithilfe einer Linearen Optimierung jedem Schüler die möglichst höchste Priorität zugewiesen werden.

Ich habe mir das erstmal nur mit zwei Prioritäten die Rechnung vorgestellt, habe aber scheinbar einen Fehler drin, wenn ich es nämlich grafisch löse, habe ich meinen Schnittpunkt bei (0,33 und 0,73). Nur was soll ich jetzt mit dem Schnittpunkt anfangen?
(siehe Bild)

Ist schon etwas beim Ansatz falsch oder fällt euch eine andere Methode zur Lösung ein?

linear_optimization

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."
Online-Nachhilfe in Mathematik
Antwort
pivot

pivot aktiv_icon

19:02 Uhr, 17.02.2017

Antworten
Hallo,

eine Bedingung für ein vernünftiges Ergebnis ist das du Binärvariablen verwendest. Ich habe aber dein Modell nicht ganz verstanden. Wie sind x und y überhaupt definiert ? Diese Frage ist die aller, aller wichtigste bei der Formulierung eines Modells.

Ich habe mir das jetzt so vorgestellt. Es gibt jeweils ein Schüler der eine bestimmte Bewertungskombination von Projekten angibt. Daneben gibt es noch weitere Bewertungskombinationen. Verschiedene Schüler können die gleiche Bewertungskombination haben. Beispielhaft habe ich jetzt 3 Bewertungskombinationen (B1,B2,B3) und damit auch 3 Schüler. Die Anzahl der Projekte (Pj) ist 4.


p1p2p3p4AnzB11051051B2555101B310105101

Die erste Zeile bedeutet, dass 1 Schüler die Projekte 2 und 4 bevorzugt. Ich für meinen Teil würde bei 4 Projekten vier verschiede Bewertungspunkte vorschreiben die jeweils einmal verwendet werden müssen, z.B. 1,2,3,4.

i ist der Index für die Projekte

j ist der Index für die Bewertungskombinationen

Jeder Schüler darf nur einem Projekt zu geordnet werden.

Dafür benötigt man eine Binärvariable (xij). Sie kann nur den Wert 1 oder 0 annehmen. Sie nimmt den Wert 1 an, wenn der Schüler mit dem Bewertungsprofil i dem Projekt j zugeordnet ist. Ansonsten hat sie den Wert 0.

Die mathematische Formulierung ist

j=14xij=1i

Für i=1 ist die ausgeschriebene Version x11+x12+x13+x14=1
Insgesamt sind es 3 Gleichungen.

Man kann jetzt noch Höchst- oder Mindestanzahl an Zuordnungen von Schülern zu einem Projekt festlegen. Zum Beispiel darf jedem Projekt höchstens 2 Schüler zu geordnet werden.

i=13xij2j

Für Projekt j=1 is die ausgeschriebene Nebenbedingung

x11+x21+x312

Insgesamt wären es hier 4 Gleichungen.

Eine Mindestbedingung würde in diesem Beispiel nicht greifen, da es weniger Schüler gibt als Projekte bzw. das Programm hätte keine zulässige Lösung.

Die Zielfunktion ist dann

i=13j=14xicij

Dabei ist cij jeweils die Bewertung des Schüler i für das Projekt j.

Grüße

pivot

Antwort
Femat

Femat aktiv_icon

16:53 Uhr, 20.02.2017

Antworten
Mir würde eine Tabelle wie folgt und ein gesundes Mass an Menschenkenntnis reichen, um eine Zuordnung zu realisieren.

Screenshot (427)