Proof. \(c^{\mathsf T}x \leq (A^{\mathsf T}y)^{\mathsf T}x = y^{\mathsf T}(Ax) \leq y^{\mathsf T}b\), using \(x \geq 0\) with \(A^{\mathsf T}y \geq c\) in the first step and \(y \geq 0\) with \(Ax \leq b\) in the second. If the values are equal, no feasible \(x\) can do better than \(b^{\mathsf T}y\), and no feasible \(y\) better than \(c^{\mathsf T}x\). If (P) were unbounded and (D) had a feasible \(y\), the primal objective would be bounded by \(b^{\mathsf T}y\). □

Proof. Write (P) in standard form with slacks: minimise \(-c^{\mathsf T}x\) subject to \(Ax + s = b\), \(x, s \geq 0\), with matrix \([A \mid I]\) and costs \((-c, 0)\). By the simplex method with Bland’s rule (Theorem 3.4.1) and two phases, there is an optimal basis \(B\) at which all reduced costs are non-negative. Put \(\mu ^{\mathsf T} = (-c_B)^{\mathsf T}B^{-1}\) and \(y = -\mu \). The reduced costs of the slack columns are \(0 - \mu ^{\mathsf T}e_i = y_i \geq 0\), and those of the \(x\) columns are \(-c_j - \mu ^{\mathsf T}A_j = (A^{\mathsf T}y)_j - c_j \geq 0\). So \(y\) is feasible for (D), and \(b^{\mathsf T}y = -\mu ^{\mathsf T}b\), which is minus the optimal value of the minimisation, that is \(c^{\mathsf T}x\). By weak duality both are optimal. □