0
$\begingroup$

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.

$\endgroup$

2 Answers 2

1
$\begingroup$

By weak duality, a feasible solution for either primal or dual implies a bound on the other.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .