0
$\begingroup$

Consider the LPP of minimizing $z = -2x_1 + x_2$ subject to

$$\begin{cases} x_1 + 2x_2 \le 6, \\ 3x_1 + 2x_2 \le 12, \\ x_1, x_2 \ge 0 \end{cases}$$

First I add slack variables $x_3, x_4$ which immediately puts the problem in canonical form:

$$\begin{bmatrix} x_3 & 1 & 2 & 1 & 0 & 6 \\ x_4 & 3 & -2 & 0 & 1 & 12 \\ z & -2 & 1 & 0 & 0 & 0 \end{bmatrix} $$

By Blend's rule, I should choose a pivot in the first column because the objective function has the coefficient $-2$ there, which is negative, so it can be minimized further.

Again by Blend's rule I should pivot the second row because the ratio $12/3$ is smaller than $6/1$. So $3$ is my pivot. After pivoting, I get

$$\begin{bmatrix} x_3 & 0 & 4/3 & 1 & -1/3 & 2 \\ x_4 & 1 & 2/3 & 0 & 1/3 & 4 \\ z & 0 & 7/3 & 0 & 2/3 & 8 \end{bmatrix} $$

I cannot minimize further because all coefficients in the new form of the objective function are positive. So $z = -8$ at $x_1 = 4, x_2 = 0, x_3 = 2, x_4 = 0$. My final answer is $z = -8$ at $(4, 0)$ because $x_1$ and $x_2$ are my original variables.

So my basic solution is in terms of $x_3, x_1$. I expected to get a basic solution in terms of $x_1$ and $x_2$. Why didn't this happen and what does it mean?

$\endgroup$
0
$\begingroup$

There's no reason to expect that the final basic variables should be your original variables, unless you expect that the optimal values of all of the original variables should be non-zero. In your LP, the optimal solution happens to have $x_2=0$.

At the same time, there is one functional constraint that has positive slack (the optimal solution does not lie right on the constraint boundary), so the slack variable for that constraint is positive, i.e., basic.

Here is a plot of the feasible region for your LP (you have to imagine the $x_1,x_2\ge 0$ constraints). There are 4 corner-point feasible solutions: $(0,0)$, $(0,3)$, $(3,1.5)$, and $(4,0)$. LP theory tells us that each CPF solution should have at most two variables (including slack variables) that are non-zero. So, for $(4,0)$ there is one "regular" and one slack variable that is positive; for $(3,1.5)$ there are two regular and zero slack variables that are positive; etc.

$\endgroup$
  • $\begingroup$ What do you mean by CPF? $\endgroup$ – user136217 May 14 at 16:37
  • $\begingroup$ Corner point feasible solution $\endgroup$ – LarrySnyder610 May 14 at 16:48

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.