A typical example of a LP in my lectures looks like this:

enter image description here

From what I've learnt, we are ready to implement the simplex algorithm on this LP, since $x_3, x_4, x_5$ all have positive signs, and so are the right hand sides of the constraints.

Now I have the following LP:

maximize $z = x_1 - x_2 + 2x_3$

subject to:

$-2x_1 + 2x_2 + 2x_3 - x_4 = 2$

$2x_1 - 2x_2 + x_3 + x_5 =2$

$x_1,x_2,x_3,x_4,x_5 \geq 0$

I'm trying to turn this into the required form, and I'm considering two approaches:

Approach 1: multiplying the first constraint by $-1$, so that it becomes $2x_1 - 2x_2 - 2x_3 + x_4 = -2$, then introduce a variable $x_6 \geq 0$ into it so that the RHS becomes non-negative, i.e. $2x_1 - 2x_2 - 2x_3 + x_4 + x_6 = 0$, and then proceed to let $x_5 \text{ and } x_6$ be the basic variables.

However this approach doesn't seem right to me, since then wouldn't $x_6$ must have the value $2$? (and hence not really a variable?)

Approach 2: starting with the solution $(0,0,0,0)$, we see that the 2 LHSs must be "corrected" to attain the desired values, so we introduce $x_6, x_7 \geq 0$ to make up for the differences. But what we really want is for those two new variables to be $0$, so our LP becomes:

maximize $z = -x_6 - x_7$

subject to:

$-2x_1 + 2x_2 + 2x_3 - x_4 + x_6 = 2$

$2x_1 - 2x_2 + x_3 + x_5 + x_7 =2$

$x_1,x_2,x_3,x_4,x_5,x_6,x_7 \geq 0$

Is any of the two approaches valid? If not, why is it so, and how should I think about and resolve the issue mentioned above?

  1. Approach 1 is invalid for the reason that you've mentioned: missing value $2$ on the RHS.
  2. Approach 2 is simply the method. To improve the efficiency, you don't need to introduce $x_7$. Simply take $x_5 = x_6 = 2$ at the beginning of phase I, and eliminate $x_6$ from the current basis so as to obtain a basic feasible solution for phase II.
  3. Inspection approach: find an intial basic feasible solution by inspection: observe that $x_5$ doesn't appear in the first constraint, so choose either $x_2$ or $x_3$ to be the first basic variable, and $x_5$ as the second basic variable. This should save work for introducing additional terms.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.