Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Simplexverfahren
Autor
Universität/Hochschule Simplexverfahren
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 231
  Themenstart: 2021-09-08

Hallo zusammen, ich habe eine Frage zur Optimierung. Ich habe ein lineares Optimierungsproblem durch das Simplexverfahren gelöst. Ich habe jetzt eine Frage und zwar wieso ist die Lösung optimal, wenn c_i<=0 ? https://www.matheplanet.com/matheplanet/nuke/html/uploads/b/54010_Unbenrtkke_gktannt.PNG Danke im Voraus für die Antwort! :)


   Profil
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 3936
Wohnort: Raun
  Beitrag No.1, eingetragen 2021-09-11

Hallo s-amalgh, schreibe das Tableau wieder um in ein Ungleichungssystem, so, als ob es das Anfangstableau wäre. Dann ist direkt zu sehen, dass sich bei positiven c_i das bisherige Optimum noch verbessern lässt. Viele Grüße, Stefan


   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 231
  Beitrag No.2, vom Themenstarter, eingetragen 2021-09-11

Danke erstmal für deine Antwort. Ja ist klar aber ich muss beweisen dass diese Lösung ( wenn c_i<=0) optimal ist


   Profil
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1665
Wohnort: Chile, Ulm
  Beitrag No.3, eingetragen 2021-09-11

\quoteon(2021-09-11 07:44 - StefanVogel in Beitrag No. 1) Schreibe das Tableau wieder um in ein Ungleichungssystem, so, als ob es das Anfangstableau wäre. Dann ist direkt zu sehen, dass sich bei positiven c_i das bisherige Optimum noch verbessern lässt. \quoteoff Das stimmt falls die Basislösung nicht entartet ist. Aber dass sich das bisherige Optimum bei *nichtpositivem* c_i *nicht* verbessern lässt, das stimmt wirklich immer. 😄


   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 231
  Beitrag No.4, vom Themenstarter, eingetragen 2021-09-11

Hi @Goswin Weißt du wie ich beweisen kann dass die Lösung optimal ist?


   Profil
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1665
Wohnort: Chile, Ulm
  Beitrag No.5, eingetragen 2021-09-11

\quoteon(2021-09-11 13:22 - s-amalgh in Beitrag No. 4) Weißt du wie ich beweisen kann dass die Lösung optimal ist? \quoteoff Hast du das Tableau bereits in ein Ungleichungssystem umgeschrieben? Wie so ein Ungleichungssystem aussieht, siehst du in Wikipedia:Pivotverfahren.


   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 231
  Beitrag No.6, vom Themenstarter, eingetragen 2021-09-13

Das ist die Aufgabe und die komplette Lösung. Weil die Werte in der Zielfunktionszeile negativ sind, ist die Lösung optimal. Ich verstehe aber nicht wieso die Lösung allgemein optimal ist wenn die Werte in der Zielfunktionszeile negativ sind. Ich hätte der Beweis davon. 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önnte mir jemand bitte dabei unbedingt helfen? ich habe eine Prüfung in ein paare Tage und ich werde zu 100% diese Frage gefragt. Danke im Voraus! https://www.matheplanet.com/matheplanet/nuke/html/uploads/b/54010_Unbendfvdffdvssvannt.PNG https://www.matheplanet.com/matheplanet/nuke/html/uploads/b/54010_Unbenaljerkhflreliehwknnt.PNG


   Profil
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1665
Wohnort: Chile, Ulm
  Beitrag No.7, eingetragen 2021-09-15

@s-amalgh: (1) Warum du deine Variablen erst \(x_k\) und dann \(y_k\) nennst (oder wer immer das war), das ist mir schleierhaft, aber so etwas tut man in der Mathematik nicht ohne triftigen Grund. Ich bleibe jetzt konsequenterweise bei \(x_k\).   Und das Optimum kann unmöglich \(-3\) und damit \(<0\) sein; deine "komplette Lösung" ist also irgendwo falsch. (2) Wir haben dir wiederholt gesagt, wie man die Optimalität beweist, und du fragst immer wieder neu. Zum dritten Mal: * Schreibe das optimale Tableau als Ungleichungssystem hin * Weißt du nicht wie man das macht? Kennst du den Sinn so eines Tableaus, weißt du überhaupt, was die Zahlen darstellen? Dein Startsystem besteht aus 4 Gleichungen und 5 Ungleichungen \[ ~~z = 0 + 1\,x_1 + 1\,x_2\\ x_3 = 4 - 1\,x_1 - 2\,x_2\\ x_4 = 3 - 2\,x_1 + 1\,x_2\\ x_5 = 1 - 0\,x_1 - 1\,x_2\\[1ex] x_1\ge0,x_2\ge0,x_3\ge0,x_4\ge0,x_5\ge0\\ \quad\max~z \] Wichtig sind hier die 4 Gleichungen. Im Optimaltableau wurde das obige Gleichungssystem nach den Variablen \(z,x_3,x_1,x_2\) aufgelöst. Das musst du auch tun, gerade so wie es in der Schule gemacht wird!


   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 231
  Beitrag No.8, vom Themenstarter, eingetragen 2021-09-18

