Probleme mit Simplexverfahren

21.03.2007, 12:05

MacLeod

Probleme mit Simplexverfahren

Hi,
ich sitzte hier über dem Simplexverfahren und habe das einige Problem, die ich trotz Literatur nicht klären kann unglücklich

Grundsätzlich sollte ich vielleich sagen, dass ich mit Mathe eher weniger am Hut habe (zumindest mit der Uni-Mathe), da ich mit der ganzen theoritischen und formalen Definition meine Probleme habe unglücklich

Ich benutze aktuell folgende Literatur:
[1] Neumann/Morlock - Operations Research (Hanser)
[2] Domschke/Drexel - Einführung in Operations Research (Springer)
[3] Ose/Lochmann/ea - Ausgewählte Kapitel d. Mathematik für Ingenieur- u. Fachschulen (Fachbuchverlag Leipzig)

[3] nutze ich, da dort doch einigen Sachen weniger formal, dafür aber verständlicher erklärt sind Augenzwinkern

1.) In [1] wird das Simplextableau immer mit der $\begin{eqnarray*} m \times n \end{eqnarray*}$ - Matrix aufgestellt, wobei $\begin{eqnarray*} m \end{eqnarray*}$ die Basisvariablen und $\begin{eqnarray*} n \end{eqnarray*}$ die Nichtbasisvariablen sind. In [2] und [3] werden dagegen die Tableaus immer als $\begin{eqnarray*} m \times o \end{eqnarray*}$ - Matrix aufgestellt, wobei $\begin{eqnarray*} m \end{eqnarray*}$ wiederum die Basisvar. sind. Aber $\begin{eqnarray*} o \end{eqnarray*}$ sind hier die Nichtbasisvar. + Basisvariablen (lt. Tableauschema). Die Koeffizienten sind im Grunde hier die Matrix aus [1] mit der Einheitsmatrix der Schlupfvariablen.
Warum werden in den Büchern solche Unterschiede gemacht? Worauf begründert sich diese Vereinfachung?

Weitere Fragen folgen hier im gleichen Thread Augenzwinkern

Gruß
MacLeod

21.03.2007, 12:42

Abakus

Auf diesen Beitrag antworten »

RE: Probleme mit Simplexverfahren

Zitat:

Original von MacLeod
Warum werden in den Büchern solche Unterschiede gemacht? Worauf begründert sich diese Vereinfachung?

Willkommen im Forum, MacLeod Wink

Du kannst das Simplextableau in langer und verkürzter Form schreiben. Bei letzterer werden die Spalten der Basisvariablen weggelassen (da steht nur eine 1 und sonst alles Nullen drin und das weiß man ja).

Für die ersten Schritte ist es aber wohl übersichtlicher, mit der langen Form des Tableaus zu rechnen.

Meintest du das ?

Grüße Abakus smile

21.03.2007, 13:57

MacLeod

Auf diesen Beitrag antworten »

RE: Probleme mit Simplexverfahren

Zitat:

Original von Abakus
Willkommen im Forum, MacLeod Wink

Danke, ich werde wohl jetzt wohl öfters hier meine Fragen loswerden, da demnächst meine Matheprüfung ansteht.

Zitat:

Original von Abakus
Meintest du das ?

Ja ok, damit ist die Frage erstmal geklärt.

Im folgenden beziehe ich mich auf das vereinfachte Tableau aus [1].

Mein nächstes Problem ist die Deutung von Simplextableaus. Wenn ich ein Tableau habe (egal ob jetzt Endtableau oder nicht), stellt sich ja die Frage, was man da sehen kann ...

1) Liegt eine zulässige Lösung vor?

2) Liegt eine optimale Lösung vor?

-> eine optimale Lösung liegt vor, wenn gilt: $\begin{eqnarray*} \zeta_l \ge 0 \end{eqnarray*}$ $\begin{eqnarray*} \forall l \in N \end{eqnarray*}$ , d.h IMHO wenn alle reuzierten Zielkoeffizienten positiv oder gleich Null sind.

3) Liegen unendlich viele optimale Lösungen vor?

4) Ist das Problem entartet?

