LP in kanonische Form bringen

Question

Aufgabe:

Bringen die das LP in kanonische Form:

$$min \ c^Tx+d^Ty \\ s.t. \ Ax \geq a \\ By= b \\ x \geq 0$$

Ein LP ist in kanonischer Form, wenn es wie folgt aussieht:

$$max \ g^Tz \\ s.t. \ Fz \leq f \\ z \geq 0$$

Benutzen Sie eine passende Matrix F und jeweils einen passenden Vektor f und g.

Problem/Ansatz:

Hallo, ich habe das LP bereits in die folgende Form gebracht:

$$- max \ -c^Tx-d^Ty \\ s.t. \ Ax - d=a \\ By=b \\ x,d \geq 0$$

Dann habe ich noch das folgende gemacht, um die Gleichzeichen zu kleiner gleich zu bekommen:

$$- max \ -c^Tx-d^Ty \\ s.t. \ \begin{pmatrix} A & -I \\ -A & I \end{pmatrix}\begin{pmatrix} x\\d \end{pmatrix} \leq\begin{pmatrix} a\\-a \end{pmatrix} \\ \begin{pmatrix} B\\-B \end{pmatrix}y\leq \begin{pmatrix} b\\-b \end{pmatrix} \\ x,d \geq 0$$

(I soll die entspr. Einheitsmatrix sein)

Meine Frage wäre, ob bis jetzt die Umformungen stimmen und wie ich die letzten Schritte zur kanonische Form schaffen kann? Also konkret wie bekomme ich das auf eine Matrix f und die Vektoren f ung g umgeformt

Answer 1

Definiere doch entsprechend einfach neue Vektoren \(g\) und \(z\), so dass die Zielfunktion erstmal die gesuchte Form hat. Erst dann würde ich mich an die Nebenbedingungen machen bzw. dann weiß man auch, wie man \(z\) in die Nebenbedingungen unterbringen kann.

Comments

Dann wäre

$$g = \begin{pmatrix} c & 0 \\ 0 & d \end{pmatrix}$$

$$g^T = \begin{pmatrix} c^T & 0 \\ 0 & d^T \end{pmatrix}$$

und

$$z = \begin{pmatrix} x & 0 \\ 0 & y \end{pmatrix}$$

wobei y die nicht-Negativitätsbedingung nicht erfüllt und deshalb ersetzt werden sollte durch

$$y = y^+ - y^-$$

mit $$y^+, y^- \geq 0$$

Dann hätten wir oben schonmal die gewünschte Form:

$$-max \ g^Tz$$

Die Nebenbedingungen wäre dann also:

$$\begin{pmatrix} A & B \\ -A & -B \end{pmatrix} \begin{pmatrix} x & 0 \\ 0 & y^+-y^- \end{pmatrix} \leq \begin{pmatrix} a+d & b \\ -a-d & -b \end{pmatrix} \\ x,d,y^+,y^- \geq 0$$

Also ist $$F= \begin{pmatrix} A & B \\ -A & -B \end{pmatrix}$$

und $$f = \begin{pmatrix} a+d & b \\ -a-d & -b \end{pmatrix}$$

Stimmt das dann so?

---

Das Problem ist glaube ich jetzt, dass die Zielfunktion zur Matrix wird und kein Wert mehr ist, aber der Rest erfüllt glaube ich die Bedingungen

---

Ich glaube das ist besser, oder?

$$g = \begin{pmatrix} c\\d \end{pmatrix} \\ g^T = (c^T \ d^T) \\ z = \begin{pmatrix} x\\y^+ - y^- \end{pmatrix} \\ F = \begin{pmatrix} A & 0 \\ -A & 0 \\ 0 & B \\ 0 & -B \end{pmatrix} \\ f = \begin{pmatrix} a+d \\ -a-d \\ b \\ -b \end{pmatrix}$$

---

Ja genau. Das ist die Wahl von \(g\) und \(z\) besser. Aber muss die Zielfunktion nicht noch negativ, weil du ja von min zu max übergehst?

---

Ja, das Minus fehlt noch.

Und die Schlupfvariable sollte nicht "d" heißen (sondern z.B. "e"), da "d" schon anderweitig benutzt wird.

Ansonsten vielen Dank, das hat mir sehr geholfen!

---

Ich kann hier wirklich mal ein Lob aussprechen, wie selbstständig du die Aufgabe bearbeitet hast. Es freut mich sehr, dass dir meine Anregungen weitergeholfen haben. :)