1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.