Dismiss Notice
Join Physics Forums Today!
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

  1. Jul 14, 2011 #1
    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 [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 for every i in I both [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 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
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?