How get the extreme directions of an unbounded feasible region The following constraints form a feasible region.
$-x_1+x_2 \le 2$
$-x_1+2x_2 \le 6$
$x_1,x_2 \ge 0$
The feasible region have three extreme points: $e_1=\left[\begin{array}{cc}
  0\\
  0
\end{array}\right]$ $e_2=\left[\begin{array}{cc}
  0\\
  2
\end{array}\right]$ $e_3=\left[\begin{array}{cc}
  2\\
  4
\end{array}\right]$
What is the procedure that I need to follow to extract the extreme direction from this data?
Extrene Direction: An extreme direction of a convex set is a direction of the set that cannot be represented as a positive combination of two distinct directions of the set.
 A: In standard format, we get the system:
\begin{equation*}
\begin{alignedat}{2}
-x_1 & {}+{} & x_2&{}+{}&x_3& &&= 2\\
-x_1&{}+{}&2x_2& &&{}+{}&x_4\ &=6
\end{alignedat}
\end{equation*}
with all variables positive. The matrix of the system is:
$$A=\begin{pmatrix}-1&1&1&0\\
-1&2&0&1\end{pmatrix}.$$
Any extreme direction $d$ can be obtained as:
$$d=\begin{pmatrix}-B^{-1}a_j\\e_j\end{pmatrix},$$
where $B$ is a $2\times 2$ invertible submatrix of $A$, $a_j$ is the $j$th column of $A$, not in $B$, such that $B^{-1}a_j\leq0$ and $e_j$ is the canonical vector with a one in the position of the column $a_j$.
For example, let $B=\begin{pmatrix}1&0\\0&1\end{pmatrix}$, invertible submatrix of $A$. We have that $B^{-1}a_1=\begin{pmatrix}-1\\-1\end{pmatrix}\leq0$. The canonical vector $e_1$ has a one in the position of $a_1$, i. e., $e_1=\begin{pmatrix}1\\0\end{pmatrix}$.
Therefore, we get the direction $$d=\begin{pmatrix}1\\0\\1\\1\\\end{pmatrix},\ \text{writing }-B^{-1}a_1\text{ in the position of }B\text{ and }e_1\text{ in the left entries.}$$
In our original system, by erasing the variables $x_3$ and $x_4$, we get the extreme direction $\begin{pmatrix}1\\0\end{pmatrix}$.
A: Draw the LP using the graphical method (Just plot the conditions as line on the $x_1$ and $x_2$ axis) let $x_1$ be the horizontal axis and $x_2$ be the vertical axis. Find the line that remains in the feasible region as $x_1$ tends to infinity. and take the ratio of increase in $x_2$ and $x_1$. So if you have a line $-x_1 +2x_2 \geq 8$ that stays in the feasible region as $x_1$ tends to infinity, then the extreme direction is $(2,1)$ as when $x_1$ increases by $2$ then $x_2$ increases by $1$.
Another example: you have a line $x_2 \geq 2$,that stays in the feasible region as $x_1$ tends to infinity, then the extreme direction is $(1,0)$.
