Finding set of extreme points and directions in an LP problem with constraints of constraints

109 Views Asked by At

Considering LP Problem z:

$z^*$ = min $x_{1} - x_{2} - 2x_{3}$
s.t. $x_{1} + x_{2} + x_{3} = 3$
$ 0 ≤ x_{1} ≤ 2$
$ 0 ≤ x_{2}$
$ 0 ≤ x_{3} ≤ 2$

and $$ P= \{ \begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \end{pmatrix}: 0 ≤ x_{1} ≤ 2, 0 ≤ x_{2}, 0 ≤ x_{3} ≤ 2\} $$

If {$x^j$ : j = 1,...,k} be the set of extreme points of P and {$d^j$ : j = 1,...,l} be the set of extreme directions of P, how do find the value of k and l? I'm struggling because slack variables do not seem to work when $x_{1}$,$x_{3}$ are bounded both ways over range $(0,2)$. Any help would be really appreciated!

1

There are 1 best solutions below

1
On BEST ANSWER

$P$ is a cuboid with infinite length in the $x_2$ positive direction.

The base is a square, hence $k=4$ and $l=1$.