-> eine Ecke ist entartet, wenn mind ein $\begin{eqnarray*} k \in B \end{eqnarray*}$ mit $\begin{eqnarray*} x_k = 0 \end{eqnarray*}$ , d.h. IMHO wenn für eine Basisvariable das zugehörige Ergebnis gleich Null ist

5) Gibt es für das Problem keine Lösung?

Auf die Fragen, wo ich mir einen Reim machen konnte, habe ich mal meine Vermutung hingeschrieben.

21.03.2007, 19:13

Abakus

Auf diesen Beitrag antworten »

RE: Probleme mit Simplexverfahren

Zitat:

Original von MacLeod
1) Liegt eine zulässige Lösung vor?

2) Liegt eine optimale Lösung vor?

-> eine optimale Lösung liegt vor, wenn gilt: $\begin{eqnarray*} \zeta_l \ge 0 \end{eqnarray*}$ $\begin{eqnarray*} \forall l \in N \end{eqnarray*}$ , d.h IMHO wenn alle reuzierten Zielkoeffizienten positiv oder gleich Null sind.

3) Liegen unendlich viele optimale Lösungen vor?

4) Ist das Problem entartet?

-> eine Ecke ist entartet, wenn mind ein $\begin{eqnarray*} k \in B \end{eqnarray*}$ mit $\begin{eqnarray*} x_k = 0 \end{eqnarray*}$ , d.h. IMHO wenn für eine Basisvariable das zugehörige Ergebnis gleich Null ist

5) Gibt es für das Problem keine Lösung?

Auf die Fragen, wo ich mir einen Reim machen konnte, habe ich mal meine Vermutung hingeschrieben.

Siehe zunächst mal hier: Simplexverfahren.

Ansonsten solltest du dir einige konkrete Beispiele vornehmen und die durchrechnen (dazu kannst du konkrete Fragen stellen). Dabei merkst du dann meist, wann du fertig bist und wann es nicht mehr weiter geht. Du brauchst zu jedem deiner Fragen Beispiele.

Ein wesentlicher Punkt beim Simplexverfahren ist sicher erstmal, es rechnen zu können.

Grüße Abakus smile

21.03.2007, 19:51

MacLeod

Auf diesen Beitrag antworten »

Das mit dem Rechnen klappt einigermaßen.
Aber mit dem Tableaus interpretieren klappt es eben nicht. Aber gut, dann hab ich hier ein paar Beispiele:
Gegeben: Endtableaus für das Standdardprob. Min x^Tx; udN Ax<=b, x>=0
Geuscht die Fragen 1-3 aus meinem vorherigen Post mit zusätzlich 3a) Falls keine optimalen Lösungen ex, geben sie einen Strahl an, der im zulässigen Beriech liegt und auf dem der ZF-Wert nicht nach unten beschränkt ist.

Beispiel 1)

| 1 4 5 |
-----------------
2|0 3 1 | -2
3|1 7 7 | 2
-----------------
3 2 4 | 18
zu 1) Nein
zu 2) Nein
zu 3) Nein (3a) braucht hier nicht angegeben zu werden)

Beispiel 2)

| 1 5 3 |
-----------------
2|-6 1 -2 | 8
4|-2 3 -7 | 4
-----------------
6 4 0 | 32
zu1) ja
zu2) ja
zu3) ja
zu 3a) X = (x1 x2 x3)T = (0 8 0)T + d*(0 2 1)T mit d>=0

Das Grundproblem ist hierbei jeweils nicht bekannt, es sind nur die Tableaus gegeben.
Ich sehe hier halt nicht, wie man zu den Lösungen der Fragen 1-3 kommt besonders nicht, wie ich dann diesen Strahl bei 3a) erkenne.

Und noch zu den Punkten 2 + 4 meines voheriegen Postings:
Verstehe ich das so richtig, wie ich das da jeweils vermute oder liege ich da schon falsch?

Grüße
MacLeod

22.03.2007, 13:12

MacLeod

Auf diesen Beitrag antworten »

Ok, hier mal ein konkretes Beispiel, wo ich mich anscheinend vertan habe ...

