wieso ist die Lösung optimal, wenn c_i <=0?

Question

wieso ist die Lösung optimal, wenn c_i <=0?

2 Antworten

Beste Antwort

Hallo,

das Restriktions-Ungleichungssystem wurde durch eine nichtnegative, additive Schlupfvariable je Ungleichung (y₃,y₄,y₅) in ein äquivalentes lineares Gleichungssystem überführt .

Jetzt soll der Zielfunktionswert z , unter Einhaltung der Restriktionen, maximiert werden.

Eine erste zulässige Basislösung wäre z.B. :

y₁ = 0 , y₂ = 0 , y₃ = 4 , y₄ = 3, y₅ = 1 .

Diese Lösung ergibt den Zielfunktionswert z = 0.

z = 1y₁ + 1y₂ = 1 * 0 + 1 * 0 = 0

Dies ist aber noch nicht die optimale Lösung, denn wenn z.B. y₁ oder y₂ vergrößert wird, vergrößert sich auch z.

Gem. "deinem" 2. kondensierten Simplextableau lautet die Zielfunktion:

z - 1,5 = - 0,5y₄ +1,5y₂ → z = 1,5 - 0,5y₄ + 1,5y₂

Auch das ist nicht die optimale Lösung, denn wird y₂ vergrößert, steigt auch z an, wird stattdessen y₄ vergrößert, nimmt z ab. Das ist offensichtlich durch die unterschiedlichen Vorzeichen.

Gem. "deinem" 3. kondensierten Simplextableau lautet die Zielfunktion:

z - 3 = - 0,5y₄ - 1,5y₅ → z = 3 - 0,5y₄ - 1,5y₅

In diesem Falle würde eine Vergrößerung von y₄oder y₅ aber z verringern. Folglich ist y₁ = 2 und y₂ = 1 (y₃=y₄=y₅=0) die optimale Lösung : z = y₁ + y₂ = 1 + 2 = 3

Das ist ja auch logisch, weil y3, y4, und y5 die Schlupfvariblen sind, d.h. ökonomisch nicht ausgenutzte Kapazitäten.

Und in diesem Beispiel gibt es keine unausgenutzten Kapazitäten, weil y₃= y₄ = y₅ = 0.

Beantwortet 13 Sep 2021 von Enano

Ist eine Lösung optimal wenn der Fall vorkommt dass die Nichtbasisvariablen vergrößert werden aber z abnimmt ? oder wie?

Es wurde ja bereits geschrieben, dass eine optimale Lösung gefunden wurde, wenn alle Koeffizienten der Zielfunktion negativ (bei Start mit positiven Koeffizienten) bzw. positiv (bei Start mit negativen Koeffizienten) sind.

Im Ausgangstableau sind die Schlupfvariablen die BV und die Problemvariablen die NBV. Wenn aber z.B. bereits das Ausgangstableau die Optimallösung darstellt, würde z abnehmen, wenn eine der NBV zur BV gemacht werden würde.

Ich habe das im Internet gefunden :

Wo hast du das denn gefunden? Ist denn kein Beispiel dabei?

ich glaube dass das der Beweis ist

Wenn das alles sein sollte, ist es für mich eher verwirrend, aber kein Beweis.

aber ich verstehe die Schritte nicht so gut.

Welche Schritte? Ich sehe nur einen mehr oder weniger unverständlichen Text.

Kommentiert 14 Sep 2021 von Enano

“Wenn aber z.B. bereits das Ausgangstableau die Optimallösung darstellt, würde z abnehmen, wenn eine der NBV zur BV gemacht werden würde.” Ich habe das nicht so gut verstanden was du meinst. Könntest du mir bitte das klarer machen?

“Ist denn kein Beispiel dabei?”

Eigentlich habe ich das von meinen Altklausuren ( die Prüfung ist mündlich ) : nachdem die Aufgabe dann gelöst ist (rechnen musst du da nicht viel, nur die Pivotelemente auswählen) will er bestimmt, dass du ihm dann beweist, warum die Lösung jetzt optimal ist. Dafür stellst du einfach die Zielfunktion mit nicht-eingetzten Werten auf und dann setzt du danach alle Werte ein und argumentierst, warum für (positive!) x, dasjenige x, was jetzt das optimierungsproblem löst gerade den kleinsten zielfkt.-wert liefert (sieht man schnell mit den Nullen und so)

