# Linear Programming question - Optimal solution

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

• 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. – Niklas B. Mar 30 '13 at 14:37

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