Converting a LP problem to standard form

203 Views Asked by At

Consider the following LP problem:

$$ \min -x_1 +2x_2 $$ $$ \text{s.t.} \ \ x_1 + x_2 -1 \leq 0 $$ $$ x_1 \geq 0 $$ $$ x_2 \geq 0 $$

I Want to write it in the standard form (to apply a specific algorithm):

$$ \min \hat{c}^T \hat{x} $$ $$ A\hat{x} = \hat{b}$$ $$ \hat{x} \geq 0 $$

The suggestion that I was given is to introduce a new variable $\lambda > 0$ so that the first constraint becomes:

$$ x_1 + x_2 + \lambda -1 = 0$$

This will give us $\hat{x} = [x_1 \ x_2 \ \lambda]^T$. I am not sure how $A$, $\hat{b}$, and $\hat{c}$ will be in the standard form. Also, what will the value of $\lambda_0$ be in $\hat{x}_0 = [x_0 \ \lambda_0]$ to guarantee $\hat{x}_0$ is still strictly feasible in the new formulation (assuming $x_0 \in \mathbb{R}^2$ is)?

1

There are 1 best solutions below

1
On

We want $\lambda$ to be nonnegative so that the first inequality can be binding in the original formulation. The nonnegative constraint

Your $\hat{b}$ remains the same to be $1$.

We have $-x_1+2x_2=-x_1+2x_2+0\lambda = [-1, 2, 0] \begin{bmatrix} x_1 \\ x_2 \\ \lambda \end{bmatrix}$

I will leave writing down of $A$ as an exercise, you just have to rewrite $x_1 + x_2 + \lambda$ in a similar way I wrote down the objective function.

An $x$ that works in the original constraint will remain feasible in the new formulation as $\lambda$ is just the slack. Similarly, the nonnegative constraints will ensure that the new formulation is equivalent to old formulation.