Min $\begin{eqnarray*} 2x_1 - 3x_3 \end{eqnarray*}$
u.d.N.
$\begin{eqnarray*} -x_1 + x_2 \leq 1 \end{eqnarray*}$
$\begin{eqnarray*} -x_1 + 2x_2 \leq 4 \end{eqnarray*}$
$\begin{eqnarray*} x_1 + x_2 \leq 8 \end{eqnarray*}$
$\begin{eqnarray*} 2x_1 + x_2 \leq 14 \end{eqnarray*}$
$\begin{eqnarray*} x_1, x_2 \geq 0 \end{eqnarray*}$

Von mir eingeführt Schlupfvariablen: $\begin{eqnarray*} x_3,x_4,x_5,x_6 \end{eqnarray*}$ jeweils größer gleich Null.

1. Tableau:
$\begin{eqnarray*} \begin{vmatrix} & x1 & x2 & x_k \\ x3 & -1 & 1 & 1 \\ x4 & -1 & 2 & 4 \\ x5 & 1 & 1 & 8 \\ x6 & 2 & 1 & 14 \\ & 2 & -3 & 0 \end{vmatrix} \end{eqnarray*}$

Als erste Pivotspalte wähle ich x2, da dort der kleinste Index ist. Entartet ist nicht, da in der letzten Spalte xk keine 0 vorkommt.
Da alle Koeffizienten der Pivotspalte größer 0 sind, berechne ich die den jewilegen Quotienten xk/Element der Pivotspalte aus. Der kleinste Quotient ist Zeile x3, das wird meine Pivotzeile.
Ich vertausche x2 + x3, es ergibt sich folgendes Tableau:

$\begin{eqnarray*} \begin{vmatrix} & x1 & x3 & x_k \\ x2 & -1 & 1 & 1 \\ x4 & 1 & -2 & 2 \\ x5 & 2 & -1 & 4 \\ x6 & 3 & -1 & 13 \\ & -1 & 3 & -3 \end{vmatrix} \end{eqnarray*}$

Neue Pivotspalte ist x1. Für das negative Element in der Pivotspalte muß ich keinen Quotienten bilden. Bei den anderen drei zeigt sich Zeile x4 als kleinster Quotient und neue Pivotzeile. Tausch x1 + x4

$\begin{eqnarray*} \begin{vmatrix} & x4 & x3 & x_k \\ x2 & 1 & 3 & 3 \\ x1 & 1 & -2 & 2 \\ x5 & -2 & 3 & 3 \\ x6 & -3 & 5 & 7 \\ & 1 & 1 & -1 \end{vmatrix} \end{eqnarray*}$

So laut Regel, das alle reduz. Zielkoeff. größer Null sein müßen um eine optimale Lösung zu haben, sollte ich jetzt fertig sein. Aber irgendwie stört mich, das der Zielfunktionswert größer als beim zweiten Tableau ist.

Basislösungen der Tableaus sollten sein:
Basislösung 1: x = (0,0,1,4,8,14)T
Basislösung 2: x = (0,1,0,2,7,13)T ?
Basislösung 3: x = (2,3,0,0,3,7)T ?

Wo liegen meine Fehler, oder bin gar richtig?

22.03.2007, 14:30

Abakus

Auf diesen Beitrag antworten »

Erstmal hierzu:

Zitat:

Original von MacLeod
Gegeben: Endtableaus für das Standdardprob. Min x^Tx; udN Ax<=b, x>=0
Geuscht die Fragen 1-3 aus meinem vorherigen Post mit zusätzlich 3a) Falls keine optimalen Lösungen ex, geben sie einen Strahl an, der im zulässigen Beriech liegt und auf dem der ZF-Wert nicht nach unten beschränkt ist.

Beispiel 1)

| 1 4 5 |
-----------------
2|0 3 1 | -2
3|1 7 7 | 2
-----------------
3 2 4 | 18
zu 1) Nein
zu 2) Nein
zu 3) Nein (3a) braucht hier nicht angegeben zu werden)

Es soll vermutlich $\begin{eqnarray*} z = Min ~c^T \cdot x \end{eqnarray*}$ heißen ? (ansonsten behandelst du quadratische Probleme, was natürlich auch geht)

