Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Simplex: Zweiphasen nötig? Quotient mit Null
Autor
Universität/Hochschule Simplex: Zweiphasen nötig? Quotient mit Null
Ritter
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.06.2009
Mitteilungen: 631
Wohnort: Dunkler Ort
  Themenstart: 2022-01-11 15:11

Hallo Ich habe zwei Fragen zum Simplexverfahren: a) Wenn man eine "größergleich"-Nebenbedingung mit positiver rechter Seite hat, nimmt man dann automatisch das Zweiphasenverfahren? b) Um die Pivotzeile zu ermitteln nimmt man ja die Zeile, in der der Quotient ab kleinsten ist. Dabei ignoriert man die Quotienten, bei denen man durch etwas negatives oder durch 0 teilen müsste. --> Wie ist das, wenn man aber im Zähler die Null hat. Dann hat man hier ja automatisch den kleinsten Quotienten. Meine Antworten wären a) ja und b) 0 im Zähler wird berücksichtigt (sofern der Nenner positiv ist). Bei a hat mich verwirrt, dass in der mir bekannten Einführung zum Zweiphasenmodell in einem konkreten Beispiel mit drei Nebenbedingungen im Starttableau nur ein Einheitsvektor war (da zwei der Nebenbedingung "größergleich" waren) und dies als Begründung für das Zweiphasenmodell angegeben wurde. Ein konkretes Beispiel, bei der mir die Fragen aufgefallen sind. Hier habe ich drei Nebenbedingungen, aber auch drei Einheitsvektoren. Das wäre also noch kein Widerspruch. Allerdings habe ich eine künstliche Variable, so dass ich trotzdem die Zweiphasenmethode anwenden würde. Zu maximieren ist die Funktion Z(a,b,c) = 50a + 70b + 75c unter folgenden Nebenbedingungen: 5a+7b+8c <= 2400 8a+7b+10c <= 3000 c >= 50 a,b,c >= 0 In Gleichungen umgeformt: 5a+7b+8c + y_1 = 2400 8a+7b+10c + y_2 = 3000 c - y_3 + z = 50 mit y_1, y_2, y_3, z >= 0 $ Erste Phase (z entfernen)\\ \begin{tabular}{c|ccccccc|crr} & a & b & c & y1 & y2 & y3 & z & b & Quotient & Rechnung\\ & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & & -III \\ & 0 & 0 & -1& 0 & 0 & 1 & 0 & -50 & & + III\\ \hline I & 5 & 7 & 8 & 1 & 0 & 0 & 0 & 2400 & 2400:8=300 & -8 III\\ II & 8 & 7 & 10 & 0 & 1 & 0 & 0 & 3000 & 3000:10=300 & +10 III\\ III & 0 & 0 & 1 & 0 & 0 & -1& 1 & 50 & 50:1=50 & bleibt\\ \end{tabular} \begin{tabular}{c|ccccccc|crr} & a & b & c & y1 & y2 & y3 & z & b & Quotient & Rechnung\\ & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & & \\ \hline I & 5 & 7 & 0 & 1 & 0 & 8 & -8 & 2000 & & \\ II & 8 & 7 & 0 & 0 & 1 & 10 & -10 & 2500 & & \\ III & 0 & 0 & 1 & 0 & 0 & -1& 1 & 50 & & \\ \end{tabular} Zweite Phase, c, y1 und y2 müssen zu Beginn entfernt werden (also nur noch c)\\ \begin{tabular}{c|cccccc|crr} & a & b & c & y1 & y2 & y3 & b & Quotient & Rechnung\\ & -50 & -70 & -75 & 0 & 0 & 0 & 0 & & +75 III\\ & -50 &0 -70 & 0 & 0 & 0 & -75 & 3750 && +7,5 II\\ \hline I & 5 & 7 & 0 & 1 & 0 & 8 & 2000 & 2000:8=250 & -0,8 II \\ II & 8 & 7 & 0 & 0 & 1 & 10 & 2500 & 2500:10=250 & :10 \\ III & 0 & 0 & 1 & 0 & 0 & -1 & 50 & 50:(-1) egal & +0,1 II \\ \end{tabular} Man hätte auch Zeile I als Pivotzeile nehmen können. \begin{tabular}{c|cccccc|crr} & a & b & c & y1 & y2 & y3 & b & Quotient & Rechnung\\ & 10 & -17,5 & 0 & 0 & 7,5 & 0 & 22500 & & +12,5 I\\ \hline I & -1,4 & 1,4 & 0 & 1 & -0,8 & 0 & 0 & 0:1,4=0 & :1,4 \\ II & 0,8 & 0,7 & 0 & 0 & 0,1 & 1 & 250 & 250:0,7=357 & -0,5 I \\ III & 0,8 & 0,7 & 1 & 0 & 0,1 & 0 & 300 & 300:0,7=43 & -0,5 I \\ \end{tabular} \begin{tabular}{c|cccccc|crr} & a & b & c & y1 & y2 & y3 & b & Quotient & Rechnung\\ & -7,5 & 0 & 0 & 12,5 & -2,5 & 0 & 22500 & & +5 II\\ \hline I & -1 & 1 & 0 & 5/7 & -4/7 & 0 & 0 & 0:(-1) egal & +2/3 II \\ II & 3/2 & 0 & 0 & -1/2 & 1/2 & 1 & 250 & 250:3/2=167 & :1,5 \\ III & 3/2 & 0 & 1 & -1/2 & 1/2 & 0 & 300 & 300:3/2=200 & -II \\ \end{tabular} \begin{tabular}{c|cccccc|crr} & a & b & c & y1 & y2 & y3 & b & Quotient & Rechnung\\ & 0 & 0 & 0 & 10 & 0 & 0 & 23750 & & \\ \hline I & 0 & 1 & 0 & 8/21 & -5/21 & 2/3 & 500/3 & & \\ II & 1 & 0 & 0 & -1/3 & 1/3 & 2/3 & 500/3 & & \\ III & 0 & 0 & 1 & 0 & 0 & -1 & 50 & & \\ \end{tabular} Die optimale Lösung ist also a=b=500/3 und c=50, maximaler Funktoinswert 23750. $ Was mich auch etwas irritiert hat war, dass der Funktionswert im vorletzten Schritt konstant geblieben ist. Was im Prinzip auch logisch ist, da in beiden Fällen a=b=0 und c =50 galt. Gruß Ritter


   Profil
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1681
Wohnort: Chile, Ulm
  Beitrag No.1, eingetragen 2022-01-13 01:25

\quoteon(2022-01-11 15:11 - Ritter im Themenstart) a) Wenn man eine "größergleich"-Nebenbedingung mit positiver rechter Seite hat, nimmt man dann automatisch das Zweiphasenverfahren? \quoteoff Du meinst vermutlich das primale Simplexverfahren bei: "...ausschließlich nichtnegativen rechten Seiten..." Und die Antwort auf die Frage hängt dann wohl davon ab, wer "man" ist. Ich würde es nicht tun, denn es ist völlig überflüssig. (Wenn nur einige der rechten Seiten nichtnegativ sind, dann brauchst du natürlich eine erste Phase) \quoteon(2022-01-11 15:11 - Ritter im Themenstart) b) Um die Pivotzeile zu ermitteln nimmt man ja die Zeile, in der der Quotient ab kleinsten ist. Dabei ignoriert man die Quotienten, bei denen man durch etwas negatives oder durch 0 teilen müsste. --> Wie ist das, wenn man aber im Zähler die Null hat. Dann hat man hier ja automatisch den kleinsten Quotienten. \quoteoff Wenn (in Phase_1) der konstante Wert Null ist, dann ist dieser nichtnegativ und die entsprechende Zeile kommt entsprechend den Pivotierregeln als Pivotzeile überhaupt nicht in Betracht.


   Profil
Ritter
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.06.2009
Mitteilungen: 631
Wohnort: Dunkler Ort
  Beitrag No.2, vom Themenstarter, eingetragen 2022-01-14 17:21

Hallo Goswin, \quoteon(2022-01-13 01:25 - Goswin in Beitrag No. 1) Du meinst vermutlich das primale Simplexverfahren bei: "...ausschließlich nichtnegativen rechten Seiten..." Und die Antwort auf die Frage hängt dann wohl davon ab, wer "man" ist. Ich würde es nicht tun, denn es ist völlig überflüssig. (Wenn nur einige der rechten Seiten nichtnegativ sind, dann brauchst du natürlich eine erste Phase) \quoteoff Deine letzte Formulierung meinte ich. Wenn man nämlich nur solche Nebenbedingungen I: 4x_1 + 3x_2 >= 50 II: 5x_1 + 7x_2 >= 52 hätte, dann wäre die zulässige Menge ja nach oben unbeschränkt und es gibt gar keine optimale Lösung \quoteon(2022-01-13 01:25 - Goswin in Beitrag No. 1) Wenn der Zähler Null ist, dann ist die rechte Seite nichtnegativ und die entsprechende Zeile kommt entsprechend den Pivotierregeln als Pivotzeile überhaupt nicht in Betracht. \quoteoff Oh. Bei mir steht, dass ich die Zeile mit dem Minimum von (b_m)/(a_(mn)) mit a_(mn) > 0 wählen soll. Von b_m > 0 steht dort nichts. Allerdings kommt mir deine Variante auch merkwürdig vor bzw. widerspricht völlig meinen Erfahrungen. Wenn ich alle nichtnegativen rechten Seiten ausschließe, dann hat man ja in den Standardaufgaben gar keine Zeile mehr zur Auswahl?? Ein einfacheres Beispiel: $ \text{Maximiere } 5x_1 + 2x_2 \text{ unter}\\ I: 5x_1 + 10x_2 \leq 60\\ II: 4x_1 + 2x_2 \leq 15\\ x_1, x_2 \geq 0\\ \begin{tabular}{c|cccc|c|cr|r} & x_1 & x_2 & y1 & y2 & b & Quotient & Rechnung\\ ZF & -5 & -2 & 0 & 0 & 0 & & +1,25 II\\ \hline I & 5 & 10 & 1 & 0 & 60 & 12 & -1,25 II\\ II & 4 & 2 & 0 & 1 & 15 & 3,75 & :4\\ \end{tabular}\\ \text{Die Pivotspalte ist bei } x_1. \text{ Da aber alle rechten Seiten nichtnegativ sind, gibt es keine Pivotzeile. ???}\\ \text{Nach meinem Wissen muss man die zweite Zeile nehmen.}\\ \begin{tabular}{c|cccc|c|c|r|r} & x_1 & x_2 & y1 & y2 & b & Quotient & Rechnung\\ ZF & 0 & 0,5 & 0 & 1,25 & 18,75 & &\\ \hline I & 0 & 7,5 & 1 & -1,25 & 41,25 & 12 &\\ II & 1 & 0,5 & 0 & 0,25 & 3,75 & 3,75 &\\ \end{tabular}\\ Die optimle Lösung ist also x_1 = 3,75 \text{ und } x_2 = 0 $ Vermutlich habe ich einen Denkfehler?


   Profil
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1681
Wohnort: Chile, Ulm
  Beitrag No.3, eingetragen 2022-01-15 01:02

