Exercise 2.4

One is tempted to make this implication based on the fact that every polyhedron and the corresponding cost function can be equivalently transformed into a standard polyhedron form when solving an optimization problem.

The word "equivalently", however, is used exclusively with respect to the optimization problem and thus refers only to the fact that we get the same optimization result on both polyhedra (cf. page 5); it does not say that the equivalent transformation preserves polyhedra in a geometrical sense.

To sum up the above argument shortly: we can convert the original linear program into a linear program in standard form, solve the standard form problem, and obtain an optimal solution of the original problem in case it exists. A vertex $x$ of the standard form problem is the unique minimum for some objective function $c$. However, when we map this vertex back onto the original problem, we are not guaranteed to obtain a vertex again.

Example 1. To illustrate our reasoning, we give an example of an original problem whose feasible set contains a line and thus has no vertices. Consider the polyhedra given by the constraint

$$x_1^{\text{+}}-x_1^{\text{−}}+y_1^{\text{+}}-y_1^{\text{−}}-z=0$$

$$x_1^{\text{+}},x_1^{\text{−}},y_1^{\text{+}},y_1^{\text{−}},z\ge 0$$

or in other words,

$$P=\left\{x\in {\Re }^5|\left[\begin{array}{ccccc}\hfill 1\hfill & \hfill -1\hfill & \hfill 1\hfill & \hfill -1\hfill & \hfill -1\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1^{\text{+}}\hfill \\ \hfill x_1^{\text{−}}\hfill \\ \hfill y_1^{\text{+}}\hfill \\ \hfill y_1^{\text{−}}\hfill \\ \hfill z\hfill \end{array}\right]=0,\left[\begin{array}{c}\hfill x_1^{\text{+}}\hfill \\ \hfill x_1^{\text{−}}\hfill \\ \hfill y_1^{\text{+}}\hfill \\ \hfill y_1^{\text{−}}\hfill \\ \hfill z\hfill \end{array}\right]\ge 0\right\}.$$

This large standard form condition specifies a polyhedron in the five dimensions - it is bounded from below in all axes and has a vertice at $0$.

We can, however, give it a simpler general form specification

$$P^{\prime }=\left\{x\in {\Re }^2|\left[\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \end{array}\right]\ge 0\right\}.$$

This is an equivalent problem and it specifies a polyhedron that contains a line over the point $0\in P^{\prime }$, i.e.,

$$0+\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \end{array}\right]\cdot \lambda \in P^{\prime }$$

for all $\lambda \in \Re$. By Theorem 2.6 (b), $P^{\prime }$ is guaranteed to have no extreme points. Thus, this polyhedron serves as a counterexample to the assertion made in the exercise.

I think the main issue is that the polyhedra after transformation is another polyhedra.