geometrylinear programmingpolyhedra
Find all the extreme points of the polyhedral set, $X=\{(x_1,x_2,x_3):x_1-x_2+x_3\leq 1, x_1-2x_2\leq 4, x_1,x_2,x_3\geq 0\}$
I usually start out by drawing the feasible region but I couldn't do it for this one because it has another variable $x_3.$ How should I go about it? Is it possible to find the extreme points without having to depend on a drawing?
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.
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.
Best Answer
You said that in two dimensions you would simply draw the feasible set and then visually check where the vertices are. We can do the same for higher dimensions without drawing anything. You will have observed that the vertices of the feasible set are where two constraints intersect. And this observation we can use to find the vertices of higher dimensional polyhedra. We have to intersect all combinations of(in this case) 3 constraints with each other and check if the point of intersection is feasible. If it is feasible, then it is a vertex.
For example, if we intersect the two hyperplanes $x_1-x_2+x_3 =1$ with $x_1-2x_2=4$ and $x_1=0$ we obtain the following system of equations:
$$ \left[\begin{array}{rrr|r} 1 & 0 & 0 & 0 \\ 1 & -1 & 1 & 1 \\ 1 & -2 & 0 & 4 \\ \end{array} \right] $$ Solving it yields the point (0,-2,-1). However, this point is not feasible for $x_2\geq 0$, so we can discard it.
Next, we intersect $x_1-x_2+x_3 =1$ with $x_1-2x_2=4$ and $x_2=0$ and obtain (4,0,-3) as a solution. Since this point violates $x_3\geq 0$, we can also discard it.
Then we intersect $x_1-x_2+x_3 =1$ with $x_1-2x_2=4$ and $x_3=0$ and find (-2,-3,0), which violates $x_1 \geq 0$. So far, we haven't been lucky.
Next, we intersect $x_1-x_2+x_3 =1$ with $x_1=0$ and $x_2=0$ and obtain (0,0,1) as a candidate for a vertex. It is feasible for all the nonnegativity constraints but we also have to check whether it is feasible for $x_1-2x_2\leq4$ as well. Plugging it in yields $0-0 = 0 \leq 4$ so the constraint holds. We have found our first vertex!
Now, we intersect $x_1-x_2+x_3 =1$ with $x_1=0$ and $x_3=0$ and obtain (0,-1,0), which again violates a nonnegativity constraint ($x_2 \geq 0$).
Intersecting $x_1-x_2+x_3 =1$ with $x_2=0$ and $x_3=0$ results in (1,0,0) which is cleary nonnegative. Moreover, $1-2\cdot 0 = 1 \leq 4$ holds as well. Hence, we have found a second vertex.
We now intersect the constraint $x_1-2x_2=4$ with $x_1=0$ and $x_2=0$ and find that there is no solution.
We then intersect $x_1-2x_2=4$ with $x_1=0$ and $x_3=0$ and obtain (0,-2,0), which is infeasible for $x_2 \geq 0$.
As the next combination we intersect $x_1-2x_2=4$ with $x_2=0$ and $x_3=0$ and obtain (4,0,0), which is nonnegative but violates $4-0+0 = 4 \leq 1$.
Lastly, we intersect $x_1=0$ with $x_2=0$ and $x_3=0$ and, trivially, obtain the origin, which also satisfies the other two constraints. Thus, (0,0,0) also is a vertex.
The vertices we have found are (0,0,0),(0,0,1),(1,0,0).