optional · interactive figures

Explore: polyhedra and Fourier–Motzkin

Unit 01's polygon to poke at: switch constraints on and off, turn the objective, hover for slacks, and watch Fourier–Motzkin project it.

optional: nothing in the lab depends on itback to the slides

01 · explore

Poke the polygon

Try: hover the corner (2.5, 1.5); tick constraint 5; point the arrow along constraint 4; untick constraint 3; tick constraint 8. Static versions: the running example, tight constraints.

What it shows. The polygon of constraints 1–4 (unit 01's running example), with constraints 5–8 available to switch on. Everything is computed in the page from the constraints written in this file: the region by clipping, the corners by solving every pair of constraints and keeping the feasible ones, the optimum by comparing corners, the certificate by writing $c$ as a nonnegative combination of two constraints tight at the optimum.

Things to try.

Hover $(2.5, 1.5)$: constraints 3 and 4 light up as tight (slack 0). Hover $(1, 1)$: nothing is tight.
Tick constraint 5, $3x - y \le 6$: the shape doesn't change, but $(2.5, 1.5)$ has three tight constraints. That is the degenerate corner of "Finding corners by trying pairs of constraints".
Drag the arrow to $c = (1, -1)$: a whole edge is optimal, the face of "Faces".
Untick constraint 3: the region runs off to the right and $\max 2x + y$ is unbounded; the dashed edges mark where the view, not a constraint, cuts the region.
Tick constraint 8, $x \ge 5$: nothing is left. That system has a Farkas certificate: constraints 3 and 8 add to $y \le -1$, and with constraint 2 to $0 \le -1$.
With $c = (2, 1)$ the certificate reads $1.5 \cdot$ constraint 3 $+ 0.5 \cdot$ constraint 4: those weights are the dual values units 02 and 03 compute.

01 · explore

The shadow on the y-axis

Try: switch constraints on and off and watch the list of derived constraints and the bar on the left. Static version: eliminate x.

What it shows. Fourier–Motzkin elimination of $x$, live. The constraints are sorted by the sign of their $x$-coefficient; every upper bound on $x$ is added to every lower bound with positive multipliers so that $x$ cancels, and constraints without $x$ are kept. The derived constraints describe the projection, drawn as the thick bar on the left.

With constraints 1–4 you get the slide's result, $0 \le y \le 4$, including the redundant $-y \le 1$.
Tick constraint 7 ($y \le 3$): it has no $x$, so it passes straight through, and the bar shrinks to $[0, 3]$.
Tick constraint 8 ($x \ge 5$): one derived constraint reads $0 \le$ something negative after the next elimination, or the interval turns empty: the Farkas certificate of the constructive proof.
Tick constraint 5: another upper bound on $x$, so another pair and another derived constraint. That growth, repeated, is the explosion of "Deciding feasibility".