Linare Optimierung - Basislösung

15.07.2008, 18:48

luisa_86

Linare Optimierung - Basislösung

Hallo,

habe eine Frage. Und zwar habe ich eine Lineare Optimierungsaufgabe die ich in eine Normalform gebracht habe. Das erste Simplex-Tableau sieht folgendermaßen aus:

http://img99.imageshack.us/img99/7681/0028mp1.th.jpg

Zur Info: x4 und x5 sind Schlupfvariablen die entstanden sind als ich die Ungleichungen in Gleichungen transformiert habe.

Die Frage lautet nun: Ist die zugehörige Basislösung optimal?

So, für mich stellen sich jetzt erstmal zwei Fragen die meine Mathebücher leider nur sehr kryptisch beantworten. Erstmal, was ist die zugehörige Basislösung zu diesem Tableau? Ist das einfach x4=10 ; x5=4 und x3=6 ?

Und ist optimal das gleiche wie zulässig?

15.07.2008, 20:41

Abakus

Auf diesen Beitrag antworten »

RE: Linare Optimierung - Basislösung

Zitat:

Original von luisa_86
So, für mich stellen sich jetzt erstmal zwei Fragen die meine Mathebücher leider nur sehr kryptisch beantworten. Erstmal, was ist die zugehörige Basislösung zu diesem Tableau? Ist das einfach x4=10 ; x5=4 und x3=6 ?

Zugehörige Basislösung ist $\begin{eqnarray*} (x_3, x_4, x_5) = (6, 10, 4) \end{eqnarray*}$ und vollständige Basislösung ist $\begin{eqnarray*} (0, 0, 6, 10, 4) \end{eqnarray*}$ . Möglich, dass ihr letzteres auch oder nur als Basislösung bezeichnet.

Zitat:

Und ist optimal das gleiche wie zulässig?

Nein. Es gibt i.A. mehrere zulässige Basislösungen, von denen i.A. nicht alle optimal sind.

Die Kriteriumszeile sollte dir sagen, ob die Basislösung optimal ist oder nicht.

Grüße Abakus smile

EDIT: Basislösung korrigiert

15.07.2008, 21:28

luisa_86

Auf diesen Beitrag antworten »

So langsam kommt Licht ins Dunkeln. Eine Frage vorweg. Also x4, x5 und x3 sind doch diese sogenannten Basisvariablen richtig? Und x1 und x2 die Nichtbasisvariablen?

Also die Lösung habe ich glaube ich auch verstanden wie du darauf kommst. Bei der Basislösungen müssen die Nichbasisvariablen ja Null sein und nur die Basisvariablen dürfen Koeffizienten >0 haben richtig?

Also wäre hier:

x1=0
x2=0
x3=6
x4=10
x5=4

das deckt sich ja mit deiner Antwort. Nur warum weiß ich das ich für die Basislösung x1, x2 und x3 nehmen muss und nicht wie ich erst dachte meine Basisvariablen (wenn das so ist) x3, x4 und x5. Oder nimmt man dafür die Variablen die keine Schlupfvariablen sind? Also für die Verkürzte Form halt, weil bei der langen ist ja ohnehin jede Variable drin.

So das sollte erstmal reichen :-) Wie ich rauskriege ob die Basislösung optimal ist versuche ich noch mal selber rauszukriegen.

16.07.2008, 11:30

lusia_86

Auf diesen Beitrag antworten »

So, ich bin wieder weitergekommen. Also wenn ich alles richtig verstanden habe kann man jetzt folgendes sage:

Die Basislösung ist ist zwar zulässig aber nicht optimal, weil die Zielfunktion noch negative Koeffizienten hat. Und darüber hinaus kann man die Aufgabe hier schon beenden, weil es gar keine optimale Lösung gibt (alle Elemente des Spaltenvektors von x2 sind kleiner oder gleich null)

Ist das richtig?

16.07.2008, 12:06

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von luisa_86
So langsam kommt Licht ins Dunkeln. Eine Frage vorweg. Also x4, x5 und x3 sind doch diese sogenannten Basisvariablen richtig? Und x1 und x2 die Nichtbasisvariablen?

Ja, richtig.

Zitat:

Also die Lösung habe ich glaube ich auch verstanden wie du darauf kommst. Bei der Basislösungen müssen die Nichbasisvariablen ja Null sein und nur die Basisvariablen dürfen Koeffizienten >0 haben richtig?

