- #1
Jamin2112
- 986
- 12
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 Ax ≤ b, x ≥ 0
(Though the problem doesn't say it, I'm sure we assume x1 ≠ x2)
The Attempt at a Solution
So it'll suffice to show that Ax1 = Ax2 = sup{Ax | Ax ≤ b, x ≥ 0} implies the existence of another x3 = sup{Ax | Ax ≤ b, x ≥ 0}. 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 | Ax ≤ b, x ≥ 0}. How do I do this?