Was sind die Eckpunkte in meinem Beispiel? - x1=0 und x2=0 - x1=3/2 und x2=0 - x1=2 und x2=1 sie? wenn je, gibt es noch andere? Meine Idee : Ich glaube ich könnte das auch so beweisen dass ich die Eckpunkte in die Zielfunktion einsetze und dann kommt die optimale Lösung raus oder? z = 1 * 0 + 1 * 0 = 0 z = 1 * 1,5 + 1 * 0 = 1,5 z = 1 * 2 + 1 * 1 = 3 --> Maximum! (Also die Lösung ist optimal für x1=2 und x2=1 ) Stimmt meine Idee oder nicht? wenn ja, könntest du mir bitte sagen ob es noch Werte gibt die ich in die Zielfunktion einsetzen soll? Danke im Voraus! :)


   Profil
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1665
Wohnort: Chile, Ulm
  Beitrag No.9, eingetragen 2021-09-18

\quoteon(2021-09-18 01:31 - s-amalgh in Beitrag No. 8) Sind [folgende Punkte] Eckpunkte in meinem Beispiel? - x1=0 und x2=0 - x1=3/2 und x2=0 - x1=2 und x2=1 Wenn ja, gibt es noch andere? \quoteoff Ja, das sind Eckpunkte. Es gibt sehr wahrscheinlich noch andere Eckpunkte, aber ich habe keine Lust danach zu suchen. \quoteon(2021-09-18 01:31 - s-amalgh in Beitrag No. 8) Ich glaube ich könnte das auch so beweisen dass ich die Eckpunkte in die Zielfunktion einsetze und [das Maximum ist] dann die optimale Lösung. Stimmt meine Idee oder nicht? \quoteoff Nein, deine Idee taugt nicht. Selbst wenn du alle Eckpunkte findest die es gibt und sie einsetzt, ist der größte Wert den du erhältst nicht unbedingt ein Optimum: es könnte ja noch andere Punkte geben, die keine Eckpunkte sind und ein größeres \(z\) liefern.


   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 231
  Beitrag No.10, vom Themenstarter, eingetragen 2021-09-18

Ich habe noch eine Frage und zwar wenn wir ein Hilfsproblem lösen müssen, 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? Danke im Voraus!


   Profil
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1665
Wohnort: Chile, Ulm
  Beitrag No.11, eingetragen 2021-09-18

\quoteon(2021-09-18 16:24 - s-amalgh in Beitrag No. 10) Ich habe noch eine Frage und zwar wenn wir ein Hilfsproblem lösen müssen, hat das immer eine Lösung? \quoteoff Es gibt vielerlei Hilfsprobleme, welches meinst du? Eine Antwort hängt sehr davon ab. \quoteon(2021-09-18 16:24 - s-amalgh in Beitrag No. 10) Und warum hat das Ursprungsproblem keinen zulässigen Punkt, wenn der optimale Wert der Hilfszielfunktion größer als 0 ist? \quoteoff Ob das stimmt, hängt vom Hilfsproblem ab, und ich weiß nicht, welches Hilfsproblem du meinst. Und falls es stimmt, kann man es sicher "beweisen", was dir anscheinend etwas schwer fällt. * Wenn du verschiedene Fragen hast, stelle sie künftig bitte in verschiedene Themenstränge *


   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 231
  Beitrag No.12, vom Themenstarter, eingetragen 2021-09-18

Das ist ein Beispiel https://www.matheplanet.com/matheplanet/nuke/html/uploads/b/54010_Unbenakldjgiogtrpoiwgunnt.PNG https://www.matheplanet.com/matheplanet/nuke/html/uploads/b/54010_Unbrt_gjrhporieh_otpienannt.PNG


   Profil
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1665
Wohnort: Chile, Ulm
  Beitrag No.13, eingetragen 2021-09-18

@ s-amalgh: mit dieser neuen Frage weiter in 'Simplexverfahren: Hilfsfunktion'


   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 231
  Beitrag No.14, vom Themenstarter, eingetragen 2021-09-18

Hab gemacht https://www.matheplanet.com/matheplanet/nuke/html/viewtopic.php?topic=255522&start=0&lps=1856006#v1856006


   Profil
s-amalgh
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.12.2020
Mitteilungen: 231
  Beitrag No.15, vom Themenstarter, eingetragen 2021-09-21

Hallo @Goswin Ich habe das von einem Student bekommen der die Prüfung schon gemacht hat. Der Prüfer will für die Frage (wieso ist die Lösung jetzt optimal wenn alle Zielfunktionskoeffizienten negativ sind) das hören: (siehe Bild) 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! :-) https://www.matheplanet.com/matheplanet/nuke/html/uploads/b/54010_241356571_547661726445109_2434732014440887003_n.jpg


   Profil
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 3936
Wohnort: Raun
  Beitrag No.16, eingetragen 2021-10-02

