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

## 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

Related Calculus and Beyond Homework Help News on Phys.org
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.

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:
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.

Ray Vickson
Science Advisor
Homework Helper
Dearly Missed

## 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 $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