Wie bringe ich Lineares Problem in Standardform

Question

Folgendes Problem:

Text erkannt:

(a) Bringen Sie das folgende lineare Programm auf Standardform
$\left.\begin{array}{rl} \min _{x, y \in \mathbb{R}^{n}} c^{\top} x \\ \text { s.t. } & A x+B y \leq 0, \quad x \leq a \end{array}\right\}$

Mein Ansatz wäre nun eine Schlupfvariable s einzuführen, sodass ich Ax+By+s=0 erhalte. Wie kann ich x<=a denn nun so schreiben, dass ich x>=0 erhalte?

Answer 1

Du fügst auch für $x\leq a$ eine Schlupfvariable ein, so dass $x+s_2=a$ mit $s_2\geq 0$. Für unbeschränkte Variablen nutzt man den Ansatz $x=x^+-x^-$ mit $x^+,\ x^-\geq 0$.

Comments

Okay, danke.

Jetzt ist aber die Defintion der Standardform ja eigentlich, dass x>=0 sein soll. Wie stelle ich das denn dar? Habe ich dann drei Nebenbedingungen (einmal die Bedingungen mit den zwei schlupfvariablen und  >=0) oder hab ich nur zwei Nebenbedingungen?

---

Du ersetzt $x$ durch die Variabeln $x^+$ und $x^-$, mit $x^+,\ x^-\geq 0$.

Mit $x^+-x^-=x$ hast du dann die Nebenbedingung als Gleichung, aber die Variablen $x^+$ und $x^-$ erfüllen die Nichtnegativitätsbedingung.

---

Also wäre meine Lösung dann

Min c^Tx

s.t. Ax=-By-s₁

x+s₂ = a

Mit x=x⁺-x^-  wobei x⁺ und x^->0