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

1. Aug 16, 2012

### Jamin2112

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. Aug 16, 2012

### voko

Substitute x3 thus defined and check that it satisfies the conditions and that the value of the objective function does not change.

3. Aug 16, 2012

### Jamin2112

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
4. Aug 16, 2012

### voko

Plug that into the objective function; mind its linearity.

5. Aug 16, 2012

### Ray Vickson

You cannot assume $Ax_1 = Ax_2,$ because at both $x_1 \text{ and } x_2$ 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 $Ax_1 \neq Ax_2.$ However, you DO both $Ax_1 \leq b$ and $Ax_2 \leq b,$ but with $cx_1 = cx_2.$ Now use convexity in the manner others have suggested.
RGV