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

[Jamin2112]

Homework Statement

If x₁ and x₂ solve the LP problem P, show that there are infinitely many solutions.

Homework Equations

(P): maximize of c^Tx subject to Ax ≤ b, x ≥ 0

(Though the problem doesn't say it, I'm sure we assume x₁ ≠ x₂)

The Attempt at a Solution

So it'll suffice to show that Ax₁ = Ax₂ = sup{Ax | Ax ≤ b, x ≥ 0} implies the existence of another x₃ = 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 x₃ = λx₁ + (1 - λ)x₂ = sup{Ax | Ax ≤ b, x ≥ 0}. How do I do this?

 

[voko]

Substitute x₃ 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.

 

[Jamin2112]

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

Suppose x ε ℝⁿ and y ε ℝⁿ, with x ≠ y, solve the linear program. Fix λ ε (0, 1) and set z = λx + (1 - λ)y.

Since x_i, y_i ≥ 0 for each i ε {1, ..., n}, and since λ, 1 - λ > 0, we have λx_i, (1 - λ)y_i ≥ 0 and subsequently z_i = λx_i + (1 - λ)y_i ≥ 0 for each i ε {1, ..., n}. Hence z ≥ 0. Similarly, since λ, 1 - λ < 1 we have have Az ≤ b. Hence z is a feasible solution for the LP. To see that c^Tz is optimal, look at z_i = λx_i + (1 - λ)y_i = λ(x_i - y_i) + y_i. Errrr not sure what to do from here

 

[voko]

Suppose x ε ℝⁿ and y ε ℝⁿ, with x ≠ y, solve the linear program. Fix λ ε (0, 1) and set z = λx + (1 - λ)y.

Since x_i, y_i ≥ 0 for each i ε {1, ..., n}, and since λ, 1 - λ > 0, we have λx_i, (1 - λ)y_i ≥ 0 and subsequently z_i = λx_i + (1 - λ)y_i ≥ 0 for each i ε {1, ..., n}. Hence z ≥ 0. Similarly, since λ, 1 - λ < 1 we have have Az ≤ b. Hence z is a feasible solution for the LP. To see that c^Tz is optimal, look at z_i = λx_i + (1 - λ)y_i = λ(x_i - y_i) + y_i.


Errrr not sure what to do from here

Plug that into the objective function; mind its linearity.

 

[Ray Vickson]

Homework Statement

If x₁ and x₂ solve the LP problem P, show that there are infinitely many solutions.

Homework Equations

(P): maximize of c^Tx subject to Ax ≤ b, x ≥ 0

(Though the problem doesn't say it, I'm sure we assume x₁ ≠ x₂)

The Attempt at a Solution

So it'll suffice to show that Ax₁ = Ax₂ = sup{Ax | Ax ≤ b, x ≥ 0} implies the existence of another x₃ = 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 x₃ = λx₁ + (1 - λ)x₂ = sup{Ax | Ax ≤ b, x ≥ 0}. 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