Exercise 2.18

Intuitively, we shall find such a $\overline{b}$ by first identifying excessive constraints and perturbing the necessary constraints by some $𝜖$. That is, if $P=H_1\cap \cdots \cap H_m$, where $H_j$ are the half-spaces whose intersection gives us $P$, then we identify those $H_j$ which are unnecessary in defining $P.$ If $H_j$ is excessive, then $P$ is well defined apart from $H_j$, which means that ${\bigcap <!--\; FUNCTION\; APPLICATION\; -->}_{k\ne j}{H}_k=P.$ Let $M$ be the set of all indices of excessive half-spaces. Then $P={\bigcap <!--\; FUNCTION\; APPLICATION\; -->}_{k\notin M}{H}_k$, that is, we can remove all the half-spaces of $M$ and still get the same polyhedron. This is true just because of our construction, since all the half-spaces removed are excessive. If $H_j=\left\{x\in {ℝ}^n:a_j^{\prime }x\ge b_j\right\}$, then let $H_k^{\prime }=\left\{x\in {ℝ}^n:a_k^{\prime }x\ge b_j-𝜀\right\}.$ Let $\overline{b}$ be defined by:

Then our new polyhedron is $P^{\prime }={\bigcap <!--\; FUNCTION\; APPLICATION\; -->}_{k\in M}{H}_k\cap {\bigcap }_{j\in M}{H}_j^{\prime }.$ Note that in $P$, the degenerate basic feasible solutions can be interpreted as having too many hyperplanes, boundary of half-spaces, touching at that point. For example, on a cube in three dimensions, all the points are nondegenerate as they all have 3 hyperplanes touching them, the three facets that connect at a corner. Moreover, every facet of a polyhedron is not excessive, since it serves as a boundary of the polyhedron. Thus, we can interpret the excessive constraints as half-spaces whose hyperplane boundary either touches the polyhedron only at some degenerate solution or at not degenerate solution.. Therefore, by perturbing these outward by $𝜖$, we remove all the degeneracy from our basic feasible solutions. Thus all the basic feasible solutions in $P^{\prime }$ are nondegenerate. Also, since we have only perturbed the excessive half-spaces by $𝜖$, it follows that by construction $\left|{\overline{b}}_i-b_i\right|\le 𝜀$ for all $i$.