3
$\begingroup$

Could someone please explain in detailed steps how to apply a sensitivity analysis to such problem:

$$maximize \ \ 2x_1 + 3x_2 \\ s.t. \ \ 4x_1+3x_2≤600 \\ 2x_1+2x_2≤320 \\ 3x_1+7x_2≤840 \\ x_i≥0$$

The goal is it to determine the boundaries of $x_2$.

$\endgroup$
  • 1
    $\begingroup$ Is the maximised quantity meant to be ... $3x_2$? $\endgroup$ – almagest Jul 8 '16 at 18:18
  • $\begingroup$ Yes of Course! Thank you! $\endgroup$ – Bastian Jul 8 '16 at 18:35
  • $\begingroup$ @BastianSchoettle Do you speak german ? $\endgroup$ – callculus Jul 8 '16 at 19:52
  • $\begingroup$ Yes, why are you asking? $\endgroup$ – Bastian Jul 8 '16 at 20:20
  • 1
    $\begingroup$ Because I want to talk about the semi-final yesterday. No, I have a link to a document in german. I would combine it with my answer. $\endgroup$ – callculus Jul 8 '16 at 20:24
1
$\begingroup$

To conduct a sensitivity analysis the final tableau is needed.

Basis   x1     x2     s1      s2      s3     RHS
x3      0       0      1     -2.375   0.25   50
x1      1       0      0      0.875  -­0.25   70
x2      0       1      0     -­0.375   0.25   90
z       0       0      0      0.625   0.25   410

The variables $x_1,x_2$ and $x_3$ are in the basis. Now it can be analyzed under which condition $x_2$ remains in the basic.

Lower bound for the parameter of $x_2$:

We take the reciprocal of every positive value of the non-basic variables in the $x_2$-row at multiply them by the corresponding objective function values. Then we take the minimum of it. In this case we have only one fraction:

$min\left( \frac{0.25}{0.25} \right)=\frac{0.25}{0.25}=1$

If there would be no positive values the lower bound would be $-\infty$.

Upper bound for the parameter of $x_2$:

We take the reciprocal of every negative value of the non-basic variables in the $x_2$-row at multiply them by the corresponding objective function values. Then we take the maximum of it. In this case we have only one fraction as well:

$max\left( \frac{0.625}{-0.375} \right)=\frac{0.625}{-0.375}=-\frac53$

If there would be no negative values the upper bound would be $\infty$.

To get the final lower/upper bound we take the value of the parameter of the initial tableau (objective function) and substract the identified values above.

Lower bound $3-1=2$

Upper bound $3-(-\frac53)=3+\frac53=4\frac23$

For further information see here, especially page 10 and 11. If you have any question about it feel free to ask.

$\endgroup$
  • $\begingroup$ Thank you very much! It's a straight forward procedure. I just have to practice it a bit to remember it correctly. Much better explained than in class. Good work! $\endgroup$ – Bastian Jul 9 '16 at 10:44
  • $\begingroup$ Could you explain how to apply this to values in the RHS column? $\endgroup$ – Bastian Jul 10 '16 at 15:37
  • $\begingroup$ @BastianSchoettle You mean the RHS at the final table ? You just have to apply the simplex algorithm. $\endgroup$ – callculus Jul 10 '16 at 15:39
  • $\begingroup$ Yes, question is how to determine the boundaries of $b_1$ (b is your RHS column) without changing the optimal solution. $\endgroup$ – Bastian Jul 10 '16 at 15:43
  • 1
    $\begingroup$ @BastianSchoettle First question: Have a look at page 4-5. You make a table. You divide the RHS by the corresponding values $a_{ir}$. The index ir means that you do not regard decision variables in the basis. Then you calc ulate the upper and lower bounds of every column. In you case $s_2$ and $s_3$ are not in the basis. thus the lower bound for $s_2$ and $s_3$ respectively are $320-min(70/0.875)=320-80=240$ and $840-min(50/0.25;90/0.25)=640$. And the lower bound of $s_1$ is just $600-50$. 50 is the value of $s_1$ at the final table. $\endgroup$ – callculus Jul 10 '16 at 17:14
1
$\begingroup$

I am not particularly keen to do your homework for you "in detail". But here is a starting point. The red line is a contour of $2x+3y$. The blue line is $4x+3y=600$; the orange line is $x+y=160$; the green line is $3x+7y=840$. The other lines are $x\ge0,y\ge0$.

The first question to settle is obviously where the allowed area is. It is in fact the area "below" the green, orange and blue lines but in the first quadrant. So the allowed area is the irregular pentagonal area shown in the plot.

Ignoring sensitivities we would maximise $2x+3y$ at the intersection of the green and orange lines, because we want the red line to be as far "upwards" as possible (whilst keeping its slope fixed).

You say nothing in the question about what kind of sensitivity analysis you want. There are a whole range of things you can change. You can "change the RHS", meaning that you shift the constraint lines, whilst keeping their slopes unchanged. Here you can see that the blue line is a "non-binding" constraint - shifting it will not change the optimisation for unless you shift it further to the left than the intersection of the green and orange lines. On the other hand, the green and orange constraints are "binding" - any shift however small will shift the optimisation.

Another sensitivity is to "change the objective function coefficients". In other words you change the coefficients 2, 3 in $2x+3y$. That has the effect of changing the slope of the red line and hence the optimisation.

Finally, of course, you can change the coefficients in the constraints, thus changing the slopes of the blue, green, orange lines. Again small changes to the blue line will make no difference, but small changes to the orange and green lines will.

enter image description here

$\endgroup$
  • $\begingroup$ It's actually not my homework but still thank you for your answer! I have an exam in a couple of days about linear programming but there is no script for it and some things didn't really made much sense during the classes so that's the most efficient way and usually offers different approaches from different people which is amazing. $\endgroup$ – Bastian Jul 8 '16 at 19:22
  • $\begingroup$ @BastianSchoettle Ok, glad to help. Good luck in your exam!. It is 8:30pm here, and I am off to have supper! $\endgroup$ – almagest Jul 8 '16 at 19:26
  • $\begingroup$ I'm sure it's about changing the coefficients to there maximum boundaries so that the optimal solution won't change. $\endgroup$ – Bastian Jul 8 '16 at 19:30
  • $\begingroup$ Enjoy your supper and thank you! $\endgroup$ – Bastian Jul 8 '16 at 19:35

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.