\quoteon(2021-09-13 03:00 - s-amalgh in Beitrag No. 6) 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. \quoteoff Zuerst hat mich die Formulierung auch verunsichert. Doch das geht so zu lösen und man braucht dafür keine Eigenschaften des Simplexverfahrens oder eines anderen Lösungsverfahrens kennen und anwenden. Man kann alles schon aus dem vorliegenden Ungleichungssystem ablesen. Behauptung: Wenn man das Tableau im Themenstart in ein Ungleichungssystem umschreibt, dann hat die Lösungsmenge des Ungleichungssystems in der Komponente z das Maximum -3 (oder Minimum, je nachdem wie das Tableau aufgestellt werden muss). Beweis: 1. Das Maximum z=-3 wird angenommen für die Lösung \((y_1,y_2,y_3,y_4,y_5,z)=(2,1,0,0,0,-3)\) 2. Das Maximum z=-3 kann nicht größer sein wegen den Bedingungen \(y_4\ge0\) und \(y_5\ge0\). Das ist das, was zu beweisen war. Mein Denkfehler war zu glauben, dass das Maximum nur ein lokales Maximum ist, welches bei einem anderen Lösungsschritt möglicherweise noch überboten werden kann. Doch die Umformungsschritte sind alles Äquivalenzumformungen, bei denen sich die Lösungsmenge nicht verändert. Jedes Ungleichungssystem aus jedem Umformungsschritt ist für alle anderen Umformungsschritte auch gültig. Deshalb ist das gefundene Maximum bereits das globale Maximum. Deinen vorhergehenden Beitrag No.15 habe ich gerade erst gesehen und den muss ich selber erst noch verstehen. Mein Beweis wäre danach nicht ausreichend und ich möchte auch gerne wissen, warum mein Beweis nicht ausreicht. Dass man zusätzlich noch Umformungen des Ungleichunssystems angeben muss, das ist schon nicht verkehrt, dass man die auch versteht, aber sind die wirklich für den Beweis nötig?


   Profil
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 3936
Wohnort: Raun
  Beitrag No.17, eingetragen 2021-10-11

\quoteon(2021-09-21 03:20 - s-amalgh in Beitrag No. 15) ...(siehe Bild) Ich verstehe das aber nicht so gut besonders Nicht-Basiszielfunktionswerts (c_N^T*x_N) und dem Basiszielfunktionswerts (c_B^T*x_B) \quoteoff Ich gehe von folgendem Ungleichungssystem aus: \(\begin{array}{rcl} z & = & c^\mathrm{T} x \\ A x & = & b\\ x & \ge & 0.\end{array}\) \(A\) ist eine gegebene Matrix aus m Zeilen und n Spalten. \(A\) soll schon Rang m haben. \(b \ge 0\) und c sind gegebene Spaltenvektoren der Länge m und n. \(x\) (als Spaltenvektor der Länge n) und Variable \(z\) sind gesucht. Weil die Zeilenzahl und der Rang von A beide gleich m sind, muss es m Spalten von A geben, die als separate Matrix zusammengefasst eine invertierbare Matrix ergeben. Eine beliebige solche Matrix wähle ich aus und bezeichne sie mit \(A_B\). Die übrigen Spalten fasse ich zusammen zur Matrix \(A_N\). Entsprechend dieser Aufteilung zerlege ich \(x\) in einen Vektor \(x_B\) der Länge m und in einen Vektor \(x_N\) der Länge n-m, so dass ich schreiben kann \(A x = A_B x_B + A_N x_N\). Das setze ich in die Gleichung \(A x = b\) ein und erhalte \(A_B x_B + A_N x_N = b\) Weil \(A_B\) invertierbar ist, kann ich diese Gleichung von links mit \(A_B^{-1}\) multiplizieren und erhalte \(x_B + A_B^{-1} A_N x_N = A_B^{-1} b\). Das stelle ich nach \(x_B\) um, \(x_B = \color{blue}{A_B^{-1} b - A_B^{-1} A_N x_N}\). Weiter mit der Gleichung \(z = c^\mathrm{T} x\): Wegen der Aufteilung von \(x\) in \(x_B\) und \(x_N\) zerlege ich auch \(c\) in einen Spaltenvektor \(c_B\) der Länge m und in einen Spaltenvektor \(c_N\) der Länge n-m und kann dann schreiben \(c^\mathrm{T} x = c_B^\mathrm{T} x_B + c_N^\mathrm{T} x_N\). Darin setze ich die zu \(x_B\) gefundene Gleichung ein und fasse die Vorfaktoren von \(x_N\) zusammen, \(c^\mathrm{T} x = c_B^\mathrm{T} x_B + c_N^\mathrm{T} x_N\), \(c^\mathrm{T} x = c_B^\mathrm{T} \left(\color{blue}{A_B^{-1} b - A_B^{-1} A_N x_N}\right) + c_N^\mathrm{T} x_N\), \(c^\mathrm{T} x = c_B^\mathrm{T} A_B^{-1} b + \left(c_N^\mathrm{T}- c_B^\mathrm{T} A_B^{-1} A_N\right) x_N\). Das ist jetzt die Gleichung (4.7) aus dem Bild, nur die Variablen sind dort etwas anders bezeichnet.


   Profil
s-amalgh hat die Antworten auf ihre/seine Frage gesehen.
s-amalgh wird per Mail über neue Antworten informiert.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]