Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 42 / 2 / b / Solution

If $x_1,x_2$ are integral, the derived surplus and slacksare also nonnegative integers. Therefore an all-integer Gomory fractional cut can be taken from the final tableau's slack rowFor a nonnegative integer dictionary row $x_B+{\sum }_j{a}_j{x}_j=b$, the quantity $x_B+{\sum }_j\lfloor a_j\rfloor x_j$ is an integer at most $b$, so it is at most $\lfloor b\rfloor$. Subtracting from the row proves the cut ${\sum }_j\{a_j\}{x}_j\ge \{b\}$. Applying it here givesBut the original row and $x_4\ge 0$ give $5x_3+4x_5\le 2$. Nonnegativity then givesThis contradicts the valid cut. Therefore the integer program is infeasible, certified by one Gomory fractional cut. It is essential to use the PDF's constraint: the altered TeX problem would have feasible integer points.