For the same multiplier convention, the Lagrangian dual problem is
For every feasible and every , the equality constraint implies . Taking first the infimum over feasible and then the supremum over proves weak duality:
The inequalities remain meaningful with the usual extended-value conventions, including when the Lagrangian is unbounded below. Equality of optimum values, or their attainment, does not follow from weak duality. If the sufficient pair in part (a) exists, it attains equality, since .
Introduce slack variables . In the initial simplex algorithm dictionary, has the largest positive objective coefficient. The ratio test gives
so enters and leaves. Solving the third constraint for gives
The objective becomes
Every reduced cost is now nonpositive, so the simplex optimality criterion gives
The other two slacks both equal one.
The dual linear program is
The vector
is dual feasible and has objective value . By weak duality, it and the displayed primal point are optimal; they also satisfy complementary slackness.
For the equality constraint, the Lagrangian and dual function are
and the Lagrangian dual problem is . Weak duality says for every . Strong duality means the dual supremum equals the primal infimum, usually with a dual maximizer. A sufficient convex constraint qualification is that be proper, closed and convex and that some satisfy .
Introduce nonnegative dual variables and for the two constraints. The dual of a minimization linear program in inequality form is
Indeed, if and are feasible, then
which is weak duality.
The dual from part (a) is
The point is dual feasible and has value . The primal point
is feasible and also has objective value
By weak duality, neither point can be improved, so
The strict dual inequalities for and , together with complementary slackness, force at any optimum; the two tight primal constraints then force and . Thus the displayed minimizer is unique.
Associate a nonnegative Lagrange multiplier with each inequality. The Lagrangian dual problem begins with
Its infimum over is finite exactly when , in which case it equals . The dual linear program is consequently
For any primal-feasible and dual-feasible ,
which proves weak duality. Strong duality means equality of the two optimal values. The stated strict feasibility is the Slater condition; together with finiteness of the primal optimum it gives strong duality and an attained dual optimum .
For every primal feasible solution , weak duality gives
Thus no primal feasible solution improves on . Similarly, for every dual feasible solution ,
Therefore both candidates are optimal, with the same objective function value. Equality is a linear programming optimality certificate and does not require a separate existence argument.
For feasible solutions , nonnegativity gives
The first inequality uses and ; the second uses and . This is weak duality.
The complementary slackness conditions are
To see their role, decompose the duality gap as
Every summand is nonnegative for feasible solutions, so the gap is zero exactly when every displayed product vanishes. Zero gap implies optimality by weak duality. Conversely, strong duality states that primal and dual optima, when both are attained, have equal values, and hence satisfy these conditions.
At , the first three dual left sides are , and , strictly above their bounds , and . Thus complementary slackness forces . Both dual variables are positive, so both primal inequalities are equalities:
Solving this linear system gives
All components are nonnegative, the two original upper bounds are met exactly, and the objective function equals the dual value. The weak duality bound therefore certifies optimality. The forced zero components and unique solution of the two remaining equalities also prove that the primal optimum is unique.
The dual is
weak duality says that any feasible primal and dual satisfy . Indeed,
The first inequality uses and , and the second uses and . This proves the theorem. In particular, feasible solutions with equal objective function values are optimal for both problems.
The two primal constraints are equalities, so let the two dual variables be free. Primal feasibility restricts to the nonnegative orthant, giving
Thus the feasible region lies above all four lines:
Its lower boundary follows the third line up to , the fourth line from there to , and then the first line. The second line never determines the envelope. Along these three pieces respectively has slopes , , and , so its unique minimum is at the first corner:
At this dual point the first two inequalities are strict, while the last two are equalities. complementary slackness therefore suggests . The remaining primal equations become , , giving . This is nonnegative and satisfies both equations. Its objective function is , equal to the feasible dual value. weak duality proves
No nonnegativity restriction was imposed on the dual variables; the negative- second corner is part of the feasible boundary, even though it is not optimal.
Figure 1.
The dual lower envelope has its objective function minimum at the intersection of the third and fourth constraints
. Details.
The dual linear program is
For feasible , nonnegativity and the two constraint inequalities imply weak duality:
If a feasible pair has equal objectives, every primal feasible objective is at most that common value and every dual feasible objective at least it. Thus both feasible solutions are optimal. Strong duality is not needed for this certificate.
For the primal equality-form linear program, the dual linear program is
If is primal feasible and dual feasible, then
This proves weak duality. Their objective gap is , a sum of nonnegative terms. The complementary slackness theorem states that a feasible pair is optimal for the two programmes exactly when
These conditions make the gap zero, which by weak duality certifies optimality; necessity follows from strong duality.
For every perfect matching , each vertex occurs exactly once, so the feasibility inequalities give
If a perfect matching uses only tight edges, equality holds. It therefore attains a lower bound valid for every perfect matching, proving minimum cost. In a bipartite graph this is the weak duality and complementary slackness certificate for the assignment problem. The Hungarian algorithm maintains feasible row and column potentials and seeks a perfect matching among tight edges.
At the current dual prices , the new product has reduced cost , so it can increase profit. Its transformed resource column is
Increasing by changes the old basic variables to and . Thus leaves at , giving
For a certificate, take dual prices . They price the four products at , respectively, each at least its profit. Their resource total is , equal to the achieved profit. Weak duality proves optimality, and the profit has increased by two.
Both objectives equal : and . Weak duality bounds the value of every primal feasible point above by every dual feasible objective. Equality for this feasible pair therefore proves both are optimal, without needing to solve either problem further.
Take the dual vector . Its column constraints have values , exceeding or equaling ; its entries are positive. Thus it is dual feasible. The first two constraints are equalities while the last two have strictly positive slack, suggesting . Solve the two primal equalities to get , , both positive.
The resulting feasible objectives agree:
Weak duality proves optimality. Strict dual slack in columns three and four and positive dual entries force the two primal equalities, proving primal uniqueness; positive first two primal coordinates force the two independent dual equalities, proving dual uniqueness.
The dual is . For feasible points , so its feasible objectives bound the primal objective from above. This is weak duality with the given maximization convention.
Try the dual intersection , . It gives ; the remaining constraint is , so it is dual feasible. Its strictly positive slack in the first column suggests , while positivity of both entries suggests . Solving , gives , which is primal feasible.
Their objective values agree:
Weak duality certifies that both are optimal. The strict first-column dual slack and the two active primal equations also show uniqueness of the primal optimum; positivity of forces the two dual equations, so the dual optimum is unique as well.