Hello. I'm quoting Bertsimas, D., and J. Tsitsiklis,(adsbygoogle = window.adsbygoogle || []).push({}); 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 [itex] a'_i x \geq{} b_i [/itex] and [itex] a'_i x = b_i [/itex]"

After proving Vertex [itex]\Rightarrow[/itex] Extreme point, and Extreme point [itex]\Rightarrow[/itex] Basic feasible solution:

"Basic feasible solution[itex]\Rightarrow[/itex]Vertex

Let x* be a basic feasible solution and let [itex] I = \{\: i\: |\: a'_i x^* = b_i \:\}[/itex]. Let [itex] c = \Sigma_{i\: in\: I} a_i[/itex]. We then have

[tex] c' x^* = \Sigma_{i\: in\: I}\: a'_i x^* = \Sigma_{i\: in\: I}\: b_i.[/tex]

Futhermore, for any x in P and any i, we have [itex] a'_i x \geq{} b_i [/itex], and

[tex] c' x = \Sigma_{i\: in\: I}\: a'_i x \geq{} \Sigma_{i\: in\: I}\: b_i.[/tex]"

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

[tex]a'_i x \leq{} b_i [/tex]

[tex]a'_i x - z = b_i, z \geq{} 0 [/tex]

[tex]a'_i x = b_i + z, z \geq{} 0 [/tex]

So I'm fine with restricting the logical operators to those two, but that does not imply that foreveryi in Iboth[itex] a'_i x \geq{} b_i [/itex] and [itex] a'_i x = b_i [/itex] 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 iin 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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**