Exercises — Linear Programming
Chapter 2 · Fully solved exercises on LP formulation, geometry, and standard forms
Exercise 1: LP Formulation — Diet Problem
Problem. A diet must provide at least 800 kcal/day and at least 50 g of protein/day. Food A provides 200 kcal and 15 g protein and costs €2 per unit. Food B provides 400 kcal and 10 g protein and costs €3 per unit. Food C provides 100 kcal and 20 g protein and costs €1.5 per unit. Formulate an LP to minimise cost. Find the optimal solution graphically using only foods A and B (2-variable case).
Solution. Let \(x_1\) = units of food A, \(x_2\) = units of food B.
\[ \begin{aligned} & \text{minimise} && 2x_1 + 3x_2 \\ & \text{subject to} && x_1 + 2x_2 \geq 4 && \text{(800 kcal, scaled by 1/200)} \\ & && 3x_1 + 2x_2 \geq 10 && \text{(50 g protein, scaled by 1/5)} \\ & && x_1, x_2 \geq 0. \end{aligned} \]
The feasible region is the intersection of two half-planes above the constraint lines, restricted to the first quadrant. We evaluate the objective at each vertex of the feasible region boundary:
| Vertex | How obtained | Cost |
|---|---|---|
| \((4, 0)\) | \(x_1 + 2x_2 = 4\), \(x_2 = 0\) | \(2(4)+3(0) = 8\) |
| \((3, 0.5)\) | Intersection of both constraints | \(2(3)+3(0.5) = 7.5\) |
| \((0, 5)\) | \(3x_1 + 2x_2 = 10\), \(x_1 = 0\) | \(2(0)+3(5) = 15\) |
Intersection of both constraints: from \(x_1 + 2x_2 = 4\) and \(3x_1 + 2x_2 = 10\), subtracting gives \(2x_1 = 6\), so \(x_1 = 3\) and \(x_2 = 0.5\).
Optimal solution: \((x_1, x_2) = (3,\, 0.5)\), minimum cost = €7.50.
The isocost line \(2x_1 + 3x_2 = 7.5\) (dashed orange) is the lowest-cost line that still touches the feasible region. It does so at the vertex \((3, 0.5)\).
Exercise 2: Convex Hull — Identify Vertices
Problem. Given eight points: \(A=(3,3)\), \(B=(3,4)\), \(C=(5,3)\), \(D=(4,4)\), \(E=(2,1)\), \(F=(1,4)\), \(G=(2,2)\), \(H=(3.5,2)\). Which are vertices of the convex hull?
Solution. A point is a vertex of the convex hull if and only if it cannot be expressed as a convex combination of the other points. We check each candidate:
- \(F = (1,4)\): leftmost point — clearly a vertex. ✓
- \(B = (3,4)\): lies on segment \(FD\) since \(F=(1,4)\), \(D=(4,4)\) are both at height 4, and \(1 < 3 < 4\). Specifically \(B = \tfrac{2}{3}F + \tfrac{1}{3}D\). Not a vertex.
- \(D = (4,4)\): top-right extreme point — vertex. ✓
- \(C = (5,3)\): rightmost point — vertex. ✓
- \(H = (3.5,2)\): lies on segment \(CE\). Parametric: \((5-3t,\, 3-2t)\); at \(t=0.5\) gives \((3.5,2) = H\). Not a vertex.
- \(E = (2,1)\): bottom-left extreme point — vertex. ✓
- \(A = (3,3)\): interior point (convex combination of \(E\), \(C\), \(D\), \(F\)). Not a vertex.
- \(G = (2,2)\): interior point (between \(E\) and \(F\)). Not a vertex.
Convex hull vertices (in order): \(E=(2,1)\), \(C=(5,3)\), \(D=(4,4)\), \(F=(1,4)\).
Green diamonds are the four hull vertices; orange circles are points that lie strictly inside the hull or on a hull edge without being extreme points.
Exercise 3: Standard Form Conversion
Problem. Convert the following LP to standard form (maximisation, equality constraints, all variables \(\geq 0\)):
\[ \begin{aligned} & \text{maximise} && 3x_1 - 2x_2 + x_3 \\ & \text{subject to} && x_1 + x_2 \leq 5 \\ & && 2x_1 - x_2 \geq 3 \\ & && x_1 + x_3 = 4 \\ & && x_1 \geq 0,\quad x_2\ \text{free},\quad x_3 \leq 0. \end{aligned} \]
Solution.
Variable substitutions:
- \(x_2\) is free: write \(x_2 = x_2' - x_2''\) with \(x_2', x_2'' \geq 0\).
- \(x_3 \leq 0\): write \(x_3 = -x_3'\) with \(x_3' \geq 0\).
Constraint transformations:
| Constraint | Transformation | Standard form |
|---|---|---|
| \(x_1 + x_2 \leq 5\) | add slack \(s_1 \geq 0\) | \(x_1 + x_2' - x_2'' + s_1 = 5\) |
| \(2x_1 - x_2 \geq 3\) | subtract surplus \(s_2 \geq 0\) | \(2x_1 - x_2' + x_2'' - s_2 = 3\) |
| \(x_1 + x_3 = 4\) | substitute \(x_3 = -x_3'\) | \(x_1 - x_3' = 4\) |
Objective (already maximisation):
\[ \max\ 3x_1 - 2(x_2' - x_2'') + (-x_3') = 3x_1 - 2x_2' + 2x_2'' - x_3' \]
Standard form LP:
\[ \begin{aligned} & \text{maximise} && 3x_1 - 2x_2' + 2x_2'' - x_3' \\ & \text{subject to} && x_1 + x_2' - x_2'' + s_1 = 5 \\ & && 2x_1 - x_2' + x_2'' - s_2 = 3 \\ & && x_1 - x_3' = 4 \\ & && x_1,\, x_2',\, x_2'',\, x_3',\, s_1,\, s_2 \geq 0. \end{aligned} \]
The resulting standard form has 6 non-negative variables (\(x_1, x_2', x_2'', x_3', s_1, s_2\)) and 3 equality constraints.
Exercise 4: LP Geometry — Optimal Solutions
Problem. For the LP \(\max\, c^\top x\) subject to \(Ax \leq b\), \(x \geq 0\), describe geometrically when: (a) there is a unique optimal vertex; (b) there are infinitely many optimal solutions; (c) the LP is unbounded; (d) the LP is infeasible.
Solution.
(a) Unique optimal vertex. The objective gradient \(\nabla c\) points strictly into the interior angle at one vertex. The objective isoline last touches the feasible region at exactly one point.
(b) Infinitely many optima (edge). \(\nabla c\) is parallel to a face (edge in 2D) of the feasible region. The optimal isoline coincides with that entire edge; every point on it achieves the same objective value.
(c) Unbounded. The feasible region extends to infinity in the direction of \(\nabla c\). No finite upper bound on the objective exists.
(d) Infeasible. The constraints are contradictory; the feasible region is empty.
Summary:
| Case | Geometric condition |
|---|---|
| (a) Unique optimum | \(\nabla c\) not parallel to any face of the optimal vertex |
| (b) Infinite optima | \(\nabla c\) parallel to a binding face (edge) |
| (c) Unbounded | Feasible region unbounded in direction \(\nabla c\) |
| (d) Infeasible | Constraints are contradictory; \(P = \emptyset\) |
Exercise 5: LP Duality Warm-up — Reading the Dual
Problem. State the dual of:
\[ \begin{aligned} & \text{minimise} && 5x_1 + 4x_2 + 3x_3 \\ & \text{subject to} && 6x_1 + x_2 + x_3 \geq 2 \\ & && x_1 + x_2 + x_3 \geq 1 \\ & && x_1 + 2x_2 + x_3 \geq 1 \\ & && x_1, x_2, x_3 \geq 0. \end{aligned} \]
Solution. The primal is of the form \(\min\, c^\top x\) subject to \(Ax \geq b\), \(x \geq 0\). The standard duality rule gives: Dual: \(\max\, b^\top y\) subject to \(A^\top y \leq c\), \(y \geq 0\).
Identifying the data:
\[ A = \begin{pmatrix} 6 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 2 & 1 \end{pmatrix}, \quad b = \begin{pmatrix} 2 \\ 1 \\ 1 \end{pmatrix}, \quad c = \begin{pmatrix} 5 \\ 4 \\ 3 \end{pmatrix}. \]
The dual problem is:
\[ \begin{aligned} & \text{maximise} && 2y_1 + y_2 + y_3 \\ & \text{subject to} && 6y_1 + y_2 + y_3 \leq 5 \\ & && y_1 + y_2 + 2y_3 \leq 4 \\ & && y_1 + y_2 + y_3 \leq 3 \\ & && y_1, y_2, y_3 \geq 0. \end{aligned} \]
Notice that the constraint matrix of the dual is \(A^\top\) — rows of \(A\) become columns of the dual, and vice versa. The cost vector \(c\) becomes the RHS of dual constraints, and \(b\) becomes the dual objective coefficients.
Weak Duality check: any feasible dual solution \(y\) gives a lower bound on the primal objective. For example, \(y = (1/2, 0, 0)\) is dual feasible (check: \(6(1/2)=3\leq5\), \((1/2)\leq4\), \((1/2)\leq3\)) and gives dual objective \(2(1/2) = 1 \leq\) primal optimal value. Strong Duality guarantees that at optimality both objectives coincide.