Formulate a linear program that will determine whether or not $Ax>b$ has a solution, where $A$ is an $m \times n$ matrix and $b$ is an $m$-vector.
We were told to use Farkas Lemma, but are not sure how to deal with strict inequalities. Any help will be very much appreciated. Thank you!
Edits: I understand Farkas' Lemma as a theorem whereby only one of the following two conditions hold:
- Either the vector $b$ $\in$ cone($a_1$,...,$a_n$)
- The vector $b$ and cone($a_1$,...,$a_n$) can be separated by a hyperplane through the origin
I am trying to rewrite $A x > b$ in standard form to apply the variant of the Farkas' lemma:
$A x = b$, $x \geqslant 0$ has a solution iff $A^Ty \geqslant 0$ , and $y^Tb \geqslant 0$
My initial steps:
$A x - et \geqslant b$ has a sol iff
$A (x^+-x^-)-et-s = b$, $x^+,x^-,s,t \geqslant 0$
$$
\left[\begin{matrix}
A & -A & -e & -I
\end{matrix}\right]
\left[
\begin{matrix}
x^+ \\ x^- \\ t \\ s
\end{matrix}\right] = b
$$
Is this correct? Thank you.