Ich habe nicht so gut verstanden was er meinte und wie ich das beweise.

Kommentiert 14 Sep 2021 von elena_12

Könntest du mir bitte das klarer machen?

Ich wollte damit nur sagen, dass deine Aussage, wann eine Lösung optimal ist, suboptimal ist (NBV vergrößern) und du es besser so formulierst, wie es bereits geschrieben wurde und ich es wiederholt habe.

Bei deinem Beispiel kam man zur optimalen Lösung, indem die NBV y₁ gegen die BV y₄ und die NBV y₂ gegen die BV y₅ getauscht wurde. Wenn du aber ein Simplextableau präsentiert bekommst, was schon die optimale Lösung darstellt, würde ein Variablentausch den Zielfunktionswert verringern, d.h. y₄ und y₅ bleiben BV und y₁ und y₂ NBV.

Dafür stellst du einfach die Zielfunktion mit nicht-eingetzten Werten auf

Also z.B.: z = x₁+ x₂ → Max.

und dann setzt du danach alle Werte ein

Da x₁ = 2 und x₂ = 1 also:

z = 1 * 2 + 1 * 1 = 3

und argumentierst, warum für (positive!) x, dasjenige x, was jetzt das optimierungsproblem löst gerade den kleinsten zielfkt.-wert liefert (sieht man schnell mit den Nullen und so)

Entweder ist "kleinsten" ein Tipp- oder Übermittlungsfehler oder es handelte sich im Gegensatz zu deinem Beispiel nicht um ein Maximum-Problem, sondern ein Minimum-Problem. Ansonsten müsste es doch "größten" heißen.

Um bei deinem Beispiel zu bleiben, könntest du jetzt andere Werte für x₁ und x₂ einsetzen, um zu "beweisen", dass 2 und 1 das größte z ergeben:

z = 1 * 0 + 1 * 0 = 0 oder

z = 1 * 1,5 + 1 * 0 = 1,5 oder

z = 1 * 0 + 1 * 1 = 1 oder

z = 1 * 1 + 1 * 1 = 2

usw. mit allen Wertepaaren, die die Restriktionen erfüllen.

Übrigens, ich ziehe es vor die Entscheidungs- oder Problemvariable immer mit x und die Schlupfvariable immer mit y zu bezeichnen.

Ihr scheint euch da nicht so sicher zu sein und abwechselnd x oder y für beide Variablen zu wählen.

Viel Erfolg!

Kommentiert 15 Sep 2021 von Enano

Was sind alle Wertepaaren in meinem Beispiel?

Wenn du die Aufgabe grafisch löst, erhältst du im 1. Quadranten ein Trapez, dessen Seiten durch die Restriktionsgeraden (2. u. 3. Restriktion) und die Koordinatenachsen gebildet wird. Als erlaubte Punktmengenkombinationen kommen alle Punkte infrage, die innerhalb und auf dem Rand / den Seiten des Trapezes liegen. Das ist der zulässige Bereich und alle in diesem Bereich liegenden Punkte sind zulässige Lösungen des LO-Problems.
Erlaubt wären z.B. der Punkt (1 ; 0,5) und der auf dem oberen Rand liegende Punkt (1 ; 1). Nicht erlaubt z.B. der Punkt (1 ; 2 ), weil er außerhalb dieses Bereiches liegt, d.h. Restriktion x₂ ≤ 1 wird nicht erfüllt
Wenn die Lösung nicht ganzzahlig sein muss, sind das unendlich viele Wertepaare.
Weil sich die optimale Lösung aber in einer Ecke (Schnittpunkt zweier Restriktionsgeraden) des zulässigen Bereichs befindet, kommen bei deinem Beispiel nur die Punkte (0 ; 0), (1,5 ; 0), (2 ; 1) und (0 ; 1) infrage.

Ich glaube die sind : ... - x1=0 und x2=3/2

Umgekehrt wäre es richtig, denn x₂= 3/2 erfüllt nicht die
NB "x₂ ≤ 1".

Gibts noch andere?

Ja, x₁ = 0, x₂ = 1 .

Kommentiert 15 Sep 2021 von Enano

