Past exam of the probability, statistics and options I course of the University of Oxford / 2007 / T (Linear Programming)

The dual isweak duality says that any feasible primal $x$ and dual $y$ satisfy $c^{T}x\le b^{T}y$. Indeed,The first inequality uses $x\ge 0$ and $A^{T}y-c\ge 0$, and the second uses $y\ge 0$ and $b-Ax\ge 0$. This proves the theorem. In particular, feasible solutions with equal objective function values are optimal for both problems.

With primal constraints $Ax=b$, the dual variable is unrestricted in sign:Membership of $x$ in the nonnegative orthant still yields $c^{T}x\le y^{T}Ax$, but the next step is now the equality $y^{T}Ax=y^{T}b$, so no sign condition on $y$ is needed. Equivalently an equality constraint can be replaced by two opposite inequalities whose nonnegative multipliers combine into one free multiplier.

The two primal constraints are equalities, so let the two dual variables $u,v$ be free. Primal feasibility restricts $x$ to the nonnegative orthant, givingThus the feasible region lies above all four lines:Its lower boundary follows the third line up to $(5/9,7/9)$, the fourth line from there to $(10/3,-1/3)$, and then the first line. The second line never determines the envelope. Along these three pieces $u+v$ respectively has slopes $-3$, $3/5$, and $3/4$, so its unique minimum is at the first corner:

At this dual point the first two inequalities are strict, while the last two are equalities. complementary slackness therefore suggests $x_1=x_2=0$. The remaining primal equations become $4x_3+2x_4=300$, $x_3+5x_4=300$, giving $x_3=x_4=50$. This is nonnegative and satisfies both equations. Its objective function is $3\cdot 50+5\cdot 50=400$, equal to the feasible dual value. weak duality provesNo nonnegativity restriction was imposed on the dual variables; the negative-$v$ second corner is part of the feasible boundary, even though it is not optimal.