1
$\begingroup$

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}

$\endgroup$
5
  • 2
    $\begingroup$ Write the tableau first, then apply dual simplex. You may find a MathJax template for simplex tableau on Mathematics Meta. $\endgroup$ Nov 11, 2018 at 19:57
  • $\begingroup$ @GNUSupporter8964民主女神地下教會 thanks for the hint! I'll work on it. $\endgroup$
    – user441848
    Nov 14, 2018 at 0:31
  • $\begingroup$ @GNUSupporter8964民主女神地下教會 but in the exercise its write directly the complete optimal tableau. With this I understand that no need to apply dual simplex is needed. am I wrong? $\endgroup$
    – user441848
    Jan 2, 2019 at 3:25
  • $\begingroup$ Thx for your update to the question. When I posted my comment, the optimal tableau wasn't there. $\endgroup$ Jan 14, 2019 at 12:58
  • $\begingroup$ @GNUSupporter8964民主女神地下教會 :) nop It wasn't but the statement was already there. $\endgroup$
    – user441848
    Jan 17, 2019 at 4:34

1 Answer 1

2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Thank you so much ^^ $\endgroup$
    – user441848
    Jan 2, 2019 at 18:26
  • $\begingroup$ btw what do you mean with your note? $\endgroup$
    – user441848
    Jan 2, 2019 at 18:26
  • $\begingroup$ It was stated "without ejecuting simplex table", so I’m not sure if my solution is executing or not. Anyway the optimal table must have the found numbers. Good luck. $\endgroup$
    – farruhota
    Jan 2, 2019 at 18:35
  • $\begingroup$ Definitely it's not ejecuting the simplex method. $\endgroup$
    – user441848
    Jan 2, 2019 at 18:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .