Bound a maximization problem from above

Try

Maximize 4x+3y subject to x+y≤5, 2x+y≤8 and x,y≥0. Add twice the first resource inequality to once the second: 4x+3y≤18. The point (3,2) is feasible and attains eighteen. The nonnegative weights (2,1) and the feasible point form a primal–dual certificate. One side supplies an achievable value, the other an upper bound. Their agreement proves optimality without requiring a claim about how either was discovered.

Predict

Predict why resource weights must be nonnegative when combining upper-bound inequalities. Multiplying an inequality by a negative weight reverses its direction, so the desired upper-bound argument would fail. Predict also why dual feasibility involves an inequality rather than necessarily equality in each objective coefficient. If a combined resource coefficient exceeds the objective coefficient, nonnegative decision variables still preserve the bound. Equality is required only for variables that are positive in a zero-gap optimal pair.

Experiment

Check candidate resource weights against the same LP. The dual constraints are u+2v≥4 and u+v≥3, with u,v≥0; its objective is 5u+8v.

Weights (u,v)	Dual feasible?	Bound if feasible
(3,1)	Yes	23
(2,1)	Yes	18
(1,1)	No: second inequality fails	No valid bound

A numerically attractive value from an infeasible dual vector is not a certificate. Similarly, an infeasible primal point can exceed the correct bound without contradicting duality. Always establish both feasibility conditions before interpreting the objective gap.

Understand

For the primal maximization problem cᵀx with Ax≤b,x≥0, the dual minimizes bᵀy subject to Aᵀy≥c,y≥0. Weak duality is the chain cᵀx≤yᵀAx≤yᵀb. The first inequality uses x≥0 and the dual coefficient bound; the second uses y≥0 and primal feasibility. Thus every primal feasible value lies below every dual feasible value. Equality certifies both optima immediately.

Strong LP duality states that a feasible primal with finite optimum has an attained dual optimum of equal value. Here is an algorithmic proof mechanism. Add slacks to obtain equality standard form and use Phase I to find a feasible basis. Exact simplex with a finite anti-cycling rule terminates; if the objective is finite it cannot terminate with an improving ray, so it reaches a feasible basis with nonpositive reduced costs. Set yᵀ=c_BᵀB⁻¹. Reduced-cost signs give Aᵀy≥c, and the basic objective equals bᵀy. Slack columns with zero objective coefficients impose the appropriate nonnegative multipliers for the original inequality formulation. The finite anti-cycling theorem supplies the existence step; the displayed algebra supplies the certificate. A separation-based proof can instead use Farkas’ alternative.

Apply

Distinguish equality standard form from the original inequality convention. For max cᵀx with Ax=b,x≥0, multipliers y are unrestricted in sign because an equality may be multiplied by any real number. The dual coefficient condition remains Aᵀy≥c. Converting an upper-bound constraint to an equality with a nonnegative slack recovers y≥0 from that slack’s dual constraint. Derive this rather than memorizing disconnected sign tables.

If the primal is feasible and unbounded above, a dual feasible point would give a finite upper bound and contradict unboundedness, so the dual is infeasible. Dual infeasibility alone does not prove primal unboundedness: both problems can be infeasible. State every known status and avoid reversing a conditional implication without its feasibility assumption.

Continue

Duality offers a global verification method that remains valuable even when a solver uses an entirely different algorithm. Continue to Complementary slackness to break the objective gap into nonnegative component products. That decomposition will identify exactly which primal resources and dual coefficient bounds must be tight at an optimal pair.

Build your own retained evidence in the optimization certificate investigation: independently derive candidates, submit exact vectors, preserve failed feasibility checks and defend a changed integer decision.