Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 212 / 1 / Solution

Introduce integer-valued slack variables $s_1=11-2x_1-x_2$ and $s_2=6+x_1-2x_2$. Write $Z=4x_1+3x_2$. The initial simplex dictionary isIn the simplex algorithm, let $x_1$ enter. The first constraint is the only limiting one, so $s_1$ leaves at $x_1=11/2$. Substitution givesNow $x_2$ enters and $s_2$ leaves: its ratio $23/5$ is smaller than the first row's ratio $11$. The resulting simplex dictionary isAll nonbasic objective coefficients are nonpositive, and the basic values are nonnegative. Thus the continuous linear program has optimum

For integer programming, a row $x_B+{\sum }_j{a}_j{x}_j=b$ with integer variables yields the Gomory fractional cut ${\sum }_j\{a_j\}{x}_j\ge \{b\}$, where $\{u\}=u-\lfloor u\rfloor$ is the fractional part. In the first row, the coefficient of $s_2$ on the left is $-1/5$, whose fractional part is $4/5$, not $-1/5$. The two possible initial Gomory fractional cuts are thereforeIndeed $s_1+2s_2=23-5x_2$. Choose the second row: $x_2\le 4$ implies $x_2\le 9/2$, so its cut removes a strictly larger portion of the feasible polygon. This compares both printed alternatives before any further integer rounding.

Use the normalized integer slack variable $s_3=4-x_2$, rather than an unnecessarily scaled cut slack. At the current basis,The simplex dictionary is dual feasible but primal infeasible. In the dual simplex algorithm, $s_3$ leaves; the ratios of objective loss to improvement of this negative basic value are $11$ for $s_1$ and $1$ for $s_2$, so $s_2$ enters. The pivot givesThe relaxed optimum is now $(7/2,4)$, still nonintegral. The fractional $x_1$ row gives the next Gomory fractional cutThe negative left-hand coefficient $-1/2$ of $s_3$ also has fractional part $1/2$. Normalize the new integer slack variable as $s_4=7-x_1-x_2$. Its dictionary row is $s_4=-1/2+s_1/2+s_3/2$. The dual simplex algorithm chooses $s_3$ to enter: its ratio is $1/(1/2)=2$, compared with $2/(1/2)=4$ for $s_1$. Substitution givesSetting the nonbasic $s_1,s_4$ to zero gives a feasible integer solution. The final objective row bounds every point in the cut relaxation by $25$, so the integer optimum isBoth cuts are valid for every original integer feasible point, making this also a certificate for the original integer program.