I have already shown that the set of all feasible solutions of the LP $ \min \{ cx : Ax = b , x \geq 0 \}$ is convex. Now, Im asked to show that the set of all optimal solutions to this LP is convex as well. But, how can I express the set all of optimal solutions? how is it defined?
Asked
Active
Viewed 5,535 times
1 Answers
2
Ouch, this is a long time ago for me. Let me try.
Let $x_1$ and $x_2$ be two optimal (and feasible) solutions with objective $z$. We have to show that $x=\lambda x_1 + (1-\lambda)x_2$ is feasible and has objective $z$ for $0\le\lambda \le 1$. The feasibility was already established in your earlier result, so we only have to prove these points in between have objective $z$.
$$\begin{align} &c^T\left[\lambda x_1 + (1-\lambda)x_2\right]\\ &=\lambda c^Tx_1 + (1-\lambda) c^Tx_2\\ &=\lambda z + (1-\lambda) z\\ &=z\end{align}$$
Erwin Kalvelagen
- 4,267
-
why show the set =1+(1−)? you didnt explain that part of the logic – james black Feb 10 '20 at 07:05
-
That, by definition, makes it convex. – Erwin Kalvelagen Feb 10 '20 at 09:30