Diskussion:Simplex-Verfahren

Dualer Simplexalgorithmus

Der duale Simplexalgorithmus unterscheidet sich vom primalen Simplexalgorithmus, nur darin, ob die reduzierten Kosten (der Vektor oben im Tableau) und die aktuelle Basislösung (der Vektor rechts im Tableau) gewissen Nichtnegativitätseigenschaften genügen. Ein Tableau heisst primal zulässig, wenn die aktuelle Lösung nicht negativ ist, und dual zulässig, wenn die reduzierten Kosten nicht negativ sind. Optimal ist eine Lösung genau dann, denn sie primal und dual zulässig ist. Geometrisch bedeutet das, dass der primale Algorithmus über Ecken (Schnitt von n unabhängigen Gleichungen) läuft, die zum Polyeder gehören, und der duale Simplexalgorithmus über solche Schnitte läuft, welche ausserhalb liegen. Dazu schreibe ich vieleicht noch etwas konkreteres, wenn ich Zeit finde.

Im ersten Kommentar steht, dass es kein duales Problem gibt. Das ist nicht korrekt. Zu einem linearen Optimierungsproblem erhält man das duale Problem, wenn man die Problemmatrix transponiert, Zielfunktion und rechte Seite vertauscht. Aus vorzeichenbeschränkten Variablen werden Ungleichungen, ansonsten Gleichungen. Aus Ungleichungen werden vorzeichenbeschränkte Variablen, ansonsten nicht Vorzeichenbeschränkte. Das Duale des dualen Problems ist wieder das Primale. Wenn eines der beiden Probleme ein (endliches) Optimum besitzt, dann besitzt auch das andere ein endliches Optimum und die Zielfunktionswerte sind gleich. Ist ein Problem unbeschränkt, dann ist das andere leer. Dann gibt es da noch ein Paar Sachen mit dem sogenannten komplementären Schlupf. Auch das kann ich mal genauer erläutern und ein Beispiel angeben.

Die Definition des dualen Problems scheint davon abzuhängen, wie das ursprüngliche Problem in eine geeignete Standardform gebracht wird. Es ist nicht klar, in welchem tieferen Sinn das eindeutig geschehen soll, zumindest oberflächlich betrachtet gibt es da verschiedene Möglichkeiten, sogar verschiedene Standardformen, siehe zum Beispiel hier. Wenn es aber verschiedene primale Formulierungen gäbe, dann gibt es auch verschiedene duale Probleme zum selben Startproblem. Wann sollen zwei verschiedene Forrmulierungen als wesentlich gleich gelten? --Heinrich Puschmann 13:23, 3. Dez. 2007 (CET)

Hallo Heinrich, da hast Du vollkommen recht. Eigentlich müsste man nicht nur von primalen und dualen Problemen sprechen, sondern von primalen und dualen Formulierungen. Ein lineares Optimierungsproblem lässt sich auf verschiedene Arten als LP schreiben, und dazu gehören jeweils unterschiedliche duale LPs. Allerdings beschreiben sie auch alle dasselbe duale Optimierungsproblem in dem Sinne, dass ihre Lösungen ineinander transformierbar sind. Diese Transformierbarkeit der Lösungen in beide Richtungen ist die Eigenschaft, die ich als Definition für „wesentlich gleich“ nehmen würde (auch im Primalen). -- Sdo 19:36, 3. Dez. 2007 (CET)

Name des Simplex-Verfahrens

"Der Name rührt daher, dass die Gleichungen des Problems ein Simplex beschreiben, dessen Rand zum Auffinden der Lösung beschritten wird." Aber die Gleichungen beschreiben doch i.A. gar kein Simplex, sondern ein Polyeder. Natürlich gibt es diesen Spezialfall, aber es gibt doch überhaupt keinen Grund, warum die Ecken des zulässigen Bereichs affin unabhängig sein sollten. Dann wäre das Problem ja gleich viel einfacher...

Ja, stimmt, danke für den Hinweis. Ich habe das erstmal auskommentiert und werde versuchen herauszufinden, wo der Name genau herkommt. -- Sdo 11:31, 14. Feb 2006 (CET)

Hallo. Bin mir ziemlich sicher, dass bei Danzig zu der geometrischen Interpretation des Simplexverfahrens steht, dass der Schritt, bei dem während der Pivotoperation die neue Basisvariable aus der Zielfunktionszeile entfernt (und damit die anderen relativen Kostenkoeffizienten verändert werden) geometrisch der Aufstellung der Lösungsgraden(im 2dim) oder Lösungsebene (im 3dim)und anschliessendem Einsetzen der Basisvariablen zur Bestimmung der relativen Lage anderer Basislösungen gleichkommt. Dies ist dann geometrisch ein Ndimensionaler Simplex...also im 2dim bilden Lösungsgerade und die jeweilige betrachtete Basislösung ein Dreieck, im 3dim die Lösungsebene und eine jeweilige betrachtete Basislösung ein Tetraeder. Ich könnte mir gut vorstellen, dass der Name daher kommt, dass man in den Einzelschritten des Verfahrens eben diese Ndimensionalen Simplizes überprüft.

Das habe ich zwar gerade nicht genau verstanden, aber ich habe den Satz trotzdem wieder einkommentiert: in Gleichungsform beschreiben die Beschränkungen wirklich einen Simplex. Dass das Problem trotzdem nicht trivial zu lösen ist, liegt vermutlich an der hohen Anzahl der Ecken dieses Simplex. -- Sdo 21:25, 18. Apr 2006 (CEST)

Motivation für den dualen Simplex

(hierher verschoben von Diskussion:Lineare Optimierung)

Welche Gründe gibt es eigentlich, in einem Solver statt des primalen den dualen Simplex zu benutzen? Zunächst entsteht ja durch die Transformation vom primalen zum dualen Problem Mehraufwand. Ist der duale Simplex in bestimmten Fällen schneller oder benötigt er weniger Speicherplatz? M.E. müsste die Anzahl der Nullen in beiden Matrizen gleich groß sein. Oder gibt es andere Gründe, die ich übersehe? Vielen Dank! Signaturnachtrag: Benutzer:145.254.110.41 -- Sdo 23:30, 1. Mär 2006 (CET)

Da gibt es mehrere Gründe. Erstmal muss das Problem nicht transformiert werden, sondern der duale Simplex läuft im selben Tableau ab wie der primale (auch wenn das in richtigen Implementierungen nicht wirklich im Tableau passiert). Gegenüber dem primalen Simplex sind dann Zeilen und Spalten vertauscht, ansonsten läuft im wesentlichen alles gleich ab. Der primale Simplex behält immer eine zulässige Primallösung und versucht, die duale Lösung zulässig zu machen; beim dualen Simplex ist es andersherum. Zum Lösen eines einzelnen LPs ist der duale Simplex in der Praxis oft schneller als der primale. Warum das so ist, weiß ich auch nicht, aber das steht schon auf meiner Liste der rauszukriegenden Dinge. Den größten Vorteil hat der duale Simplex aber im Zusammenhang mit Schnittebenenverfahren oder Branch-and-Bound: dabei wird eine zusätzliche Bedingung ins LP geschrieben oder eine Variablenschranke verändert, so dass die aktuelle Primallösung unzulässig wird, während die Duallösung zulässig bleibt. Mit dem primalen Simplex müsste man jetzt von vorne starten, während man mit dem dualen Simplex meist nur ein paar Schritte von der aktuellen Basis aus machen muss, um wieder zu einer zulässigen Primallösung zu kommen. Ich hoffe, das hilft dir weiter. Gruß, -- Sdo 23:30, 1. Mär 2006 (CET)

Alle angeführten Gründe lassen sich meiner Meinung nach auf einen zurückführen: Innerhalb der Aufgaben, die in der Praxis (nicht in der Theorie) betrachtet werden und gelöst werden müssen, ist es leichter (und manchmal sehr viel leichter) eine dual-zulässige Startbasis zu finden als eine primal-zulässige Startbasis. --Heinrich Puschmann (Diskussion) 13:37, 31. Aug. 2016 (CEST)

Simplex-Programm

Ich möchte hier mal auf ein Programm hinweisen, welches ich gemeinsam mit einigen Kommilitonen programmiert habe. Das Programm ist Open Source und unter http://sourceforge.net/projects/simplizia erhältlich. Das Besondere daran ist, dass es zum Verständnis des Algorithmus beitragen soll indem die Rechenschritte kommentiert werden. Es wird auch jeder Rechenschritt einzeln ausgegeben und außerdem ist der Quellcode durchgängig kommentiert (auch der mathematische Hintergrund wird da erläutert). Da ich daran beteiligt bin, habe ich es nicht als Link aufgeführt, aber ich möchte es hiermit mal zur Diskussion stellen. --80.143.8.209 23:17, 17. Apr. 2007 (CEST)

Formeln 2,3,4 fehlerhaft?

Wenn ich da nachrechne, komme ich auf die Formeln multipliziert mit -1, also

Pivotzeile für j ungleich s:

${\bar {a}}_{rj}:=-{\frac {{\bar {a}}_{rj}}{{\bar {a}}_{rs}}}\qquad (2)$

${\bar {b}}_{r}:=-{\frac {{\bar {b}}_{r}}{{\bar {a}}_{rs}}}\qquad (3)$

Pivotspalte für i ungleich r:

${\bar {a}}_{is}:={\frac {{\bar {a}}_{is}}{{\bar {a}}_{rs}}}\qquad (4)$ 129.13.186.1 20:29, 30. Jul. 2007 (CEST)

Was genau hast Du da nachgerechnet? Warum kommst Du auf die Formeln multipliziert mit (-1)? -- Sdo 23:08, 31. Jul. 2007 (CEST)

---Meiner Meinung nach ist auch Formel 1 (Pivotelement) falsch: das gewählte (Pivot-)Element ist i.d.R. ungleich 1, dh auch der angegebene Bruch; an Stelle der bisherigen Formel würde ich meinen, sollte das ürsprüngliche Pivotelement durch sich selbst geteilt werden, dann würde der Rest, wie in (2) beschrieben, stimmen. mfg

