I'm supposed to find the basic solutions of the given LPP graphically. I know what a bfs means, I can find that in other way (I mean by method mentioned in this post), but I don't know how to do it graphically. The system is:- $$2x + 3y \leq 21$$$$ 3x - y \leq 15$$$$ x + y \geq 5$$$$ y \leq 5$$ $$ x, y \geq 0$$ Any hint/solution would be appreciated. Thanks!
Asked
Active
Viewed 793 times
0
-
Since you only have two variables you can plot each inequality in the plane and take the intersection, maybe this is what they mean by graphically? – Jürgen Sukumaran Feb 03 '19 at 13:12
-
@TonyS.F. but that'll be a feasible solution. Not bfs if I'm not wrong... – Ankit Kumar Feb 03 '19 at 13:13
-
It depends on which one you pick, of course. You will get a polygon of sorts in the plane and if you pick a vertex you will have BFS. – Jürgen Sukumaran Feb 03 '19 at 13:14
1 Answers
1
For a linear program like this, the set of all feasible solutions is the intersection of half spaces and thus a polyhedron. A BFS corresponds to a vertex of this polyhedron.
Now, since we only have 2 variables we can plot all our half spaces in the plane and take the intersection to get a polygon. Then, the BFS are just the vertices of this polygon.
Here is a graph of your problem (more or less)
From that graph we can see (0,5), (5,0), (3,5), and (6,3) are all BFS.
Jürgen Sukumaran
- 7,645