que muestra que un conjunto de soluciones es convexo.

Question

Ya he demostrado que el conjunto de todas las soluciones factibles del LP $\min \{ cx : Ax = b , x \geq 0 \}$ es convexa. Ahora, me piden que demuestre que el conjunto de todas las soluciones óptimas de este LP también es convexo. Pero, ¿cómo puedo expresar el conjunto de todas las soluciones óptimas? ¿cómo se define?

Answer 1

Ouch, esto es hace mucho tiempo para mí. Déjame intentarlo.

Sea $x_1$ y $x_2$ sean dos soluciones óptimas (y factibles) con objetivo $z$ . Tenemos que demostrar que $x=\lambda x_1 + (1-\lambda)x_2$ es factible y tiene objetivo $z$ para $0\le\lambda \le 1$ . La viabilidad ya se estableció en su resultado anterior, por lo que sólo tenemos que demostrar estos puntos en el medio tienen objetivo $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}$$