Formel 4 - Änderung / Hinzufügung

Für die Berechnung der reduzierten Kosten in der Pivotspalte fehlte eine Formel. Habe diese hinzugefügt und im weiteren Verlauf des Arktikels darauf verwiesen (in der Beispielrechnung).

Hm, die Formeln sind insgesamt etwas missverständlich formuliert. Jetzt, wo ich mir das gerade genauer angucke, bin ich eigentlich der Meinung, dass in der Pivotspalte nach der Umformung ein Einheitsvektor stehen sollte, was aber im Beispiel nicht der Fall ist. Das muss ich mir aber ein anderes Mal in Ruhe überlegen, nicht mehr um diese Uhrzeit. -- Sdo 23:10, 31. Jul. 2007 (CEST)

Phase I

Imho nicht ganz vollständig, ein LP kann eventuell eine Matrix besitzen, die keine Basis hat, ich kenns so, dass man deshalb in Phase I wenn in der letztend Basis dort eine der Basisvariablen eine künstliche Variable ist deren Wert 0 ist, dass man dann in Abhängigkeit ihres Index eine Matrixzeile streicht (die dann nämlich abhängig von den anderen Zeilen ist) (nicht signierter Beitrag von 84.58.129.7 (Diskussion) )

Du hast insofern nicht ganz unrecht, als dass die vorgestellte Varianten vollen Spaltenrang und mindestens so viele Zeilen wie Spalten voraussetzt; das hatte ich vergessen, hinzuschreiben. Allerdings sind diese Voraussetzungen in (LP1) von Phase I erfüllt, wenn man die Nichtnegativitätsbedingungen als Ungleichungen unten dranschreibt. Die dadurch gebildete Einheitsmatrix dient dann auch gleich als Startbasismatrix. In wirklichen Implementierungen macht man das natürlich anders, aber da kenne ich die Implementierungstricks nicht so genau, und das würde auch den Rahmen des Artikels sprengen. Deshalb habe ich mich in Phase I auf die Lehrbuchvariante beschränkt. Gruß, -- Sdo 23:33, 15. Aug. 2007 (CEST)

Bland's Regel

Ich denke, die Regel von Bland ist nicht korrekt. (Ich habe das Buch von Padberg nicht zur Hand, aber das Beispiel http://glossary.computing.society.informs.org/notes/cycling.pdf zeigt, dass die Regel so nicht richtig ist.)

Die Regel von Bland (oder auch Regel vom kleinsten Index) besagt, dass unter den Spalten mit positiven reduzierten Kosten jene mit kleinsten Index zu wählen ist. Zu dieser Spalte wird unter den möglichen Zeilen für den Tausch jene mit kleinsten Index gewählt. --Elmar

Du hast recht, danke für den Hinweis. Hab's korrigiert. -- Sdo 23:57, 26. Nov. 2007 (CET)

Tableau or not Tableau?

Ist es wirklich leserfreundlich, das Simplex-Verfahren anhand von Tableaus zu beschreiben, oder sollten wir nicht lieber bei der Beschreibung algebraische Gleichungen verwenden (wie bei Chvátal oder hier), und die Tableaus in ein Kapitel rechnerische Umsetzung oder Datenstruktur verschieben? Die beim Simplexverfahren weitverbreitete Vermischung von Algorithmus und Datenstruktur ist geschichtlich gewachsen in einer Zeit, in der man beide Begriffe noch nicht so scharf trennte. Dazu kommt, dass bei algebraischen Gleichungen die Regeln zur Pivotauswahl schneller nachvollziehbar sind. --Heinrich Puschmann 13:45, 3. Dez. 2007 (CET)

Hallo Heinrich, ich gebe Dir recht darin, dass das Tableau auf den ersten Blick nur mittelmäßig leserfreundlich ist. Allerdings weiß ich nicht, ob eine algebraische Darstellung besser ist. Und das Tableau hat den Vorteil, dass man alles daran erklären kann: primalen und dualen Simplex, Basen, Pivotschritte, wo die duale Information während des Verfahrens herkommt, usw. Die Tableaumethode mit rechnerische Umsetzung zu überschreiben, halte ich für gewagt, weil sie doch mehr didaktischen als praktischen Wert hat. Meines Wissens verwendet keine konkurrenzfähige Implementierung des Simplex-Verfahrens direkt die Tableaumethode, sondern bestenfalls Weiterentwicklungen davon, die mit speziellen Datenstrukturen für dünnbesetzten Matrizen arbeiten. Aber die eignen sich leider nicht, um das Verfahren zu erklären. -- Sdo 19:43, 3. Dez. 2007 (CET)

Hallo Sebastian. Die Formeln für die Pivotauswahl sind bei der algebraischen Darstellung ähnlich kompliziert. Die Leserfreundlichkeit zeigt sich meines Erachtens bei den numerischen Beispielen, wo angesichts der verschiedenen Tableauformate leicht Verwechslungen vorkommen. Bei einer algebraischen Darstellung ist auch dem ungeübten Leser unmitterbar klar, ob sich eine Basisvariable vergrößert oder verkleinert, wenn man eine unabhängige Variable vergrößert; bei einem Tableau muss man sich, wenn man die Formeln nicht auswendig lernen möchte oder vergessen hat, genau daran erinnern, wie das Tableau nun algebraisch auszulegen ist. Ich finde, der Leser sollte erst einmal die begriffliche Motivation für die Pivotschritte beherrschen, die Formeln würden dann als Übungsmaterial der weiterführenden Erläuterung dienen.   -  -  -   Ich kann den dualen Simplexalgorithmus auch direkt anhand der algebraischen Darstellung erklären. Sicher ist ein Simplextableau nur eine rechnerische Umsetzung unter sehr vielen anderen (es müsste rechnerische Umsetzungen oder Datenstrukturen heißen), und sicher verwenden die meisten konkurrenzfähigen Umsetzungen des Simplex-Verfahrens kein Tableau (es gibt Ausnahmen), aber: ist das nun ein Argument für oder eher gegen dessen Hervorhebung im Artikel? --Heinrich Puschmann 10:55, 4. Dez. 2007 (CET)

Das Beispiel muss sowieso mal überarbeitet werden. Es verwendet den revidierten Simplex, enthält also nur die Basisspalten; das liegt daran, dass ich das Beispiel aus einer früheren Version des Artikels übernommen habe, als ich den eigentlichen Text komplett überarbeitet habe. Wenn Du das Beispiel durch algebraische Darstellung verständlicher beschreiben kannst, nur zu! Dass die Tableaumethode nicht so verwendet wird, ist für mich weder ein Argument für noch gegen die Hervorhebung im Artikel, solange klar wird, dass in der Praxis weiterentwickelte Methoden verwendet werden. Ich hatte nur ein Problem mit der vorgeschlagenen Überschrift. Gruß, -- Sdo 22:39, 4. Dez. 2007 (CET)

Angesichts der Länge des Artikels wäre es evtl. auch sinnvoll, die Rechnung auf eine Unterseite Simplex-Verfahren/Beispielrechnung auszulagern. Was meinst Du? Was meinen andere Leute dazu? -- Sdo 17:14, 5. Dez. 2007 (CET)

Ich habe derzeit noch zu wenig Erfahrung mit Wikipedia, um mir eine Meinung über Auslagern oder Nicht-Auslagern zu bilden. Die Reihenfolge im Beispiel dagegen ist wahrscheinlich nicht die optimale (ich würde Einsteigern empfehlen, zuerst den Abschnitt über algebraische Notation zu lesen und danach zu den Tableaus überzugehen). Aber Umschreiben erfordert natürlich mehr Arbeit als Patchwork. --Heinrich Puschmann 10:04, 6. Dez. 2007 (CET)

Was spricht gegen eine parallele Darstellung? Darstellung in algebraischer Notation und parallell das Tableau. --tsor 10:09, 6. Dez. 2007 (CET)

Ja, ich finde es auch ok, beides zu haben. Angesichts dessen, dass der Algorithmus am Tableau erklärt wird, sollte das vielleicht auch beim Beispiel zuerst kommen, aber am Anfang des Beispiels könnte ein Hinweis auf die algebraische Form weiter unten stehen. -- Sdo 00:40, 7. Dez. 2007 (CET)

Nix spricht dagegen, oder? --Heinrich Puschmann 13:46, 7. Dez. 2007 (CET)

So, jetzt habe ich die Arbeit mal gemacht und die Beispielrechnung neu geschrieben. Die Bruchzahlbehandlung der Einträge gehört vielleicht nicht direkt dazu; hat sich aber bei kleinen Aufgaben von mir als sehr praktisch erwiesen. --Heinrich Puschmann 10:33, 29. Apr. 2008 (CEST)

Wunderbar, vielen Dank! -- Sdo 22:17, 29. Apr. 2008 (CEST)

Left-Hand-Side

Dieser Vorschlag hat nichts mit technischer Korrektheit zu tun, sondern ausschließlich mit der Darstellung; es wäre nämlich schön, wenn sich dieser Artikel langsam in einen lesenswerten wandelt, und er macht derzeit eher einen verkrampften Eindruck.

Sollen wir beim Simplex-Tableau (nicht bei der Aufstellung der Nebnbedingungen) die traditionelle "Right-Hand-Side" oder "Rechte Seite" wirklich rechts einfügen, oder sind wir mutig genug sie links hinzustellen?
Die RHS ist eine besondere Spalte, die in dualer Beziehung zur Zielfunktion steht, welche die erste Zeile besetzt. Die für das Simplexverfahren wichtige Dualitätsbeziehung wiederum ist im wesentlichen eine negative Matrixtransposition, und die Matrixtransposition vertauscht nun einmal traditionellerweise die erste Zeile mit der ersten Spalte, und nicht mit der letzten. Die mathematische Tradition widerspricht hier der (englischsprachigen) Linear-Programming-Tradition, und dieser gordische Knoten sollte endlich einmal durchschnitten werden.

Theoretischerweise gäbe es noch andere Möglichkeiten, die Notation zu normieren, zum Beispiel, die Zielfunktion ans Ende zu setzen oder (nicht ernst gemeint) die Matrixtransposition über die zweite Diagonale zu definieren. Ich glaube aber, dass die Versetzung der RHS-Spalte nach links die einzige realistische Alternative ist. Es gibt sehr wahrscheinlich Dozenten, die das bereits tun, doch habe ich noch keine konkreten Quellen; habt ihr vielleicht welche? Es geht hier nicht um Begriffsbildung, sondern darum, dem Leser die bereits vorhandenen Begriffe so einfach wie nur möglich zu erklären.
--Heinrich Puschmann 19:08, 27. Mai 2008 (CEST)

Mach das. Dann sollten aber auch die Ungleichungen in den Beispielen als $b\leq a^{T}x$ geschrieben werden. -- Sdo 11:27, 3. Jun. 2008 (CEST)

Meinst du wirklich $b\leq Ax$ oder etwa $b\geq Ax$? Eigentlich ist es egal, denn wir werden fast immer irgendwo ein Minuszeichen einfügen müssen. Die einzige "transpositionsgerechte" Schreibweise wäre $b+Gx\geq 0$ mit $G=-A\,$, aber das ist sehr verschieden von der Masse der Literatur. Ich denke, wir können vielleicht eine Brücke schlagen indem wir beides erwähnen, den Leser so sanft wie möglich zur guten Notation hinführen, und die geschichlichen Hintergründe für diese Notationsdivergenz auch erklären. Die Hauptidee des Tableaus ist meiner Meinung nach die Automatisierung der Eintragsumwandlungen bei einem Pivot-Schritt, und diese Idee bliebe auch bei $G=-A\,$ erhalten.
--Heinrich Puschmann 19:14, 3. Jun. 2008 (CEST)

Sorry, ich meinte $b\geq Ax$. -- Sdo 00:57, 4. Jun. 2008 (CEST)

--Analyx (Diskussion) 15:29, 22. Dez. 2020 (CET)=== Tableau-Vorschlag === Ich schlage vor, folgende zwei Tableau-Varianten (die erste so klassisch wie möglich und die zweite so intuitiv/modern wie möglich) in den Artikel einzuarbeiten. Diese beiden dürften repräsentativ für die anderen sein.

Die Matrix $A\,$ ist die Matrix des Ungleichungssystems $Ax\leq b$. Die Matrix $[N\;B]\,$ ist eine Spaltenumstellung der Matrix $[A\;I]\,$. Die Variablen $x_{I}\,$ sind dann konsistenterweise die Schlupfvariablen, aber wir können sie auch anders benennen. $N\,$ steht für Nichtbasisspalten, also die restlichen Spalten, das können wir auch $R\,$ benennen. Die doppelte senkrechte Trennungslinie zeigt an, wo man sich das Gleichheitszeichen (=) zu denken hat.

Die rechte Hälfte des klassischen Tableaus ist das revidierte Simplextableau; es benutzt nur die Spalten von B, während das Dictionary-Tableau und das gedrungene Tableau von Grötschel die Spalten von N benutzen.

Das Beispiel zeigt das Anfangstableau, also mit $B=I\,$
--Heinrich Puschmann 18:56, 11. Jun. 2008 (CEST)

Gleichungen zum klassischen Tableau (rechtsseitiges Matrizenprodukt-Tableau):

${\begin{matrix}+~~~~1\,x_{1}&+~~~~2\,x_{2}&+~1\,y_{A}&+~0\,y_{B}&+~0\,y_{C}&+~0\,z&=&~~~170\\[2pt]+~~~~1\,x_{1}&+~~~~1\,x_{2}&+~0\,y_{A}&+~1\,y_{B}&+~0\,y_{C}&+~0\,z&=&~~~150\\[2pt]+~~~~0\,x_{1}&+~~~~3\,x_{2}&+~0\,y_{A}&+~0\,y_{B}&+~1\,y_{C}&+~0\,z&=&~~~180\\[3pt]-~300\,x_{1}&-~500\,x_{2}&+~0\,y_{A}&+~0\,y_{B}&+~0\,y_{C}&+~1\,z&=&~~~~~~0\end{matrix}}$

Beispiel zum klassischen Tableau:

* ${\boldsymbol {x_{1}}}$	* ${\boldsymbol {x_{2}}}$	* ${\boldsymbol {y_{A}}}$	* ${\boldsymbol {y_{B}}}$	* ${\boldsymbol {y_{C}}}$	* ${\boldsymbol {z}}$		* ${\boldsymbol {1}}$
1	2	1	0	0	0		170
1	1	0	1	0	0		150
0	3	0	0	1	0		180
-300	-500	0	0	0	1		0

Allgemeine Form des klassischen Tableaus:

* ${\boldsymbol {x_{A}}}$	* ${\boldsymbol {x_{I}}}$	* ${\boldsymbol {z}}$		* ${\boldsymbol {1}}$
$B^{-\!1}A$	$B^{-\!1}$	$0\,$		$B^{-\!1}b$
$-c_{A}+c_{B}B^{-\!1}A$	$c_{B}B^{-\!1}$	$1\,$		$f+c_{B}B^{-\!1}b$

Gleichungen zum Dictionary-Tableau (Chvatal):

${\begin{matrix}z&=&~~~~~~0&+~300\,x_{1}&+~500\,x_{2}\\[3pt]y_{A}&=&~~~170&-~~~~1\,x_{1}&-~~~~2\,x_{2}\\[2pt]y_{B}&=&~~~150&-~~~~1\,x_{1}&-~~~~1\,x_{2}\\[2pt]y_{C}&=&~~~180&+~~~~0\,x_{1}&-~~~~3\,x_{2}\end{matrix}}$

Beispiel zum Dictionary-Tableau:

		* ${\boldsymbol {1}}$	* ${\boldsymbol {x_{1}}}$	* ${\boldsymbol {x_{2}}}$
$z\,$		0	300	500
$y_{A}\,$		170	-1	-2
$y_{B}\,$		150	-1	-1
$y_{C}\,$		180	0	-3

Allgemeine Form des Dictionary-Tableaus:

		* $\,{\boldsymbol {1}}$	* $\,{\boldsymbol {x_{N}}}$
$z\,$		$f+c_{B}B^{-\!1}b$	$c_{N}-c_{B}B^{-\!1}N$
$x_{B}\,$		$B^{-\!1}b$	$-B^{-\!1}N$

Dann würde ich vorschlagen, in der theoretischen Erklärung das klassische Tableau zu verwenden und im Beispiel das Dictionary-Tableau (so wie jetzt), und dazuzuschreiben, das wir das bewusst so gemacht haben und warum, von wegen Repräsentanten und so. Für die Nichtbasisspalten würde ich $N$ vorschlagen, das finde ich intuitiver als R (und es deckt sich mit der Notation im Grötschel-Skript, die ich in der theoretischen Erklärung verwendet habe). Schon mal vielen Dank für Deine Mühe, -- Sdo 10:16, 12. Jun. 2008 (CEST)

Liebe Wikipedianer, ich habe eine neue Darstellung zum dem durchgerechneten Beispiel zum Simplexverfahren in LaTeX verfasst; ich weiß aber nicht, wie ich das in Wikipedia einbringen kann und ob meine Darstellung überhaupt erwünscht ist. Wer kann mir Weiterhelfen? --Analyx (Diskussion) 15:29, 22. Dez. 2020 (CET)

Grassierende Inkonsistenz

Verschiedene Lettern haben in den Abschnitten des Artikels nicht die gleiche Bedeutung. Zum Beispiel enthält der Vektor $x\,$ innerhalb desselben Artikels manchmal keine Schlupfvariablen und manchmal doch welche; mit der Anzahl $n\,$ der Variablen in einer Aufgabe ist hier ebenfalls mal das eine und mal das andere gemeint, und das gleiche gilt für die wankelmütige Matrix $A\,$.

Die Situation ist so verfahren, dass sie meines Erachtens durch individuelles Vorgehen kaum zu beheben ist. Das stammt natürlich daher, dass die Literatur extrem uneinheitlich ist, und jeder, der etwas beiträgt, sich nach der ihm bekannten Quelle richtet. Wenn der Artikel konsistent sein soll, brauchen wir eine Richtlinie, und es wird sich nicht vermeiden lassen, das diese einigen Lieblingsquellen widerspricht.

Ein Argument, $x\,$ ohne Schlupfvariablen zu belassen, wäre, dass primale Schlupfvariablen bei der dualen Aufgabe verschwinden. Ein Argument dagegen, Schlupfvariablen in$x\,$ einzufügen, wäre, die Matrixnotation zu vereinfachen. Wir können auch verschiedene Buchstaben für das eine und das andere verwenden, aber welche bloß?

--Heinrich Puschmann 15:45, 11. Jun. 2008 (CEST)

Im Zweifelsfall würde ich die Schlupfvariablen lieber in $x$ einfügen, wenn es die Notation vereinfacht. Das duale LP wird sowieso im Artikel kaum angefasst; ob da jetzt primale Schlupfvariablen drinstehen oder nicht, ist mir nicht so wichtig. Deine Änderungen finde ich ok, aber unter "Iterative Simplexschritte" solltest Du noch dazuschreiben, dass die Schlupfvariablen jetzt im Vektor drinstehen, um zu erklären, warum da [A I] steht. Aber eigentlich halte ich das mit den Schlupfvariablen insgesamt nebensächlich. Viel verwirrender finde ich, dass die Erklärung die vollständige Matrix benutzt, während das Beispiel den revidierten Simplex verwendet, der nur mit der Basismatrix arbeitet. Ich hatte nur bisher keine Muße, das Beispiel entsprechend anzupassen. -- Sdo 17:36, 11. Jun. 2008 (CEST)

Also, das Beispiel benutzt nicht den sogenannten revidierten Simplex, da liegt ein Missverständnis bei dir vor, sondern ein gedrungenes Tableau, das in den Vorlesungen von Grötschel (siehe Referenz) vorkommt und nicht von mir eingeführt wurde. Das ist natürlich eine weitere von vieles Inkonsistenzen, und bei so einem Wirrwarr muss es ja gezwungenerweise zu Missverständnissen kommen. --Heinrich Puschmann 18:20, 11. Jun. 2008 (CEST)

Ok, stimmt. Das Beispiel war schon drin, als ich den restlichen Artikel komplett überarbeitet habe, weil die Theorie und neuere Entwicklungen quasi komplett fehlten. Ich hatte es dann erstmal im wesentlichen so dringelassen, wie es war, weil ich mit dem Rest genug zu tun hatte. Vielleicht ist es auch gar nicht schlecht, das Beispiel so zu lassen; wir sollten nur darauf hinweisen, dass das Beispiel-Tableau nicht die komplette Matrix enthält. -- Sdo 18:38, 11. Jun. 2008 (CEST)

Grundidee des Simplex-Verfahrens

Zitat aus dem Kapitel "Grundidee des Simplex-Verfahrens"

Meist wird noch vorausgesetzt, dass alle Einträge von b nichtnegativ sind, was sich immer durch Multiplikation einzelner Zeilen des Gleichungssystems mit (-1) erreichen lässt.

Mein Einwand: Wenn man eine Zeile mit -1 mutlipliziert, dann wird doch das kleiner-gleich Zeichen zu einem größer-gleich Zeichen. (nicht signierter Beitrag von 217.229.193.196 (Diskussion) 15:23, 7. Sep. 2008)

Du hast recht, das ist etwas unklar formuliert. Das ist aber in diesem Fall Absicht, damit der Schwerpunkt des Artikels beim Simplex-Verfahren bleibt und solche Dinge wie die Transformationen zwischen den LP-Darstellungen nicht ausufern. Wenn Du eine Zeile $ax\leq b$ hast mit b negativ, kannst Du im Zweifelsfall einfach eine Schlupfvariable y einführen, die durch 1 nach oben beschränkt ist: $ax-by\leq 0$ und $y\leq 1$. -- Sdo 23:50, 9. Sep. 2008 (CEST)

Nein: Der Einwand ist richtig, und die Aussage ist nicht "etwas unklar formuliert", sondern falsch. (Siehe Diskussion "Abfassung der Grundidee") --Heinrich Puschmann (Diskussion) 20:59, 28. Aug. 2016 (CEST)

Bestimmung einer Startlösung (Phase I)

1) folgende Behauptung

"Das ursprüngliche Problem (LP) besitzt genau dann eine zulässige Lösung, wenn es eine Lösung des Hilfsproblems mit z = 0 gibt, bei der also keine künstlichen Variablen verwendet werden"

besagt eigentlich nur (in etwas umstaendlicher Form), dass das Gleichungssystem Ax=b eine Loesung besitzt (welche man z.B. mit Gauss ermitteln kann).

2) folgende Behauptung

"Findet man dabei eine Optimallösung (x * ,z * ) mit z * = 0, ist x * offensichtlich eine zulässige Startlösung für das Ausgangsproblem (LP), mit der dessen Phase II gestartet werden kann. Gelingt dies nicht, so ist das Ausgangsproblem nicht lösbar und man kann aufhören."

widerspricht der Beispielrechnung, die weiter unten folgt.

Gruss,

Friedrich Neurauter (nicht signierter Beitrag von 138.232.66.135 (Diskussion | Beiträge) 09:46, 3. Apr. 2009 (CEST))

eine kurze Frage

Am Anfang von diesem Artikel finde ich eine Problem "Ein Simplex-Verfahren (auch Simplex-Algorithmus) ist ein Optimierungsverfahren der Numerik ". Ist Simplex-Verfahren ein numerische Verfahren? Das glaube ich nicht. Obwohl manche Problem im schleuchten Fall durch Simplex-Verfahren nicht exakt gelöst werden können, ist das Verfahren eigentlich ein exakte Verfahren, oder？ (nicht signierter Beitrag von 37.201.180.244 (Diskussion) 13:37, 22. Feb. 2013 (CET))

Das Simplex-Verfahren wird schon zur Numerik gezählt, als numerisches Verfahren zur Lösung eines kontinuierlichen Optimierungproblems mit Nebenbedingungen. Dass es ein exaktes Verfahren ist, spielt dabei eigentlich keine Rolle, siehe Direktes Verfahren. -- HilberTraum (Diskussion) 10:19, 23. Feb. 2013 (CET)

Beispiel hilft nicht

Die Beispielrechnung unter Punkt 5 ist sicher ausführlich und deutlich beschrieben. Wäre es vielleicht trotzdem möglich das so zu bearbeiten, dass Koeffizienten benutzt werden, die ungleich 1 sind (und idealerweise auch verschieden). Es ist sehr schwer nachzuvollziehen, wenn durch einen Koeffizienten geteilt wird, aber sich nichts ändert und auch nicht vermerkt wird, dass es geschehen ist. Immerhin soll ein Beispiel doch alle notwendigen Schritte deutlich machen... (nicht signierter Beitrag von 77.176.69.38 (Diskussion) 14:22, 16. Jun. 2013 (CEST))

Unverständlich

Wenn man sich als Schüler nochmal kurz informieren möchte, wie der Algorithmus funktioniert, wird man mit Formeln aus der Mathematik-Vorlesung erschlagen. Kann man die Mathematik-Artikel, die Themen behandeln, die auch schon in der Schule behandelt werden, nicht so reduzieren, dass sie verständlich bleiben? Natürlich darf es dadurch nicht falsch werden. Aber so eine Art Kurzfassung für den interessierten Laien sollte doch möglich sein. Wer diesen Text versteht, wusste vorher auch schon was ein Simplex-Algorithmus ist. Wikipedia war mal als Enzyklopädie für alle gedacht. Hier sehe ich eher die Selbstbeweihräucherung von Mathematik-Studenten. Schade --11:41, 16. Apr. 2016 (CEST) (ohne Benutzername signierter Beitrag von 88.77.97.176 (Diskussion))

