2
$\begingroup$

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

$$ \begin{array}{lllll} \mathbf{maximize} & x_1&+&x_2&&\\ \text{subject to} & -x_1&+&x_2&+&x_3&&&&&=1\\ & x_1 &&&&&+&x_4&&&=3\\ & &&x_2 &&&&&+&x_5&=2\\ \end{array}\\ x_1,x_2,\ldots x_5\ge0 $$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$
  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.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .