Exercises — Duality
Chapter 5 · Fully solved exercises on LP duality, complementary slackness, and sensitivity
Exercise 1: Write the Dual (Mixed Constraints)
Problem. Write the dual of the following LP (UniUD exam problem):
\[ \begin{aligned} & \text{maximise} && 3x_1 + 2x_2 - x_3 \\ & \text{subject to} && x_1 + 2x_2 + x_3 \leq 4 \\ & && -x_1 + x_2 + 2x_3 \geq 1 \\ & && 2x_1 - x_2 + x_3 = 3 \\ & && x_1 \geq 0,\; x_2 \leq 0,\; x_3 \;\text{free.} \end{aligned} \]
Solution.
Step 1 — Bring to canonical maximisation form (all constraints \(\leq\), all variables \(\geq 0\)).
- Multiply constraint 2 by \(-1\): \(x_1 - x_2 - 2x_3 \leq -1\).
- Substitute \(x_2' = -x_2 \geq 0\) (since \(x_2 \leq 0\), \(x_2'\) is non-negative). Then \(2x_2 = -2x_2'\).
Reformulated primal:
\[ \begin{aligned} & \text{maximise} && 3x_1 - 2x_2' - x_3 \\ & \text{subject to} && x_1 - 2x_2' + x_3 \leq 4 \\ & && x_1 - x_2' - 2x_3 \leq -1 \\ & && 2x_1 + x_2' + x_3 = 3 \\ & && x_1, x_2' \geq 0,\; x_3 \;\text{free.} \end{aligned} \]
Step 2 — Apply duality rules column by column.
| Variable type | Dual constraint type |
|---|---|
| Primal \(\leq\) constraint | Dual variable \(y_i \geq 0\) |
| Primal \(=\) constraint | Dual variable \(y_i\) free |
| Primal variable \(\geq 0\) | Dual constraint \(\geq c_j\) |
| Primal variable free | Dual constraint \(= c_j\) |
Assign dual variables: \(y_1 \geq 0\) (row 1, \(\leq\)), \(y_2 \geq 0\) (row 2, \(\leq\)), \(y_3\) free (row 3, \(=\)).
Dual constraints from each primal column:
- Column \(x_1\) (coefficients \(1, 1, 2\); cost \(3\); \(x_1 \geq 0\)): \(y_1 + y_2 + 2y_3 \geq 3\)
- Column \(x_2'\) (coefficients \(-2, -1, 1\); cost \(-2\); \(x_2' \geq 0\)): \(-2y_1 - y_2 + y_3 \geq -2\)
- Column \(x_3\) (coefficients \(1, -2, 1\); cost \(-1\); \(x_3\) free): \(y_1 - 2y_2 + y_3 = -1\)
Dual problem:
\[ \begin{aligned} & \text{minimise} && 4y_1 - y_2 + 3y_3 \\ & \text{subject to} && y_1 + y_2 + 2y_3 \geq 3 \\ & && -2y_1 - y_2 + y_3 \geq -2 \\ & && y_1 - 2y_2 + y_3 = -1 \\ & && y_1, y_2 \geq 0,\; y_3 \;\text{free.} \end{aligned} \]
Exercise 2: Dual of a Minimisation Problem
Problem. Write the dual of:
\[ \begin{aligned} & \text{minimise} && 5x_1 + 3x_2 + 4x_3 \\ & \text{subject to} && 3x_1 + x_2 + 2x_3 \geq 7 \\ & && x_1 + x_2 + x_3 \geq 4 \\ & && x_1, x_2, x_3 \geq 0. \end{aligned} \]
Solution.
This is a standard min problem with \(\geq\) constraints and non-negative variables. The duality rule for \(\min\; c^\top x,\; Ax \geq b,\; x \geq 0\) is:
\[ \text{Dual:}\quad \max\; b^\top y \quad \text{s.t.}\; A^\top y \leq c,\; y \geq 0. \]
With \(A = \begin{pmatrix}3&1&2\\1&1&1\end{pmatrix}\), \(b = \begin{pmatrix}7\\4\end{pmatrix}\), \(c = \begin{pmatrix}5\\3\\4\end{pmatrix}\):
\[ \begin{aligned} & \text{maximise} && 7y_1 + 4y_2 \\ & \text{subject to} && 3y_1 + y_2 \leq 5 \\ & && y_1 + y_2 \leq 3 \\ & && 2y_1 + y_2 \leq 4 \\ & && y_1, y_2 \geq 0. \end{aligned} \]
Solving the dual graphically. The vertices of the dual feasible region are:
| Vertex \((y_1, y_2)\) | Dual objective \(w = 7y_1+4y_2\) |
|---|---|
| \((0,\;0)\) | \(0\) |
| \((5/3,\;0)\) | \(35/3 \approx 11.67\) |
| \((0,\;3)\) | \(12\) |
| \((1,\;2)\) | \(15\) |
Optimal: \((y_1^*, y_2^*) = (1, 2)\), \(w^* = 15\).
By strong duality, the primal optimum is also \(z^* = 15\). We can recover the primal solution via complementary slackness: \(y_1 > 0 \Rightarrow 3x_1+x_2+2x_3 = 7\); \(y_2 > 0 \Rightarrow x_1+x_2+x_3 = 4\). Setting \(x_3 = 0\) gives \(x_1 = 3/2\), \(x_2 = 5/2\), \(z = 15\) ✓.
Exercise 3: Multiple Choice — Duality Theory
Problem. Which of the following statements are true? Justify each.
- If the primal has a finite optimal solution, the dual is unbounded.
- If the primal is infeasible, the dual must also be infeasible.
- At any pair of primal/dual optimal solutions, complementary slackness holds.
- The dual of the dual is the primal.
- The optimal primal and dual objective values are always equal (when both are feasible and bounded).
Solution.
(a) FALSE. By the Strong Duality Theorem, if the primal has a finite optimal then the dual also has a finite optimal, and the two objective values are equal. The dual cannot be unbounded.
(b) FALSE. If the primal is infeasible, the dual is either infeasible or unbounded. Both cases are possible. Example: a primal with contradictory constraints can have a dual that is either unbounded or also contradictory depending on the structure.
(c) TRUE. The complementary slackness conditions \(s_i y_i = 0\) (primal slack times dual variable) and \(x_j r_j = 0\) (primal variable times dual slack) are necessary and sufficient for a primal-dual pair to be simultaneously optimal.
(d) TRUE. Taking the dual of a dual LP, after standard transformations, returns an equivalent form of the original primal. This is the double-dual theorem.
(e) TRUE. This is exactly the Strong Duality Theorem: \(z^*_P = z^*_D\) whenever both problems are feasible and their optimal values are finite.
Exercise 4: Complementary Slackness
Problem. Consider the primal LP:
\[ \begin{aligned} & \text{maximise} && 4x_1 + 3x_2 \\ & \text{subject to} && x_1 + x_2 \leq 4 \\ & && x_1 + 2x_2 \leq 6 \\ & && x_1, x_2 \geq 0. \end{aligned} \]
Write the dual and verify complementary slackness at the optimal solution.
Solution.
Step 1 — Find the primal optimal. The feasible vertices and their objective values are:
| Vertex | \(4x_1+3x_2\) |
|---|---|
| \((0,\;0)\) | \(0\) |
| \((4,\;0)\) | \(\mathbf{16}\) |
| \((2,\;2)\) | \(14\) |
| \((0,\;3)\) | \(9\) |
Optimal: \(x_1^* = 4,\; x_2^* = 0,\; z^* = 16\).
Step 2 — Write the dual. Assigning \(y_1 \geq 0\) to constraint 1 and \(y_2 \geq 0\) to constraint 2:
\[ \begin{aligned} & \text{minimise} && 4y_1 + 6y_2 \\ & \text{subject to} && y_1 + y_2 \geq 4 \quad (x_1) \\ & && y_1 + 2y_2 \geq 3 \quad (x_2) \\ & && y_1, y_2 \geq 0. \end{aligned} \]
Step 3 — Apply complementary slackness. At \((x_1^*, x_2^*) = (4, 0)\):
- Primal slack \(s_1 = 4 - 4 - 0 = 0\): constraint 1 is tight; \(y_1\) may be positive.
- Primal slack \(s_2 = 6 - 4 - 0 = 2 > 0\): constraint 2 is slack; CS requires \(y_2 = 0\).
CS for primal variables:
- \(x_1 = 4 > 0\) \(\Rightarrow\) dual constraint 1 is tight: \(y_1 + y_2 = 4 \Rightarrow y_1 = 4\).
- \(x_2 = 0\) \(\Rightarrow\) dual constraint 2 may be slack: \(y_1 + 2y_2 = 4 + 0 = 4 \geq 3\) ✓.
Dual optimal: \((y_1^*, y_2^*) = (4, 0)\), \(w^* = 4 \times 4 + 6 \times 0 = 16 = z^*\) ✓.
Exercise 5: Sensitivity Analysis
Problem. For the LP:
\[ \begin{aligned} & \text{maximise} && 2x_1 + 3x_2 \\ & \text{subject to} && x_1 + 2x_2 \leq 10 \\ & && 3x_1 + x_2 \leq 15 \\ & && x_1, x_2 \geq 0, \end{aligned} \]
the optimal solution is \(x_1^* = 4,\; x_2^* = 3,\; z^* = 17\). By how much can \(c_2\) (the coefficient of \(x_2\)) change while keeping the current basis optimal?
Solution.
Step 1 — Identify the optimal basis. Both constraints are tight at \((4, 3)\): \(4 + 2(3) = 10\) ✓ and \(3(4) + 3 = 15\) ✓. The optimal basis is \(\mathcal{B} = \{x_1, x_2\}\), with \(s_1 = s_2 = 0\) (non-basic slacks).
The basis matrix and its inverse are: \[ B = \begin{pmatrix}1 & 2 \\ 3 & 1\end{pmatrix}, \qquad B^{-1} = \frac{1}{-5}\begin{pmatrix}1 & -2 \\ -3 & 1\end{pmatrix} = \begin{pmatrix}-1/5 & 2/5 \\ 3/5 & -1/5\end{pmatrix}. \]
Step 2 — Compute reduced costs as a function of \(c_2 = 3 + \delta\). The reduced cost vector for the non-basic slacks is:
\[ \bar{c}_N = c_N - c_B^\top B^{-1} N = \begin{pmatrix}0\\0\end{pmatrix} - \begin{pmatrix}2 \\ 3+\delta\end{pmatrix}^\top B^{-1} \]
since the non-basic columns are \(N = I\) (identity, for the slack variables). Evaluating:
\[ \bar{c}_{s_1}(\delta) = -\left(2 \cdot (-\tfrac{1}{5}) + (3+\delta)\cdot\tfrac{3}{5}\right) = -\tfrac{7}{5} - \tfrac{3}{5}\delta \]
\[ \bar{c}_{s_2}(\delta) = -\left(2 \cdot \tfrac{2}{5} + (3+\delta)\cdot(-\tfrac{1}{5})\right) = -\tfrac{1}{5} + \tfrac{1}{5}\delta \]
Step 3 — Impose optimality. For maximisation, all reduced costs of non-basics must be \(\leq 0\):
\[ -\tfrac{7}{5} - \tfrac{3}{5}\delta \leq 0 \;\Longrightarrow\; \delta \geq -\tfrac{7}{3} \]
\[ -\tfrac{1}{5} + \tfrac{1}{5}\delta \leq 0 \;\Longrightarrow\; \delta \leq 1 \]
Conclusion: The current basis remains optimal while \(c_2 \in \left[\tfrac{2}{3},\; 4\right]\).
- \(c_2\) can decrease by at most \(\tfrac{7}{3} \approx 2.33\) (to \(c_2 = \tfrac{2}{3}\)). At this limit, vertex \((5, 0)\) becomes equally optimal.
- \(c_2\) can increase by at most \(1\) (to \(c_2 = 4\)). At this limit, vertex \((0, 5)\) becomes equally optimal.