1

So I have this linear equation system:

$inf \{3x_1 - x_2 - 2x_3 + x_4\}$

$x_1 + 4x_2 - x_3 - 3x_4 ≤ 3$
$-2x_1 + x_2 + 2x_3 - x_4 ≥ -1$
$5x_1 - 3x_2 + x_3 + 2x_4 ≤ 4$

$x_1 ≥ 0, x_2 ∈ R, x_3 ≤ 0, x_4 ∈ R$

And I have to bring it to its standard form.
I have done the following:

$x_1 + 4x_2 - x_3 - 3x_4 + x_5 = 3$
$-2x_1 + x_2 + 2x_3 - x_4 - x_6 = -1$
$5x_1 - 3x_2 + x_3 + 2x_4 + x_7 = 4$

$x_1 ≥ 0, x_2 ∈ R, x_3 ≤ 0, x_4 ∈ R, x_5 ≥ 0, x_6 ≥ 0, x_7 ≥ 0 $

Now, in class, the professor wrote the next thing, which I don't understand how he got to it:

$x_2 = x_8 - x_9;\space\space x_8 ≥ 0, x_9 ≥ 0;$
$x_3 = -x_{10};\space\space x_{10} ≥ 0$
$x_4 = x_{11} - x_{12};\space\space x_{11} ≥ 0,x_{12} ≥ 0;$

And then he substituted $x_2, x_3, x_4$ in the original equation system, therefore bringing it to its standard form. Can you please explain how he got $x_2, x_3$ and $x_4$ to equal that, and why did he choose only $x_2, x_3$ and $x_4$ out of all the variables ? Thank you.

southpaw93
  • 229

1 Answers1

0

For the standard form it is required that all variables are greater or equal to zero: $x_i\geq 0 \ \ \forall \ \ i$

Firstly we have $x_3 \leq 0$. This inequality can be multiplied by (-1). The inequality sign has to be turnded around and we get $-x_3\geq 0$. If we replace -$x_3$ by $x_4$ we get $x_4\geq 0$.

Secondly the transformation for free variables is standard. $x_2$ has to be replaced by two non-negative variables. If you apply the simplex algorithm then only one of the two variables is in the basis. The other one is not in the basis and has definitely the value of $0$.

callculus42
  • 30,550
  • yeah, but what I don't get is why does: $x2=x8−x9; x8≥0,x9≥0;$ $x3=−x10; x10≥0$ $x4=x11−x12; x11≥0,x12≥0;$, if all variables have to be greater of equal to zero why does $x_3 = -x_{10}$ with $x_{10} ≥ 0 $, doesn't that mean that $x_3$ is less than 0 ? – southpaw93 May 18 '16 at 11:12
  • @southpaw22 $ x_3 \leq 0$ is equivalent to $-x_3\geq 0\quad (1) $. We need a non negative domain. We choose $x_{10}=-x_3$. Together with (1) it follows $x_{10}\geq 0$ That is what we want, a non-negative variable. All terms $a_{ij}x_3$ have to be changed into $-a_{ij}x_{10}$ – callculus42 May 18 '16 at 11:24
  • Oh I see, so $x_3 = -x_{10}, x_{10} ≥ 0 $ is equivalent with $x_3 ≤ 0$, but that is after I multiplied by $ -1 $ to get all variables to be positive, right? – southpaw93 May 18 '16 at 13:15
  • Right, and for instance at the second constraint $2x_3$ has to be transformed to $-2x_{10}$. Suppose the optimal value is $x_{10}^=3$. That means that in your original problem $x_3^=-3$ – callculus42 May 18 '16 at 13:33