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

Weak Duality:
If x is a solution to primal constraints:
$Ax\le b$ and $x\ge 0$
and y is a solution to the dual
$A^Ty\ge c$
$y\ge 0$
then $cx\le by$

Strong Duality:
Above conditions met and x and y are optimal solutions then
$cx= by$

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.


Your Answer

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

Browse other questions tagged or ask your own question.