Consider the polyhedral set $X$ defined by the inequalities:
$−3x_1 + x_2 \leq −2$,
$−x_1 + x_2 \leq 2$,
$−x_1 + 2x_2 \leq 8$,
$−x_2 \leq −2$,
$x_1, x_2 > 0$.
Find the extreme points and extreme directions of $X$.
I plotted these and found the extreme points to be $(4,6), (2,4), (\frac{4}{3},2)$. I don't know how to find the extreme directions from here. What is the method for doing this.
I have a formula which is a method for working out extreme directions below but I only get $(1,0)$ as an extreme direction when $(4,2)$ should also be an extreme direction according to solutions.
Consider the set
$X = {x : Ax ≤ b, x ≥ 0}$.
The direction of the set is characterized by the following conditions:
$d ≥ 0, d != 0,$ and $Ad ≤ 0$.
This defines a polyhedral cone, called recession cone.
To eliminate duplication, these directions may be normalized, e.g. $e^T d = 1$. Then the set
of recession directions of $X$ can be given by
$D = {d : Ad ≤ 0, e^T
d = 1, d ≥ 0}.$
Therefore, the extreme directions of $X$ are precisely the extreme points of $D$.
Best Answer
For finding the extreme directions you should make a homogeneous system out of all the constraints and also add another constraint 1d=1 (d1+d2+...+dn=1) and then choosing groups of new constraints and solving the systems. For this example we got:
−3d1+d2≤0
-d1+d2≤0,
-d1+2d2≤0,
-d2≤0,
d1+d2=1,
d1,d2≥0
Now since we got 2 dimensions and 7 constraints which one of them is equality constraint we should include it in our system, so we have to solve $\binom{7-1}{2-1}=6$ systems, each direction we find should be nono zero and we have to try it in other constraints to make sure it also satisfies other constraints. For instance, take the first constraint, the system:
−3d1+d2=0,
d1+d2=1
solves for (d1, d2) = (1/4, 3/4) which does not satisfy other constraints therefore not an extreme direction. But for
-d1+2d2=0,
d1+d2=1
direction found is (2/3, 1/3), which satisfies other constraints therefore it is an extreme direction.