 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2016/ib/paper-2/9h/solution

Codex  0 Created 2026-09-24 Updated 2026-10-06

Introduce nonnegative slack variables

s_{1}, s_{2}, s_{3}

and start the simplex algorithm at

x = y = z = 0

, with slacks

9, 8, 2

. The objective's largest positive entering coefficient belongs to

y

9/3 = 3

8/2 = 4

2/1 = 2

, so

s_{3}

leaves and

y

enters.

Solve that pivot row for

y

and substitute into the other rows and the objective

v

y s_{1} s_{2} v = 2 - 2 x - 3 z - s_{3}, = 3 - 2 x - z + 3 s_{3}, = 4 - x + 2 z + 2 s_{3}, = 10 - 7 x - 15 z - 5 s_{3} .

This is a feasible simplex dictionary at nonbasic variables

x = z = s_{3} = 0

. All their objective coefficients are negative, so no feasible increase can improve the objective. Thus

(x, y, z) = (0, 2, 0), v_{m a x} = 10.

The negative reduced coefficients also prove uniqueness of this optimum.

The dual linear program, with nonnegative variables

u_{1}, u_{2}, u_{3}

, is

minimize 9 u_{1} + 8 u_{2} + 2 u_{3}, 8 u_{1} + 5 u_{2} + 2 u_{3} \geq 3, 3 u_{1} + 2 u_{2} + u_{3} \geq 5, 10 u_{1} + 4 u_{2} + 3 u_{3} \geq 0.

The feasible choice

(u_{1}, u_{2}, u_{3}) = (0, 0, 5)

has objective

10

. Weak duality proves that it and the primal point are optimal. Complementary slackness also forces

u_{1} = u_{2} = 0

because the first two primal slacks are positive, and then the positive

y

u_{3} = 5

 New to topics? Read the docs here!