Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Simplexverfahren: Hilfsfunktion
Autor
Universität/Hochschule Simplexverfahren: Hilfsfunktion
s-amalgh
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 16.12.2020
Mitteilungen: 122
  Themenstart: 2021-09-18

Hallo zusammen, Ich habe 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? Eine 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 Danke im Voraus!


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

@ s-amalgh: Obwohl ich mich mit dem Simplexverfahren gut auskenne und schon lange damit arbeite, kann ich dir leider nicht weiterhelfen, weil ich deine Tableaus einfach nicht verstehe. Die zweite Zeile des Tableaus soll deine Hilfszielfunktion darstellen, aber ich weiß nicht, welche Funktion damit gemeint ist. Ein Tableau ist eine Datenstruktur für Computer, wo die Koeffizienten der Funktionen und der Gleichungen ohne die Variablennamen gespeichert sind. Solange du diese Funktionen und Gleichungen nicht wie üblich mit Variablen und plus-minus-Zeichen hinschreiben kannst, wirst du mit diesen Tableaus wohl schwerlich etwas anfangen können --- ich habe es versucht und kann kann die Zahlen im Tableau nicht mit der Aufgabestellung in Einklang bringen. Frag doch am besten deinen Dozenten, deinen Übungsleiter, oder von wem immer du diesen Lösungsansatz her hast!


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2674
  Beitrag No.2, eingetragen 2021-09-18

\quoteon(2021-09-18 20:33 - Goswin in Beitrag No. 1) Die zweite Zeile des Tableaus soll deine Hilfszielfunktion darstellen, aber ich weiß nicht, welche Funktion damit gemeint ist. \quoteoff Die Hilfszielfunktion ist die Funktion, die in der ersten Phase des Zwei-Phasen-Simplex-Verfahrens minimiert wird. Das Vorgehen im Startbeitrag entspricht dem Vorgehen hier auf den Seiten 29 und 30 (es werden lediglich ein paar Spalten im Tableau nicht hingeschrieben). Im Startbeitrag sind die Nebenbedingungen, für die künstliche Variablen einzuführen sind,$$ 3=x_1+x_2-y_1+\tilde y_1 \;,\quad 2=x_2-y_2+\tilde y_2 $$und für die zu minimierende Hilfszielfunktion $\tilde y_1+\tilde y_2$ ergibt sich$$ \def\T #1*{\color{red}{#1}\,} \T5*=\T1*x_1+\T2*x_2\T-1*y_1\T-1*y_2+ \color{blue}{\tilde y_1}+\color{blue}{\tilde y_2} \;. $$Die rot markierten Koeffizienten entsprechen der Hilfszielfunktions-Zeile im Startbeitrag. \quoteon(2021-09-18 18:15 - s-amalgh im Themenstart) warum hat das Ursprungsproblem keinen zulässigen Punkt, wenn der optimale Wert der Hilfszielfunktion größer als 0 ist? \quoteoff Die künstlichen Variablen $\tilde y_i\ge0$ sind genau so definiert, dass man für $\tilde 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 $\sum_i\tilde y_i$ das Minimum 0.


   Profil
s-amalgh
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 16.12.2020
Mitteilungen: 122
  Beitrag No.3, vom Themenstarter, eingetragen 2021-09-19

Wie kann ich allgemein wissen dass die ursprünglichen Nebenbedingungen eine zulässige Lösung haben oder noch nicht?


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2674
  Beitrag No.4, eingetragen 2021-09-19

\quoteon(2021-09-19 00:16 - s-amalgh in Beitrag No. 3) Wie kann ich allgemein wissen dass die ursprünglichen Nebenbedingungen eine zulässige Lösung haben oder noch nicht? \quoteoff Das kann man den Nebenbedingungen nicht ohne weiteres ansehen. Aber dieses Ergebnis liefert dir ja die Phase 1.


   Profil
s-amalgh
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 16.12.2020
Mitteilungen: 122
  Beitrag No.5, vom Themenstarter, eingetragen 2021-09-19

Und wieso wenn der Hilfszielfunktionswert 0 ist und nicht anders?


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2674
  Beitrag No.6, eingetragen 2021-09-19

\quoteon(2021-09-19 01:13 - s-amalgh in Beitrag No. 5) Und wieso wenn der Hilfszielfunktionswert 0 ist und nicht anders? \quoteoff Das hatte ich doch oben schon geschrieben: \quoteon(2021-09-18 23:57 - zippy in Beitrag No. 2) Die künstlichen Variablen $\tilde y_i\ge0$ sind genau so definiert, dass man für $\tilde 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 $\sum_i\tilde y_i$ das Minimum 0. \quoteoff Wenn die ursprünglichen Nebenbedingungen eine zulässige Lösung haben, ist das Minimum 0 (denn $<0$ kann das Minimum nicht werden, weil die $\tilde y_i\ge0$ sind). Wenn das Minimum $>0$ ist, können die ursprünglichen Nebenbedingungen folglich keine zulässige Lösung haben.


   Profil
s-amalgh
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 16.12.2020
Mitteilungen: 122
  Beitrag No.7, vom Themenstarter, eingetragen 2021-09-19

Das ist jetzt klar dankeschön! :)) Ich habe noch eine kleine Frage : Ist (0,0,...,0) immer eine zulässige Anfangslösung ? und wie können wir eine bestimmen ? (zum Beispiel wenn man negative rechte Seiten hat) Danke im Voraus!


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2674
  Beitrag No.8, eingetragen 2021-09-19

\quoteon(2021-09-19 01:40 - s-amalgh in Beitrag No. 7) Ist (0,0,...,0) immer eine zulässige Anfangslösung ? und wie können wir eine bestimmen ? \quoteoff Dass man keine zulässige Anfangslösung erhält, wenn man alle Variablen auf 0 setzt, zeigt ja schon das Beispiel in dem oben verlinkten Skript. Man kommt aber zu einer zulässige Anfangslösung, indem man die $\tilde y_i$ groß genug wählt. Wie sich negative Vorzeichen auf der rechten Seite auf die künstlichen Variablen auswirken, kannst du z.B. hier und hier nachlesen. (Beachte die teilweise abweichenden Vorzeichenkonventionen für die $\tilde y_i$.)


   Profil
s-amalgh
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 16.12.2020
Mitteilungen: 122
  Beitrag No.9, vom Themenstarter, eingetragen 2021-09-19

- Die Anfangslösung ist in unserem Beispiel (0,0,0,0,3,3,3,2), Richtig? - Wie zeigt das Beispiel, dass man keine zulässige Anfangslösung erhält, wenn man alle Variablen auf 0 setzt?


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2674
  Beitrag No.10, eingetragen 2021-09-19

\quoteon(2021-09-19 19:43 - s-amalgh in Beitrag No. 9) Wie zeigt das Beispiel, dass man keine zulässige Anfangslösung erhält, wenn man alle Variablen auf 0 setzt? \quoteoff Die erste Nebenbedingung lautet (mit den Bezeichnungen des Skripts, also $z_1$ = Schlupfvariable, $y_1$ = künstliche Variable)$$ x_1+x_2-z_1+y_1=1 \;. $$Wenn man hier $x_1=x_2=0$ setzt, muss (wegen $z_1\ge0$) die künstliche Variable $y_1\ge1$ sein. Das meinte ich mit: \quoteon(2021-09-19 11:41 - zippy in Beitrag No. 8) Man kommt aber zu einer zulässige Anfangslösung, indem man die $\tilde y_i$ groß genug wählt. \quoteoff


   Profil
s-amalgh
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 16.12.2020
Mitteilungen: 122
  Beitrag No.11, vom Themenstarter, eingetragen 2021-09-19

Also wie ich verstanden habe: (0,0,...,0) ist keine zulässige Anfangslösung weil die künstliche Variable größer 0 sein soll Habe ich richtig verstanden?


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2674
  Beitrag No.12, eingetragen 2021-09-19

\quoteon(2021-09-19 20:47 - s-amalgh in Beitrag No. 11) weil die künstliche Variable größer 0 sein soll \quoteoff Sie soll nicht $>0$ sein, sie muss es sein (und sogar $\ge1$), damit für $x_1=x_2=0$ und $z_1\ge0$ die Gleichung $x_1+x_2-z_1+y_1=1$ erfüllt sein kann.


   Profil
s-amalgh
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 16.12.2020
Mitteilungen: 122
  Beitrag No.13, vom Themenstarter, eingetragen 2021-09-19

Aber wie meinst du damit dass die Gleichung erfüllt sein soll? Wenn wir jetzt x1=x2=0 einsetzten dann haben wir: −z1+y1=1 Wieso kann die Gleichung erfüllt sein nur wenn die y1>=1 ? Ich verstehe nicht


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2674
  Beitrag No.14, eingetragen 2021-09-19

