[Math] Find the final tableau knowing the optimal solution

linear programmingoperations researchoptimizationproof-verification

Consider the following linear program $$\displaystyle \max z=5x_1+2x_2+3x_3\\ s.t. x_1+5x_2+2x_3\le b_1\\ x_1-5x_2-6x_3\le b_2 \\
x_1,x_1,x_3\ge0$$

If the optimal solution is reached at $x_1=30,x_5=10,$ write directly the complete optimal tableau, whitout executing the simplex method. And then find the values of $b_1$ and $b_2$.

Attempt

The optimal tableau should have the following structure

\begin{array}{r|rrrrr|r}
& x_1 & x_2 & x_3 & x_4 & x_5 & \\ \hline
z & 0 & & & & 0 & 150 \\ \hline
x_1 & 1 & & ? & & 0 & 30 \\
x_5 & 0 & & & & 1 & 10 \\
\end{array}

I don't know how to calculate what is inside the tableau. How will I calculate $B^{-1}$? Please help me.

I know the last simplex tableau in matrix form is this

\begin{array}{|r r|r}
c_BB^{-1}N-c & c_BB^{-1} & c_BB^{-1}b \\ \hline
B^{-1}N & B^{-1} & B^{-1}b
\end{array}

Best Answer

From the given optimal solution $z(x_1,x_2,x_3,x_4,x_5)=z(30,0,0,0,10)=150$, you can find: $$x_1+5x_2+2x_3+x_4=b_1=\color{red}{30},\\ x_1-5x_2-6x_3+x_5=b_2=\color{red}{40}, $$ where $x_4$ and $x_5$ are the slack variables.

Since in the optimal table only the slack variable $x_4$ is replaced with $x_1$, then the intersection of $x_4$ row and $x_1$ column was the pivot element, which corresponds to the original value $1$. Hence the row remained from the initial table: $$\begin{array}{r|rrrrr|r} & x_1 & x_2 & x_3 & x_4 & x_5 & \\ \hline z & 0 & & & & 0 & 150 \\ \hline x_1 & \boxed 1 & \color{red}5 & \color{red}2 & \color{red}1 & 0 & 30 \\ x_5 & 0 & & & & 1 & 10 \\ \end{array}$$ In order to get $0$ as the first element in the row $z=5x_1+2x_2+3x_3$, where the first element was $-5$ initially, pivot row must have been multiplied by $5$ and added to it: $$\begin{array}{r|rrrrr|r} & x_1 & x_2 & x_3 & x_4 & x_5 & \\ \hline z & 0 & \color{red}{23} & \color{red}7 & \color{red}5 & 0 & 150 \\ \hline x_1 & \boxed 1 & \color{red}5 & \color{red}2 & \color{red}1 & 0 & 30 \\ x_5 & 0 & & & & 1 & 10 \\ \end{array} $$ In order to get $0$ as the first element in the row $x_5$, where the first element was $1$ initially, pivot row must have been multiplied by $-1$ and added to it: $$\begin{array}{r|rrrrr|r} & x_1 & x_2 & x_3 & x_4 & x_5 & \\ \hline z & 0 & \color{red}{23} & \color{red}7 & \color{red}5 & 0 & 150 \\ \hline x_1 & \boxed 1 & \color{red}5 & \color{red}2 & \color{red}1 & 0 & 30 \\ x_5 & 0 & \color{red}{-10} & \color{red}{-8} & \color{red}{-1} & 1 & 10 \\ \end{array} $$ Note: I am not sure if this is ejecuting (executing). But it is reverse engineering (backwards working).

Related Question