Convex hull and optimal solutions

convex-analysisconvex-hullslinear programming

Consider the LP problem:

$max$ $3x_1 + 2x_2+x_3$

$s.t$ $3x_1 + 4x_2 + x_3 ≤ 6 $

$2x_1+x_2 + 3x_3 ≤ 5 $

$x_1,x_2,x_3 ≥0$

I have solved the problem and found that the optimal value is 6 at $x=(2,0,0)$.

Now I have to find two points $x_1$ and $x_2$ so that the set of optimal solutions of the problem above can be written as $conv(x_1,x_2)$. How do I solve this?

I also have all the extreme points of the feasible region.

Best Answer

Assume $3x_1+2x_2+x_3=6$, plug that into the first inequality to derive $2x_2\leq 0$ implying $x_2=0$ using the first equation $$3x_1+x_3=6$$ we derive at $$x_3=6-3x_1$$

now intersect this with the feasible region (second inequality) and you should be done by using the boundary values of the set of solutions (note that these values are $\subset \mathbb{R}^3$) because the relationship is linear