Lineare Optimierungsprobleme lösen (Simplex-Verfahren)

03.12.2012, 00:56

Molly23

Lineare Optimierungsprobleme lösen (Simplex-Verfahren)

Hallo zusammen!

Ich lerne gerade für meine Optimierungsklausur mit einigen Aufgabenblättern aus dem Internet bzw. alten Blättern von Dozenten meiner Uni. Jetzt habe ich Aufgaben gefunden, die mich etwas verwirren.

http://www.math.tu-bs.de/~degbers/einfop...fopt0910_04.pdf

Also Aufgabe 1 ist natürlich gar kein Thema.
Bei Aufgabe 2 soll man ja einmal die Zweiphasenmethode und dann die M-Methode benutzen... Jetzt habe ich in einigen Büchern und im Internet aber gelesen, dass man die Zweiphasenmethode auch als M-Methode bezeichnen kann, weil das das gleiche ist?! In meinem Skript wird z.B. unterschieden zwischen Zweiphasenmethode und Lexikographischer M-Methode. Kann das damit gemeint sein? Also a) kann ich ohne Probleme lösen, aber b) bereitet mir hier Schwierigkeiten.
Bei Aufgabe 3b) verstehe ich überhaupt nicht, was genau verlangt wird. Diese ganze Aufgabenstellung irritiert mich total. Was muss man da machen? Und ist bei c) die Pivotregel von Bland gemeint?

Es wäre nett, wenn sich jemand Zeit für meine Fragen nehmen und mir ein wenig helfen könnte Augenzwinkern

LG Molly

03.12.2012, 12:02

Math1986

Auf diesen Beitrag antworten »

RE: Lineare Optimierungsprobleme lösen [Optimierung]
Zur Aufgabe 2:
Zwei-Phasen-Methode und Big-M-Methode sind 2 verschiedene Methoden.
Halte dich an die Definition in deinem Skript.

Zu Aufgabe 3:
b) Du musst einfach nur zeigen, dass bei den genannten Strategien das Simplex-Verfahren kreiseln kann.
c) Bland ist da schon richtig, um Kreiseln zu verhindern.

03.12.2012, 14:14

Molly23

Auf diesen Beitrag antworten »

RE: Lineare Optimierungsprobleme lösen [Optimierung]
Danke für deine schnelle Antwort!
Ist denn die Big-M-Methode das gleiche wie die lexikographische M-Methode oder ist das was anderes? Bzw. wo gibt es Unterschiede?
Und zu 3b): beduetet das, dass ich zweimal rechen muss? Also einmal mit Zeilenauswahl- und das andere Mal mit Spaltenauswahlregel?

03.12.2012, 16:04

Math1986

Auf diesen Beitrag antworten »

RE: Lineare Optimierungsprobleme lösen [Optimierung]

Zitat:

Original von Molly23
Danke für deine schnelle Antwort!
Ist denn die Big-M-Methode das gleiche wie die lexikographische M-Methode oder ist das was anderes? Bzw. wo gibt es Unterschiede?

Ich habe die "lexikographische M-Methode" noch nie gehört, würde aber mal vermuten, dass es das selbe Verfahren meint.

Zitat:

Original von Molly23
Und zu 3b): beduetet das, dass ich zweimal rechen muss? Also einmal mit Zeilenauswahl- und das andere Mal mit Spaltenauswahlregel?

Nein, nicht zweimal. Innerhalb des Simplex-Tableaus musst du ja an gegebener Stelle die Pivotzeile bzw. -spalte auswählen. Im Allgemeinen ist aber weder die Zeile noch die Spalte eindeutig bestimmt. Daher wendest du bei Nichteindeutigkeit die genannten Auswahlregeln an.

04.12.2012, 02:36

Molly23

Auf diesen Beitrag antworten »

RE: Lineare Optimierungsprobleme lösen [Optimierung]
Ich habe zur Big-M-Methode nochmal eine Frage.
Also ich bin folgendermaßen vorgegangen:

max $\begin{eqnarray*} x_{1}+6x_{2}-My_{1}-My_{2} \end{eqnarray*}$
unter $\begin{eqnarray*} x_{1}+x_{2}-x_{3}+y_{1}=7 \end{eqnarray*}$
$\begin{eqnarray*} x_{1}-x_{2}-x_{4}+y_{2}=4 \end{eqnarray*}$
$\begin{eqnarray*} x_{1}+x_{5}=8 \end{eqnarray*}$
$\begin{eqnarray*} x_{1},x_{2},x_{3},x_{4},x_{5},y_{1},y_{2}\geq 0 \end{eqnarray*}$

$\begin{eqnarray*} y_{1}=7-x_{1}-x_{2}+x_{3} \end{eqnarray*}$
$\begin{eqnarray*} y_{2}=4-x_{1}+x_{2}+x_{4} \end{eqnarray*}$
einsetzen in max:
$\begin{eqnarray*} (2M+1)x_{1}+6x_{2}-Mx_{3}-Mx_{4}-11M \end{eqnarray*}$

Ist das soweit richtig? Und was mache ich mit dem $\begin{eqnarray*} 6x_{2} \end{eqnarray*}$ in meinem Tableau in der M-Zeile?

04.12.2012, 02:49

Molly23

Auf diesen Beitrag antworten »

RE: Lineare Optimierungsprobleme lösen [Optimierung]
Ok das mit dem $\begin{eqnarray*} 6x_{2} \end{eqnarray*}$ habe ich jetzt verstanden. Da stand ich wohl etwas auf dem Schlauch... Ist der Rest denn so ok?

04.12.2012, 03:31

Molly23

Auf diesen Beitrag antworten »

RE: Lineare Optimierungsprobleme lösen [Optimierung]
Meine optimale Lösung ist übrigens $\begin{eqnarray*} x_{1}=8 \end{eqnarray*}$ , $\begin{eqnarray*} x_{2}=4 \end{eqnarray*}$ mit dem Zielwert 32.

04.12.2012, 08:08

Mystic

Auf diesen Beitrag antworten »

RE: Lineare Optimierungsprobleme lösen [Optimierung]
Ja, scheint alles in Ordnung zu sein... Freude

04.12.2012, 08:33

Molly23

Auf diesen Beitrag antworten »

RE: Lineare Optimierungsprobleme lösen [Optimierung]
Super danke! Wink

Neue Frage »

Antworten »

Lineare Optimierungsprobleme lösen (Simplex-Verfahren)

Verwandte Themen