2
$\begingroup$

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.


Proof.

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$$

Have

$$ty_1+(1-t)y_2$$

$$=tc^Tx_1+(1-t)c^Tx_2$$

$$=c^T(tx_1+(1-t)x_2)$$

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.

$\endgroup$

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.