Question: Consider $A \subset \mathbb{R^3} $ convex set such that:

$(x_1,x_2,x_3) \in A \Leftrightarrow x_1,x_2,x_3 \geq0 , 2x_1+x_2+4x_3 \leq 6 , x_1+4x_2 -x_3 \leq 4$

Consider the function $z= 2x_1 +x_2 -x_3$

The question asks to show that we can find the maximum of $ z $ by enumerating all the extreme points of A, which is simple and consists of solving 2x2 linear systems, and also asks if the same strategy is valid if the first constraint is replaced by $x_1 + x_2 -4x_3 \leq 6$

Doubt: We know that if there is a point that maximizes the function, then there is an extreme point that maximizes the function, isn't the strategy of enumerating the extreme points valid in any problem? (I'm guessing it is possible to enumerate all the extreme points) In these two cases presented here does not seem to me to have any mystery in enumerating the extreme points, is there something very subtle that I am not seeing?


The point is, besides testing the extreme points of the feasible region for the most optimal one (which becomes very time-consuming for large-scale problems), finding them through linear algebraic processes is almost the most limiting of all specially for inequality constraints. In a set of inequalities, say $n$ of them, you must always check whether any $m$ number of them makes an extreme point. For all-equality constraints, this is simpler, however almost complicated algorithms (such as simplex) are used to solve such LP problems.


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.