Du hast hier als vollständige Basislösung (0, -2, 2, 0, 0), diese ist wegen der -2 und den Nichtnegativitätsbedingungen nicht zulässig.

Zitat:

Beispiel 2)

| 1 5 3 |
-----------------
2|-6 1 -2 | 8
4|-2 3 -7 | 4
-----------------
6 4 0 | 32
zu1) ja
zu2) ja
zu3) ja
zu 3a) X = (x1 x2 x3)T = (0 8 0)T + d*(0 2 1)T mit d>=0

Hier hast du die vollständige Basislösung (0, 8, 0, 4, 0), diese ist auch zulässig.

Bei Betrachtung des Tableaus siehst du in der Kriteriumszeile bei $\begin{eqnarray*} x_3 \end{eqnarray*}$ jedoch eine Null, und in der Zeile stehen nur negative Zahlen. D.h. du kannst $\begin{eqnarray*} x_3 \end{eqnarray*}$ beliebig erhöhen, ohne dass der Zielfunktionswert sich verändert, bei Erhöhung von $\begin{eqnarray*} x_3 \end{eqnarray*}$ um 1 verändern sich nur die Werte der linken Seite um (-2, -7). Das ist aber durch die Basisvariablen kompensierbar:

Du erhälst: $\begin{eqnarray*} (0, 8, 0, 4, 0) + d \cdot (0, 2, 1, 7, 0) \end{eqnarray*}$

Zitat:

Und noch zu den Punkten 2 + 4 meines voheriegen Postings:
Verstehe ich das so richtig, wie ich das da jeweils vermute oder liege ich da schon falsch?

Ich denke, du meinst das Richtige.

Grüße Abakus smile

22.03.2007, 15:33

Abakus

Auf diesen Beitrag antworten »

Ausnahmsweise als Doppelposting (da verschiedene Aufgaben):

Zitat:

Original von MacLeod
Ok, hier mal ein konkretes Beispiel, wo ich mich anscheinend vertan habe ...

Min $\begin{eqnarray*} 2x_1 - 3x_3 \end{eqnarray*}$
u.d.N.
$\begin{eqnarray*} -x_1 + x_2 \leq 1 \end{eqnarray*}$
$\begin{eqnarray*} -x_1 + 2x_2 \leq 4 \end{eqnarray*}$
$\begin{eqnarray*} x_1 + x_2 \leq 8 \end{eqnarray*}$
$\begin{eqnarray*} 2x_1 + x_2 \leq 14 \end{eqnarray*}$
$\begin{eqnarray*} x_1, x_2 \geq 0 \end{eqnarray*}$

Von mir eingeführt Schlupfvariablen: $\begin{eqnarray*} x_3,x_4,x_5,x_6 \end{eqnarray*}$ jeweils größer gleich Null.

1. Tableau:
$\begin{eqnarray*} \begin{vmatrix} & x1 & x2 & x_k \\ x3 & -1 & 1 & 1 \\ x4 & -1 & 2 & 4 \\ x5 & 1 & 1 & 8 \\ x6 & 2 & 1 & 14 \\ & 2 & -3 & 0 \end{vmatrix} \end{eqnarray*}$

Als erste Pivotspalte wähle ich x2, da dort der kleinste Index ist. Entartet ist nicht, da in der letzten Spalte xk keine 0 vorkommt.
Da alle Koeffizienten der Pivotspalte größer 0 sind, berechne ich die den jewilegen Quotienten xk/Element der Pivotspalte aus. Der kleinste Quotient ist Zeile x3, das wird meine Pivotzeile.
Ich vertausche x2 + x3, es ergibt sich folgendes Tableau:

$\begin{eqnarray*} \begin{vmatrix} & x1 & x3 & x_k \\ x2 & -1 & 1 & 1 \\ x4 & 1 & -2 & 2 \\ x5 & 2 & -1 & 4 \\ x6 & 3 & -1 & 13 \\ & -1 & 3 & -3 \end{vmatrix} \end{eqnarray*}$

Ich komme auf:

