0

Ich hätte da drei Fragen, die denke ich recht einfach zu beantworten sind, aber ich mir nicht 100% sicher bin.

1.
Ecke finden:
Ich soll für eine Aufgabe alle Ecken finden. Ich habe folgendes Video herangezogen:
Basislösungen eines linearen Gleichungssystems (zulässig, degeneriert) - YouTube

Ich würde eben die Nebenbedingungen mittels Schlupfvariablen erweitern und zu Gleichungen umformen und Ax=b mittels Gauß lösen wie im Video. Indem ich alle x-Werte finde. 

Ist das die richtige Herangehensweise und zählen auch degenerierte Ecken als Lösungen bzw. auch als Max- oder Min-Lösungen?

2.
Min/Max Umwandlung:
Bei einer einzlenen Zeile reicht es wenn ich es wenn ich die Vorzeichen ändere und bei einer Matrix ist sie zu transponieren. Meine Frage ist es ob das immer in beide Richtungen (von min zu max oder auch von max zu min) möglich ist bzw erlaubt ist?

3.
Bei der erweiterten Standardform muss doch bei einer Nebenbedingung wie z.B.:

$ x_1 + 3x_2 + 3 x_3 -  2x_4 = -1$

In zwei Ungleichungen umgeformt werden, wobei eine $\leq$ in ein $\geq$ umgewandelt werden muss.

$x_1 + 3x_2 + 3 x_3 -  2x_4 \leq -1, \quad x_1 + 3x_2 + 3 x_3 -  2x_4 \geq -1$

$-x_1 - 3x_2 - 3 x_3 +  2x_4 +s_1 = 1$

$x_1 + 3x_2 + 3 x_3 -  2x_4 +s_2 = -1$

Ist das so korrekt?

gefragt

Punkte: 29

 
Kommentar schreiben
1 Antwort
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.
Diese Antwort melden
geantwortet

Punkte: 2.19K

 

Ist es bei 3. nicht notwendig die Gleichung auf zwei Ungleichungen zu formen? Dachte das sei notwendig.   ─   oiram 28.03.2024 um 09:01

1
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

Kommentar schreiben