Probably not. ThereHere is a conceptual argument, which is based on
Farkas AlternativeFarkas Lemma: Exactly Exactly one of $Ax\le b$, $x\ge 0$ or $y^TA\ge 0$ $y^Tb < 0$the following alternatives has a solution.:
- $Ax \le b$ and $x \ge 0$
- $y^TA\ge 0$ and $y^Tb < 0$
Assuming this, takeNow let $\delta$ to be the optimal objective value of the primal in an optimal solution. Define Let $\epsilon > 0$ be arbitrary. Let $A'$ to be the matrix that is $A$ with an additional $-c^T$ as the last row and. Let $b'$ to be the vector $(b, -\delta - \epsilon)$. For any$b$ with an additional $\epsilon > 0$,$-\delta - \epsilon$ as the last value.
The system $A'x'\le b'$ has no solution, so according to. By Farkas, there is a $y' = (y,\alpha)$ such that $y^TA\le \alpha c$ and $y^Tb < \alpha (\delta + \epsilon)$. Moreover, $\alpha > 0$, since, when:
$y^TA\ge \alpha c$ and $y^Tb < \alpha (\delta + \epsilon)$.
Note that if $\epsilon = 0$ we are in the other alternative of Farkas. Therefore $\alpha > 0$.
To finish up, just scaleScale $y'$ so that $\alpha = 1$. Now $y$ is dual feasible, so. The weak duality implies $\delta \le y^Tb < \delta + \epsilon$, and we are done.