# Does {$a_2,a_3$} define a basic feasible solution for the Linear Program?

Question: Consider the following linear program $$\begin{split} \text{Minimize} \ x_2 \\ \text{subject to} \ x_1+ x_2 +x_3 = 4\\ -2x_1+x_2 = -3\\ x_1,x_2,x_3 \ge 0 \\ \end{split}$$

Does $B = \{a_2,a_3\}$ define a BFS?

My attempt

I believe it doesn't represent a linear program because I work out $B^{-1}b$ which equals $\left[ \begin{array}{c} -3\\ 0 \end{array} \right]$

Which is negative therefore cannot be a BFS, is this correct?

## 1 Answer

You're correct except for the value of $B^{-1}b = \left[ \begin{array}{c} -3\\ \color{red}7 \end{array} \right]$.

It is not a BFS (basic feasible solution) because you require $x_1,x_2,x_3 \ge 0$, but $-7 < 0$. However, you can still begin with this basic infeasible solution to find a baisc feasible solution by the dual simplex algorithm.

Tranform the problem into

\begin{array}{lllll} \max z &= &-x_2 & & \\ \text{s.t} & x_1 &+ x_2 &+ x_3 &= 4 \\ & -2x_1 &+ x_2 & &= -3 \\ & & &x_1,x_2,x_3 &\ge 0 \end{array}

You've chosen $B = \{a_2,a_3\} = \begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}$ and $c = (0,-1,0)^T$, so $B^{-1} = \begin{bmatrix}0 & 1 \\ 1 & -1\end{bmatrix}$, $c_B = (-1,0)^T$.

\begin{align} B^{-1}A &= \begin{bmatrix}-2 & 1 & 0 \\ 3 & 0 & 1\end{bmatrix} \\ B^{-1}b &= \begin{bmatrix}-3 \\ 7\end{bmatrix} \end{align}

The simplex tableau is

\begin{array}{c|c} B^{-1}A & B^{-1}b \\ \hline c_B B^{-1}A - c^T & c_B B^{-1}b \end{array}

\begin{array}{rrrr|r} & x_1 & x_2 & x_3 & \\ \hline x_2 & -2 & 1 & 0 & -3 \\ x_3 & 3 & 0 & 1 & 7 \\ \hline z & 2 & 0 & 0 & 3 \end{array}

The only choice of pivot element is $y_{12}$, so $x_2$ is the leaving variable, while $x_1$ is the entering variable.

\begin{array}{rrrr|r} & x_1 & x_2 & x_3 & \\ \hline x_1 & 1 & \frac12 & 0 & \frac32 \\ x_3 & 0 & -\frac32 & 1 & \frac52 \\ \hline z & 0 & 1 & 0 & 0 \end{array}

Therefore, the optimal BFS of the problem is $\left(\dfrac32,0,\dfrac52\right)^T$.

• Thank you very much for your help! – THISISIT453 Jan 7 '16 at 16:51