Maximize $$ x_1 + 2x_2$$
\begin{align} x_1 – 4x_2 &\le 4 \\
-2x_1 + x_2 &\le 2 \\
-3x_1 + 4x_2&\le 12 \\
2x_1 + x_2 &\le 8 \end{align}
Identify all the extreme points and reformulate the problem in terms
of convex combination of the extreme points. Solve the resulting
problem. Is any extreme point degenerate? Explain.
Best Answer
There are two decision variables, so an extreme point corresponds to a point where two of the constraints are binding. There are four constraints, so there are a total of $\binom 42=6$ potential extreme points. We solve: \begin{align} x_1-4x_2 &= 4\\ -2x_1 + x_2 &= 2 \end{align} for $(x_1,x_2) = \left(-\frac{12}7,-\frac{10}7\right),\tag1$ \begin{align} x_1-4x_2 &= 4\\ -3x_1+4x_2&=12 \end{align} for $(x_1,x_2) = \left(-8,-3\right),\tag2$ \begin{align} x_1-4x_2 &= 4\\ 2x_1+x_2&=8 \end{align} for $(x_1,x_2) = \left(4,0\right),\tag3$ \begin{align} -2x_1+x_2&=2\\ -3x_1+4x_2&=12 \end{align} for $(x_1,x_2) = \left(\frac45,\frac{18}5\right),\tag4$ \begin{align} -2x_1+x_2&=2\\ 2x_1+x_2&=8 \end{align} for $(x_1,x_2) = \left(\frac32,5\right),\tag5$ \begin{align} -3x_1+4x_2&=12\\ 2x_1+x_2&=8 \end{align} for $(x_1,x_2) = \left(\frac{20}{11},\frac{48}{11}\right).\tag6$ Checking for feasibility, we find that $(2)$ and $(5)$ do not satisfy the constraints. Reforumulating the problem in terms of convex combinations of the extreme points, we have \begin{align} \max&\quad -\frac{32}7\lambda_1 + 4\lambda_3 + 8\lambda_4 + \frac{116}{11}\lambda_6\\ \mathrm{s.t.}&\quad \lambda_1+\lambda_3+\lambda_4+\lambda_6 = 1\\ &\quad\lambda_1,\lambda_3,\lambda_4,\lambda_6\geqslant 0. \end{align}
This has optimal solution $\lambda_6=1$ with objective value $\frac{116}{11}$, corresponding to the optimal basic feasible solution in the original LP with the last two constraints binding.