How to read Linear Program from an optimal tableau

960 Views Asked by At

Suppose we are given an optimal tableau and the objective function. How can we determine the RHS of constraints or if possible the constraint equations?

For example consider the given tableau with objective to maximize $z = 5x_1 + 6x_2 + 8x_3$

Example tableau

We can tell that there are two sets of constraints. How can we determine the RHS of each constraint say $A$ and $B$?

1

There are 1 best solutions below

2
On BEST ANSWER

It is impossible to determine the initial RHS of each constraint without the initial LHS. Given two initial constraints $\eqref{A}$ and $\eqref{B}$.

\begin{align} \sum_{j=1}^n a_{1j} x_j &= b_1 \tag{A} \label{A} \\ \sum_{j=1}^n a_{2j} x_j &= b_2 \tag{B} \label{B} \end{align}

If none of these two equations is redundant (which is true in this case since the basic solution in the given optimal tableau is not degenerate), you can change one constraint by adding another to it. This will give you a different initial RHS.

\begin{align} \sum_{j=1}^n a_{1j} x_j &= b_1 \tag{A'} \label{A'} \\ \sum_{j=1}^n (a_{1j} + a_{2j}) x_j &= b_1 + b_2 \tag{B'} \label{B'} \end{align}