Symplex Algorithmus < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:28 Di 03.01.2006 | | Autor: | Freak84 |
| Aufgabe | Eine Reha Klinik bereut stationär und ambulant. Es gibt 50 Betten, pro Monat können 200 Patienten ambulant behandelt werden. 72Personen leisten monatlich maximal 10000 Arbeitsstunden. Auf einen Stationären Patienten muss man eine Arbeitskraft und 150 Arbeitsstunden monatlich berechnen; bei einem ambulanten sind es 1/5 Arbeitskraft und 25 Arbeitsstunden monatlich. Der Gewinn pro Monat beträgt pro stationärem Fall 2500 , pro ambulantem Fall 450 monatlich.
Wie wirtschaftet die Klinik am besten? Man löse die Aufgabe geometrisch und algorithmisch. |
So ich habe mir als erstes die Gleichungen mal zusammengebastelt allergins weiß ich nicht ob diese Stimmen da ich mir noch sehr unsicher bin.
x = ambulant
y = stationär
z = 450x + 2500y = soll maximal werden.
0 [mm] \le [/mm] x [mm] \le [/mm] 200 da ja maximal 200 Patienten behandelt werden können
0 [mm] \le [/mm] y [mm] \le [/mm] 50 da es nur 50 Betten für die Stationären gibt.
[mm] \bruch{1}{5} [/mm] x + y [mm] \le [/mm] 72 Personal
25x + 150y [mm] \le [/mm] 10000 Arbeitsstunden
Das sind die Gleichung die ich für sinnvoll halte.
Stimmen diese auch ?
Falls ja wie soll ich jetzt weiter machen ?
Und wie sieht es aus wenn ich das jetzt in so eine Symplet Algorithmus Tabelle übertrage?
Vielen Dank
Michael
|
|
| |
|
Hallo Michael,
das LP schaut gut aus. Jetzt kannst Du in ein 2-dim. Koordinatensystem (x- und y-Achse
entsprechend Deinen Variablen x,y) zu den Ungleichungen die affinen Unterr"aume
der Dimension 1, naemlich Geraden, einzeichnen, die dem Ersetzen von [mm] \leq [/mm] durch = entsprechen, also zB zu [mm] \frac{1}{5}x+y=72. [/mm] Der Schnitt aller sich ergebenden affinen Halbr"aume (zB [mm] \frac{1}{5}+y\leq [/mm] 72 beschreibt einen solchen) ist die Menge der
zulaessigen Loesungen. Dann zeichnest Du die Zielfunktion ein, d.h. eine
Gerade zu einer Gl. 450 x + 2500 y = [mm] z_0 [/mm] mit von Dir gewaehltem [mm] z_0 [/mm] und verschiebst
diese Gerade so, dass sie gerade noch nicht-leeren Schnitt mit der Menge der zul. Loesungen hat und unter dieser Praemisse [mm] z_0 [/mm] maximal wird.
Das war die graphische Loesung, fuer das Simplex-Tableau empfehle ich zB einen
Blick in das Buch von Alexander Schrijver, dort ist die Tableau-Methode ausfuehrlich
beschrieben.
Viele Gruesse,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:19 Mi 04.01.2006 | | Autor: | Freak84 |
Hi
Also Graphisch und mit den Gleichungen habe ich das Ergebnis rausbekommen.
Nur mit dem Symplex verstehe ich das überhaupt nicht. Habe mir von nem Kumpel ein Buch ausgeliehen was richtig gut sein soll aber ich Raff es einfach nicht.
Kann vielleicht jemand mal den Ansatz aufschreiben von dem Tablou
Vielen Dank
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:45 Mi 04.01.2006 | | Autor: | piet.t |
Hallo Michael,
was bedeutet "mit den Gleichungen habe ich das Ergebnis rausbekommen"?
Wenn Du das meinst was jetzt kommt kannst Du ja erst mal die beiden nächsten Gleichungsblöcke überspringen und dann weiterlesen....
In "verständlicher" Form würde man ja den Simplex-Alogrithmus so starten, dass man die logischen Variablen [mm] s_1 [/mm] bis [mm] s_4 [/mm] (alle >= 0) einführt und dann das LP schreibt als:
[mm]
\begin{array}{ccccc}
s_1 & = & 200 & -x & \\
s_2 & = & 50 & & -y \\
s_3 & = & 72 & - 0,2 x & - y \\
s_4 & = & 10000 & -25x & -150y\\
z & = & 0 & +450x & + 2500 y
\end{array}
[/mm]
zur Verbesserung von z wird nun y (Pivot-Spalte) erhöht, bis eine der s-Variablen 0 wird, in diesem Fall wäre das y = 50 bei [mm] s_2 [/mm] = 0.
Nun wird y in der zweiten Gleichung (der Pivot-Zeile) auf die linke Seite gebracht, in allen anderen Gleichungen wird y entsprechend ersetzt:
[mm]
\begin{array}{ccccc}
s_1 & = & 200 & -x & \\
y & = & 50 & & -s_2 \\
s_3 & = & 22 & - 0,2 x & +s_2 \\
s_4 & = & 2500 & -25x & -150s_2\\
z & = & 125000 & +450x & - 2500 s_2
\end{array}
[/mm]
...und dann wieder von vorne bis alle Koeffizienten der Zielfunktion negativ sind.
Die Simplex-Tableaus sind eigentlich nur eine andere Schreibweise in diesem Algorithmus:
Wir bringen alle Variablen auf die linke Seite, rechts bleiben die Konstanten. Wenn man dann aufpasst, dass die Reihenfolge der Variablen in allen Zeilen gleich ist kann man noch die Variablennamen weglassen und bekommt die Tableau-Schreibweise:
[mm]
\begin{array}{cccccccc}
1&0&1&0&0&0& &200\\
0&1&0&1&0&0& &50 \\
0,2&1&0&0&1&0& &72 \\
25&150&0&0&0&1& &200\\
& & & & & & & \\
450&2500&0&0&0&0& &0
\end{array}
[/mm]
nun wird genauso eine Spalte ausgewählt, die "begrenzende" Zeile bestimmt und dann die betroffene Spalte mittels Zeilenumformungen auf einen "Einheitsvektor" mit der 1 in der Pivot-Zeile gebracht.
Fazit: zu Rechnen ist das gleiche, nur schreibt man es eben anders hin!
Ich hoffe das hilft etwas weiter
Gruß
piet
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:40 Mi 04.01.2006 | | Autor: | Freak84 |
Vielen Dank der Algorithmus wie du das jetzt umgefort hast und wie du auf die gleichnungen gekommen bist glaube ich jetzt verstanden zu haben.
Nur wo oder besser wie kann ich jetzt das Ergebnis ablesen ?
Das ist mir noch unklar.
Auf welche spaöte muss ich achten und welche muss ich wie umformen?
Gruß
Michael
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:14 Mi 04.01.2006 | | Autor: | piet.t |
Ich habe oben in der "Gleichungsvariante" natürlich nur den ersten Schritt des Algorithmus durchgeführt, wegen [mm] z = 125000 + 450 x - 2500 s_2[/mm] kann man das Ergebnis durch Erhöhung von x natürlich noch verbessern - aber das kannst Du dann ja selber noch durchrechnen. Ziel ist, dass in der Formulierung von z neben der Konstanten nur noch Variablen mit negativen Koeffizienten stehen. Dann findet man den optimalen Wert, indem man alle Variablen die aktuell auf der rechten Seite stehen gleich 0 setzt. Die Werte der anderen Variablen sind dann über die übrigen Gleichungen zu bestimmen.
Im Simplex-Tableau habe ich noch gar keine Iteration durchgeführt - ich denke die hlift auch nicht gross zum Verständnis des ganzen.
Nochmal das Kochrezept im Tableau:
1. Suche in der letzten Zeile den größten positiven Wert p. So findest Du die Pivot-Spalte
2. Für jede Zeile wird nun der Eintrag r in der rechten Spalte durch p dividiert. Die Zeile mit dem kleinstem p/r wird Pivot-Zeile
3. Die Pivot-Zeile wird durch die Zahl dividiert, die am Shnittpunkt von Pivot-Zeile und -Spalte steht
4. Von allen anderen Zeilen wird ein vielfaches der Pivot-Zeile abgezogen, so dass in der Pivot-Spalte eine 0 entsteht
Dann wieder von vorne, bis man in Schritt 1 kein passendes Element mehr findet. Der Wert der Zielfunktion steht dann in der rechten unteren Ecke. Zum bestimmen der Variablenwerte würde ich das ganze dann aber nochmal als Gleichungssystem aufschreiben und die passenden Variablen = 0 setzen.
Gruß
piet
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:40 Mi 04.01.2006 | | Autor: | Freak84 |
Ich glaube ich bin einfach zu Blöd oder steh einfach total auf dem schlauch
ich habe das ganze jetzt mal weiter gerechnet und in der zielfunktion ist alles negativ aber was jetzt ?
ich habe
$ [mm] \begin{array}{ccccc} x & = & 200 & - s_1 & \\ y & = & 50 & & -s_2 \\ s_3 & = & -18 & - 0,2 s_1 & +s_2 \\ s_4 & = & -2500 & -25 s_1 & -150s_2\\ z & = & 215000 & -450 s_1 & - 2500 s_2 \end{array} [/mm] $
das hätte ich jetzt aber wie nun weiter ich seh da im moment noch sehr wenig sinn drin.
Ich weiß es muss nach meiner Lösung die ich Graphisch gemacht habe 160 und 40 rauskommen.
Nur irgendwie bin ich hier noch weit von weg
Danke schonmal
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 03:19 Do 05.01.2006 | | Autor: | wilma |
Hallo,
um Alle Eckpunkte in deinem Gleichungssystem zu durchlaufen um das maximum zu finden, musst Du versuchen alle Koeffizienten der Zielfunktion positiv zu bekommen.
Schau dir das mal an:
[mm] \vmat{ z & x1 & x2 & s1 & s2 & s3 & s4 & ZWert \\
0 & 1 & 0 & 1 & 0 & 0 & 0 & 200 \\
0 & 0 & 1 & 0 & 1 & 0 & 0 & 50 \\
0 & \bruch{1}{5} & 1 & 0 & 0 & 1 & 0 & 72 \\
0 & 25 & 150 & 0 & 0 & 0 & 1 & 10000 \\
1 & -450 & -2500 & 0 & 0 & 0 & 0 & 0} [/mm]
Das ist der unterste, linke Eckpunkt (0|0). Ziel ist es jetzt nach und nach alle Eckpunkte des Gleichungssystems zu durchlaufen.
Jetzt musst Du eigentlich immer die Spalte mit dem kleinsten Wert in der Zielfunktion als Pivotspalte wählen. Als Pivotzeile wählst Du die Zeile, bei der der ZWert geteilt durch das Element der jeweiligen Zeile aus der Pivotspalte der kleinste ist.
Nun hast Du Pivotspalte und Pivotzeile, und daraus ergibt sich das Pivotelement. Bringe das Pivotelement auf 1, indem Du die Pivotzeile durch das Pivotelement teilst. Jetzt bringst Du alle restlichen Werte aus der Pivotspalte auf Null, indem Du immer ein Vielfaches der Pivotzeile abziehst bzw. aufaddierst.
In unserem Beispiel ist die Spalte x2 die Pivotspalte und die zweite Zeile die Pivotzeile.
Der nächste Eckpunkt (0|50) sieht dann so aus:
[mm] \vmat{ z & x1 & x2 & s1 & s2 & s3 & s4 & ZWert \\
0 & 1 & 0 & 1 & 0 & 0 & 0 & 200 \\
0 & 0 & 1 & 0 & 1 & 0 & 0 & 50 \\
0 & \bruch{1}{5} & 0 & 0 & -1 & 1 & 0 & 22 \\
0 & 25 & 0 & 0 & -150 & 0 & 1 & 2500 \\
1 & -450 & 0 & 0 & 2500 & 0 & 0 & 125000} [/mm]
Hier ist die Spalte x1 die Pivotspalte, und die vierte Zeile die Pivotzeile.
Nach dem nächsten durchlauf sieht es folgendermaßen aus:
[mm] \vmat{ z & x1 & x2 & s1 & s2 & s3 & s4 & ZWert \\
0 & 0 & 0 & 1 & 6 & 0 & -\bruch{1}{25} & 100 \\
0 & 0 & 1 & 0 & 1 & 0 & 0 & 50 \\
0 & 0 & 0 & 0 & \bruch{1}{5} &1 & -\bruch{1}{125} & 2 \\
0 & 1 & 0 & 0 & -6 & 0 & \bruch{1}{25} & 1000 \\
1 & 0 & 0 & 0 & -200 & 0 & 18 & 170000} [/mm]
Das ist der Punkt (100|50). Das machst Du jetzt solange bis Du alle Punkte durchlaufen hast (alle Koeffizienten der Zielfunktion müssten dann positiv sein). Außerdem erhälst Du als ZWert in der Zielfunktion dann automatisch den Zielfunktionswert, das sollte dann der größte aufgetretene Wert hierfür sein.
Ich hoffe ich konnte Dir weiterhelfen...
Gruß, Wilma
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:02 Do 05.01.2006 | | Autor: | piet.t |
Hallo Michael,
irgendwie hast Du im Laufe Deiner Rechnungen wohl mal die falsche Pivot-Zeile erwischt.....
der Algorithmus würde an dieser Stelle sagen setze [mm] s_1 [/mm] und [mm] s_2 [/mm] auf 0.
Dann ergibt sich:
x=200
y=50
[mm] s_3 [/mm] = -18 (was nicht sein darf, da alle [mm] s_i [/mm] >= 0 sein müssen)
[mm] s_4 [/mm] = -2500 (ebenso)
z = 215000 (ist dann natürlich zu hoch)
Wenn wir nochmal auf meinem zweiten Gleichungssystem aufsetzen sieht man ja, dass x erhöht werden muss.
Preisfrage: welche Gleichung beschränkt das Wachstum von x, wie gross darf x folglich höchstens werden?
Gruß
piet
|
|
|
|
