Past exam of the mathematics course of the University of Cambridge / 2023 / ib / Paper 3 / 19H (Optimisation)

The origin belongs to $S$, so $S$ is nonempty. Each displayed inequality defines a closed half-space, and every half-space is a convex set. An intersection of convex sets is convex: if $x,y\in S$ and $0\le t\le 1$, each linear inequality remains valid for $(1-t)x+ty$. Thus $S$ is a nonempty convex polytope.

An extreme point of a convex set $C$ is a point $x\in C$ that cannot be written as $x=(1-t)y+tz$ with $y\ne z$ in $C$ and $0<t<1$.

Start with the eight vertices of the unit cube. The constraint $x_1+x_2+x_3\le 5/2$ removes $(1,1,1)$ and retains the other seven. The cutting plane meets the three cube edges incident to the removed vertex atThese are new vertices. No others occur: at a vertex in three dimensions, three linearly independent bounding planes are active, and choosing triples from the six cube faces and the cutting plane yields precisely the listed points. Hence the ten extreme points are

Put $y_i=1-x_i$. Feasibility gives $y_i\ge 0$ andwhile the objective isTo maximize it, the required total deficit $1/2$ must be assigned entirely to the cheapest variable $y_1$. Thusand the unique optimizer isThis is the vertex $A$ from part (b).

Orient every edge of the feasible convex polytope in the direction of increasing objective. WriteThe possible improving simplex method paths from $O$ to $A$ areThese exhaust the directed edge graph: the ordinary cube edges remain except those incident to the removed vertex $111$; each such edge ends at one of $A,B,C$; and the cutting face contributes the triangle with edges $AB,AC,BC$.

The first two paths use three pivots, while the two paths through both $C$ and $B$ use five. Therefore the smallest and largest possible numbers of simplex steps areand the total number of distinct outcomes isThis is the simplex paths on a cube with one truncated corner calculation.