Kann ich die Wertepaaren wissen nur in dem ich die Aufgabe grafisch löse?

Ja, das wären dann die Koordinaten der vier Eckpunkte des zulässigen Bereichs.

Aber die grafische Lösung hat ihre Grenzen. Bei nur 2 Problemvariablen, wie hier, lässt sich die optimale Lösung problemlos grafisch ermitteln, bei 3 Problemvariablen ist die grafische Methode wegen der dreidimensionalen Darstellung nicht so handlich und bei 4 und mehr Problemvariablen nicht möglich.

Das problem ist dass ich nicht noch nicht verstanden habe wie ich das Problem grafisch lösen kann..

Dazu gibt es aber zahlreiche Erklärungen, einschließlich Videos im Netz, u.a. dieses:
https://studyflix.de/mathematik/lineare-optimierung-318

In dem zweiten Tableau sind x1=0 und x2=3/2

Ich weiß jetzt nicht welches Tableau du meinst, aber in dem 2. kondensierten Tableau unter deinem Beispiel steht doch in der 2. Spalte 3/2 neben y_1.

Wenn ich die Wertepaaren vom Tableau wissen könnte, würde ich jetzt nicht verstehen wieso x1 = 0, x2 = 1

Aus den Tableaus können nicht immer alle Koordinaten der Eckpunkte abgelesen werden, weil beim Simplexverfahren mehr oder weniger schnell, je nach Pivotspalten-Auswahl, die optimale Lösung gefunden wird.

Bei deinem Beispiel zeigt bereits das 3. Tableau die optimale Lösung an, folglich sind auch keine weiteren Schritte erforderlich, die dir aber gezeigt hätten, dass (0;1) ebenfalls eine zulässsige Lösung ist.

Kommentiert 15 Sep 2021 von Enano

Alles klar danke! :)

Ich habe noch ein paar Fragen aus den Altklausuren. Einige konnte ich nicht und einige habe ich beantwortet aber mir ist nicht sicher ob ich richtig beantwortet habe. Ich schreibe erst was in den Altklausuren steht: Bei mir ging es los mit der Frage, was ein lineares Optimierungsproblem ist. Danach musste ich sagen, ob es immer eine Lösung hat und verschiedene Fälle aufzeichnen (also jeweils ein kleines Beispielbild zu beschränkt, unbeschränkt und kein zulässiger Punkt).
Dann sollte ich das Simplexverfahren erklären, einmal an einer der Zeichnungen und danach dann was man im Tableau macht.
Dann hat er gefragt, ob (0,0,...,0) immer eine zulässige Anfangslösung ist und wie wir eine bestimmen können (zum Beispiel wenn man negative rechte Seiten hat)
Danach hatte er eine Beispielaufgabe dabei, mit einer negativen rechten Seite, bei der ich jeweils die Pivotelemente bestimmen musste (er hat ein Programm, welches die Rechnungen dann automatisch durchführt, du musst also nur die Pivots bestimmen und nicht noch das Tableau ausrechnen). Dann hat er gefragt, wann wir dort fertig sind und warum wir eine optimale Lösung gefunden haben, wenn alle Zielfunktionskoeffizienten negativ sind.
Dann hat er gefragt, wenn wir ein Hilfsproblem lösen müssen, ob das immer eine Lösung hat und warum das Ursprungsproblem keinen zulässigen Punkt hat, wenn der optimale Wert der Hilfszielfunktion größer als 0 ist.
Danach sind wir zum dualen Problem übergegangen, da musste ich eine primale Aufgabe in das duale Problem umschreiben. Danach hat er nach dem schwachen Dualitätssatz und dem Beweis dazu gefragt (aber ohne Kegel) und dann musste ich noch die Komplementaritätsbedingungen aufschreiben.
Als letztes hat er mich noch zum Transportproblem befragt, das sollte ich aufschreiben und dann hat er noch gefragt, ob man das auch mit dem normalen Simplexverfahren berechnen könnte.

Danach musste ich sagen, ob es immer eine Lösung hat und verschiedene Fälle aufzeichnen (also jeweils ein kleines Beispielbild zu beschränkt, unbeschränkt und kein zulässiger Punkt)

- LP hat nicht immer eine Lösung. Die Lösung ist unbeschränkt wenn es unendliche Lösung gibt. Wie z.B. wenn alle Werte in der Pivotspalte negativ sind (Ich weiß es nicht ob ich das so begründen soll..)

- Die Lösung ist beschränkt wenn es eine Lösung gibt oder? In unserem Beispiel oben ist die Lösung unbeschränkt weil wir eine optimale Lösung gefunden haben, richtig?

- wann hat die Lösung kein zulässiger Punkt?

Dann hat er gefragt, ob (0,0,...,0) immer eine zulässige Anfangslösung ist und wie wir eine bestimmen können (zum Beispiel wenn man negative rechte Seiten hat)

Das habe ich nicht verstanden. Könntest du mir bitte das erklären und ein Beispiel geben?

Dann hat er gefragt, wann wir dort fertig sind und warum wir eine optimale Lösung gefunden haben, wenn alle Zielfunktionskoeffizienten negativ sind.

Da sollte ich so machen wie wir oben gemacht haben oder

Dann hat er gefragt, wenn wir ein Hilfsproblem lösen müssen, ob das immer eine Lösung hat und warum das Ursprungsproblem keinen zulässigen Punkt hat, wenn der optimale Wert der Hilfszielfunktion größer als 0 ist.

Hat das immer eine Lösung? und warum hat das Ursprungsproblem keinen zulässigen Punkt, wenn der optimale Wert der Hilfszielfunktion größer als 0 ist?

Als letztes hat er mich noch zum Transportproblem befragt, das sollte ich aufschreiben und dann hat er noch gefragt, ob man das auch mit dem normalen Simplexverfahren berechnen könnte.

Kann man das mit dem normalen Simplexverfahren berechnen?

Ich wäre wirklich sehr dankbar wenn du mir dabei helfen könntest, da meine Prüfung nächste Woche stattfindet und diese Fragen immer rankommen und ich muss sie irgendwie verstehen..

Danke im Voraus! :)

Kommentiert 16 Sep 2021 von elena_12

Hallo Elena,

Ich weiß es nicht ob du meine Nachricht schon gesehen

Ja, ich habe sie gerade gelesen.

... das mir nicht kostenlos erklären möchtest, ...

Das ist für mich keine Frage des Geldes, sondern inwieweit der Fragende bereit ist, mitzuarbeiten. Ich helfe dir gerne kostenlos weiter, soweit ich kann, aber erst, nachdem du dich bemüht hast, selbst Antworten z.B. in deinen Unterlagen, im Netz oder bei deinen Kommilitonen zu finden.

Deine Frage z.B. nach der grafischen Lösung zeigt mir, dass du dich noch nicht ausreichend bemüht hast, weil es dazu zahlreiche Erklärungen und sogar Videos gibt, die schnell gefunden werden können.

Auch z.B. zu den möglichen Lösungen eines LO-Problems oder die Transport-Problem-Frage habe ich auf Anhieb etwas im Netz gefunden:

https://www.mathebibel.de/lineare-optimierung

Das sollte doch auch dir gelingen.

Also versuche doch erst einmal selbst Antworten z.B. bei den von mir genannten Quellen zu finden. Falls dann noch Fragen übrig bleiben, bin ich gerne bereit, sofern ich dazu in der Lage bin, sie kostenlos zu beantworten.

Kommentiert 18 Sep 2021 von Enano

Danke für deine Antwort und für den Link das hat mir geholfen :)

Ich versuche mit den Fragen nochmal:

„Danach musste ich sagen, ob es immer eine Lösung hat und verschiedene Fälle aufzeichnen (also jeweils ein kleines Beispielbild zu beschränkt, unbeschränkt und kein zulässiger Punkt)“

Grafisch habe ich die Fälle schon verstanden.

Ich versuche aber jetzt ohne Grafik.

- Die Lösung ist beschränkt wenn das LP mindestens eine Optimallösung besitzt

- Die Lösung hat keinen zulässigen Punkt wenn es keine Lösung gibt, die alle Ungleichungen erfüllt.

- Die Lösung ist unbeschränkt wenn die Zielfunktion parallel zu einer Restriktion ist ( das habe ich nur grafisch so gut verstanden, könntest du mir bitte das klarer machen?:) )

„Dann hat er gefragt, wenn wir ein Hilfsproblem lösen müssen, ob das immer eine Lösung hat und warum das Ursprungsproblem keinen zulässigen Punkt hat, wenn der optimale Wert der Hilfszielfunktion größer als 0 ist.“

Das Hilfsproblem hat eine Lösung nur wenn z=0 .

Die künstlichen Variablen y~i≥0 sind genau so definiert, dass man für y~i=0 wieder die ursprünglichen Nebenbedingungen erhält. Wenn also die ursprünglichen Nebenbedingungen eine zulässige Lösung haben, hat die Hilfszielfunktion ∑y~i das Minimum 0 ( Ich weiß es nicht ob diese Antwort genug ist )

„Als letztes hat er mich noch zum Transportproblem befragt, das sollte ich aufschreiben und dann hat er noch gefragt, ob man das auch mit dem normalen Simplexverfahren berechnen könnte.“

Ja kann man und man kann auch die Netzwerk-Simplexmethode verwenden.

„Dann hat er gefragt, ob (0,0,...,0) immer eine zulässige Anfangslösung ist und wie wir eine bestimmen können (zum Beispiel wenn man negative rechte Seiten hat)“

Dafür habe ich gar keine Ahnung…

Könntest du mir bitte sagen wenn ich irgendwas falsch verstanden habe und dabei helfen die Fragen, die ich nicht konnte, zu beantworten ?

Danke im Voraus! :)

Kommentiert 19 Sep 2021 von elena_12

Die Lösung ist unbeschränkt wenn die Zielfunktion parallel zu einer Restriktion ist ( das habe ich nur grafisch so gut verstanden, könntest du mir bitte das klarer machen?:) )

Wo hast du das genau so gelesen?

Ist die Zielfunktion parallel zu einer Restriktion, handelt es sich um eine mehrdeutige optimale Lösung.

Wenn der zulässige Bereich nicht begrenzt ist, liegt eine unbeschränkte Lösung vor:

z.B.

z = x₁ + x₂ → Max.

NB: -x₁ + x₂ ≤ 3 , -x₁ + 2 x₂ ≤ 9, x₁,x₂ ≥ 0

Du hast hier einen zulässigen Bereich, der grafisch gesehen, nach "Nordosten" oder "rechts oben" unbegrenzt ist, so dass die Zielfunktionsgerade beliebig weit in diese Richtung verschoben werden kann, d.h. die Zielfunktion kann beliebig große Werte annehmen. Das wird auch klar wegen des negativen Vorzeichens von x₁. Beim Simplexverfahren sind in der entsprechenden Tableauspalte die Werte negativ.

Siehe auch:

https://www.matopt.de/lineare-optimierung/unbeschraenkte-loesung.html

Kommentiert 19 Sep 2021 von Enano

- Unbeschränkt bedeutet dass es viele unendliche Lösungen gibt oder?

Du meinst wohl "unendlich viele". ;-)

Ja, das kannst du so sehen. Aber bei dem Sonderfall, den du ansprichst, bei dem die Zielfunktionsgerade parallel zu einer Restriktion verläuft bzw. deckungsgleich ist und bei dem der Raum des Minimal-Problems nach " links unten" durch die grüne Restriktionsgerade begrenzt ist , habe ich diesen Begriff noch nicht gelesen, sondern "mehrdeutige optimale Lösung".

Wann ist der zulässiger Bereich begrenzt und unbegrenzt

Das siehst du doch an der Grafik. Bei meinem Maximal-Problem-Beispiel ist der zulässige Bereich nach "rechts oben" offen, wird also dort nicht durch eine Restriktionsgerade begrenzt, so dass die Zielfunktionswerte beliebig groß werden können. In diesem Falle spricht man von einer unbeschränkten Lösung des LO-Problems.

Woher weißt du dass das andere Beispiel unendlich viele (optimale) Lösungen hat?

Da wo die Zielfunktionsgerade bei Parallelverschiebung mit der Restriktionsgeraden zur Deckung kommt, findest du die die optimalen Lösungen. Und weil sich auf der entsprechenden Restriktionsgeradenstrecke (die Strecke, die sich zwischen den Schnittpunkten der Restriktionsgeraden mit den Koordinatenachsen ergibt), unendlich viele Punkte befinden, gibt es auch unendich viele optimale Lösungen und natürlich auch unendlich viele zulässige Lösungen.

