I'm supposed to use the fundamental theorem of LP, weak duality and strong duality to prove this.
Fundamental Theorem of LP:
1) If there's a feasible solution there's a basic feasible solution
2) If there's an optimal solution there's a basic optimal solution
If x is a solution to primal constraints:
$Ax\le b$ and $x\ge 0$
and y is a solution to the dual
then $cx\le by$
Above conditions met and x and y are optimal solutions then
I'm still not entirely sure what's the difference between a "feasible solution" is and a "basic feasible solution." So if someone can explain that, that'd be very helpful.
Using the above I have to prove $x,y$ are vectors and $A$ is a matrix then
$\exists x$ st $x \le 0$ and $Ax \le b$ or $\exists y$ st $A^Ty\ge 0, y\ge 0$ and $by<0$, but not both
This seems very similar to Farkas lemma, except $Ax=b$ is a requirement in Farkas so it's not exactly the same.