1
$\begingroup$

The following constraints form a feasible region.

$-x_1+x_2 \le 2$

$-x_1+2x_2 \le 6$

$x_1,x_2 \ge 0$

The feasible region have three extreme points: $e_1=\left[\begin{array}{cc} 0\\ 0 \end{array}\right]$ $e_2=\left[\begin{array}{cc} 0\\ 2 \end{array}\right]$ $e_3=\left[\begin{array}{cc} 2\\ 4 \end{array}\right]$

What is the procedure that I need to follow to extract the extreme direction from this data?

Extrene Direction: An extreme direction of a convex set is a direction of the set that cannot be represented as a positive combination of two distinct directions of the set.

$\endgroup$
  • $\begingroup$ the costraints equations with the term on the right 0 and with "=" instead of $\le$. $\endgroup$ – tommycautero Jan 23 at 14:07
  • $\begingroup$ What do you mean by "extreme directions" in this context? $\endgroup$ – callculus Jan 23 at 18:38
  • $\begingroup$ Check the edit that I've done $\endgroup$ – user637533 Jan 23 at 19:03
0
$\begingroup$

Draw the LP using the graphical method (Just plot the conditions as line on the $x_1$ and $x_2$ axis) let $x_1$ be the horizontal axis and $x_2$ be the vertical axis. Find the line that remains in the feasible region as $x_1$ tends to infinity. and take the ratio of increase in $x_2$ and $x_1$. So if you have a line $-x_1 +2x_2 \geq 8$ that stays in the feasible region as $x_1$ tends to infinity, then the extreme direction is $(2,1)$ as when $x_1$ increases by $2$ then $x_2$ increases by $1$. Another example: you have a line $x_2 \geq 2$,that stays in the feasible region as $x_1$ tends to infinity, then the extreme direction is $(1,0)$.

$\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.