Lineare Optimierung - Simplex |
04.12.2006, 17:47 | Kleine79 | Auf diesen Beitrag antworten » | ||
Lineare Optimierung - Simplex ich habe ein Problem beim Aufstellen des richtigen Simplex-Tableaus. Die Aufgabe lautet: Minimiere unter den Nebenbedingungen: Daraus ergibt sich folgendes Tableau: Nachdem ich das aufgestellt habe fange ich an zu rechnen indem ich mein Pivot-Element wähle. Komme dann aber immer auf ein falsches Ergebnis. Ist das Tableau so richtig aufgestellt oder hab ich da schon einen Fehler gemacht? Danke für die Hilfe! edit (Abakus): Latex eingefügt (ohne das ist von den Nebenbedingungen wenig zu erkennen) |
||||
04.12.2006, 20:43 | Abakus | Auf diesen Beitrag antworten » | ||
RE: Lineare Optimierung - Simplex
Du hast 3 Typen von Nebenbedingungen (<=, >=, =), die du auf dieselbe Art in ein Tableau steckst. Das musst du vorher zunächst auf eine Normalform bringen. Die Schlupfvariablen und rechte Seiten fehlen ganz, die sind zu ergänzen. Wie setzt ihr die Zielfunktion um ? (willst du mit dem Tableau maximieren oder minimieren ?) Grüße Abakus |
||||
04.12.2006, 21:41 | Kleine79 | Auf diesen Beitrag antworten » | ||
RE: Lineare Optimierung - Simplex Ich möchte minimieren. Wie stelle ich denn das ganze auf Normalform um? War in der Stunde krank und komm mit den Mitschriften der anderen nicht ganz zurecht. Wie die Schlupfvariablen zu ergänzen sind weiß ich. Danke für die schnelle Hilfe! |
||||
04.12.2006, 22:13 | Abakus | Auf diesen Beitrag antworten » | ||
RE: Lineare Optimierung - Simplex
Es gibt verschiedene Normalformen. Am Besten hälst du dich da an die Mitschrift und eure Version des Simplex-Verfahrens. Wie wurde dies definiert ? Eine Möglichkeit ist zB durch Multiplikation mit (-1) den Typ einer Ungleichung zu ändern. Grüße Abakus |
||||
04.12.2006, 22:16 | Kleine79 | Auf diesen Beitrag antworten » | ||
Also müßte ich die 4. Ungleichung mit -1 multiplizieren, damit ich dann überall <= stehen hab? Grüße Kleine |
||||
04.12.2006, 22:41 | Abakus | Auf diesen Beitrag antworten » | ||
Damit hättest du die eine Ungleichung umgewandelt, hast aber noch 2 Gleichungen. Der Struktur nach sähe das dann nach einem Maximierungs-Problem aus. Grüße Abakus |
||||
Anzeige | ||||
|
||||
10.03.2007, 07:58 | Matheloser :( | Auf diesen Beitrag antworten » | ||
Simplexaufgabe Hi Ich muss eine Aufgabe mit dem Simplexverfahren lösen, finde aber nur Sachaufaugaben, die ich irgendwie nicht auf meine Aufgabe beziehen kann (jaaa, ich bin nicht gut in Mathe). Ich wäre auch wirklich dankbar, wenn ihr mir helfen könntet. Aufgabe: Max. (3, 4)x udN x >= 0 und eine Frage ´nebebei: Was bedeutet das hochgestellte T hier? ct(hochgestellt)x |
||||
10.03.2007, 17:34 | Abakus | Auf diesen Beitrag antworten » | ||
RE: Simplexaufgabe
Das hochgestellte "T" beteutet "transponiert", du multiplizierst hier einen Zeilenvektor mit einem Spaltenvektor. Da c aber ein Spaltenvektor ist, musst du c einmal transponieren. Bei deiner Aufgabe fehlen erkennbar weitere Nebenbedingungen. Du kannst nämlich beliebig große einsetzen. Grüße Abakus |
||||
11.03.2007, 13:19 | Matheloser :( | Auf diesen Beitrag antworten » | ||
Und was soll ich da jetzt hinschreiben? Nicht lösbar? Danke für die Antwort |
||||
11.03.2007, 14:18 | Matheloser :( | Auf diesen Beitrag antworten » | ||
Wieder ich Wie würde die Simplex denn aussehen, wenn es Max (2,3) udN x>=0 im Gleichunssysthem |x1+2x2<=4 |x1+x2<=3 heißt? |
||||
11.03.2007, 17:24 | Matheloser :( | Auf diesen Beitrag antworten » | ||
Okay, ich bin etwas weiter gekommen Also, ich hab jetzt durch ein Programm diese Tableaus: x1 x2 x3 1 2 4 2 x4 1 1 3 3 2 3 0 und x1 x3 x2 0,5 0,5 2 4 x4 0,5 -0,5 1 2 0,5 -1.5 -6 Ich versteh nun nicht, wie man vom ersten Tableau aufs zweite kommt. Könnt ihr mir es vllt bitte erklären? |
||||
11.03.2007, 17:26 | Matheloser :( | Auf diesen Beitrag antworten » | ||
http://i21.photobucket.com/albums/b277/ichw16/second/123.jpg Sieht man besser |
||||
11.03.2007, 19:33 | Abakus | Auf diesen Beitrag antworten » | ||
Die Variablen und wurden mit einem Simplexschritt ausgetauscht. Um das zu verstehen, solltest du dich allerdings zunächst mit den Grundlagen des Simplex-Verfahrens befassen: dazu gehört, wie du den Pivot auswählst und was du dann damit machst. Grüße Abakus |
||||
12.03.2007, 18:43 | Matheloser :( | Auf diesen Beitrag antworten » | ||
Ich versuch es ja... Hier steht was von "altes Privotelement". Mein Privotelement (1.T) ist doch 2, ist davor noch eins? *verzweifel* |
||||
12.03.2007, 18:54 | Abakus | Auf diesen Beitrag antworten » | ||
Möglicherweise wurde in deinem Beispiel schon vorher ein Simplexschritt gemacht. Das braucht dich aber nicht zu interessieren. Der relevante Pivot ist die 2, völlig richtig. Grüße Abakus |
||||
12.03.2007, 19:13 | Matheloser :( | Auf diesen Beitrag antworten » | ||
Immerhn etwas. okay, dann noch was. Ich hab hier Gleichungen (a = 1/a) etc. die mir die Lösungen angeblich bringen sollen. Wenn ich das so aufteile, wie das hier steht, dann funktioniert es nicht. das wäre: Zeile x3 u. x4 Spalte 1 und 2 = d, daneben c, unter d b und unter c a. |
||||
12.03.2007, 19:44 | Abakus | Auf diesen Beitrag antworten » | ||
Offenbar meinst du die Gleichungen für den Simplexschritt ? Kennst du das Gaußverfahren ? Im Prinzip geht es hier genauso. Die Schwierigkeit hier ist, dass du gleich mit dem verkürzten Simplex-Tableau arbeitest; wenn du das vollständige Tableau hinschreiben würdest, hättest du zunächst mehr Übersicht. Grüße Abakus |
||||
12.03.2007, 20:01 | Matheloser :( | Auf diesen Beitrag antworten » | ||
ich kriegs nicht hin Ich kenn zwar den Gaußschen Algorithmus (ich denk mal, dass du den meinst..?) aber es klappt nicht. Ich ´weiß, dass ich nerve, tut mir leid Kannst du mir das bitte genauer erklären? Ich bin wirklich verzweifelt. Seit 2 Wochen versuche ich das zu lösen komme aber kein Stück weiter... |
||||
12.03.2007, 20:22 | Abakus | Auf diesen Beitrag antworten » | ||
Also ich schreibe das Problem zunächst in vollständiger Darstellung: Das erste was ich mache, ist die erste Zeile mit dem Pivot zu normalisieren; d.h. die Zeile wird durch 2 geteilt (damit der Pivot auch schön 1 ist): Jetzt werden in der Spalte des Pivots Nullen erzeugt, dazu wird zB die erste Zeile von der zweiten abgezogen: OK, die nächste Zeile kannst du dann selbst umformen ? Grüße Abakus |
||||
12.03.2007, 20:45 | Matheloser :( | Auf diesen Beitrag antworten » | ||
Frage: muss in der nächsten Zeile in der Spalte des Pivots auch eine 0? |
||||
12.03.2007, 20:48 | Abakus | Auf diesen Beitrag antworten » | ||
Ja, genau. Dann ist der Simplexschritt erst beendet. Grüße Abakus |
||||
12.03.2007, 20:55 | Matheloser :( | Auf diesen Beitrag antworten » | ||
okay, dann müsste das 0,5 0 1,5 0 -6 sein. Oder? Muss ich dann im letzten Tableau, also für die Optimallösung, das genauso machen? Achja, es gibt kein Wort um meine Dankbarkeit zu beschreiben. Deswegen benutze ich ein Smiley: |
||||
12.03.2007, 21:05 | Abakus | Auf diesen Beitrag antworten » | ||
Hier also der letzte Schritt: Die letzte Zeile wird noch umgeformt (bis auf ein Vorzeichen dein Ergebnis), die erste Spalte wird richtig gesetzt: OK, jetzt musst du das Tableau interpretieren: dein Zielfunktionswert hat sich auf 6 erhöht, aber du hast noch keine optimale Lösung. D.h. du musst noch mindestens einen weiteren Simplex-Schritt durchführen. Als erstes wäre dazu der neue Pivot zu bestimmen. Grüße Abakus |
||||
12.03.2007, 21:16 | Matheloser :( | Auf diesen Beitrag antworten » | ||
oookayyyy Vllt: 3/2...? ....ich bin ein Versager.... |
||||
12.03.2007, 21:23 | Abakus | Auf diesen Beitrag antworten » | ||
Ja, richtig. Nur die erste Spalte kommt als Pivotspalte in Frage, die Pivotspalte kriegst du über das MinMax-Zulässigkeitskriterium. Kannst du damit den Simplexschritt jetzt durchführen ? Grüße Abakus PS: wenn du auf "zitieren" klickst, kannst du meine Matrix kopieren bzw. siehst, wie die in Latex geschrieben ist |
||||
12.03.2007, 21:46 | Matheloser :( | Auf diesen Beitrag antworten » | ||
Ich habs mal wie oben versucht. Hoffe mal, dass ich dein Zitat richtig umgeändert habe edit (Abakus): Matrix gelöscht, wegen Latex-Codeverwirrung |
||||
12.03.2007, 21:48 | Matheloser :( | Auf diesen Beitrag antworten » | ||
das war wohl nichts xD Ich gebs mal so ein: 0 -2 -1 1/6 2/3 -3 1/3 1 0 -1/6 2/3 2/3 0 3 1/3 -4/3 -4/3 |
||||
12.03.2007, 22:12 | Abakus | Auf diesen Beitrag antworten » | ||
Das sind 7 Zahlen in der ersten Reihe, da passen aber nur 5 rein. Ich forme es mal so um, dass die Pivotzeile bereits richtig steht: Von da aus geht es also weiter. Mit \frac a b stellst du einen Bruch dar: Ansonsten: wenn du dich anmeldest, kannst du deine Beiträge auch editieren. Grüße Abakus |
||||
12.03.2007, 22:27 | Matheloser :( | Auf diesen Beitrag antworten » | ||
Soo geschafft |
||||
12.03.2007, 22:38 | Abakus | Auf diesen Beitrag antworten » | ||
Ich komme auf (versuch das mal zu überprüfen): Jetzt hast du ein Optimum von . Grüße Abakus |
||||
12.03.2007, 22:41 | Matheloser :( | Auf diesen Beitrag antworten » | ||
Ich werd es sofort versuchen zu überprüfen. Nur eine Frage: Das Programm, dass das ausgerechnet hat, kam auf 7--rundet jetzt das Programm merkwürdig oder ist ein Fehler drin? Danke |
||||
12.03.2007, 22:55 | Matheloser :( | Auf diesen Beitrag antworten » | ||
Tut mir leid, ich komm nicht auf deine Lösungen. Welche Zeilen hast du denn wie mit einander verrechnet? *auf dem Schlauch steh* |
||||
12.03.2007, 23:11 | Abakus | Auf diesen Beitrag antworten » | ||
Da kann natürlich immer ein RF drin sein, klar. Hier mal eine Skizze, die gut aussieht: Wenn du es als Programmlösung möchtest: MAX 2x1 + 3x2 ST x1 + 2x2 <= 4 2x1 +x2 <= 3 END LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 6.333333 VARIABLE VALUE REDUCED COST X1 0.666667 0.000000 X2 1.666667 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 1.333333 3) 0.000000 0.333333 NO. ITERATIONS= 2 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 2.000000 4.000000 0.500000 X2 3.000000 1.000000 2.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 4.000000 2.000000 2.500000 3 3.000000 5.000000 1.000000 Grüße Abakus |
||||
12.03.2007, 23:16 | Matheloser :( | Auf diesen Beitrag antworten » | ||
Der Programmlösung nach zu urteilen scheinst du richtig zu liegen Auch wenn ich immer noch nicht weiß, wie du das gemacht hast xD Auf jeden Fall: Danke ohne dich würde ich wohl noch Ewigkeiten dran sitzen lg |
||||
12.03.2007, 23:20 | Matheloser :( | Auf diesen Beitrag antworten » | ||
Doch noch eine Frage: wie kommst du auf die Gleichungen zum erstellen der Graphen? |
||||
12.03.2007, 23:20 | Abakus | Auf diesen Beitrag antworten » | ||
OK, bei welchem Schritt steckst du fest ? Beim letzten Simplexschritt musst du die Pivotzeile mit -1/2 malnehmen und zu den anderen beiden Zeilen jeweils addieren. Hast du das berücksichtigt ? Grüße Abakus EDIT: im Graphen siehst du die beiden Nebenbedingungen und die Zielfunktion mit dem Niveau der optimalen Lösung |
||||
12.03.2007, 23:29 | Matheloser :( | Auf diesen Beitrag antworten » | ||
Okay, ich hatte mich beim rechnen vertan. Stimmt, danke Beim Graphen hänge ich bei der Gleichung 3-2x fest. Den Rest verstehe ich |
||||
12.03.2007, 23:38 | Abakus | Auf diesen Beitrag antworten » | ||
Naja, du hast als Nebenbedingung 2x + y <= 3. Also y <= 3 - 2x. Grüße Abakus |
||||
12.03.2007, 23:41 | Matheloser :( | Auf diesen Beitrag antworten » | ||
<= 4 nicht 3 Aber egal, Hauptsache ich habe diese Aufgabe endlich. DANKE |
||||
12.03.2007, 23:46 | Abakus | Auf diesen Beitrag antworten » | ||
Es ergibt sich aus der zweiten Nebenbedingung (und da steht eine 3). Bei der anderen (x + 2y <= 4) musst du letztendlich noch durch 2 teilen und auch umstellen. Grüße Abakus |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |