Turn a zero gap into coordinatewise conditions

Try

For max 2x+y with x+y≤4, x≤3 and x,y≥0, consider x=3,y=1 and dual resource weights u=1,v=1. The primal value is seven and the dual bound is 4u+3v=7. Both resource constraints are tight, and both positive decision variables have tight dual coefficient bounds. These equalities are consequences of a zero duality gap, not separate numerical coincidences. Complementary slackness exposes that structure coordinate by coordinate.

Predict

Predict what a positive resource slack forces on its dual multiplier at a zero-gap optimum. The multiplier must be zero; otherwise the unused amount would contribute a positive gap. Reverse the implication carefully: a binding resource need not have a positive multiplier. It may be redundant or have no marginal value in the chosen objective. Likewise, a zero decision variable may have either a tight or loose dual coefficient bound.

Experiment

The live experiment uses a separate LP: max 3x+2y with x+y≤b and 2x+y≤6. Change a primal coordinate and a dual weight independently. Predict which feasibility test fails before inspecting the gap. Then request an optimal certificate and identify the products that vanish. This bounded model enumerates boundary intersections; it is not a general simplex implementation or an integer solver.

Live experiment: certify an optimum from both sides

Choose nonnegative production quantities x,y to maximize 3x+2y, subject to x+y≤b and 2x+y≤6. The dual chooses nonnegative resource prices u,v to minimize bu+6v, subject to u+2v≥3 and u+v≥2. Predict which resource should have a positive price, then test all inequalities.

First resource b 2345678Quantity x 00.511.522.533.544.555.566.577.58Quantity y 00.511.522.533.544.555.566.577.58Price u 00.511.522.533.54Price v 00.511.522.533.54

Show one optimal certificateReset experiment

Primal slacks: b−x−y=1; 6−2x−y=2. Primal feasible. Objective 3x+2y=7.

Dual slacks: u+2v−3=0; u+v−2=0. Dual feasible. Objective bu+6v=10.

The algebraic gap is 10−7=3. It decomposes as u(b−x−y)+v(6−2x−y)+x(u+2v−3)+y(u+v−2) = 1 + 2 + 0 + 0.

Both proposals are feasible, so the nonnegative gap bounds how far this primal objective can be below the optimum. A positive gap means this pair does not certify optimality; either proposal may need improvement.

Start at b=4 and find a zero gap. Then change b to 2 or 7 without adjusting the proposals: which feasibility or complementary condition breaks? Prices give local sensitivity only while the relevant optimal structure persists. The reveal button enumerates boundary intersections for this small bounded problem and supplies one dual certificate; it is not a general simplex implementation. All selected values are exact half units in browser arithmetic. Settings are temporary.

Return to the opening worked problem and list its four complementary products. They are u(4−x−y), v(3−x), x(u+v−2), and y(u−1). At the displayed pair every product is zero. Perturb x downward while holding the other numbers fixed and recompute the products and objective gap. Feasibility must still be checked before interpreting any sign.

Understand

For the maximization primal Ax≤b,x≥0 and dual Aᵀy≥c,y≥0, insert and subtract yᵀAx to obtain bᵀy−cᵀx=yᵀ(b−Ax)+xᵀ(Aᵀy−c). Every term on the right is nonnegative for a feasible pair. The gap is zero exactly when each multiplier times its primal slack and each primal variable times its dual slack is zero. These are the complementary-slackness conditions.

Necessity follows for optimal pairs from strong duality and the fact that a finite sum of nonnegative terms is zero only if every term vanishes. Sufficiency needs only weak duality: a feasible pair satisfying these products has equal objective values, so no feasible primal or dual point can improve on them. This distinction is useful when checking a proposed certificate. You do not need to reproduce the solver’s path or invoke a convergence theorem to verify a zero-gap feasible pair.

Apply

Use complementary slackness to recover unknown variables. If both resource multipliers are strictly positive, their resource constraints must be equalities. Solve those equalities to propose a primal point, then check nonnegativity and every other constraint. If both primal variables are positive, their dual coefficient bounds must be equalities. Solve those to propose multipliers, then check nonnegativity. The final checks are essential: assuming an active pattern does not prove that pattern is feasible.

For a counterexample to the reversed implication, maximize the constant zero objective over 0≤x≤1. At x=1 the upper bound is tight, but zero is an optimal multiplier. A constraint can be active without contributing value. In numerical work, near-zero products alone are also insufficient if a feasibility residual is large; report primal residuals, dual residuals and the objective gap together.

Continue

Write an optimality certificate as a short independently checkable record: primal coordinates, dual coordinates, both feasibility checks, complementary products and agreeing objectives. Continue to Sensitivity and parametric LP to interpret multipliers as supporting bounds when resource limits change. A shadow price is not permission to extrapolate one local slope through every future constraint regime.