5.1 The dual problem
Consider the primal in the form \[ \text {(P)}\quad \text {maximise } c^{\mathsf T}x \quad \text {subject to}\quad Ax \leq b, \quad x \geq 0 . \] Multiply the \(i\)th constraint by a number \(y_i \geq 0\) and add. If \(A^{\mathsf T}y \geq c\), then for every feasible \(x\), \(c^{\mathsf T}x \leq (A^{\mathsf T}y)^{\mathsf T}x = y^{\mathsf T}Ax \leq y^{\mathsf T}b\): every such \(y\) gives an upper bound on the primal objective. The best bound is the dual \[ \text {(D)}\quad \text {minimise } b^{\mathsf T}y \quad \text {subject to}\quad A^{\mathsf T}y \geq c, \quad y \geq 0 . \] There is one dual variable per primal constraint and one dual constraint per primal variable. The dual of the dual is the primal. For other forms the rules are: a primal equality constraint gives a dual variable free in sign, and a primal variable free in sign gives a dual equality constraint; \(\geq \) constraints in a maximisation give \(y_i \leq 0\). These all follow by writing the problem in the form (P) first.
Example 5.1.1. The dual of Example 2.3.1 (maximise \(10x_1 + 15x_2\) with resource limits \(26\), \(56\), \(5\)) is \[ \text {minimise } 26y_1 + 56y_2 + 5y_3 \quad \text {subject to}\quad 2y_1 + 2y_2 - y_3 \geq 10, \quad y_1 + 4y_2 + y_3 \geq 15, \quad y \geq 0 . \] Read \(y_i\) as a price per unit of resource \(i\). A buyer who wants to acquire all the firm’s resources must offer prices at which making a product is no more profitable than selling the resources it uses (the dual constraints), and wishes to pay as little as possible in total. The answer (Software 5.6.1) is \(y = (\frac 53, \frac {10}3, 0)\), with total value \(26\cdot \frac 53 + 56\cdot \frac {10}3 = 230\), exactly the maximum profit.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.