$$\begin{array}{ll} \text{minimize} & x_1+2x_2+x_3\\ \text{subject to} & 3x_1+3x_2+x_3\ge3\\ &x_1+x_2+x_3\le2\\ & x_1,x_2,x_3\ge0\end{array}$$

For the given linear programming problem, I am tasked to find the extreme points graphically. I believe the points (0, 1/2, 3/2) and (1/2, 0, 3/2) are the only extreme points but there are also other points such as (1, 0, 0) and (0, 1, 0) to name a few that satisfy all constraints and have three active constraints which meets the critieria of being a basic feasible solution/extreme point??

I'm just really confused when it comes to finding extreme points with three variables, I just want somebody to tell me if (0, 1/2, 3/2) and (1/2, 0, 3/2) are the only extreme points or if there are more that I need to find. Thanks!

  • $\begingroup$ Are you allowed to use the dual LP? $\endgroup$ – Rodrigo de Azevedo Oct 20 '19 at 20:18
  • $\begingroup$ Haven't learned about duality yet, I'm required to solve it graphically only. $\endgroup$ – Gordqir Oct 20 '19 at 20:26
  • $\begingroup$ So, try to draw a picture. You are in the 1st octant, co if should be quite easy. To draw a plane, mark the intersections with axes. Then draw three triangles and so on. $\endgroup$ – szw1710 Oct 20 '19 at 20:30
  • $\begingroup$ I don't think it's at all trivial to draw a three-dimensional picture and determine the extreme points from that. True, it is all within the first octant and there are only two planes to draw, but it is not easy to accurately draw arbitrary planes. If I were given this problem I would enumerate the basic solutions (of which there are $\binom 52$) and check each for feasibility, since we cannot use duality here. $\endgroup$ – Math1000 Oct 20 '19 at 21:46
  • $\begingroup$ Okay so I drew the graph and even though it's a bit difficult to picture which points are within the feasible region, I think it's safe to say that (0, 1/2, 3/2) and (1/2, 0, 3/2) are not the only extreme points, right? For example, (1, 0, 0) would indeed be considered an extreme point in this problem? This was also confirmed by enumerating the basic solutions. $\endgroup$ – Gordqir Oct 20 '19 at 21:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.