$\begin{eqnarray*} \begin{pmatrix} & x_1 & x_3 & b \\ x_2 & -1 & 1 & 1 \\ x_4 & 1 & -2 & 2 \\ x_5 & 2 & -1 & 7 \\ x_6 & 3 & -1 & 13 \\ z & -1 & 3 & 3 \end{pmatrix} \end{eqnarray*}$

Der Zielfunktionswert sollte sich hier nur vergrößern (weil du eigentlich maximierst, der Wert deiner Zielfunktion ist dann das Negative davon).

Grüße Abakus smile

22.03.2007, 16:03

MacLeod

Auf diesen Beitrag antworten »

Zitat:

Original von Abakus
Ich komme auf:

$\begin{eqnarray*} \begin{pmatrix} & x_1 & x_3 & b \\ x_2 & -1 & 1 & 1 \\ x_4 & 1 & -2 & 2 \\ x_5 & 2 & -1 & 7 \\ x_6 & 3 & -1 & 13 \\ z & -1 & 3 & 3 \end{pmatrix} \end{eqnarray*}$

Der Zielfunktionswert sollte sich hier nur vergrößern (weil du eigentlich maximierst, der Wert deiner Zielfunktion ist dann das Negative davon).

Grüße Abakus smile

Ja Vorzeichenfehler beim Ausrechnen des Elements und dann noch ein Denkfehler. Im folgenden Tableau bekomme ich dann 5 statt -1.
Das sollte dann aber das Maximum darstellen.
Die Basislösung lautet dann x = (2,3,0,0,3,7)T

Die Werte der Basislösung erfüllen meine Gleichungen mit den Schlupfvariablen, die gefundenen Werte für x1=2 und x2=3 erfüllen die Ungleichungen der NB und wenn ich sie ein die zu mimimierende ZF einsetzte, dann bekomme ich die -5 als Ergebnis.

Ist das so korrekt?

22.03.2007, 16:48

Abakus

Auf diesen Beitrag antworten »

Im Tableau stände eine 5, d.h. -5 wäre der erreichte Zielfunktionswert.

Zum Nachrechnen würde ich es vorziehen, wenn du den gesamten Simplexschritt mit beiden Tableaus angeben würdest (dann lässt sich da leichter drüber gucken und ggf. das Ergebnistableau diskutieren).

Grüße Abakus smile

27.03.2007, 18:37

MacLeod

Auf diesen Beitrag antworten »

So ich habe hier noch einmal eine Frage:
Folgendes Endtableau:
$\begin{eqnarray*} \begin{vmatrix} & x1 & x4 & x2 & x_k \\ x5 & 0 & 2 & 1 & 2 \\ x3 & -1 & 3 & -4 & 0 \\ z & 2 & 2 & 4 & 0 \end{vmatrix} \end{eqnarray*}$

1) Da hier ein xk = 0 ist, ist dieses Tableau entartet?
2) Die Optimale Lösung würde lauten: x* = (x1, x2, x3)T = (0,0,0)T?
3) die optimale Lsg stellt auch gleichzeitig die zulässige Lösung dar, das alle x entsprechende der NB positiv sind?

Anderes Problem:
$\begin{eqnarray*} \begin{vmatrix} & x1 & x5 & x4 & x_k \\ x3 & 0 & 1 & 3 & 7 \\ x2 & -1 & 2 & 7 & 2 \\ z & -2 & 10 & 60 & -358 \end{vmatrix} \end{eqnarray*}$

Dieses Porblems soll KEINE optimale Lösung haben, ABER eine zulässige Lösung. Warum und Welche? Ich finde da wieder nichts.

Gruß
MacLeod

28.03.2007, 00:45

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von MacLeod
Folgendes Endtableau:
$\begin{eqnarray*} \begin{vmatrix} & x1 & x4 & x2 & x_k \\ x5 & 0 & 2 & 1 & 2 \\ x3 & -1 & 3 & -4 & 0 \\ z & 2 & 2 & 4 & 0 \end{vmatrix} \end{eqnarray*}$

