$$\max z=-x_1+3x_2 $$
$$\text{s.t.} -x_1+x_2\leq 2 $$
$$ -x_1+2x_2 \leq 6 $$
$$ x_1,x_2\geq 0 $$
Is there any way to find extreme points and directions/extreme directions of problems like this without using graphs?
After drawing the graph the extreme points becomes quite evident but I still cannot figure out a way to find the direction(s) of the set.
[Math] How to find the direction in linear optimization
linear programmingnonlinear optimizationnumerical optimizationoptimization
Best Answer
As for the extreme points:
The extreme points are at the intersections of the hyperplanes defining your feasible set. In total there are four hyperplanes in your example, namely:
\begin{align} -x_1+x_2= 2 \\ -x_1+2x_2 = 6 \\ x_1 = 0 \\ x_2 = 0 \end{align}
Intersecting the first two yields the point (2,4). However, it can only be an extreme point if it is feasible. Substituting it in equations 3 and 4 we obtain that it is indeed a feasible point and thus also an extreme point (checking equations 3 and 4 is sufficient because (2,4) necessarily has to be feasible for the first two equations as it is in their intersection).
Next, we check the intersection of the first and third equation and obtain (0,2). Since $2\geq 0$ it is valid for the fourth equation and since $0+2*2=4 \leq 6$ holds, it is also feasible for the second constraint. Thus, it is also an extreme point.
Intersecting the first and fourth equation yields the point (-2,0). We immediately see that it violates $x_1 \geq 0$ and thus it is not a feasible point and, hence, no extreme point.
The intersection of the second and third equation yields the point (0,3). Even though it satisfies the fourth constraint, it violates the first because $-0+3 =3 \not \leq 2$. Hence, it is not extreme point.
Two more intersections to go. The point (-6,0) is in the intersection of the second and fourth equation. Since $x_1$ is negative, the third constraint is violated and hence it is no feasible (and thus not extreme) point.
Lastly, intersection the last two equations yields (0,0), which again is feasible for all constraints.
Thus, the extreme points are (2,4), (0,2) and (0,0). The graph of the feasible set confirms our calculations:
Regarding the extreme directions: what are those in this example? If you can read them off the graph, try, for example, to construct one using the extreme points.