<s>[INST] Need help finding unknowns in simplex tableau. 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?
 [/INST] 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}
</s>