# Show that $\ x_ 0 \$ cannot be an optimal solution

Consider the LP maximize $\large z = cx \$ subject to $\ Ax ≤ b \ , x ≥ 0 \$ where $\ c \$ is a nonzero vector. Suppose that the point $\ x_ 0 \$ is such that $\ Ax_ 0 < b \$ and $\ x_ 0 > 0 \$.

Show that $\ x_ 0 \$ cannot be an optimal solution.

Max $\ Z=cx \$ subject to $\ Ax \leq b , \ x \geq 0 \$

Given $\ x_0 \$ satisfying $\ Ax_0 <b \$.

Then for $\ \epsilon >0 \$ , there exists $\ x'=x_0+\epsilon \$ such that $Ax' \leq b \ , \ x' \geq 0$

Also,

$cx_0 \leq cx' \$

$\Rightarrow x_0 \$ is not optimal solution.

I need confirmation of my work.

• You would need strictness to show that $x_0$ is not optimal. Try $x_0+t c^T$ for some small $t>0$. Then $c x_0 < c (x_0 + t c^T)$. – copper.hat Jan 14 '18 at 5:54
• Would $\ x_0+tc^T \$ satisfy $\ Ax \leq b \$ ? – M. A. SARKAR Jan 14 '18 at 5:57
• Yes, for sufficiently small $t$ because $Ax_0 < b$ so you have room to move a little in any direction. – max_zorn Jan 14 '18 at 6:20