Extreme point theorem of linear programming

Question

So I was told to find a counterexample to this linear programming extreme point theorem:

"If $S$ is nonempty and not bounded and if an optimal solution to the problem exists, then an optimal solution occurs at an extreme point."

Is there any hint? Thank you for your assistance in advance.

score 0 · Answer 1 · answered Sep 24 '21 at 15:20

0

Main idea: Follow the gradient to find an optimum. This is possible because the feasible area is convex. Now imagine as feasible area something like a rectangle with infinite length to the right.

answered Sep 24 '21 at 15:20

user7427029

719

Would you like to explain "the gradient"? – LianNuo Sep 24 '21 at 15:26
https://en.wikipedia.org/wiki/Gradient The gradient of the function to be optimized points into the direction of fastest increase. – user7427029 Sep 25 '21 at 10:24

Extreme point theorem of linear programming

1 Answers1