What does it mean when we can't put a particular variable as a basic variable in a LPP?

Question

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?

Answer 1

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.