optional · interactive figures

Explore: duality

The duals as prices you can push on, and the dual simplex re-optimising after a cut, replayed from the reference solution.

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

03 · explore

Prices, and how long they hold

Try: slide b₁ from 4 to 5 and back, then below 3 and above 6. Static versions: shadow prices, ranging.

What it shows. The textbook LP $\max 3x + 2y$, $x + y \le b_1$, $2x + y \le b_2$, with both right-hand sides on sliders. Left: the region and its optimum. Right: $z^*$ as a function of $b_1$ (with $b_2$ fixed), the prices $u, v$ read off the optimum, and the interval of $b_1$ over which they stay the same.

How the numbers are computed. In the page, from the rows: the optimum by comparing corners, the prices by writing $c$ as a nonnegative combination of the two rows tight at the optimum (the certificate of unit 01), the curve by re-solving at 161 values of $b_1$, and the shaded range as the run of those values where the same two rows and weights are optimal.

At $b_1 = 4$, $b_2 = 6$: optimum $(2, 2)$, $z^* = 10$, prices $(1, 1)$, range $[3, 6]$: "Ranging: how long the price holds".
Inside the range the dashed prediction $z^* + u \Delta$ lies on the curve; outside it leaves the curve, which is why lab step 5 refuses to predict there.
Below $b_1 = 3$ the row $2x + y \le 6$ has slack: its price drops to 0 and $b_1$'s price jumps to 3.
The check row is strong duality: $b_1 u + b_2 v = z^*$ for every slider position.

03 · explore

Add a cut, and re-optimise from the old basis

Try: step through each cut in the menu; watch which rhs is negative and which column wins the ratio test. Static version: one dual simplex pivot.

What it shows. The dual simplex method warm-starting after a cut. Each run starts at the optimum $(2, 2)$, adds one cut in the current basis (reference add_constraint), and re-optimises with the reference dual_simplex; its pivots are recorded as they happen by slides/viz/traces/u03.py. The "ratio" row lists objective entry ÷ −(row entry) for the negative entries of the leaving row.

x ≤ 1.5: the deck's example, one pivot to $(1.5, 2.5)$, duals $(2, 0, 1)$.
x ≤ 1: the same pivot, landing on $(1, 3)$ with $z = 9$.
y ≤ 1: now $s_1$ enters, and the new corner is $(2.5, 1)$ on $2x + y = 6$.
x + y ≥ 5: the cut's row has a negative rhs and no negative entry, so no pivot is possible: the LP is infeasible, the case lab step 4's third test builds.