Zulässige Richtung aus Optimaltableau berechnen

15.03.2013, 14:39

Shizorano

Zulässige Richtung aus Optimaltableau berechnen

Meine Frage:
Hallo Leute,

ich habe die folgende lineare Optimierungsaufgabe gegeben:
$\begin{eqnarray*} max x_1 + x_2 s.d. 2x_1 + 2x_2 \leq 5 x_1 -2x_2 \leq 1 x_2 \leq 2 x_1 ,x_2 \geq 0 \end{eqnarray*}$

Ich sollte eine Skizze anfertige und die Optimallösung mit Normaltableaus berechnen.
Herausbekommen habe ich eine Optimallösung $\begin{eqnarray*} x = \begin{pmatrix} \frac 1 2 \\ 2 \end{pmatrix} \end{eqnarray*}$

Nun verlangt die Aufgabe:
Bestimmen Sie aus dem Optimaltableau eine zulässige Richtung d, entlang derer der Zielfunktionswert konstant bleibt und geben Sie eine zweite optimale Basislösung mithilfe von d und der von Ihnenn ermittelten Optimallösung an.

Von da an bin ich ratslos -.-

Meine Ideen:
Das Optimaltableau hat die Form:
$\begin{eqnarray*} \begin{pmatrix} 1&0&\frac 1 2&0&-1 \\ 0&0&-\frac 1 2&1&3 \\ 0&1&0&0&1 \end{pmatrix} * \begin{pmatrix} x_1\\x_2\\y_1\\y_2\\y_3 \end{pmatrix} = \begin{pmatrix} 0.5 \\ 4.5 \\ 2 \end{pmatrix} \end{eqnarray*}$
Dabei sind x normale und y Schlupfvariablen.

Die andere Optimallösung wäre ja (aus der Skizze abgelesen) $\begin{eqnarray*} x = \begin{pmatrix} 2 \\ \frac 1 2 \end{pmatrix} \end{eqnarray*}$
Bzw. alle Optimallösungen liegen nach der Skizze auf der Geraden $\begin{eqnarray*} f(x)= \frac 5 2 - x \end{eqnarray*}$ , wobei $\begin{eqnarray*} \frac 1 2 \leq x \leq 2 \end{eqnarray*}$ gelten muss.

Aber wie komme ich darauf AUS dem Optimaltableau heraus?!

Vielen Dank schonmal im vorraus für die Hilfe
MFG
Shizorano

15.03.2013, 15:17

Math1986

Auf diesen Beitrag antworten »

RE: Zulässige Richtung aus Optimaltableau berechnen

Zitat:

Original von Shizorano
Bzw. alle Optimallösungen liegen nach der Skizze auf der Geraden $\begin{eqnarray*} f(x)= \frac 5 2 - x \end{eqnarray*}$ , wobei $\begin{eqnarray*} \frac 1 2 \leq x \leq 2 \end{eqnarray*}$ gelten muss.

Das ist keine Gerade verwirrt

Poste mal die reduzierten Kosten im letzten Schritt

15.03.2013, 15:20

Shizorano

Auf diesen Beitrag antworten »

RE: Zulässige Richtung aus Optimaltableau berechnen
Keine Gerade? geschockt

Was ist es denn? verwirrt

reduzierte Kosten, kam in der ganzen Vorlesung leider nicht einmal begrifflich vor. Was meinst du genau?

15.03.2013, 15:24

Math1986

Auf diesen Beitrag antworten »

RE: Zulässige Richtung aus Optimaltableau berechnen

Zitat:

Original von Shizorano
Keine Gerade? geschockt

Was ist es denn? verwirrt

Es ist eine Funktion $\begin{eqnarray*} \mathbb R\to\mathbb R \end{eqnarray*}$ (genauer: $\begin{eqnarray*} \left[\frac 12 ,2\right]\to\mathbb R \end{eqnarray*}$ )

Zitat:

Original von Shizorano
reduzierte Kosten, kam in der ganzen Vorlesung leider nicht einmal begrifflich vor. Was meinst du genau?

Diese obere Zeile vom Tableau.

15.03.2013, 15:46

Kasen75

Auf diesen Beitrag antworten »

@Math1986

"reduzierte Kosten" würde ich das nicht nennen. Vor allem deswegen nicht, weil die Zielfunktion maximiert wird.

Grüße.

15.03.2013, 15:51

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von Kasen75
"reduzierte Kosten" würde ich das nicht nennen. Vor allem deswegen nicht, weil die Zielfunktion maximiert wird.

Ja, das war mir entgangen.

17.03.2013, 09:58

Shizorano

Auf diesen Beitrag antworten »

Die oberste Zeile im Tableau wäre:

0 0 0.5 0 0 || 2.5

(Ich hoffe, dass das so verständlich ist Augenzwinkern

)

17.03.2013, 13:33

Math1986

Auf diesen Beitrag antworten »

Ja, und aus der dritten Spalte kannst du den Richtungsvektor der gesuchten Gerade ablesen.

17.03.2013, 23:06

Shizorano

Auf diesen Beitrag antworten »

Öhm... kann ich?

Das versteh ich so grad nicht. =(

Wie sieht der Vektor denn aus?

18.03.2013, 11:02

Math1986

Auf diesen Beitrag antworten »

Das ist der RichtungsVektor, der an der Position 0,5 steht, also da, wo du normalerweise eine Verbesserung ablesen würdest..

Neue Frage »

Antworten »

Zulässige Richtung aus Optimaltableau berechnen

Verwandte Themen