0
$\begingroup$

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.

$\endgroup$

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.