0
$\begingroup$

Consider $S \subset \mathbb{R^2}$ a set such that $\forall (x_1,x_2) \in S$ :

$ 2x_1+3x_2 \leq 6 $

$-2x_1+ x_2 \leq 2$

$x_1 \geq 0 , x_2 \geq 0$

How can I find extreme points of $S$? What is a good strategy to start tackling this kind of problem?

$\endgroup$
1
$\begingroup$

Because $x_1,x_2\geqslant0$ we can write the inequalities as equalities with the use of slack variables: \begin{align} 2x_1+3x_2+s_1&=6\\ -2x_1+x_2+s_2&=2\\ x_1,x_2,s_1,s_2&\geqslant 0. \end{align} Extreme points are equivalent to basic feasible solutions. Because $S\subset\mathbb R^2$, a basic solution has two basic variables; hence there are six candidates: $$(x_1,x_2), (x_1,s_1), (x_1,s_2), (x_2,s_1), (x_2,s_2), (s_1,s_2).$$ Solve the system of equations by setting each nonbasic variable equal to zero; if the resulting solution is positive, then it is feasible, and hence a basic feasible solution. I'll leave the computations to you, but the extreme points we find in this process are $(0,0), (3,0), (0,2)$ (in terms of $(x_1,x_2)$).

$\endgroup$
1
$\begingroup$

Ummmm.... why don't you just plot it?

enter image description here

and analogously in higher dimensions:

enter image description here

$\endgroup$
  • $\begingroup$ This works fine for $\mathbb R^2$ but what about higher-dimensional problems? :) $\endgroup$ – Math1000 Sep 4 '19 at 0:02
  • $\begingroup$ What tool did you use for the second plot? $\endgroup$ – user550103 Sep 4 '19 at 3:33
  • $\begingroup$ Mathematica's RegionPlot3D functionality. $\endgroup$ – David G. Stork Sep 4 '19 at 4:40

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.