# how to check whether feasible solutions exist for linear programming

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?

• please state the complete feasible set. If it is $\{x|Ax\le B\}$ and $B\ge 0$, then $x=0$ is feasible. – user251257 Jul 14 '15 at 10:31
• This is just a special case, I need a general answer. Thank you all the same. – Frank Jul 14 '15 at 11:18
• Do you need a constructive method? – user251257 Jul 14 '15 at 11:27
• 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. – Frank Jul 14 '15 at 11:46
• That's what I meant. then, in general, you need to implement the simplex method or something similar. – user251257 Jul 14 '15 at 13:46

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