0
$\begingroup$

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.

Answer:

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.

$\endgroup$
  • 1
    $\begingroup$ 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)$. $\endgroup$ – copper.hat Jan 14 '18 at 5:54
  • $\begingroup$ Would $ \ x_0+tc^T \ $ satisfy $ \ Ax \leq b \ $ ? $\endgroup$ – M. A. SARKAR Jan 14 '18 at 5:57
  • 1
    $\begingroup$ Yes, for sufficiently small $t$ because $Ax_0 < b$ so you have room to move a little in any direction. $\endgroup$ – max_zorn Jan 14 '18 at 6:20

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.