Maximise 3x + 5y subject to x + y <= 4, x + 3y <= 6 and x, y >= 0. Write the dual, solve both, and verify strong duality along with complementary slackness.

Maximise 3x + 5y subject to x + y <= 4, x + 3y <= 6 and x, y >= 0. Write the dual, solve both, and verify strong duality along with complementary slackness.

Approach: Enumerate the vertices of the feasible region for the primal, then transpose the constraint matrix to write the dual and solve the two equations that the active primal constraints force to be tight.

Both optima equal 14, at the primal point (3, 1) and the dual point (2, 1). The feasible vertices are (0, 0), (4, 0), (0, 2) and the intersection of x + y = 4 with x + 3y = 6, which is (3, 1). Vertex enumeration gives objective values 0, 12, 10 and 14, so the primal optimum is 14 at (3, 1). The dual of this linear programming problem is minimise 4u + 6v subject to u + v >= 3, u + 3v >= 5 and u, v >= 0. Since both primal variables are strictly positive, complementary slackness forces both dual constraints to be tight, so u + v = 3 and u + 3v = 5 give v = 1 and u = 2, with dual objective 4*2 + 6*1 = 14. Strong duality holds as the two values agree, and the multipliers are shadow prices: relaxing the first constraint from 4 to 5 raises the optimum by 2, and the second by 1, which is exactly what a desk needs when deciding which capacity limit to buy relief on.

Follow-up: Change the objective to 3x + 9y. What happens to the dual solution, and what does the degeneracy mean for the shadow price?

Key concepts: linear programming duality, complementary slackness, vertex enumeration, shadow price.