0 Daumen
1,3k Aufrufe

Aufgabe:


Hallo zusammen, ich habe eine Frage zur Optimierung.
Ich habe eine lineare Optimierungsproblem durch das Simplexverfahren gelöst. Ich habe jetzt eine Frage und zwar wieso ist die Lösung optimal, wenn c_i<=0 ?







Unbenrtkkeägktannt.PNG



für die Antwort! :)

Avatar von

Hm,

weiß man beiläufig was c_i<=0 ist oder aussagen soll?

Ich geht mal davon aus, dass die Zielfunktion "oben" steht?

Es gibt gefühlt 1000 Verfahren einen Simplex aufzuschreiben - mit den Angaben kann ich so nix sagen. Komplette Aufgabe!

c_i<=0 ist ja die Zielfunktion

Das ist die komplette Aufgabe :


Unbenannt.PNG



Unbenaljknnt.PNG



Ich wäre wirklich sehr dankbar wenn du mir dabei helfen würdest da ich nächste Woche eine mündliche Prüfung habe und der Prüfer mich sicherlich fragen wird wieso die Lösung optimal ist und ich muss das beweisen

Sorry,

wie ich schon sagte was die Anzahl der Verfahren angeht. Mußt Du hoffen, dass hier jemand genau diesen Pfeil im Köcher hat - ehr net vermute ich...

Musst Du in Deinem Skript studieren wie das "kondensierte" Simplex-Tableau gebacken wird - jedenfalls ohne Schlupfvariablen. Offensichtlich stoppt es, wenn alle Koeffizienten der Zielfunktion negativ sind. Kann man auch umdrehen und mit neg. Koeff starten und stoppen wenn alle positiv sind.

Ja genau also wenn alle Koeffizienten der Zielfunktion negativ sind, stoppt es dann weil die Lösung optimal ist.

Meine Frage ist jetzt: wieso ist die Lösung optimal, wenn alle Koeffizienten der Zielfunktion negativ sind?

Das muss ich nun beweisen

einem simplex tableau liegt ein lgs (bei einführung von schlupfvariablen) zugrunde dazu hab ich hier einen artikel eingestellt, der erklärt, wie dieses verfahren funktioniert.

das wird oben wohl als „übliches“ simplex tableau bezeichnet. man darf auch davon ausgehen, das der mann dann auf ein system von ungleichungen wechselt und das auch erklärt hat.

also, lesen bildet :-)

2 Antworten

0 Daumen
 
Beste Antwort

Hallo,

das Restriktions-Ungleichungssystem wurde durch eine nichtnegative, additive Schlupfvariable je Ungleichung (y3,y4,y5) 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. :

y1 = 0 , y2 = 0 , y3 = 4 , y4 = 3, y5 = 1 .

Diese Lösung ergibt den Zielfunktionswert z = 0.

z = 1y1 + 1y2 = 1 * 0 + 1 * 0 = 0

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

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

z - 1,5 = - 0,5y4 +1,5y2  →  z = 1,5 - 0,5y4 + 1,5y2

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

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

z - 3 = - 0,5y4 - 1,5y5 →  z = 3 - 0,5y4 - 1,5y5

In diesem Falle würde eine Vergrößerung von y4 oder y5 aber z verringern. Folglich ist y1 = 2 und y2 = 1 (y3=y4=y5=0) die optimale Lösung : z = y1 + y2 = 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 y3 = y4 = y5 = 0.

Avatar von

Danke erstmal für deine Antwort.

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

und noch eine Frage : so beweise ich dass eine Lösung optimal ist?

Ich habe das im Internet gefunden : (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).) und ich glaube dass das der Beweis ist aber ich verstehe die Schritte nicht so gut.

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.

“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.

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 y1 gegen die BV y4 und die NBV y2 gegen die BV y5 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. y4 und y5 bleiben BV und y1 und y2 NBV.

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

Also z.B.: z = x1 + x2  →  Max.

und dann setzt du danach alle Werte ein

Da x1 = 2 und x2 = 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 x1 und x2 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!

