Lineare Optimierung - Simplex

Neue Frage »

Kleine79 Auf diesen Beitrag antworten »
Lineare Optimierung - Simplex
Hallo Wink ,

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)
Abakus Auf diesen Beitrag antworten »
RE: Lineare Optimierung - Simplex
Zitat:
Original von Kleine79
Minimiere

unter den Nebenbedingungen:








Daraus ergibt sich folgendes Tableau:



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 smile
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!
Abakus Auf diesen Beitrag antworten »
RE: Lineare Optimierung - Simplex
Zitat:
Original von Kleine79
Ich möchte minimieren.

Wie stelle ich denn das ganze auf Normalform um?


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 smile
Kleine79 Auf diesen Beitrag antworten »

Also müßte ich die 4. Ungleichung mit -1 multiplizieren, damit ich dann überall <= stehen hab? verwirrt

Grüße

Kleine Wink
Abakus Auf diesen Beitrag antworten »

Zitat:
Original von Kleine79
Also müßte ich die 4. Ungleichung mit -1 multiplizieren, damit ich dann überall <= stehen hab? verwirrt


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 smile
 
 
Matheloser :( Auf diesen Beitrag antworten »
Simplexaufgabe
Hi Wink
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). Forum Kloppe

Ich wäre auch wirklich dankbar, wenn ihr mir helfen könntet. Mit Zunge


Aufgabe:
Max. (3, 4)x udN x >= 0


und eine Frage ´nebebei:
Was bedeutet das hochgestellte T hier?
ct(hochgestellt)x
Abakus Auf diesen Beitrag antworten »
RE: Simplexaufgabe
Zitat:
Original von Matheloser unglücklich
Aufgabe:
Max. (3, 4)x udN x >= 0

und eine Frage ´nebebei:
Was bedeutet das hochgestellte T hier?
ct(hochgestellt)x


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 smile
Matheloser :( Auf diesen Beitrag antworten »

Und was soll ich da jetzt hinschreiben? Nicht lösbar?

Danke für die Antwort smile
Matheloser :( Auf diesen Beitrag antworten »

Wieder ich Wink

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?
Matheloser :( Auf diesen Beitrag antworten »

Okay, ich bin etwas weiter gekommen smile

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?
Matheloser :( Auf diesen Beitrag antworten »

http://i21.photobucket.com/albums/b277/ichw16/second/123.jpg

Sieht man besser
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 smile
Matheloser :( Auf diesen Beitrag antworten »

Ich versuch es ja...unglücklich

Hier steht was von "altes Privotelement". Mein Privotelement (1.T) ist doch 2, ist davor noch eins? *verzweifel*
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 smile
Matheloser :( Auf diesen Beitrag antworten »

Immerhn etwas. smile

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.
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 smile
Matheloser :( Auf diesen Beitrag antworten »

ich kriegs nicht hin unglücklich 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 traurig

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...
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 smile
Matheloser :( Auf diesen Beitrag antworten »

Frage: muss in der nächsten Zeile in der Spalte des Pivots auch eine 0?
Abakus Auf diesen Beitrag antworten »

Zitat:
Original von Matheloser unglücklich
Frage: muss in der nächsten Zeile in der Spalte des Pivots auch eine 0?


Ja, genau. Dann ist der Simplexschritt erst beendet.

Grüße Abakus smile
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: Gott
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 smile
Matheloser :( Auf diesen Beitrag antworten »

oookayyyy Lehrer

Vllt: 3/2...? ....ich bin ein Versager.... Forum Kloppe
Abakus Auf diesen Beitrag antworten »

Zitat:
Original von Matheloser unglücklich
Vllt: 3/2...?


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 smile

PS: wenn du auf "zitieren" klickst, kannst du meine Matrix kopieren bzw. siehst, wie die in Latex geschrieben ist
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
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
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 smile
Matheloser :( Auf diesen Beitrag antworten »

Soo geschafft smile

Abakus Auf diesen Beitrag antworten »

Ich komme auf (versuch das mal zu überprüfen):



Jetzt hast du ein Optimum von .


Grüße Abakus smile
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 Mit Zunge
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*
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 smile
Matheloser :( Auf diesen Beitrag antworten »

Der Programmlösung nach zu urteilen scheinst du richtig zu liegen smile 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 Mit Zunge

lg
Matheloser :( Auf diesen Beitrag antworten »

Doch noch eine Frage: wie kommst du auf die Gleichungen zum erstellen der Graphen?
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 smile

EDIT: im Graphen siehst du die beiden Nebenbedingungen und die Zielfunktion mit dem Niveau der optimalen Lösung
Matheloser :( Auf diesen Beitrag antworten »

Okay, ich hatte mich beim rechnen vertan. Stimmt, danke smile

Beim Graphen hänge ich bei der Gleichung 3-2x fest. Den Rest verstehe ich
Abakus Auf diesen Beitrag antworten »

Naja, du hast als Nebenbedingung 2x + y <= 3. Also y <= 3 - 2x.

Grüße Abakus smile
Matheloser :( Auf diesen Beitrag antworten »

<= 4 nicht 3 smile Aber egal, Hauptsache ich habe diese Aufgabe endlich.

DANKE Big Laugh
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 smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »