(Twitter)
1
Zu 1: Degenererierte Ecken sind m.E. auch Ecken, also zählen sie dazu.
Um alle Ecken zu finden, muss man den Gaußalgorithmus mehrfach anwenden, und zwar \(\displaystyle \binom{n}{m}\) mal, wobei m=Zeilenanuahl von A, n = Spaltenanzahl von A. Man muss alle m-elementen Teilmengen von \(\{1,\ldots,n\}\) bestimmen, und zu jeder dieser Teilmengen I bestimmen, ob \(A_I\) invertierbar ist.
Wenn ja, löse \(A_I x_I=b_I\), wobei \(b_I\) der Vektor ist, der diejenigen Elemente von b enthält, die der Indexmenge I entspechen.
Dann muss man noch \(x_I\) durch 0-en ergänzen (für jedes Element in \(\{1,\ldots,n\}\setminus I\) eine 0) und erhält so eine Ecke.
Diese mag unzulässig und/oder degeneriert sein, die zählt trotzdem als Ecke.
Zu 2: Der Übergang Min=>Max geht genauso wie der Übergang Max=>Min, nämlich über das duale Problem: Aus \(A\) with \(A^T\), aus den Koeffizienten der Zielfunktion werden die rechten Seiten der Ungleichungen und umgekehrt, aus \(\le\) wird \(\ge\).
Zu 3: Hier kann man die Gleichung mit -1 multiplizieren; dadurch wird die rechte Seite positiv. Schlupfvariablen braucht man hier m.E. nicht.
Um alle Ecken zu finden, muss man den Gaußalgorithmus mehrfach anwenden, und zwar \(\displaystyle \binom{n}{m}\) mal, wobei m=Zeilenanuahl von A, n = Spaltenanzahl von A. Man muss alle m-elementen Teilmengen von \(\{1,\ldots,n\}\) bestimmen, und zu jeder dieser Teilmengen I bestimmen, ob \(A_I\) invertierbar ist.
Wenn ja, löse \(A_I x_I=b_I\), wobei \(b_I\) der Vektor ist, der diejenigen Elemente von b enthält, die der Indexmenge I entspechen.
Dann muss man noch \(x_I\) durch 0-en ergänzen (für jedes Element in \(\{1,\ldots,n\}\setminus I\) eine 0) und erhält so eine Ecke.
Diese mag unzulässig und/oder degeneriert sein, die zählt trotzdem als Ecke.
Zu 2: Der Übergang Min=>Max geht genauso wie der Übergang Max=>Min, nämlich über das duale Problem: Aus \(A\) with \(A^T\), aus den Koeffizienten der Zielfunktion werden die rechten Seiten der Ungleichungen und umgekehrt, aus \(\le\) wird \(\ge\).
Zu 3: Hier kann man die Gleichung mit -1 multiplizieren; dadurch wird die rechte Seite positiv. Schlupfvariablen braucht man hier m.E. nicht.
Diese Antwort melden
Link
geantwortet
m.simon.539
Punkte: 2.22K
Punkte: 2.22K
Ist es bei 3. nicht notwendig die Gleichung auf zwei Ungleichungen zu formen? Dachte das sei notwendig.
─
oiram
28.03.2024 um 09:01
In der Wikipedia steht tatsächlich, dass man das so macht ("Vorhandene Gleichungsgruppen können in Ungleichungsgruppen aufgespalten werden", siehe hier: https://de.wikipedia.org/wiki/Simplex-Verfahren).
Später steht in diesen Wiki-Artikel allerdings: "Für das Simplex-Verfahren werden die Ungleichungen zunächst in Gleichungen überführt. " Damit hat man aus einer Gleichung zwei Gleichungen gemacht.
In meinem Teubner-Taschen-Buch der Mathematik steht es wiederum anders: Anstatt Gleichungen in zwei Ungleichungen aufzuspalten, die man in je einer eine zu Gleichung umformt, lässt man die Gleichung unverändert.
Ich sehe keinen Sinn dahinter, aus einer Gleichung zwei Gleichungen zu machen. Wenn das allerdings in Deinem Skript so steht, dass man Gleichungen in je 2 Ungleichungen umwandeln soll, dann bitte so machen. Dann lautet die Antwort auf Frage 3: "Ja". ─ m.simon.539 28.03.2024 um 23:23
Später steht in diesen Wiki-Artikel allerdings: "Für das Simplex-Verfahren werden die Ungleichungen zunächst in Gleichungen überführt. " Damit hat man aus einer Gleichung zwei Gleichungen gemacht.
In meinem Teubner-Taschen-Buch der Mathematik steht es wiederum anders: Anstatt Gleichungen in zwei Ungleichungen aufzuspalten, die man in je einer eine zu Gleichung umformt, lässt man die Gleichung unverändert.
Ich sehe keinen Sinn dahinter, aus einer Gleichung zwei Gleichungen zu machen. Wenn das allerdings in Deinem Skript so steht, dass man Gleichungen in je 2 Ungleichungen umwandeln soll, dann bitte so machen. Dann lautet die Antwort auf Frage 3: "Ja". ─ m.simon.539 28.03.2024 um 23:23