Consider the LPP of optimizing the objective function $c^Tx$ over the polyhedron $$P=\{x\in\mathbb{R}^n:Ax\ge b\}$$ Show that the set $$S=\{c^Tx:x\in P\}$$ of values of the objective function over all feasible points is a convex set.


Since $S=\{c^Tx:x\in P\}=\{y:y=c^Tx \wedge x\in P\}$

Let $y_1,y_2\in S$, Have $$y_1=c^Tx_1\wedge y_2=c^Tx_2\wedge Ax_1\ge b\wedge Ax_2\ge b$$

$$\text{WTS }ty_1+(1-t)y_2\in S$$





Since any polyhedron in $\mathbb{R}^n$ is a convex set and $P$ is a polyhedron implies

$$tx_1+(1-t)x_2\in P$$

That proves $c^T(tx_1+(1-t)x_2)\in S\tag*{$\square$}$

Is my proof correct, any suggestion would be appreciated.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.