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: 122
  Themenstart: 2021-09-08 17:23

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: 3893
Wohnort: Raun
  Beitrag No.1, eingetragen 2021-09-11 07:44

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: 122
  Beitrag No.2, vom Themenstarter, eingetragen 2021-09-11 12:29

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: 1638
Wohnort: Chile, Ulm
  Beitrag No.3, eingetragen 2021-09-11 13:12

\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: 122
  Beitrag No.4, vom Themenstarter, eingetragen 2021-09-11 13:22

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: 1638
Wohnort: Chile, Ulm
  Beitrag No.5, eingetragen 2021-09-11 14:02

\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: 122
  Beitrag No.6, vom Themenstarter, eingetragen 2021-09-13 03:00

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: 1638
Wohnort: Chile, Ulm
  Beitrag No.7, eingetragen 2021-09-15 00:02

@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: 122
  Beitrag No.8, vom Themenstarter, eingetragen 2021-09-18 01:31

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: 1638
Wohnort: Chile, Ulm
  Beitrag No.9, eingetragen 2021-09-18 14:48

\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: 122
  Beitrag No.10, vom Themenstarter, eingetragen 2021-09-18 16:24

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: 1638
Wohnort: Chile, Ulm
  Beitrag No.11, eingetragen 2021-09-18 16:48

\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: 122
  Beitrag No.12, vom Themenstarter, eingetragen 2021-09-18 17:19

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: 1638
Wohnort: Chile, Ulm
  Beitrag No.13, eingetragen 2021-09-18 18:11

@ 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: 122
  Beitrag No.14, vom Themenstarter, eingetragen 2021-09-18 18:16

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: 122
  Beitrag No.15, vom Themenstarter, eingetragen 2021-09-21 03:20

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