Normalform linearer Programme

08.06.2006, 23:33

tigerbine

Normalform linearer Programme

Gegeben ist folgendes lin Programm

min! |x1| + |x2| + |x3| unter den Nebenbed. x1 + x2 d 1, 2x1 + x3 d 3

Unter eine Normalenform: min! (c^T)x u.d.N. Ax =b, 0dx. Mein Hauptproblem besteht in den Beträgen der zu Minimierenden Funktion, welches c gehört dann dazu? Schlupfvariablen und die Restriktion 0dx bekomme ich alleine formuliert.

Vielen Dank! traurig

09.06.2006, 00:13

Ben Sisko

Auf diesen Beitrag antworten »

was ist denn d1, d3 und dx?

Und sind $\begin{eqnarray*} x_1,x_2,x_3 \in \mathbb R \end{eqnarray*}$ ?

09.06.2006, 00:21

tigerbine

Auf diesen Beitrag antworten »

Ups, da ist mir ein Kopierfehler unterlaufen. d war mal ein "kleiner gleich" zeichen. Ja, x1, x2, x3 sind reell, lassen sich als einträge des Vektors x auffassen.

09.06.2006, 00:26

Ben Sisko

Auf diesen Beitrag antworten »

OK, du wirst die Einträge $\begin{eqnarray*} x_i \end{eqnarray*}$ "duplizieren" müssen weil ja in der Normalform $\begin{eqnarray*} x_i \geq 0 \end{eqnarray*}$ gelten muss.

Reicht das als Tipp?

10.06.2006, 12:38

tigerbine

Auf diesen Beitrag antworten »

Der Begriff dupliziren ist mir in diesem Zusammenhang neu. Also mir ist bekannt, dass man falls zu $\begin{eqnarray*} x_{i} \end{eqnarray*}$ keine Restriktion gebegen ist, man das über $\begin{eqnarray*} x_{i} \end{eqnarray*}$ = $\begin{eqnarray*} x_{i}^+ \end{eqnarray*}$ - $\begin{eqnarray*} x_{i}^- \end{eqnarray*}$ realisiert wird. Ebenso wie man die Ungleichheitszeichen der Restriktion durch einführen von Schlupfvariablen zu Gleichungen macht. Mein Problem ist das c in der Minimierungsbedingung $\begin{eqnarray*} c^{T}x \end{eqnarray*}$ = min! zu finden

10.06.2006, 12:46

Ben Sisko

Auf diesen Beitrag antworten »

Du musst zwei Versionen $\begin{eqnarray*} x_i \end{eqnarray*}$ und $\begin{eqnarray*} x_i^\prime \end{eqnarray*}$ einführen. Wenn dein "neues" x etwa $\begin{eqnarray*} x=(x_1,x_2,x_3,x_1^\prime,x_2^\prime,x_3^\prime)^T \end{eqnarray*}$ wäre, so wäre $\begin{eqnarray*} c^T=(1,1,1,-1,-1,-1) \end{eqnarray*}$ und deine Nebenbedingungen müssten zusätzlich für die "Strich-Versionen" gelten.

Wie ist denn bei dir $\begin{eqnarray*} x_i^+ \end{eqnarray*}$ und $\begin{eqnarray*} x_i^- \end{eqnarray*}$ definiert? Damit könnte es auch gehen...

Gruß vom Ben

10.06.2006, 13:19

tigerbine

Auf diesen Beitrag antworten »

Also, bei uns wurde gesagt, dass wenn über eine Variable $\begin{eqnarray*} x_{i} \end{eqnarray*}$ keine Aussage gemacht wird man schreibt:
$\begin{eqnarray*} x_{i}=x_{i}^{+} - x_{i}^{-} \end{eqnarray*}$ mit $\begin{eqnarray*} x_{i}^{+} \geq 0, x_{i}^{-} \geq 0 \end{eqnarray*}$

Mein Problem bei c ist, dass in der "Funktion" $\begin{eqnarray*} c^{T}x=|x_{1}|+|x_{2}|+|x_{3}|=min! \end{eqnarray*}$ Beträge stehen.

Gruß
Bine

10.06.2006, 14:27

Ben Sisko

Auf diesen Beitrag antworten »

Also soll $\begin{eqnarray*} x_i^+ \end{eqnarray*}$ die Rolle von $\begin{eqnarray*} x_i \end{eqnarray*}$ für positive Werte übernehmen und $\begin{eqnarray*} x_i^- \end{eqnarray*}$ für negative.

Dann kannst du $\begin{eqnarray*} x_i^+ \end{eqnarray*}$ für $\begin{eqnarray*} x_i \end{eqnarray*}$ schreiben und $\begin{eqnarray*} x_i^- \end{eqnarray*}$ für $\begin{eqnarray*} x_i^\prime \end{eqnarray*}$ (im obigen Vektor).

Verstehst du den Ansatz?

10.06.2006, 20:24

tigerbine

Auf diesen Beitrag antworten »

Servus,
also irgendwie steh ich da auf dem Schlauch. Wenn ich deine Idee umsetze, wieso stehen dann Beträge in der Funktion?

Schreib deine Idee doch mal aus.

Thanks
Bine

11.06.2006, 00:23

Ben Sisko

Auf diesen Beitrag antworten »

$\begin{eqnarray*} c^T=(1,1,1,1,1,1),x=(x_1^+,x_1^-,x_2^+,x_2^-,x_3^+,x_3^-)^T \end{eqnarray*}$

Wenn ich es richtig verstanden habe hat von $\begin{eqnarray*} x_i^+,x_i^- \end{eqnarray*}$ immer mind. einer den Wert 0, je nachdem ob $\begin{eqnarray*} x_i \end{eqnarray*}$ poitiv oder negativ ist (bei $\begin{eqnarray*} x_i=0 \end{eqnarray*}$ natürlich beide).

Die Beträge will man ja gerade entfernen, weil sie sich nicht mit $\begin{eqnarray*} c^Tx \end{eqnarray*}$ ausdrücken lassen. Man will eine äquivalente Formulierung.

In obiger Formulierung minimiert man also je nach Vorzeichen eins von $\begin{eqnarray*} x_i^+,x_i^- \end{eqnarray*}$ und das andere ist eh 0.

Edit: Falls der Teil

Zitat:

Wenn ich es richtig verstanden habe hat von $\begin{eqnarray*} x_i^+,x_i^- \end{eqnarray*}$ immer mind. einer den Wert 0, je nachdem ob $\begin{eqnarray*} x_i \end{eqnarray*}$ poitiv oder negativ ist (bei $\begin{eqnarray*} x_i=0 \end{eqnarray*}$ natürlich beide).

nicht stimmt: Meine erste Idee oben, mit den $\begin{eqnarray*} x_i^\prime \end{eqnarray*}$ war, dass man sozusagen "gleichzeitig" $\begin{eqnarray*} x_i \end{eqnarray*}$ und $\begin{eqnarray*} -x_i \end{eqnarray*}$ minimiert.

Neue Frage »

Antworten »

Normalform linearer Programme

Verwandte Themen