0
$\begingroup$

Is it possible that for a general linear program none of the optimal solutions have to be basic? Meanwhile, for a program in standard form an optimal solution has be basic. If so, why ?

$\endgroup$
0
$\begingroup$

For $$\min_{x \geq 0} \{ x : x \leq 1\}$$ the only basic feasible solution is $x=1$, which is not optimal.

$\endgroup$
  • $\begingroup$ Why $x = 0$ is not a basic feasible solution? If I add a slack variable $s \ge 0$, then $x + s = 1$. The optimal solution $(x,s) = (0,1)$ has one non-zero entry, so it's basic. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Apr 6 '18 at 17:18
  • 1
    $\begingroup$ @GNUSupporter That's a different polygon. I am looking at $Ax \leq b$, not $Ax + s = b$ (even though its projection on $x$ is the same). Also see this definition of basic feasible solution. $\endgroup$ – LinAlg Apr 6 '18 at 17:42
  • $\begingroup$ This is not clear to me. I thought that a basic solution is the same beetween standard form and general form of a linear program... $\endgroup$ – Qwerto Apr 7 '18 at 13:19
  • $\begingroup$ basic solutions relates to polyhedra in standard form $\endgroup$ – Marcello Sammarra Apr 13 '18 at 16:49
  • $\begingroup$ @MarcelloSammarra my previous comment contains a reference that states the opposite of what you are saying. Another reference is Definition 2.9 in Introduction to linear optimization by Bertsimas and Tsitsiklis. $\endgroup$ – LinAlg Apr 18 '18 at 0:37

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.