Past exam of the mathematics course of the University of Cambridge / 2017 / ib / Paper 1 / 8H (Optimisation)

Introduce nonnegative slack variables $s_1,s_2$ and use the origin as the initial feasible simplex basis:In the simplex method, let $x_2$ enter. The ratio test is $\min (10,15)=10$, so $s_1$ leaves. Solving the first constraint for $x_2$ yields the dictionaryAll nonbasic variables are nonnegative and have negative reduced objective coefficients. Setting them to zero is feasible and optimal:Subtracting $\Delta$ from both right-hand sides changes the same dictionary toIt remains feasible throughout $0\le \Delta \le 10$, including the degenerate endpoint $\Delta =10$, and the reduced coefficients are unchanged. HenceAs an independent optimality certificate, $z\le 2(x_1+x_2+2x_3)\le 2(10-\Delta )$, with equality at the stated point. Negative reduced coefficients also prove uniqueness of the optimal decision vector.