0
$\begingroup$

Question: Consider the following linear program \begin{equation} \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} \end{equation}

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?

$\endgroup$
0
$\begingroup$

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$.

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

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.