Find all extreme points of 4 variable polyhedral set of dimension 3

Question

$$P = \{x\in\mathbb R^4_+ | x_1 + 2x_2 + 3x_3 + 4x_4 = 36, x_1 + x_2 + x_3 + x_4 \le 12\}$$ a) By enumerating all quadruplets of relevant constraints, find all extreme points of $P$.

I know 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 polyhedral. We have to intersect all combinations of constraints with each other and check if the point of intersection is feasible. If it is feasible, then it is a vertex. But the problem is the dimension of $P$ is $3$ and I can t find system equation to solve.

Answer 1

You have $6$ constraints (including the four lower bounds $x_i \ge 0$), and you want at least $4$ of them to be satisfied with equality. Because one of them is already an equality, there are $\binom{6-1}{4-1} = \binom{5}{3} = 10$ subsets of $4$ constraints to consider. I'll get you started:

1. Suppose $x_1 + 2x_2 + 3x_3 + 4x_4 = 36, x_1 = 0, x_2 = 0, x_3 = 0$. Then $x_4 = 9$ and $\sum_i x_i = 9 \le 12$, so $(0,0,0,9)$ is an extreme point of $P$.
2. Suppose $x_1 + 2x_2 + 3x_3 + 4x_4 = 36, x_1 = 0, x_2 = 0, x_4 = 0$. Then $x_3 = 12$ and $\sum_i x_i = 12 \le 12$, so $(0,0,12,0)$ is an extreme point of $P$.
3. Suppose $x_1 + 2x_2 + 3x_3 + 4x_4 = 36, x_1 = 0, x_3 = 0, x_4 = 0$. Then $x_2 = 18$ and $\sum_i x_i = 18 > 12$, so $(0,18,0,0)$ is not an extreme point of $P$.

I'll leave the remaining $7$ cases to you.