Formulating LPP from given optimal table in Simplex method

Question

I have a problem set in my assignment sheet that asks to formulate a Linear Programming Problem from a given optimal solution and we know that method used is Simplex method.

What is the correct procedure for going in reverse order? I know our basic thinking to go for such a problem is to make s1 and s2 equal to 0 in z row.

Here is the snapshot of the problem: Question in Assignment

Answer 1

To explain why the basis matrix can be read from the given simplex tableau, I introduce these additional symbols:

• $A \in M_{m\times n}(\Bbb R)$ ($m\le n$) has rank $n$ and current basis matrix $B$.
• $x_B$ denotes the current 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.)

As the comment from the asker of the question Need help finding unknowns in simplex tableau. suggests, $B^{-1}$ can be directly read under the columns for slack variables 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 given that $B^{-1} = \begin{bmatrix} 2/7 & -1/7 \\ -1/7 & 4/7 \end{bmatrix}$. It's easy to (mentally) calculate $B = \begin{bmatrix} 4 & 1 \\ 1 & 2 \end{bmatrix}$. To calculate $A$ in the initial tableau, we left multiply $B^{-1}A$ by $B$. ($A = B(B^{-1}A)$). The third column of $A$ is $$\begin{bmatrix} 4 & 1 \\ 1 & 2 \end{bmatrix} \begin{bmatrix} 1/7 \\ 17/7 \end{bmatrix} = \begin{bmatrix} 3 \\ 5 \end{bmatrix}.$$ $$\therefore A = \begin{bmatrix} 1 & 4 & 3 \\ 2 & 1 & 5 \end{bmatrix}$$ $$b = B(B^{-1}b) = \begin{bmatrix} 4 & 1 \\ 1 & 2 \end{bmatrix} \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 1 \\ 2 \end{bmatrix}$$ To compute the objective function $c$, note that \begin{align} c^T &= c_B^T B^{-1}A-(c_B^T B^{-1}A-c^T) \\ &= \begin{bmatrix} 4\\2 \end{bmatrix}^T \begin{bmatrix} 0 & 1 & 1/7 \\ 1 & 0 & 17/7 \end{bmatrix} - \begin{bmatrix} 0 & 0 & 17/7 \end{bmatrix} \\ &= \begin{bmatrix} 2 & 4 & 3 \end{bmatrix} \end{align}

Therefore, the LPP is to maximize $2x_1+4x_2+3x_3$ subject to $$x_1+4x_2+3x_3 \le 1 \\ 2x_1+x_2+5x_3 \le 2 \\ x_1,x_2,x_3 \ge 0.$$