Need help finding unknowns in simplex tableau.

Question

I need help with this homework problem.

The objective is to maximize $2x_1 - 4x_2$, and the slack variables are $x_3$ and $x_4$. The constraints are $\le$ type.

Tableau
$\begin{matrix}z & x_1 & x_2 & x_3 & x_4 & \text{RHS}\\ 1 & b & 1 & f & g & 8\\ 0 & c & 0 & 1 & 1\over5 & 4\\ 0 & d & e & 0 & 2 & a\end{matrix}$

a) Find the unknowns $a$ through $g$.
b) Find $B^{-1}$.
c) Is the tableau optimal?

I can't figure out which columns make up the basis. Can anyone please help me get started?

Answer 1

Additional notations

• $A \in M_{m\times n}(\Bbb R)$ ($m\le n$) has rank $n$ and basis matrix $B$.
• $x_B$ denotes the basic solution.
• $c_B$ denotes the reduced objective function so that $c^T x=c_B^T x_B$. (So the order/arrangement of basic variables is very important.)

Unknown entries in the tableau

• From the $x_3$ column, we know that $x_3 = 4$ is a basic variable, so $f=0$.
• The current objective value is $8$. Since $x_i$'s are nonnegative, this forces $x_1 = 4$, $x_2 = 0$, $a = 4$, $b = 0$, $c = 0$, $d = 1$.
• As OP's comment suggests, $B^{-1}$ can be directly read under the $x_3,x_4$ columns because the initial tableau has the form \begin{array}{cc|c} -c^T & 0 & 0 \\ \hline A & I & b \end{array} Multiplying $B^{-1}$ on both sides gives \begin{array}{cc|c} c_B^T B^{-1}A-c^T & c_B^T B^{-1} & c_B^T B^{-1}b \\ \hline B^{-1}A & B^{-1} & B^{-1}b \tag1 \label1 \end{array} It's easy to (mentally) calculate $B = \begin{bmatrix} 1 & -1/10 \\ 0 & 1/2 \end{bmatrix}$.

The simplex tableau becomes \begin{array}{r|rrrr|r} z & x_1 & x_2 & x_3 & x_4 & \text{RHS} \\ \hline 1 & 0 & 1 & 0 & g & 8 \\ \hline 0 & 0 & 0 & 1 & 1/5 & 4 \\ 0 & 1 & e & 0 & 2 & 4 \end{array} $c^T = (2,-4)$ is given, and $c_B^T = (0,2)$ and $x_B^T = (4,4)^T$ since $x_3,x_1$ are current basic variables. (Note the arrangement of $x_3,x_1$ in the above tableau.) This allows us to (mentally) calculate $g$ using \eqref{1} $$(0,g) = c_B^T B^{-1} = (0,2) \begin{bmatrix} 1 & 1/5 \\ 0 & 2 \end{bmatrix} = (0,4). $$ Therefore, the current solution is optimal. Finally, to find $e$ \eqref{1}, we focus on the $x_2$ column. \begin{align} 1 &= c_B^T B^{-1} {\bf a}_2 - c_2 \\ -3 &= (0,4){\bf a}_2 \\ 4a_{22} &= -3 \\ a_{22} &= -\frac34 \end{align} Calculate $B^{-1}{\bf a}_2$ in \eqref{1}. \begin{align} B^{-1}{\bf a}_2 &= (0,e)^T \\ {\bf a}_2 &= B (0,e)^T \\ (\star, a_{22})^T &= (\clubsuit,e/2)^T \\ e &= 2a_{22} = 2\left( -\frac34 \right) = -\frac32 \end{align} Hence the optimal tableau is \begin{array}{r|rrrr|r} z & x_1 & x_2 & x_3 & x_4 & \text{RHS} \\ \hline 1 & 0 & 1 & 0 & 4 & 8 \\ \hline 0 & 0 & 0 & 1 & 1/5 & 4 \\ 0 & 1 & -3/2 & 0 & 2 & 4 \end{array}