Show that the feasible region of a linear programming is a Polyhedron

255 Views Asked by At

Show that the feasible region of a linear programming is a Polyhedron.


My try:

I assume that the linear programming is of the following forms:

$$\text{min}/\text{max} \;\; z=\mathbf c \mathbf x $$ $$\text{s.t.}\;\; \mathbf A\mathbf x =\mathbf b $$ $$\mathbf x \ge \mathbf 0$$ $$$$

On the other hand by the definition every polyhedron is defined as a finite intersection of half-spaces, so denote by $M$ the polyhedron defined by the intersction of $m$ half-spaces, also every lower half-space $H^{-}=\{\mathbf x: \mathbf p^t \mathbf x \le \alpha\}$ can be written as $$H^{-}=\{\mathbf x: \mathbf p^t \mathbf x \le \alpha\}=\{\mathbf x: -\mathbf p^t \mathbf x \ge -\alpha\}=H^{+}$$

From here we see that $$M=\bigcap_{i=1}^{m} H^{+}=\bigcap_{i=1}^{m}\{\mathbf x: \mathbf p_{i}^{t} \mathbf x \ge \alpha_i\}=\bigcap_{i=1}^{m}\{\mathbf x: \mathbf p_{i}^{t} \mathbf x -\beta_i \mathbf x = \alpha_i\}$$ $$=\{\mathbf x: \mathbf p_{i}^{t} \mathbf x -\beta_i \mathbf x = \alpha_i , i\in \{1,...,m\}\}$$

$$=\{\mathbf x:\underbrace{\begin{bmatrix} \mathbf p_{1}^{t} -\beta_1 \\ \vdots \\ \mathbf p_{m}^{t} -\beta_m \end{bmatrix}}_{\mathbf A}\mathbf x = \underbrace{\begin{bmatrix} \mathbf \alpha_1\\ \vdots \\ \alpha_m \end{bmatrix}}_{\mathbf b}\}$$

$$=\{\mathbf x:\mathbf A\mathbf x = \mathbf b\}\tag{I}$$

On the other hand the feasible region of the given linear programming is given by $$\{\mathbf x:\mathbf A\mathbf x = \mathbf b,\mathbf x \ge \mathbf 0\}=\underbrace{\{\mathbf x:\mathbf A\mathbf x = \mathbf b\}}_{*} \cap \{\mathbf x:\mathbf x \ge \mathbf 0\}$$

By $(\text{I})$, we know that $*$ is a polyhedron, so the feasible region is the intersection of a polyhedron with $ \{\mathbf x:\mathbf x \ge \mathbf 0\}$, but is such intersection a polyhedron itself?

1

There are 1 best solutions below

0
On

if you understand how $Ax = b$ is polyhedron, then $x\geq0$ is just the non negative orthant, which you can easily visualize as intersection of half spaces. for instance is $x$ is in $R^2$, then $x\ge0$ means both it's components are positive. so, it is intersection of the half spaces $x_1 \geq 0$ and $x_2 \geq0$. to put it in matrix representation, $x\geq0$ means $Ix\ge b$ where $b$ is zero vector. so, you can write this as set of $m$ half space equations like you did. it is intersection of these $m$ halfspaces. $I_ix \ge 0$ for $i = 1, 2, ...m$, where $I_i$ is ith row of identity matrix.