Graph the following system of inequalities. Show (by shading in) the feasible region.
$$x+2y\leq 12$$
$$2x+y\leq 12$$
$$x\geq 0 , y \geq 0$$
I would like to know how to graph these inequalities.
[Math] Graph the following system of inequalities
graphing-functionsinequality
Related Solutions
First draw the line $y=3$. It will separate the plane into two regions: shade the entire region which contains the points $(x,y)$ such that $y<3$.
(If you are not sure on which side of the line that region is, pick any side and choose any point on that side. Replace the values of the coordinates of the chosen point in the inequality. If the inequality is true for these values, shade that side. Otherwise, shade the other side.)
Repeat with the other inequality, probably using other colors or marks to avoid confusion. Pretend the previous line and shading aren't there. The drawings will most probably overlap.
Now: the intersection will be the region which is shaded by both colors or marks. The union will be the whole region which is covered by at least one color or mark.
This can be extended to any number of inequalities.
As @Milten noted in the comments, the number of solutions to a system of linear inequalities (over $\mathbb{R}$) may only be $0,1$ or infinite. This is because of convexity: if $v,w$ are two solutions, then $\alpha v + (1-\alpha)w$ is a solution for any $0 \leq \alpha \leq 1$, and for $v \neq w$ this gives an infinite number of solutions. This means that you only need to find two distinct solutions to decide whether there is an infinite number of them.
As you say, linear programming can be used to decide whether there is any solution, but with a bit more work it can also tell you whether there are multiple solutions or just one. Heuristically, you can use linear programming to maximize a random objective function $c\cdot x$ over the feasible region; one would expect that if the feasible region has more than one points then with high probability you would obtain multiple solutions. Granted, this is just a heuristic, but for practical purposes it should be good enough. (See also this answer.)
For an honest polynomial-time algorithm to decide whether the solution is unique you may want to take a look at this article, in which the authors reduce the problem of deciding uniqueness to finding the solution to another linear program. The article also contains a survey of previous results on this problem. Sadly, all the (legal) links I could find to the article are paywalled. If you would like to, I can describe their solution in more detail.
Finally, I would just like to note that in general you "can't avoid" linear programming in the sense that deciding whether there is at least one solution to a linear program is almost as difficult as finding an optimal solution. This is true in the sense that if you can decide whether there is a solution, then you can use a binary search-like algorithm to find an optimal solution in reasonable time.
Best Answer