In Linear programming, you want to optimize stuff. For example; minimize the costs and maximize the profit. We have a series of constraints, in my case on either 2 or 3 variables. You can draw them in a coordinate system and you'll get a feasible region. If I understood correctly; one of the vertexes of feasible region is the optimization.

  • How do you know which vertex is the solution to your problem? Also, how do you get the exact coordinates of the vertexes. Consider this example:

$$a \geq 0$$

$$ u \geq 0$$

$$ a + u \leq 20$$

$$5a + 8u \leq 120$$

If I draw this, I get a simple polygon. How do I find the coordinates of the vertexes and more importantly, how do I know that a certain vertex is the one I'm looking for? Let's say in this case I want to minimize, and maximize (just to help my understand both with 1 example).

  • $\begingroup$ If you have found $n$ candidates (maybe the vertices of the polygon), you can find the maximum by iterating over them in $O(n)$. Every inequality describes a half-plane, so the polygon you are looking for is the convex hull of the intersection points of the half-plane edges. $\endgroup$ – Niklas B. Mar 30 '13 at 14:37

To find the coordinates of the vertexes you have to change two of your inequalities by equalities and to sovle the sistem of two obtained equations. Taking all pairs of inequalities you will get all vertices. Then calculate the values of your function in the vertices and choice minimal/maximal of them.

  • $\begingroup$ Which in this case I believe would be $u = 6\dfrac{2}{3}$ and $a=13\dfrac{1}{3}$. Thanks $\endgroup$ – Ylyk Coitus Mar 30 '13 at 15:02

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.