Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Suppose we have a primal maximization LP:
$$ \text{maximize } c^Tx \\ \text{subject to } Ax \le b, x \ge 0 $$
If $x$ is a feasible solution to the primal LP, and $y$ is a feasible solution to the dual LP, is the primal LP bounded?
My thought is that by the weak duality theorem, the primal LP is not required to be bounded.
By weak duality, a feasible solution for either primal or dual implies a bound on the other.
The dual of your linear program is $$ \text{minimize } b^Ty \\ \text{subject to } A^Ty \ge c, y \ge 0\ .\\ $$ Therefore, if $\ x\ $ and $\ y\ $ are feasible solutions of the primal and dual, respectively, then \begin{align} b^Ty&\ge x^TA^Ty\ \ (\text{because}\ b^T\ge x^TA^T\ \text{ and }\ y\ge0)\\ &\ge x^Tc \ \ \ \ \ \ \ (\text{because}\ A^Ty\ge c\ \text{ and }\ x\ge0)\\ &=c^Tx\ . \end{align} That is, the objective of the primal is bounded above by the objective value of the feasible solution of the dual.
