Provide an appropriate response.A set S in Rn is convex if, for each p and q in S, the line segment between p and q lies in S. [This line segment is the set of points of the form (1 - t)p + tq for 0 ? t ? 1. ]Let F be the feasible set of all solutions x of a linear programming problem Ax ? b with x ? 0. Assume that F is nonempty. Show that F is a convex set in Rn.[Hint: Consider points p and q in F and t such that 0 ? t ? 1. Show that (1 - t)p + tq is in F.]

Question

What will be an ideal response?

Answer 1

Take any p and q in F. Then Ap ? b, Aq ? b, p ? 0, q ? 0. Take any scalar t such that 0 ? t ? 1 and let x = (1 - t)p + tq. Then Ax = A[(1 - t)p + tq] = (1 - t)Ap + tAq ? (1 - t)b + tb = b because (1 - t) and t are both nonnegative and p and q are in F. Also x ? 0 because p and q are ? 0 and (1 - t) and t are nonnegative. Thus x is in F. So the line segment between p and q is in F. This proves that F is convex.