0

I am working on some problems on the Simplex Algorithm for Linear Programming. In order to apply the simplex algorithm, the LP must be in standard form. If the constraint is an inequality with a $\leq$, then I just add a slack variable, $s_1\geq 0$. If the constraint is an inequality with a $\geq$, then I just subtract an excess variable, $e_1\geq 0$. If the constraint is bounded above and below: $a\leq x_1\leq b$ (assuming $a\neq0$), then I can use an excess variable $e_1\in[0,b-a]$.

Examples of what I'm talking about:

$(1)$ $2x_1\leq 0$ becomes $2x_1+s_1=0, s_1\geq 0$

$(2)$ $x_1\geq 2$ becomes $x_1-e_1=2, e_1\geq 0$

$(3)$ Given that $x_1\in [1,4]$, then $x_1\leq 3$ becomes $x_1-e_1=1,e_1\in [0,3] $

But if I was given the information that a variable was unrestricted, $-\infty< x_1<\infty$, how would I write that as an equality? My constraint is neither bounded above nor below, so none of the above work.

Sujaan Kunalan
  • 10,944

1 Answers1

1

The typical approach is to write $x_1$ as a difference of two auxiliary non-negative variables, like so: $x_1 = y_1 - w_1, y_1 \ge 0, w_1 \ge 0$. Now add the corresponding excesses to $w_1$ and $y_1$ and you are done.

baudolino
  • 1,885