• Support PF! Buy your school textbooks, materials and every day products Here!

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

  • Thread starter Jamin2112
  • Start date
  • #1
986
8

Homework Statement



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

Homework Equations



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

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

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?
 

Answers and Replies

  • #2
6,054
390
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.
 
  • #3
986
8
Substitute x3 thus defined and check that it satisfies the conditions and that the value of the objective function does not change.
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:
  • #4
6,054
390
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
Plug that into the objective function; mind its linearity.
 
  • #5
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,705
1,722

Homework Statement



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

Homework Equations



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

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

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?
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.
RGV
 

Related Threads for: If x1 and x2 solve an LP problem, show that there are

  • Last Post
Replies
12
Views
13K
Replies
5
Views
788
  • Last Post
Replies
2
Views
766
  • Last Post
Replies
3
Views
933
Replies
7
Views
12K
Replies
2
Views
1K
Replies
8
Views
2K
Top