\quoteon(2022-01-14 17:21 - Ritter in Beitrag No. 2) Ein einfacheres Beispiel: $ \text{Maximiere } 5x_1 + 2x_2 \text{ unter}\\ I: 5x_1 + 10x_2 \leq 60\\ II: 4x_1 + 2x_2 \leq 15\\ x_1, x_2 \geq 0\\ \begin{tabular}{c|cccc|c|cr|r} & x_1 & x_2 & y1 & y2 & b & Quotient & Rechnung\\ ZF & -5 & -2 & 0 & 0 & 0 & & +1,25 II\\ \hline I & 5 & 10 & 1 & 0 & 60 & 12 & -1,25 II\\ II & 4 & 2 & 0 & 1 & 15 & 3,75 & :4\\ \end{tabular}\\ \text{Die Pivotspalte ist bei } x_1.\\ \text{Nach meinem Wissen muss man die zweite Zeile nehmen.}\\ \begin{tabular}{c|cccc|c|c|r|r} & x_1 & x_2 & y1 & y2 & b & Quotient & Rechnung\\ ZF & 0 & 0,5 & 0 & 1,25 & 18,75 & &\\ \hline I & 0 & 7,5 & 1 & -1,25 & 41,25 & 12 &\\ II & 1 & 0,5 & 0 & 0,25 & 3,75 & 3,75 &\\ \end{tabular}\\ Die optimle Lösung ist also x_1 = 3,75 \text{ und } x_2 = 0 $ Vermutlich habe ich einen Denkfehler? \quoteoff Was du sagst ist alles richtig. Meine obige Aussage bezog sich auf eine Phase_1, die es bei dieser verqeinfachten Aufgabe ja nicht gibt (wobei mir die Phase_1 offenbar anders als dir beigebracht wurde) Wenn in Phase_2 einige der Zähler Null sind, dann ist eine dieser Zeilen natürlich die Pivotzeile. In so einem Fall ist freilich die Zielsetzung gefährdet 😉, weil das Simplexverfahren ohne zusätzliche Maßnahmen in einen unendlichen Kreislauf geraten kann.


   Profil
Ritter
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.06.2009
Mitteilungen: 631
Wohnort: Dunkler Ort
  Beitrag No.4, vom Themenstarter, eingetragen 2022-01-17 12:16

Ok, danke! Ja, ich kenne es so, dass es beim Erzeugen des Einheitsvektors in den beiden Phasen im Prinzip keinen Unterschied gibt, zumindest nicht in Hinblick auf die Quotienten. Phase 1: - Künstliche Variablen aus Hilfszielfunktionszeile (minimiere z, also maximiere -z) durch Zeilenoperationen entfernen - Mit dieser neuen Hilfszielfunktion mit den gewohnten Regeln so lange das Simplexverfahren anwenden, bis alle künstlichen Variablen den Wert 0 haben (falls möglich). Übergang: - Man verwendet in dem erhaltenen Tableau nun die eigentliche Zielfunktion. - Die momentanen Basisvariablen werden durch Zeilenoperationen aus der Zielfunktionszeile entfernt. Phase 2: - Normal mit gleicher Regel für die Pivotzeile wie in Phase 1. \quoteon(2022-01-15 01:02 - Goswin in Beitrag No. 3) Wenn in Phase_2 einige der Zähler Null sind, dann ist eine dieser Zeilen natürlich die Pivotzeile. In so einem Fall ist freilich die Zielsetzung gefährdet 😉, weil das Simplexverfahren ohne zusätzliche Maßnahmen in einen unendlichen Kreislauf geraten kann. \quoteoff Kennst du dafür ein (einfaches) Beispiel?


   Profil
Ritter hat die Antworten auf ihre/seine Frage gesehen.

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