The Certificate

Dual Prices

A transportation optimum comes with prices on supplies and demands. These prices are useful because they form a certificate that can be checked without trusting the search.

highlighted = computed this step

Dual Prices

The supply prices are 0 and -4; the demand prices are 2 and 5. Motivation: these prices are an optimality certificate, not a second shipment plan.

uA=0uB=−4vX=2vY=5u_A=0\quad u_B=-4\quad v_X=2\quad v_Y=5
Dual pricesThe potentials are recomputed from the tight shipped arcs.dual pricesuAuBvXvYdualprice0-42511

Dual Objective

The dual objective value is 11. Why: a feasible dual with the same value as the shipment cost proves optimality.

∑siui+∑djvj=11\sum s_i u_i+\sum d_j v_j=11
Dual pricesThe potentials are recomputed from the tight shipped arcs.dual pricesuAuBvXvYdualprice0-42511

Diagram note

Certificate note: the price row is recomputed from the same cost matrix and shipment basis. Pixel positions are rounded for layout; every number shown is exact.

dual prices are exact certificate values\text{dual prices are exact certificate values}
Dual pricesThe potentials are recomputed from the tight shipped arcs.dual pricesuAuBvXvYdualprice0-42511