1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: If x1 and x2 solve an LP problem, show that there are

  1. Aug 16, 2012 #1
    1. The problem statement, all variables and given/known data

    If x1 and x2 solve the LP problem P, show that there are infinitely many solutions.

    2. Relevant equations

    (P): maximize of cTx subject to Axb, x0

    (Though the problem doesn't say it, I'm sure we assume x1x2)

    3. The attempt at a solution

    So it'll suffice to show that Ax1 = Ax2 = sup{Ax | Axb, x0} implies the existence of another x3 = sup{Ax | Axb, x0}. I remember my professor saying something about convex sets (I wasn't taking notes so I can't remember the gist of it). I think I need to choose λ ε (0, 1) and then show that x3 = λx1 + (1 - λ)x2 = sup{Ax | Axb, x0}. How do I do this?
  2. jcsd
  3. Aug 16, 2012 #2
    Substitute x3 thus defined and check that it satisfies the conditions and that the value of the objective function does not change.

    Then, please read up on the theory.
  4. Aug 16, 2012 #3
    Suppose x ε ℝn and y ε ℝn, with xy, solve the linear program. Fix λ ε (0, 1) and set z = λx + (1 - λ)y.

    Since xi, yi ≥ 0 for each i ε {1, ..., n}, and since λ, 1 - λ > 0, we have λxi, (1 - λ)yi ≥ 0 and subsequently zi = λxi + (1 - λ)yi ≥ 0 for each i ε {1, ..., n}. Hence z0. Similarly, since λ, 1 - λ < 1 we have have Azb. Hence z is a feasible solution for the LP. To see that cTz is optimal, look at zi = λxi + (1 - λ)yi = λ(xi - yi) + yi.

    Errrr not sure what to do from here
    Last edited: Aug 16, 2012
  5. Aug 16, 2012 #4
    Plug that into the objective function; mind its linearity.
  6. Aug 16, 2012 #5

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    You cannot assume [itex] Ax_1 = Ax_2,[/itex] because at both [itex]x_1 \text{ and } x_2[/itex] we can have some rows of Ax being strictly less than the corresponding components of b; and the differences between the right and left-hand sides at those "non-binding" constraints can be different at the two optima. In other words, in the situation you describe we usually have [itex] Ax_1 \neq Ax_2.[/itex] However, you DO both [itex]Ax_1 \leq b[/itex] and [itex]Ax_2 \leq b,[/itex] but with [itex] cx_1 = cx_2.[/itex] Now use convexity in the manner others have suggested.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook