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?


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


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.