\quoteon(2021-09-19 22:00 - s-amalgh in Beitrag No. 13) −z1+y1=1 Wieso kann die Gleichung erfüllt sein nur wenn die y1>=1 ? Ich verstehe nicht \quoteoff Versuch doch doch mal eine Lösung hinzuschreiben, bei der nicht $y_1\ge1$ ist. Vergiss dabei aber nicht: \quoteon(2021-09-19 20:10 - zippy in Beitrag No. 10) Wenn man hier $x_1=x_2=0$ setzt, muss (wegen $\color{red}{z_1\ge0}$) die künstliche Variable $y_1\ge1$ sein. \quoteoff


   Profil
s-amalgh
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 16.12.2020
Mitteilungen: 122
  Beitrag No.15, vom Themenstarter, eingetragen 2021-09-20

also wenn ich in der Prüfung gefragt wurde: wieso erhält man keine zulässige Anfangslösung, wenn man alle Variablen auf 0 setzt? sage ich : weil (wegen z1≥0) die künstliche Variable y1≥1 sein muss, und man kommt zu einer zulässige Anfangslösung, indem man die y~i groß genug wählt. stimmt so? fehlt was wichtiges zu sagen?


   Profil
s-amalgh
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 16.12.2020
Mitteilungen: 122
  Beitrag No.16, vom Themenstarter, eingetragen 2021-09-21

Hey @zippy Ich habe eine Frage und zwar wenn wir ein Optimierungsproblem mit der negativen rechten Seite haben, Was ist die Idee (min y~)? und warum fügt man zusätzliche Schlupfvariablen? https://www.matheplanet.com/matheplanet/nuke/html/uploads/b/54010_Unbentrhlthlrannt.PNG Ich wäre sehr dankbar wenn du mir dabei helfen könntest da ich am Donnerstag Prüfung habe und diese Frage in den Altklausuren gefunden habe..


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2674
  Beitrag No.17, eingetragen 2021-09-21

1. Du hast eine Nebenbedingung $Ax\le b$ mit $b<0$. 2. Mit der Schlupfvariablen $y\ge0$ kann man das als Gleichung $Ax+y=b$ schreiben. 3. Für $x=0$ gibt es keine zulässige Lösung (da die linke Seite $\ge0$ und die rechte $<0$ ist), also führt man künstliche Variablen $\tilde y\ge0$ ein und kommt zu dem Hilfsproblem $Ax+y-\tilde y=b$. 4. Wenn man hierfür eine zulässige Lösung mit $\tilde y=0$ findet, hat man eine zulässige Lösung des ursprünglichen Problems. Wegen $\tilde y\ge0$ ist $\tilde y=0$ äquivalent zu $\sum_{i=1}^k\tilde y_i=0$. Außerdem ist $\sum_{i=1}^k\tilde y_i\ge0$. Also geht es darum, $\sum_{i=1}^k\tilde y_i$ unter der Nebenbedingung $Ax+y-\tilde y=b$ zu minimieren.


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

\quoteon(2021-09-21 08:20 - s-amalgh in Beitrag No. 16) Was ist die Idee (min y~)? [...] Ich habe diese Frage in den Altklausuren gefunden. \quoteoff Es gibt sehr viele verschiedene Arten so ein Hilfproblem zu definieren, und der Professor von dieser Altklausur macht es einfach anders als deiner. Wenn du von einem dieser Hilfsprobleme wirklich verstehst warum es funktioniert, dann verstehst du die meisten der anderen auch. [Die Antwort wurde nach Beitrag No.16 begonnen.]


   Profil
s-amalgh
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 16.12.2020
Mitteilungen: 122
  Beitrag No.19, vom Themenstarter, eingetragen 2021-09-22

Danke für deine tolle Erklärung! :) @zippy Ich habe eine letzte Frage (Dann bin ich bereit für die Prüfung morgen :D). Nachdem ich ein lineares Optimierungsproblem gelöst habe, sieht man im letzten Tableau dass die Lösung jetzt optimal ist. Wie kann ich beweisen dass die Lösung optimal ist wenn alle Zielfunktionskoeffizienten kleiner gleich 0 also c_i<=0 sind? Ich habe das von einem Student bekommen der die Prüfung schon gemacht hat. Der Prüfer will hören : https://www.matheplanet.com/matheplanet/nuke/html/uploads/b/54010_241356571_547661726445109_2434732014440887003_n.jpg 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 klar machen und vielleicht auf mein Beispiel oben anwenden oder so? Danke im Voraus! :-)


   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]