Einverstanden. Aber schau einmal in den Artikel Pivotverfahren; der enthält alle Grundbegriffe und ist abgerundet. --Heinrich Puschmann (Diskussion) 19:59, 28. Aug. 2016 (CEST)

Abfassung der Grundidee

Ich habe den Abschnitt "Grundidee" nun umgeschrieben, weil er so wie bisher den völlig falschen Tatbestand andeutete, dass eine lineare Optimierungsaufgabe "durch einfache Umformungen" in die Form

$\max _{x\in \mathbb {R} ^{n}}\left\{c^{T}x\mid \;Ax\leq b,\;x\geq 0\right\}$

gebracht werden kann, bei welcher $b$ "ein Vektor mit Beschränkungen ist". Da mit den vage gehaltenen "Beschränkungen" ganz offenbar (und danach auch bestätigterweise) $b\geq 0$ gemeint ist, ist diese Aussage barer Unsinn. Wenn dem wirklich so wäre, dann hätten Mathematiker jahrzehntelang ihre Zeit vergeudet, über Phase 1 der Simplexverfahren nachzudenken.

Das obige Missverständnis ist unter Schülern trotzdem weit verbreitet, weil in den meisten Lehrbüchern die Phase 2 des Verfahrens vor Phase 1 beschrieben wird, und im Gymnasialunterricht die Beschreibung der (unverzichtbaren!) Phase 1 oft einfach fortgelassen wird.

Auch stilistisch war der Abschnitt ziemlich unmöglich. Die geheimnisvollen "Beschränkungen" sollten am Anfang aufgezeigt werden. Und nähere Einzelheiten der erwähnten Umformungen haben ihren Platz daselbst, im spezifischen Artikel, und sollten nicht über Verlinkungen zum allgemeineren Artikel "Lineare Optimierungen" unter den Teppich gekehrt werden.

--Heinrich Puschmann (Diskussion) 20:49, 28. Aug. 2016 (CEST)

Ich weiß, dass der letzte Beitrag hierzu fast 3 Jahre alt ist, aber das Problem besteht weiterhin. Bei der "Grundidee" wird gesagt, dass $b\geq 0$ gewählt werden kann, aber das lässt sich nur durch die nichttriviale Phase 1 erreichen. Schauen wir aber in Phase 1, dann sehen wir, dass dort behauptet wird, $(x,z)=(0,b)$ wäre eine zulässige Lösung für das Hilfsproblem. Das stimmt aber nur, wenn man bereits weiß, dass $b\geq 0$ ist und dann braucht man die Phase 1 doch gar nicht, oder übersehe ich etwas? --2A00:1398:4:2004:1D0E:1C2D:39F6:449B 14:36, 27. Jun. 2019 (CEST)

Summen statt Matrizen

Soll man zur Beschreibung der Simplexverfahren wirklich Matrizen oder lieber Summen verwenden? Vermutlich ist diese Diskussion bereits alt, vielleicht aber auch nicht, und die Meinungen, was Oma (oder Enkel) nun leichter versteht, gehen sicher auseinander. Aber bisher ist es im Artikel so, dass beides wüst durcheinandergemischt wird, so dass ein Leser dieses Artikels (gibt es solche überhaupt noch?) nicht umhin kommt, beides beherrschen zu müssen. Das können wir ihm auf jeden Fall leichter machen, indem wir uns auf eins von beiden beschränken.

Zusätzlich habe ich den Eindruck, dass gewisse Teile nur mit Summen (halbwegs anständig) zu beschreiben sind, während andere Artikel praktisch gezeigt haben, dass man auch ohne Matrizen sehr weit kommt. Und wenn der Leser die Summennotation sowieso kennen muss, dann sind es demzufolge die Matrizen und Vektoren, auf die wir in den ersten 50% des Artikels tunlichst verzichten sollten. Vielleicht könnten wir auch ganz darauf verzichten, aber ich mache mir da bezüglich des bereits Etablierten wenig Hoffnung.

Wenigstens die Grundlagen ohne Matrizen beschreiben wäre schön - wenn wir uns darin einig werden. Denn wer ist schon bereit, seine Zeit mit Umschreiben zu vergeuden, wenn er sich danach mitten in einem Editierkrieg wiederfindet?

--Heinrich Puschmann (Diskussion) 13:24, 31. Aug. 2016 (CEST)