The Certificate

Reduced-Cost Certificate

Reduced costs compare every arc cost with the dual prices assigned to its endpoints. Nonnegative reduced costs plus equality of objectives certifies optimality.

highlighted = computed this step

Reduced Costs

The reduced costs are 0, 0, 6, and 0. Motivation: nonnegative reduced costs say no unused reroute can lower cost.

cij−ui−vj≥0c_{ij}-u_i-v_j\ge 0
dual certificate: all reduced costs nonnegativearccostu+vreducedroleA-X220tightA-Y550tightB-X4-26slackB-Y110tightdual11equals primal

Equality Certificate

The shipment cost and dual objective both equal 11. Interpretation: matching primal and dual values closes the optimality gap.

11=1111=11
Primal and dual equalityThe primal shipment cost and the dual objective are recomputed independently.equality certificateshipmentdualvalue1111

Diagram note

Certificate note: tight arcs have zero reduced cost; the one slack arc has positive reduced cost. Pixel positions are rounded for layout; every number shown is exact.

nonnegative reduced costs certify optimality\text{nonnegative reduced costs certify optimality}
dual certificate: all reduced costs nonnegativearccostu+vreducedroleA-X220tightA-Y550tightB-X4-26slackB-Y110tightdual11equals primal