1) Da hier ein xk = 0 ist, ist dieses Tableau entartet?
2) Die Optimale Lösung würde lauten: x* = (x1, x2, x3)T = (0,0,0)T?
3) die optimale Lsg stellt auch gleichzeitig die zulässige Lösung dar, das alle x entsprechende der NB positiv sind?

zu 1) Das $\begin{eqnarray*} x_k \end{eqnarray*}$ sollte die zugehörige Kapazität darstellen. Nein, das Tableau ist nicht entartet. (EDIT: Es ist wegen $\begin{eqnarray*} x_3 = 0 \end{eqnarray*}$ natürlich doch entartet !)

zu 2) Ja, wobei ich die Angabe der vollständigen Basislösung bevorzuge: $\begin{eqnarray*} x = (0, 0, 0, 0, 2) \end{eqnarray*}$

zu 3) Ja, richtig. Die Optimalität siehst du allerdings in der Kriteriumszeile.

Zitat:

Anderes Problem:
$\begin{eqnarray*} \begin{vmatrix} & x1 & x5 & x4 & x_k \\ x3 & 0 & 1 & 3 & 7 \\ x2 & -1 & 2 & 7 & 2 \\ z & -2 & 10 & 60 & -358 \end{vmatrix} \end{eqnarray*}$

Dieses Porblems soll KEINE optimale Lösung haben, ABER eine zulässige Lösung. Warum und Welche? Ich finde da wieder nichts.

Eine zulässige Basislösung kannst du sofort aus dem Tableau ablesen. Wegen der -2 in der Kriteriumszeile kann diese Lösung aber nicht optimal sein. Weiter geht es mit Simplex aber auch nicht, weil du keinen zulässigen Pivot wählen kannst.

Grüße Abakus smile

28.03.2007, 08:52

MacLeod

Auf diesen Beitrag antworten »

Zitat:

Original von Abakus

Zitat:

zu 1) Das $\begin{eqnarray*} x_k \end{eqnarray*}$ sollte die zugehörige Kapazität darstellen. Nein, das Tableau ist nicht entartet.

zu 2) Ja, wobei ich die Angabe der vollständigen Basislösung bevorzuge: $\begin{eqnarray*} x = (0, 0, 0, 0, 2) \end{eqnarray*}$

zu 3) Ja, richtig. Die Optimalität siehst du allerdings in der Kriteriumszeile.

Jetzt bin ich ganz verwirrt. In einem Buch steht:
Eine Entartung liegt dann vor, wenn in der Basis einer Simplextabelle eine der Basisvariablen den Wert Null annimmt.
In einem anderen Buch (Neumann/Morlock) heißt es:
Sei $\begin{eqnarray*} x \end{eqnarray*}$ eine entartete Ecke mit der Basis $\begin{eqnarray*} { a^k | k \in \mathfrak{B} } \end{eqnarray*}$ . Dann gibt es (mind.) ein $\begin{eqnarray*} k \in \mathfrak{B} \end{eqnarray*}$ mit $\begin{eqnarray*} x_k = 0 \end{eqnarray*}$ .
Aus beiden Zitate würde ich jetzt schließem, dass dieses Tableau entartet ist, da ja das x3 in der Basis 0 ist.

Bitte berichtige mich, wo mein (Denk)Fehler liegt.

Zu 2) Naja der Prof scheint sich in seinem Skript stark an dem Buch von Neumann/Morlock zu orientieren und gibt wie im Buch die Basislösung ohne die Werte der Schlupfvariablen an.

Und zu 3): Die Kriteriumszeile ist doch die Z-Zeile, oder? und da hier nicht alle reduzierten Zielkoeffizienten größer gleich Null sind, ist hier eine optimalen Lösung gegeben, oder?
Und eine Zulässige Lösung muß in allen Koeffizienten der Zeile Z und der Spalte Xk der Nichtnegativitätsbedingung genügen?
Das wäre die Begründung?

Was wäre aber, wenn die reduziteren Zielkoef. in der Zeile Z größer gleich Null sind, aber die Basisvariablen in der SPalte xk kleiner Null sind?

Zitat:

Original von Abakus

Zitat:

