# How to find extreme points for a linear program in $3$ variables?

It is rather easy to find extreme points in the $2$ variable case. How to find them for higher dimensions, say, in $3$ variables? For instance,

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

• You have four inequalities -- the non-negativity conditions are included here -- so take them three at a time, solve for $x_1,x_2,x_3$, and then find $-3x_1-2x_2-x_3$. For instance: $2x_1+x_2-x_3=2$, $x_1=0$, $x_3=0$ implies that $x_2=2$; $-3\cdot0-2\cdot2-0=-4$ is the objective value at that corner. (Make sure your solutions are feasible points!) – Christopher Carl Heckman Apr 4 '16 at 6:45
• why also find the objective value at each extreme point? – 104078 Apr 4 '16 at 6:48
• it is to find the optimal, right. Nothing to do with finding extreme points. – 104078 Apr 4 '16 at 6:50
• It has everything to do with extreme points actually. The central idea in linear programming is the following: the optimal value of a linear function defined on a polyhedron (the feasible region bounded by the constraints) is attained at an extreme point of the feasible region, provided a solution exists. In other words, if an optimal solution(s) exists, then it is among the list of extreme points of the feasible region. – user3816 Jul 25 '18 at 14:11

In your example, you can have arbitrary small values for your objective function. Just take $x_1=0,x_2=c,x_3=c$, then the constraint is satisfied for all $c\geq 0$, and you can make $c$ arbitrarily large, so your objective function $-3x_1-2x_2-x_3$ becomes arbitrarily small. In general you can use the simplex algorithm.
• However, $0 \le x_2 = c$, so $c$ can't be arbitrarily small. Hence, the minimization instruction. – Christopher Carl Heckman Apr 4 '16 at 6:59