Lineare Programmierung < Gleichungssysteme < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:44 Di 10.04.2007 | | Autor: | MoritzB |
| Aufgabe | In einem Bewerbungsverfahren wurde die Leistungsfähigkeit der vier Bewerber (A,B,C,D) für jede der drei Stellen auf einer 10er Skala ermittelt:
Stelle 1; A: 4; B: 2; C: 9; D: 9
Stelle 2; A: 10; B: 9; C: 8; D: 9
Stelle 3; A: 9; B: 4; C: 1; D: 8
Stellen Sie das lineare Programm auf, mit der die optimale Zuordnung der Bewerber auf die Stellen ermittelt werden könnte. Vergessen Sie nicht, alle Variablen zu definieren. |
Ich habe als Lösungsweg folgende Gleichungen erstellt:
Zielfunktion:
x1 + x2 + x3 + x4 -> MAX!
Nebenbedingungen:
4x1 + 2x2 + 9x3 + 9x4 <= 10 (für Stelle 1)
10x1 + 9x2 + 8x3 + 9x4 <= 10 (für Stelle 2)
9x1 + 4x2 + 1x3 + 8x4 <= 10 (für Stelle 3)
x1 + x2 + x3 + x4 <= 40
Definition:
x1 bis x4, die Bewerber A, B, C, D
Nun, meine Frage ist einfach die, ist das so richtig oder gibt es hier einen Denkfehler? Die Technik der Lösung ist kein Problem, ich bin mir "nur" bei der Aufstellung der ZF und NB nicht sicher. Vielleicht hat jemand eine solche Aufgabe bereits gelöst und Zeit und Lust mir zu helfen, vielen Dank!
Und zum Schluss:
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:19 Di 10.04.2007 | | Autor: | piet.t |
Hallo Moritz und ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
Ich sortiere Deine Lösung mal um und gebe dann ein bisschen meinen Snf dazu....
> Definition:
>
> x1 bis x4, die Bewerber A, B, C, D
Ist dann immer [mm] x_1 [/mm] = A, [mm] x_2 [/mm] = b usw. ? Oder ist [mm] x_1 [/mm] der Qualifikationswert von Bewerber A auf der Stelle, die er erhält? Wie würde der dann ermittelt??
> Ich habe als Lösungsweg folgende Gleichungen erstellt:
>
> Zielfunktion:
>
> x1 + x2 + x3 + x4 -> MAX!
Nach Deiner Definition steht da: "maximiere die Summe aus den 4 Bewerbern". Ich weiss ja noch nicht mal, wie man denn 2 Bewerber addiert (Herr Maier+Herr Huber = Herr Schmidt??) - insofern würde das dann der zweiten Vermutung oben entsprechen, nämlich dass [mm] x_1,...,_x4 [/mm] die entsprechenden Qualifikationspunkte sind.
>
> Nebenbedingungen:
>
> 4x1 + 2x2 + 9x3 + 9x4 <= 10 (für Stelle 1)
Nehmen wir mal an, dass Bewerber 1 die Stelle 1 bekommt. Nach obiger Lesart der Zielfunktion steht dann hier:
4*4<=10 (denn A hat auf Stelle 1 ja den Punktwert 4) , d.h. die Restriktion ist nicht erfüllt. Bei den andern Bewerbern wird das ganze noch viel schlimmer.... :-(
>
> 10x1 + 9x2 + 8x3 + 9x4 <= 10 (für Stelle 2)
>
> 9x1 + 4x2 + 1x3 + 8x4 <= 10 (für Stelle 3)
>
> x1 + x2 + x3 + x4 <= 40
>
>
> Nun, meine Frage ist einfach die, ist das so richtig oder
> gibt es hier einen Denkfehler? Die Technik der Lösung ist
> kein Problem, ich bin mir "nur" bei der Aufstellung der ZF
> und NB nicht sicher. Vielleicht hat jemand eine solche
> Aufgabe bereits gelöst und Zeit und Lust mir zu helfen,
> vielen Dank!
>
So ganz klar ist die Lösung noch nicht, vor allem über die Definition der Variablen solltest Du nochmal gründlich nachdenken!
Nach dem ganzen Gemecker noch ein paar Tipps hinterher:
- Das ganze ist sicher kein kontinuierliche Optimierungsproblem, d.h. Du wirst wohl mit diskreten Variablen arbeiten müssen - so was kommt in Deiner Problemformulierung bisher nicht vor (oder können die Personen auch Jobsharing betreiben? A arbeitet 30% auf Stelle 1 und 70% auf Stelle 2? Dann nehme ich diese Aussage wieder zurück!)
- Du wirst m.E. sicher nicht mit 4 Variablen auskommen. Die Lösung. die ich mir auf die Schnelle aus dem Ärmel geschüttelt hätte verwendet 12 0/1-Variablen. Welche könnten das sein?
- Bevor Du die Restriktionen als Gleichung aufstellst überlege Dir einmal für jede Restriktion eine kleine verbale Beschreibung, was diese denn eigentlich aussagen soll. Sinnvollerweise schreibst Du die dann irgendwo neben die entsprechende Gleichung, dann wird das ganze deutlich leichter nachzuvollziehen - nicht nur für uns hier sondern vor allem für Dich.
Dann nochmal frisch ans Werk!
Gruss
piet
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:09 Di 10.04.2007 | | Autor: | MoritzB |
Zunächst einmal Danke für die schnelle Antwort!
Ehrlich gesagt bin ich mit der Logik der Aufgabe überfordert (das merkt man vermutlich). Also, meine Überlegung war folgende: Ich möchte am Ende der Optimierung in der Basis des Simplex-Tableaus die drei Kandidaten haben, die auf die drei Stellen gesetzt werden. Aus der Ausgabe geht leider nicht hervor, ob sich die Kandidaten auf verschiedene Stellen verteilen können, also gehe ich davon aus, dass sie entweder auf einer Stelle eingesetzt werden können oder nicht.
D.h. mit den X müssten die Kandidaten codiert werden, also x1 bis x4. Wie ich aus dem Ergebnis des Tableaus dann ersehen kann welcher Kandidat auf welcher Stelle eingesetzt wird, ist mir im Augenblick unklar.
Gleichzeitig soll die durch die 10er-Skala definierte Punktezahl der eingesetzten Kandidaten maximal sein, d.h. die höchstqualifizierten sollen auf ihren "Lieblingspositionen" eingesetzt werden. Das wäre also die Zielfunktion.
Und zuletzt habe ich noch die drei Nebenbedingungen: die einzelnen Qualifikationen der Kandidaten, auf die drei Stellen bezogen. Auf jeder Stelle können ja maximal 40 Qualifikationspunkte erreicht werden, also würden sich die NBs ändern, so dass jede mit <= 40 schließt.
Jetzt verstehe ich nur nicht, ich habe jetzt drei Nebenbedingungen und vier Variablen, wenn mich nicht alles täuscht benötige ich doch für die eindeutige Lösung eines GLS entsprechend viele NB. Die vierte NB ist mir nicht klar.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:49 Di 10.04.2007 | | Autor: | piet.t |
> Zunächst einmal Danke für die schnelle Antwort!
Bitteschön!
>
> Ehrlich gesagt bin ich mit der Logik der Aufgabe
> überfordert (das merkt man vermutlich). Also, meine
> Überlegung war folgende: Ich möchte am Ende der Optimierung
> in der Basis des Simplex-Tableaus die drei Kandidaten
> haben, die auf die drei Stellen gesetzt werden.
Wie vorhin gesagt geht es hier aber leider um ein diskretes Optimierungsproblem (die Variablen können nur bestimmte Werte annehmen), d.h. mit einem klassischen Simplex wirst Du das LP nicht gelöst bekommen, sondern da müssen irgendwelche MIP-Verfahren herhalten. Aber die Lösung des Programms ist in der Aufgabe (soweit Du sie gepostet hast) ja noch gar nicht gefordert.
> Aus der
> Ausgabe geht leider nicht hervor, ob sich die Kandidaten
> auf verschiedene Stellen verteilen können, also gehe ich
> davon aus, dass sie entweder auf einer Stelle eingesetzt
> werden können oder nicht.
Das sehe ich auch so.
>
> D.h. mit den X müssten die Kandidaten codiert werden, also
> x1 bis x4. Wie ich aus dem Ergebnis des Tableaus dann
> ersehen kann welcher Kandidat auf welcher Stelle eingesetzt
> wird, ist mir im Augenblick unklar.
Mir auch, ich weiss noch nicht mal, wie ich jetzt z.B. [mm] x_1 [/mm] = 1 interpretieren müsste.
Wir sollten vielleicht die Variablen noch etwas aufbohren.
Aus den Variablen sollte man also ablesen können, ob Stelle Y mit Kandidat Z besetzt wird. Für jede Kombination Kandidat<->Stelle gibt es zwei Werte: besetzt oder nicht besetzt. Wie viele Variablen wären das??
>
> Gleichzeitig soll die durch die 10er-Skala definierte
> Punktezahl der eingesetzten Kandidaten maximal sein, d.h.
> die höchstqualifizierten sollen auf ihren
> "Lieblingspositionen" eingesetzt werden. Das wäre also die
> Zielfunktion.
So in etwa. Die Summe über alle "Qualifikationspunkte" muss maximiert werden, d.h. es kann auch mal notwendig sein, jemanden nicht unbedingt auf seiner Paradestelle anzustellen um andere Schwächen auszugleichen - aber das zeigt ja dann die Lösung. Wenn wir wie oben vorgeschlagen einen anderen Satz Problemvariablen verwenden muss die Zielfunktion natürlich entsprechend angepasst werden.
>
> Und zuletzt habe ich noch die drei Nebenbedingungen: die
> einzelnen Qualifikationen der Kandidaten, auf die drei
> Stellen bezogen. Auf jeder Stelle können ja maximal 40
> Qualifikationspunkte erreicht werden, also würden sich die
> NBs ändern, so dass jede mit <= 40 schließt.
Ich wüsste jetzt nicht, wie ich für eine Stelle auf 40 Qualifikationspunkte zusammenbekommen kann. M.E. kann ich eine Stelle ja mit maximal einer Person besetzen - das sehe ich als Restriktion pro Stelle an, unabhängig, welche Qualifikationspunktzahl damit erreicht wird.
>
> Jetzt verstehe ich nur nicht, ich habe jetzt drei
> Nebenbedingungen und vier Variablen, wenn mich nicht alles
> täuscht benötige ich doch für die eindeutige Lösung eines
> GLS entsprechend viele NB. Die vierte NB ist mir nicht
> klar.
Allerdings geht es hier ja nicht um die Lösung eines Gleichungssystems sondern um die Optimierung einer Zielfunktion unter irgendwelchen Nebenbedingungen - und da könnte u.U. die Zahl der Restriktionen auch kleiner sein als die Zahl der Variablen.
Aber hier noch meine Vorschlägfe für die Restriktionen (in Textform, die Gleichungen darfst Du dann aufstellen; ist nicht schwer, wenn man die richtigen Variablen gewählt hat).
- Jede Stelle muss mit genau einem Bewerber besetzt werden (3 Restriktionen); es würde u.U. auch ausreichen zu fordern "jede Stelle darf mit höchstens einem Bewerber besetzt werden", der Rest ergibt sich dann aus der Zielfunktion (weil es keine negativen Qualifikationspunkte gibt)
- Jeder Bewerber darf auf höchstens einer Stelle eingesetzt werden; "genau eine" ist hier nicht möglich, weil einer der Bewerber ja leider auf der Strecke bleibt - wie im richtigen Leben, wenn sich 4 Leute auf 3 Stellen bewerben.
Kommst Du damit vielleicht etwas weiter?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:29 Di 10.04.2007 | | Autor: | MoritzB |
Hallo piet.t,
da ich es toll finde, dass Du dir soviel Mühe machst wollte ich nur kurz über diesen Weg Bescheid geben, ich werde versuchen das Problem weiter zu lösen und mir ggf. auch einen Termin beim Lehrstuhl besorgen, der diese Aufgabe in einer alten Klausur ausgegeben hatte, leider ohne Lösung. Bin jedoch bis Donnerstag nachmittag mit Klausurvorbereitung beschäftigt, nur damit dieser Thread nicht "aufgegeben" aussieht :)
Also nochmals, vielen Dank. Ich werde mir was überlegen.
|
|
|
|