Kommentiert 19 Sep 2021 von Enano

Wann ist das LP unbeschränkt?

Wenn es z.B. unendlich viele zulässige Lösungen gibt mit beliebig hohen Zielfunktionswerten.

Siehe mein Beispiel.

Und dann zeichne ich das

Ja.

und sage: Da ist unbegrenzt (rot markiert) deswegen gibt es unendich viele optimale Lösungen.

Nein, das solltest du so nicht sagen, sondern:

"Der zulässige Bereich ist nach "rechts" bzw. "rechts oben" unbegrenzt, so dass die Zielfunktion beliebig große Werte annehmen kann."

Eine optimale zulässige Lösung erhältst du, wenn der Zielfunktionswert bei einem Maximal-Problem maximal ist. Aber in diesem Beispiel wird er beliebig größer, da die Zielfunktionsgerade immer weiter in Richtung wachsender z-Werte verschoben werden kann.

Unendlich viele optimale Lösungen hast du bei dem anderen Minimal-Problem-Beispiel, bei dem die Zielfunktionsgerade zur Deckung mit der Restriktionsgeraden kommt.

Ist der zulässiger Bereich der ich rot markiert habe oder das

Nein, weder noch. Der zulässige Bereich ist nach "oben" durch die beiden Restriktionsgeraden, nach "links" durch die x₂-Achse und nach "unten" durch die x₁-Achse begrenzt. Die obere Grenze ist bis zum Schnittpunkt der Restriktionsgeraden deine Restriktionsgerade I und danach deine Restriktionsgerade II . Wenn du den zulässigen Bereich z.B. nach rechts durch eine weitere Restriktion x₁≤ 8 schließen würdest, wäre der zulässige Bereich ein Fünfeck.

Kommentiert 20 Sep 2021 von Enano

Sind die Fünfeck die ich mit blau markiert habe?

Nein, die oberste Ecke, die du blau markiert hast (lks. neben der I) ist nicht Teil des 5-Ecks welches ich gemeint habe, sondern selbstverständlich der Ursprung, also Punkt (0;0).

Und der mit grün markiert ist der zulässiger Bereich oder?

Ja, so ist es bei dem abgewandelten Beispiel.

Stimmt das? wenn ja, wie sieht dann die Grafik aus?

Ja, das stimmt. Wenn es z.B. Restriktionen vom Typ " ≥ " als auch " ≤ " gibt, kann es vorkommen, dass der zulässige Bereich leer ist, d.h. kein Punkt erfüllt alle Restriktionen.Es gibt keine zulässige Lösung und somit natürlich auch keine optimale Lösung.

Z.B.: 6x₁ + 4x₂ ≥ 60, x₁ + x₂ ≤ 7, x₁,x₂ ≥ 0

wie sieht dann die Grafik aus?

Mein Beispiel ist doch so einfach gewählt, dass du du dir das doch schnell mal selbst skizzieren kannst. Wäre doch eine weitere Übung für dich.Vielleicht unterstützt dich aber auch wieder wächter mit einer schönen Grafik.

Kommentiert 21 Sep 2021 von Enano

Ein anderes Problem?

Stell deine Frage

wächter · Answer 1 · 2021-09-10T18:00:29+0000

Abschließend hab ich ein Skript für dieses Verfahren gefunden:

https://www.math.fau.de/wp-content/uploads/2019/04/Barth_la2set.pdf

S.164 ( Es ist übrigens die gleiche Aufgabe)

Das kondensierte Simplex-Tableau basiert auf dem Standard-Verfahren - LGS mit Schlupfvariablen - und führt nur eine kompaktere Schreibweise ein - ohne die Spalten mit den Schlupfvariablen.

Für das Verständnis wäre also die Kenntnis des Standard-Verfahrens ausschlaggebend, weil sich nur die Niederschrift des Simplex ändert und nicht die zu Grunde liegende Theorie.

wieso ist die Lösung optimal, wenn c_i <=0?

2 Antworten

Ähnliche Fragen

Eingabetools:

Beliebte Fragen:

Heiße Lounge-Fragen: