2

I've just had a lecture in which the simplex method was described and solved graphically (not using the tableau method I've seen after a quick Google).

The professor would give us examples and we'd identify the function to maximize/minimize and then write the constraints as inequalities. Then them in standard form as equalities. That all makes sense.

Then we were asked to graph them and for a constraint like $x> 4$. I can just draw in the line $x = 4$ and see it just be higher than that, which is fine. We then had to graph the function itself e.g. $4x_1 + 5x_2 > 13$. Am I correct that to do that, you just graph it as equal to $13$? And of course you know how to graph it based on rearranging it in terms of $x_2$ i.e. $x_2 = \dfrac {13 - 4x_1} 5$, right?

Then if I understand you shade the region in which all the constraints are met and the first point you reach meeting the criteria (from the left or right depending on min or max) is the optimal solution?

If I've misunderstood this, I'd like to know now. It seems to make sense but I don't feel very confident with it and I couldn't find much on Google.

Alex M.
  • 35,207
Christian
  • 23

1 Answers1

1

In principle, your understanding is correct. Small correction appears after you found the shaded region: You have to find the direction of optimisation. After that, depending on minimising, or maximising, you are interested in the ''first'' or ''last'' intersection/point of that region from that direction (and not left or right).

Stefan Gyürki
  • 908
  • I see, thank you! I didn't feel like my understanding was complete but the professor wasn't very good so that's unsurprising. How exactly do you ascertain the direction of optimisation? Does that come from the problem at hand e.g. if you wish to minimise costs then the direction is from a high number of dollars to a low number of dollars? – Christian Oct 06 '15 at 12:32
  • For example, if you have to maximise $x_1+2x_2$, then you can draw lines $x_1+2x_2=c$ for a few different values of $c$. I am sure that from the picture you will see in which direction the line is moving, when you are increasing/decreasing $c$. In other words, the direction of optimisation is parallel to the normal vector of the objective function. – Stefan Gyürki Oct 06 '15 at 19:04