0

Let an LP of the form:

$\max \ 2x_1+2x_2+x_3$

$s.t. \ x_1+2x_2+x_3 \leq 4 =b_1$

$\ \ \ \ \ \ \ \ 2x_1+x_2+x_3\leq3 =b_2$

$\ \ \ \ \ \ \ \ x_1,x_2\geq0$

And let the final tableau be:

enter image description here

being $x_4$ and $x_5$ the slack variables.

Question: Which action is more profitable? Buying more resources of $b_1$ or $b_2$? And how much should I buy?

1 Answers1

1

Suppose we increase resounces $b_i$ by $\delta e_i$, the profit would change by $$\delta c_B'B^{-1}e_i=\delta \begin{pmatrix} 2 & 2\end{pmatrix}B^{-1}e_i$$

For the first resource, $B^{-1}e_1=\begin{pmatrix} \frac23 \\ -\frac13 \end{pmatrix}$ and for the second resources $B^{-1}e_2=\begin{pmatrix} -\frac13 \\ \frac23 \end{pmatrix}$, hence they are equally profitable.

Suppose we increase resources of $b_i$, the basis remains the same if

$$x_B+\delta B^{-1}e_i \geq 0$$

For resource $1$, we have $$\begin{pmatrix} \frac53 \\ \frac23 \end{pmatrix}+\delta \begin{pmatrix} \frac23 \\ -\frac13 \end{pmatrix} \geq \begin{pmatrix} 0 \\ 0 \end{pmatrix}$$

Hence if $\delta \leq 2$, the basis remains the same. (remark: However, if $\delta > 2$, we will have to continue with dual simplex.)

We can repeat the same thing for resource $b_2$.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149