3
$\begingroup$

It is rather easy to find extreme points in the $2$ variable case. How to find them for higher dimensions, say, in $3$ variables? For instance,

$$\begin{array}{ll} \text{minimize} & -3x_1-2x_2-x_3\\ \text{subject to} & 2x_1+x_2-x_3\le2\\ & x_1,x_2,x_3\ge0\end{array}$$

$\endgroup$
  • 3
    $\begingroup$ You have four inequalities -- the non-negativity conditions are included here -- so take them three at a time, solve for $x_1,x_2,x_3$, and then find $-3x_1-2x_2-x_3$. For instance: $2x_1+x_2-x_3=2$, $x_1=0$, $x_3=0$ implies that $x_2=2$; $-3\cdot0-2\cdot2-0=-4$ is the objective value at that corner. (Make sure your solutions are feasible points!) $\endgroup$ – Christopher Carl Heckman Apr 4 '16 at 6:45
  • 1
    $\begingroup$ why also find the objective value at each extreme point? $\endgroup$ – 104078 Apr 4 '16 at 6:48
  • 1
    $\begingroup$ it is to find the optimal, right. Nothing to do with finding extreme points. $\endgroup$ – 104078 Apr 4 '16 at 6:50
  • $\begingroup$ It has everything to do with extreme points actually. The central idea in linear programming is the following: the optimal value of a linear function defined on a polyhedron (the feasible region bounded by the constraints) is attained at an extreme point of the feasible region, provided a solution exists. In other words, if an optimal solution(s) exists, then it is among the list of extreme points of the feasible region. $\endgroup$ – user3816 Jul 25 '18 at 14:11
1
$\begingroup$

In your example, you can have arbitrary small values for your objective function. Just take $x_1=0,x_2=c,x_3=c$, then the constraint is satisfied for all $c\geq 0$, and you can make $c$ arbitrarily large, so your objective function $-3x_1-2x_2-x_3$ becomes arbitrarily small. In general you can use the simplex algorithm.

$\endgroup$
  • 1
    $\begingroup$ However, $0 \le x_2 = c$, so $c$ can't be arbitrarily small. Hence, the minimization instruction. $\endgroup$ – Christopher Carl Heckman Apr 4 '16 at 6:59
  • 2
    $\begingroup$ Sorry, you are right, I edited my answer, now it should be correct. $\endgroup$ – Hua Apr 5 '16 at 12:07

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.