Umwandlung von einem primalen nach einem dualen Problem

schneevater schrieb:

Ich finde leider nirgends richtige Beispiele, kann das wer erklären anhand z.b. EA7 Aufgabe 7.2b ?

Das Primale Problem ist denn ja das Problem in Standardform, dass in 7.2a aufgestellt werden sollte.

also wäre bei mir:

max 3x -4y
unter: x+y+s1 = 1
x-y+s2 = -2
x+y+k1 = -1
2x-4y -s3 +k2 = -4
3x -8y-s4+k3 = 1

Zum Vergrößern anklicken....

wieso hast du da noch ein kx hinzugefügt? Die dritte Nebenbedingung war doch Gleichheit und bei vier und fünf sollte doch die Schlupfvariable reichen

Bei der Umwandlung in das duale Problem weiß ich nun das aus dem Maximierungsproblem ein Minimierungsproblem wird.
Die Koeffizienten der Nebenbedingungen werden transponiert, alles was auf der rechten Seite des Gleichheitszeichens steht wird die Zielfunktion
Die Koeffizienten der Zielfunktion werden die Ergebnisse der Nebenbedingungen.

Ich komme denn zu so etwas :

min s1- 2s2 - k1 - 4s3- 4k2 + s4+ k3
unter x1 +x2+x3+2x4+3x5 = 3
y1-y2+y3-4y4-8y5= -4

Aber das ist bestimmt irgendwie anders oder ?

Zum Vergrößern anklicken....

ich komme auf
-min (1 -2 -1 -4 1) y
unter
[tex]\left(\begin{array}{ccccc}
1 & 1 & 1 & 2 & 3\\
1 & -1 & 1 & -4 & -8\\
1 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & -1 & 0\\
0 & 0 & 0 & 0 & -1\end{array}\right)y\geq\left(\begin{array}{c}
3\\
-4\\
0\\
0\\
0\\
0\end{array}\right)[/tex]
Ob das aber stimmt bin ich mir nicht wirklich sicher

wieso hast du da noch ein kx hinzugefügt? Die dritte Nebenbedingung war doch Gleichheit und bei vier und fünf sollte doch die Schlupfvariable reichen

Zum Vergrößern anklicken....

Ich habe mir folgendes gemerkt:

Bei der Umformung der Nebenbedingungen in Standardform gilt:
Für: "<=" -> 1x Schlupfvariable mit positivem Vorzeichen +sx
Für: ">=" -> 1x Schlupfvariable mit negativem Vorzeichen und eine Kunstvariable mit negativem Vorzeichen -> -sx + kx
Für: "=" -> Nur eine Kunstvariable mit positivem Vorzeichen notwendig: +kx

Bei "=" habe ich das soweit verstanden:
Es muss auch hier eine Kunstvariable eingeführt werden um die Lösbarkeit des Gleichungssystem zu gewährleisten.

ich komme auf
-min (1 -2 -1 -4 1) y

Zum Vergrößern anklicken....

Warum nimmst du hierbei gerade das y in die Zielfunktion?
Das die (1 -2 -1 -4 1) verwendet werden müssen ist soweit klar, da diese Spalte ja zur Zielfunktion wird.
Frage mich nur welche Variablen man denn verwendet.

Ich bin jetzt noch mehr ins Grübeln geraten.

Was bedeutet in Definition 8.1.4 b>=0
Auf Seite 320 kommt der Satz: Zunächst einmal können wir b>=0 immer erreichen, indem wir die entsprechende Nebenbedingung mit -1 duchmultiplizieren

Ich würde das jetzt so interpretieren, dass jede Komponente von b>=0 sein soll.
Damit habe ich meine Lösung für 7.2 a nochmal angepasst, ich komme jetzt auf

-max [tex]\left(\begin{array}{cccccc}
3 & -4 & 0 & 0 & 0 & 0\end{array}\right)x_v[/tex]
unter
[tex]\left(\begin{array}{cccccc}
1 & 1 & 1 & 0 & 0 & 0\\
-1 & 1 & 0 & -1 & 0 & 0\\
-1 & -1 & 0 & 0 & 0 & 0\\
-2 & 4 & 0 & 0 & 1 & 0\\
3 & -8 & 0 & 0 & 0 & -1\end{array}\right)x_{v}=\left(\begin{array}{c}
1\\
2\\
1\\
4\\
1\end{array}\right)[/tex] wobei
[tex]\left(\begin{array}{cccccc}
x & y & z1 & z2 & z3 & z4\end{array}\right)^T[/tex]

Mit dem Ansatz komme ich dann auf das duale Problem

-min [tex]\left(\begin{array}{ccccc}
1 & 2 & 1 & 4 & 1\end{array}\right)y_{v}[/tex]
unter
[tex]\left(\begin{array}{ccccc}
1 & -1 & -1 & -2 & 3\\
1 & 1 & -1 & 4 & -8\\
1 & 0 & 0 & 0 & 0\\
0 & -1 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & -1\end{array}\right)y_{v}\geq\left(\begin{array}{c}
3\\
-4\\
0\\
0\\
0\\
0\end{array}\right)[/tex]

ich habe jetzt für die Vektoren jeweils noch ein Index v hinzugefügt, da mein x und y als Vektor nichts mit dem x und y aus der zu Maximierenden Funktion zu tun haben.

Aber ich bin mir auch nicht sicher, ob das Umstellen des primalen zu dem dualen Problem so simpel ist. Ich habe allerdings nichts genaueres dazu gefunden.

Aber wo hast du das mit den Kunstvariablen gefunden? Ich finde das eigentlich unlogisch bei einer Gleichung, die ja schon der gewünschten Form entspricht noch eine Kunstvariable hinzuzufügen.
Ich würde mir also merken
Für: "<=" -> 1x Schlupfvariable mit positivem Vorzeichen +sx
Für: ">=" -> 1x Schlupfvariable mit negativem Vorzeichen -sx

Die Kunstvariablen kamen doch erst später dran, wenn es darum geht eine gültige Basis zu erhalten um das ganze mit dem Simplexalgorithmus zu lösen.

Aber wo hast du das mit den Kunstvariablen gefunden? Ich finde das eigentlich unlogisch bei einer Gleichung, die ja schon der gewünschten Form entspricht noch eine Kunstvariable hinzuzufügen.

Zum Vergrößern anklicken....

Das für Gleichheit ist hier beschrieben:
Der 2-Phasen Simplex-Algorithmus mit künstlichen Variablen

Der Mentor in Leverkusen hat das ebenso gesagt und die Mentorin aus Neuss (auch ne Diplom Mathematikerin) hat dies ebenso uns beigebracht.

Was ich mich Frage ist aber warum ich nicht eine gültige Basis erhalten muss.
Die Frage war ja nach der Standardform und ich war nun davon ausgegangen das es mit (falls nötig) Kunstvariablen ist.
Warum sollte ich nun bei dieser Aufgabe diese Standardform nicht mehr so anwenden ?

Hast du denn bei der Aufgabe 7.5b bei Gleichung in der Nebenbedingung auch keine Kunstvariable gesetzt ?