For a linear programming problem, how to decide whether there exists a feasible solution without solving it?

For $Ax\le B$, is there any sufficient and/or necessary condition represented by A and B to decide the existence of a feasible solution without solving the problem?

  • $\begingroup$ please state the complete feasible set. If it is $\{x|Ax\le B\}$ and $B\ge 0$, then $x=0$ is feasible. $\endgroup$ – user251257 Jul 14 '15 at 10:31
  • $\begingroup$ This is just a special case, I need a general answer. Thank you all the same. $\endgroup$ – Frank Jul 14 '15 at 11:18
  • $\begingroup$ Do you need a constructive method? $\endgroup$ – user251257 Jul 14 '15 at 11:27
  • $\begingroup$ what do you mean by constructive method? I want a method which can easily be implemented on computer, I don't really care about the theory behind. $\endgroup$ – Frank Jul 14 '15 at 11:46
  • $\begingroup$ That's what I meant. then, in general, you need to implement the simplex method or something similar. $\endgroup$ – user251257 Jul 14 '15 at 13:46

You can use the following result:

Theorem (Farkas lemma, 1894): Let $A\in\mathbb{R}^{m\times n}$ and $b\in\mathbb{R}^m$. Then $Ax\le b$ has a solution if and only if $A^Ty=0$, $y\ge 0$, $b^Ty<0$ has no solution.

Corollary: In other words, $A^Ty=0$, $y\ge 0$ $\Rightarrow$ $b^Ty\ge 0$.

  • $\begingroup$ thanks, I will have a try. $\endgroup$ – Frank Jul 14 '15 at 11:26

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.