Auch hier wieder die zulässige Basislösung, das die Basisvariablen positiv sind (7,2)?
Pivotspalte würde man hier eigentlich die Spalte x1 wählen, da der ZielKoef. kleiner Null ist. Da aber die Koeffzienten der Spalte x1 kleiner gleich Null sind, komme ich hier zu keiner optimalen/besseren Lösung (das ist ja die Bedingung für den 2. Schritt, um die Koef. $\begin{eqnarray*} \frac{x_k}{\gamma_{kl'}} \end{eqnarray*}$ ausrechnen zu können, damit ich die Pivotzeile bestimmen kann. Es können in der Pivotspalte negative Werte stehen, solange auch $\begin{eqnarray*} \gamma_{kl'} > 0 \end{eqnarray*}$ vorhanden sind. denn mit diesen Werten kann ich den Quotienten errechen und die Pivotzeile bestimmen.
Richtig?

Grüße
MacLeod

28.03.2007, 11:57

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von MacLeod
Jetzt bin ich ganz verwirrt. In einem Buch steht:
Eine Entartung liegt dann vor, wenn in der Basis einer Simplextabelle eine der Basisvariablen den Wert Null annimmt.
In einem anderen Buch (Neumann/Morlock) heißt es:
Sei $\begin{eqnarray*} x \end{eqnarray*}$ eine entartete Ecke mit der Basis $\begin{eqnarray*} { a^k | k \in \mathfrak{B} } \end{eqnarray*}$ . Dann gibt es (mind.) ein $\begin{eqnarray*} k \in \mathfrak{B} \end{eqnarray*}$ mit $\begin{eqnarray*} x_k = 0 \end{eqnarray*}$ .
Aus beiden Zitate würde ich jetzt schließem, dass dieses Tableau entartet ist, da ja das x3 in der Basis 0 ist.

Du hast natürlich recht, wegen $\begin{eqnarray*} x_3 = 0 \end{eqnarray*}$ und $\begin{eqnarray*} x_3 \end{eqnarray*}$ Basisvariable liegt eine Entartung vor. (Mich hat hier irritiert, dass du $\begin{eqnarray*} x_k \end{eqnarray*}$ für den Kapazitätsvektor genommen hast und mit $\begin{eqnarray*} x_k \end{eqnarray*}$ gleichzeitig als Variable arbeitest; nimm für den Kapazitätsvektor doch b als Bezeichnung).

Zitat:

Zu 2) Naja der Prof scheint sich in seinem Skript stark an dem Buch von Neumann/Morlock zu orientieren und gibt wie im Buch die Basislösung ohne die Werte der Schlupfvariablen an.

Und zu 3): Die Kriteriumszeile ist doch die Z-Zeile, oder? und da hier nicht alle reduzierten Zielkoeffizienten größer gleich Null sind, ist hier eine optimalen Lösung gegeben, oder?
Und eine Zulässige Lösung muß in allen Koeffizienten der Zeile Z und der Spalte Xk der Nichtnegativitätsbedingung genügen?
Das wäre die Begründung?

Was wäre aber, wenn die reduziteren Zielkoef. in der Zeile Z größer gleich Null sind, aber die Basisvariablen in der SPalte xk kleiner Null sind?

Weil ein Zielkoeffizient kleiner Null ist, ist es gerade keine optimale Lösung (ob die Lösung optimal ist, erkennst du anhand der Kriteriumszeile z). Ob die Nichtnegativitätsbedingung eingehalten ist, erkennst du anhand des Tableaus (wenn also eine Basisvariable kleiner Null ist, wäre die Lösung unzulässig).

In einer Erweiterung des Simplex-Verfahrens gibt es dann auch Variable, für die die Nichtnegativitätsbedingungen ggf. aufgehoben sind.

Zitat:

Original von Abakus

Zitat:

Die Basislösung wäre $\begin{eqnarray*} (x_2, x_3) = (2, 7) \end{eqnarray*}$ (hier nach der Reihenfolge der Variablen). Alles andere siehst du richtig.

Grüße Abakus smile

Neue Frage »

Antworten »

Probleme mit Simplexverfahren

Verwandte Themen