# Defining a polyhedron WLOG to prove that a basic feasible solution is a vertex

1. Jul 14, 2011

### nancyiskander

Hello. I'm quoting Bertsimas, D., and J. Tsitsiklis, Introduction to Linear Optimization:

"For the purposes of this proof and without loss of generality, we assume that P is represented in terms of constraints of the form $a'_i x \geq{} b_i$ and $a'_i x = b_i$"

After proving Vertex $\Rightarrow$ Extreme point, and Extreme point $\Rightarrow$ Basic feasible solution:

"Basic feasible solution $\Rightarrow$ Vertex
Let x* be a basic feasible solution and let $I = \{\: i\: |\: a'_i x^* = b_i \:\}$. Let $c = \Sigma_{i\: in\: I} a_i$. We then have
$$c' x^* = \Sigma_{i\: in\: I}\: a'_i x^* = \Sigma_{i\: in\: I}\: b_i.$$

Futhermore, for any x in P and any i, we have $a'_i x \geq{} b_i$, and
$$c' x = \Sigma_{i\: in\: I}\: a'_i x \geq{} \Sigma_{i\: in\: I}\: b_i.$$"

How has generality not been lost? I understand that $\leq$ can be represented by = and $\geq$ as follows:

$$a'_i x \leq{} b_i$$
$$a'_i x - z = b_i, z \geq{} 0$$
$$a'_i x = b_i + z, z \geq{} 0$$

So I'm fine with restricting the logical operators to those two, but that does not imply that for every i in I both $a'_i x \geq{} b_i$ and $a'_i x = b_i$ will apply! If this is really what is being implied, how come generality is not lost? If not, what am I misunderstanding?

Edit: I figured it out a few minutes after posting (it doesn't actually say for any i in I, but since we've restricted the operators, for any i it will be either one of them), but I can't find a delete button.

Last edited: Jul 14, 2011