Danke für deine tolle Erklärung! :)

Ich habe kleine Frage und zwar

Was sind alle Wertepaaren in meinem Beispiel?

Ich glaube die sind :

- x1=0 und x2=0

- x1=0 und x2=3/2

- x1=2 und x2=1

Gibts noch andere?





“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.”


Eigentlich er hat so geschrieben: es gab nach Umformung eine neg. rechte Seite bei mir, also zB Zweiphasenmethode

Aber wie ich weiß das Problem muss als Maximumproblem gelöst werden auch wenn die rechte Seite negativ ist oder?

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 x2 ≤ 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 x2 = 3/2 erfüllt nicht die
NB "x2 ≤ 1".

Gibts noch andere?

Ja, x1 = 0, x2 = 1 .

Nachtrag:

Aber wie ich weiß das Problem muss als Maximumproblem gelöst werden auch wenn die rechte Seite negativ ist oder?

Ja, ein Minimum-Problem kann gelöst werden, in dem es in ein äquivalentes Maximum-Problem transformiert wird.

Kann ich die Wertepaaren wissen nur in dem ich die Aufgabe grafisch löse? Das problem ist dass ich nicht noch nicht verstanden habe wie ich das Problem grafisch lösen kann..



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

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

Ich habe also die Wertepaaren von den Tableau gelesen. Falsch?





“Ja, x1 = 0, x2 = 1 .”

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

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 y1.

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.




Meinst du reicht nicht, um die Optimalität zu zeigen,  nur diese drei Eckpunkte einzusetzen?

 - x1=0 und x2=0

- x1=3/2 und x2=0

- x1=2 und x2=1



besonderes in der Prüfung

Meinst du reicht nicht, um die Optimalität zu zeigen, nur diese drei Eckpunkte einzusetzen?

Ich würde auch die vierte Alternative x1 = 0, x2 = 1 hinzunehmen, denn um zu erkennen, dass dies auch eine zulässige Lösung ist, bedarf es keiner Grafik, sondern kannst du einfach überprüfen, indem du diese Werte in die NB einsetzt :

1 * 0 + 2 * 1 ≤ 4  ✓
2 * 0 - 1 * 1 = ≤ 3 ✓
1 ≤ 1  ✓
0 ≥ 0  ✓
1 ≥ 0 ✓

Und weil unter diesen insgesamt 4 Wertepaaren x1 = 2 und x2 = 1 den größten Zielfunktionswert ergibt, nämlich 3 und es bei dieser Lösung keinen Schlupf gibt (x3 = x4 = x5 = 0), muss dies die optimale Lösung sein.

1 * 2 + 2 * 1 = 4  ✓
2 * 2 - 1 * 1 =  3 ✓
1 = 1  ✓
2 ≥ 0  ✓
1 ≥ 0 ✓

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! :)

Hey @Enano

Ich weiß es nicht ob du meine Nachricht schon gesehen hast oder nicht aber wenn du sie schon gesehen hättest und das mir nicht kostenlos erklären möchtest, könntest du mir bitte dann Nachhilfe für diese Fragen geben?
bitte wie gesagt diese Fragen kommen in der Prüfung immer ran und ich muss ihre Antworte verstehen egal ob kostenlos oder nicht kostenlos
Meine Prüfung ist am Donnerstag
Danke im Voraus für deine Antwort.

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.

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! :)

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 = x1 + x2 →  Max.

NB: -x1 + x2 ≤ 3 , -x1 + 2 x2 ≤ 9, x1,x2 ≥ 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 x1 . Beim Simplexverfahren sind in der entsprechenden Tableauspalte die Werte negativ.

Siehe auch:

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

Wo hast du das genau so gelesen?

Da


Unbenannt.PNG

Text erkannt:

Unendlich viele optimale Lösungen Ist die Zielfunktion parallel zu einer Restriktion, gibt es mehrere Lösungen. Graphisch bedeutet das, dass bei der Parallelverschiebung die Zielfunktion mit dieser Restriktionsgeraden zusammenfällt.

Falsch?


z = x1 + x2 →  Max.

NB: -x1 + x2 ≤ 3 , -x1 + 2 x2 ≤ 9, x1,x2 ≥ 0

Ich habe die Grafik davon gezeichnet


de0a27f8-da2d-41b5-8d91-8f1c97daf509.jpg

Richtig ?

Da

Ich meinte, woher du hast, dass diese Lösung unbeschränkt ist?

Das steht doch da gar nicht.

Falsch?

Nein, was da steht ist richtig.

Nur mein Beispiel behandelt ein Maximal-Problem und das andere ein Minimal-Problem.

Bei meinem Beispiel ist nicht nur der zulässige Bereich unbegrenzt, sondern die Zielfunktion kann auch beliebig große Werte annehmen, sie kann aber bei dem anderen Beispiel nicht beliebig kleine Werte annehmen, obwohl es dort unendlich viele (optimale) Lösungen gibt.

Richtig ?

Ja, deine Grafik ist richtig.

Ich meinte, woher du hast, dass diese Lösung unbeschränkt ist?

Das steht doch da gar nicht.

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

- Wann ist der zulässiger Bereich begrenzt und unbegrenzt


obwohl es dort unendlich viele (optimale) Lösungen gibt.

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

- 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.

Ok also wenn ich in der Prüfung gefragt wurde: Wann ist das LP unbeschränkt?

Was soll ich genau sagen? soll ich sagen :

Das LP ist unbeschränkt, d. h., es gibt unendlich viele zulässige Lösungen wenn der zulässiger Bereich unbegrenzt ist.

Und dann zeichne ich das und sage:

Inkedde0a27f8-da2d-41b5-8d91-8f1c97daf509_LI.jpg

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

Richtig? fehlt was?

Ich bin jetzt verwirrt..

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

db15c04b-657f-48c0-a13a-ad5218dfe40d.jpg

und warum?

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 x2-Achse und nach "unten" durch die x1-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 x1 ≤ 8 schließen würdest, wäre der zulässige Bereich ein Fünfeck.

Ich unterstütze mal die Anschaung mit einem korrekten Graph...

blob.png


Wenn du den zulässigen Bereich z.B. nach rechts durch eine weitere Restriktion x1 ≤ 8 schließen würdest, wäre der zulässige Bereich ein Fünfeck.

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

7f135a04-076d-4df9-970d-c3428d4c44d8.jpg

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

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

Stimmt das? wenn ja, wie sieht dann die Grafik aus? Könntest du mir bitte ein Beispiel geben?

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.: 6x1 + 4x2 ≥ 60, x1 + x2 ≤ 7, x1,x2 ≥ 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.

Alles klar danke für deine tolle Erklärung! :)

Ich habe das von einem Student bekommen der die Prüfung schon gemacht hat (siehe Bild). Der Prüfer will für die Frage (wieso ist die Lösung jetzt optimal wenn alle Zielfunktionskoeffizienten negativ sind) das hören:


Ich verstehe das aber nicht so gut besonders Nicht-Basiszielfunktionswerts (c_N^T*x_N) und dem Basiszielfunktionswerts (c_B^T*x_B)
Könntest du mir bitte das alles mit meinem Beispiel oben klar machen oder so?
Danke im Voraus!

54010_241356571_547661726445109_2434732014440887003_n.jpg

0 Daumen

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.

Avatar von 21 k

Ich muss beweisen dass die Lösung optimal ist wenn die Werte in der Zielfunktionszeile negativ sind. Ich habe das im Internet gefunden : (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).) und ich glaube dass das der Beweis ist aber ich verstehe die Schritte nicht so gut. Könntest du mir bitte dabei unbedingt helfen? ich habe eine Prüfung in ein paare Tage und ich werde zu 100% diese Frage gefragt.

Das steht ziemlich genau in meinem Artikel dazu (mit Schlupfvariablen)

https://www.mathelounge.de/523248/artikel-optimierung-grafischen-rechnerischen-algorithmus

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community