How can I start looking for extreme points in convex polytopes?

Question

Consider $S \subset \mathbb{R^2}$ a set such that $\forall (x_1,x_2) \in S$ :

$ 2x_1+3x_2 \leq 6 $

$-2x_1+ x_2 \leq 2$

$x_1 \geq 0 , x_2 \geq 0$

How can I find extreme points of $S$? What is a good strategy to start tackling this kind of problem?

Answer 1

Because $x_1,x_2\geqslant0$ we can write the inequalities as equalities with the use of slack variables: \begin{align} 2x_1+3x_2+s_1&=6\\ -2x_1+x_2+s_2&=2\\ x_1,x_2,s_1,s_2&\geqslant 0. \end{align} Extreme points are equivalent to basic feasible solutions. Because $S\subset\mathbb R^2$, a basic solution has two basic variables; hence there are six candidates: $$(x_1,x_2), (x_1,s_1), (x_1,s_2), (x_2,s_1), (x_2,s_2), (s_1,s_2).$$ Solve the system of equations by setting each nonbasic variable equal to zero; if the resulting solution is positive, then it is feasible, and hence a basic feasible solution. I'll leave the computations to you, but the extreme points we find in this process are $(0,0), (3,0), (0,2)$ (in terms of $(x_1,x_2)$).

Answer 2

Ummmm.... why don't you just plot it?

and analogously in higher dimensions: