Question

prove that the feasible region of a linear program is always convex, i.e., if (x1, . . . , xn) and (y1, . . . , yn) are feasible for the lp then (z1, . . . , zn) is also feasible where the i-th coordinate zi

Answer 1

The feasible region of a linear program is always convex because any point on the line segment connecting two feasible solutions is also a feasible solution.

Step-by-step explanation:

The feasible region of a linear program is always convex. In order to prove this, we need to show that if two points are feasible solutions, then any point on the line segment connecting them is also a feasible solution.

1. Let (x1, . . . , xn) and (y1, . . . , yn) be feasible solutions for the linear program.
2. Any point on the line segment connecting these two points can be expressed as (1-t)(x1, . . . , xn) + t(y1, . . . , yn), where t is a scalar between 0 and 1.
3. By the definition of a linear program, if (x1, . . . , xn) and (y1, . . . , yn) are feasible, then for any linear constraint, a1x1 + ... + anxn ≥ b and a1y1 + ... + anyn ≥ b.
4. Substituting the expression for the point on the line segment, we get a1((1-t)x1 + ty1) + ... + an((1-t)xn + tyn) ≥ b.
5. Expanding and simplifying the inequality, we have ((1-t)(a1x1 + ... + anxn) + t(a1y1 + ... + anyn)) ≥ b.
6. Since (x1, . . . , xn) and (y1, . . . , yn) are feasible, the left-hand side of the inequality is greater than or equal to b.
7. Therefore, any point on the line segment connecting (x1, . . . , xn) and (y1, . . . , yn) is also a feasible solution.

This shows that the feasible region is convex.