1
$\begingroup$

will the feasible region of a linear programming problem with linear mathematical relations and linear constraints, always be a convex polygon? will concave feasible regions have optimal value at corner points?

$\endgroup$
2
$\begingroup$

Let's get the feel of this in 2-D (so with 2 variables). When you add a constraint, you add a line in the plane and forbid the solution to be in one of the two sides, and only allow it to be in the remaining side. It is noticeable that it gives a convex feasable solution region. With n constraints, it's the same : for each line (from each constraint), you have to be in one side, so you have to be in the intersection of all the "half" spaces. The intersection of convex regions being convex, you have your answer.

The same idea can be used with k dimensions, but "lines" are replaced by "hyperplans" (for example a plane in 3-D).

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