Past exam of the probability, statistics and options I course of the University of Oxford / 2011 / T / 1

For the primal equality-form linear program, the dual linear program isIf $x\ge 0$ is primal feasible and $y$ dual feasible, thenThis proves weak duality. Their objective gap is ${\sum }_j{x}_j((A^{T}y{)}_j-c_j)$, a sum of nonnegative terms. The complementary slackness theorem states that a feasible pair is optimal for the two programmes exactly whenThese conditions make the gap zero, which by weak duality certifies optimality; necessity follows from strong duality.

Let $x^{\ast }=(0,3,4,0,5{)}^T$. By strong duality, an optimal dual vector $y^{\ast }$ exists. Complementary slackness at $x^{\ast }$ makes the dual constraints equalities at indices $2,3,5$, where $x_j^{\ast }>0$. The vector $\hat{x}=(0,1,2,0,3{)}^T$ has exactly that same support. It is nonnegative and satisfies $A\hat{x}=\hat{b}$, while $y^{\ast }$ remains dual feasible because dual feasibility depends on $A,c$, not on the right-hand side. HenceThe objective gap is zero, so $\hat{x}$ is optimal for the modified programme. This is support-preserving right-hand-side changes in linear programming.