0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

You can use my python function for this: https://github.com/r4ndompuff/polyhedral_set

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.