Benutzer Diskussion:Timo Weingärtner

Begrüßung und Simplex-Verfahren

Hallo Timo!

Erstmal herzlich willkommen in der Wikipedia – schön, dass Du hier mitmachen willst! Bei evtl. Fragen hilft hoffentlich Wikipedia:Hilfe weiter; ansonsten kannst Du Dich gerne an mich wenden. Was Deine Änderung beim Simplex-Verfahren angeht: da stand mit Absicht Ax = b und nicht Ax <= b, weil der Algorithmus in seiner Grundversion von einem LP in Gleichheitsform ausgeht. Im Prinzip kann man das mit beiden Varianten erklären. Wir sollten uns aber für eine davon entscheiden und sie dann im Text konsequent durchziehen. Im Moment ist der Text inkonsistent, weil er mal von Gleichungen und mal von Ungleichungen ausgeht. Insbesondere beziehen sich die Umformungen des LPs direkt hinter der gerade geänderten Stelle alle auf die Gleichheitsform. Wenn Du solche Änderungen durchführst, musst Du solche Stellen auch mit ändern.

Gruß, -- Sdo 21:43, 6. Mai 2007 (CEST)

In Gleichungsform macht es (für mich zumindest) keinen Sinn, da sich selten alle Gleichungen erfüllen lassen und dadurch evtl. das Maximum nicht zugelassen wird (Beispiel: x1 + x2 <= 2, x1 <= 1, Zielfunktion x2 => Maximum bei (0,2); in strengen Gleichungen wäre nur (1,1) zugelassen). Bitte korrigiere mich, wenn ich mich irre. --Timo Weingärtner 01:07, 7. Mai 2007 (CEST)

Hallo Timo, Du kannst ein beliebiges LP in Ungleichungsform durch Multiplikation von Ungleichungen mit (-1) und durch Einführung von Schlupfvariablen in eine Gleichungsform bringen (und umgekehrt). Dein obiges Beispiel ist äquivalent zu

$\max \;\{x_{2}\;|\;x_{1}+x_{2}+s_{1}=2,\;x_{1}+s_{2}=1,\;x_{1},x_{2},s_{1},s_{2}\geq 0\}.$

Das Gleichungssystem lebt in einer anderen Dimension, ist aber äquivalent zum Ungleichungssystem. Jede Lösung des einen Systems entspricht genau einer Lösung des anderen Systems und umgekehrt. Die Schlupfvariablen $s_{i}$ geben an, wieviel Platz eine Lösung $(x_{1},x_{2})$ in der jeweiligen Ungleichung noch lässt. Und das Simplex-Verfahren geht halt von solch einem LP in Gleichungsform aus, weil es in seiner Grundversion letztlich nur eine Abfolge von linearen Gleichungssystemen löst. Gruß, -- Sdo 12:54, 7. Mai 2007 (CEST)