Also wäre hier:

x1=0
x2=0
x3=6
x4=10
x5=4

das deckt sich ja mit deiner Antwort. Nur warum weiß ich das ich für die Basislösung x1, x2 und x3 nehmen muss und nicht wie ich erst dachte meine Basisvariablen (wenn das so ist) x3, x4 und x5. Oder nimmt man dafür die Variablen die keine Schlupfvariablen sind? Also für die Verkürzte Form halt, weil bei der langen ist ja ohnehin jede Variable drin.

Du hattest recht, Basislösung ist $\begin{eqnarray*} \chi_B = (x_3, x_4, x_5) = (6, 10, 4) \end{eqnarray*}$ (ich hab es weiter oben korrigiert). Bei den Basisvariablen bilden die Koeffizienten Einheitsvektoren.
Bei Angabe der vollständigen Basislösung stellt sich das Problem, die richtigen Komponenten herauszusuchen (bzw. zu überlegen, welche Komponenten es sind), dann nicht mehr.

Zitat:

So das sollte erstmal reichen :-) Wie ich rauskriege ob die Basislösung optimal ist versuche ich noch mal selber rauszukriegen.

Es reicht ein Blick in die Kriteriumszeile (das ist die z-Zeile hier). Wenn ich einmal davon ausgehe, dass du hier ein Maximum-Problem bearbeitest (am Besten gibst du das noch irgendwo an, ob Max./Min.), hast du noch ein negatives Element in der Kriteriumszeile. Für den nächsten Simplex-Schritt hast du damit die aufzunehmende Nichtbasisvariable ( $\begin{eqnarray*} x_2 \end{eqnarray*}$ ).

Fraglich ist, ob es eine zu eliminierende Basisvariable gibt, da in der fraglichen Zeile nur negative Zahlen und die Null stehen (-> Zulässigkeitskriterium und Nichtnegativitätsbedingungen). Insgesamt kannst du den Spezialfall einer unbeschränkten Lösungsmenge erkennen ( $\begin{eqnarray*} x_2 \end{eqnarray*}$ kann beliebig groß werden).

Zitat:

Die Basislösung ist ist zwar zulässig aber nicht optimal, weil die Zielfunktion noch negative Koeffizienten hat. Und darüber hinaus kann man die Aufgabe hier schon beenden, weil es gar keine optimale Lösung gibt (alle Elemente des Spaltenvektors von x2 sind kleiner oder gleich null)

Korrekt, nur statt Zielfunktion spreche ich von Kriteriumszeile.

Bei einem Minimumproblem müsstest du entsprechend andersrum überlegen.

Grüße Abakus smile

16.07.2008, 12:24

lusia_86

Auf diesen Beitrag antworten »

Danke dir

Also ursprünglich ist das eine Maximierungsaufgabe und die Zielfunktion hieß:

$\begin{eqnarray*} z=-x_1+x_2 \end{eqnarray*}$

Die soll wie gesagt maximiert werden. Wir sollen aber alle Aufgaben immer in eine Minimierungsaufgabe umwandeln. Also habe ich die Zielfunktion mit (-1) durchmultipliziert und dann hat man ja eine neue Zielfunktion die minimiert werden muss, damit die ursprüngliche maximiert wird.

(Das es um ein Minimum geht habe ich mit dem Minus vor dem z deutlich machen wollen)

Also dann versuche ich noch einmal das Ergebnis zu erklären:

Also das Ergebnis ist doch dann in dem Fall, das es keine optimale Lösung gibt, das Lineare Problem ist also nicht lösbar. Und zwar weil es ein Element gibt in der Kriteriumzeile das <0 ist und die darüber liegenden Elemente sind < 0 oder = 0.

Korrekt?

16.07.2008, 17:38

Abakus

Auf diesen Beitrag antworten »

OK, einverstanden. Bei der Begründung würde ich schreiben, dass die Lösungsmenge der Restriktionen unbeschränkt ist (um das von dem Fall einer leeren Lösungsmenge abzugrenzen) und die Zielfunktion beliebig große Werte annehmen kann.

Grüße Abakus smile

Neue Frage »

Antworten »

Linare Optimierung - Basislösung

Verwandte Themen