Duality

297. Duality

297.1. Linear Programming Duality

Every linear program (primal) has a unique and symmetric dual problem. For any primal LP, there is a unique dual, whose dual is the primal.

Solving the dual gives you information about the primal.

297.1.1. General Form

297.1.2. Standard Form

Obj	max	min	Obj
Constraint			Variable
Variable			Constraint

Example

Minimization

Maximization

297.1.3. Weak Duality

Dual objective gives a lower bound for a minimization primal

Dual objective gives an upper bound for a maximization primal

Sufficiency of optimality

If and are primal and dual feasible and , then and are primal and dual optimal

Example

Given a primal feasible solution , if we find a dual feasible solution so that their objective values are identical, is optimal (strong duality)

297.1.4. Dual Oprimal solution

If we have solved the primal LP, the dual optimal solution can be obtained

If is primal optimal with basis , then is dual optimal

297.1.5. Strong Duality

If both primal and dual are feasible and at least one has an optimal solution:

and are primal and dual optimal iff and are primal and dual feasible and

Example

Using the simplex method, we obtain the optimal tableau:

The associated optimal basis is
The optimal solution is
The associated objective value is

For the standard form primal LP:

Given and :

For :

It is dual feasible: and
Its dual objective value

Therefore is dual optimal

Example

Minimization

297.1.6. Feasibility-Infeasibility Certificates

If the primal is infeasible, the dual is either infeasible or unbounded
If the primal is unbounded, the dual is necessarily infeasible

Primal	Dual
Primal	Infeasible	Unbounded	Finitely Optimal
Infeasible	✅	✅	❌
Unbounded	✅	❌	❌
Finitely Optimal	❌	❌	✅

✅ means possible and ❌ means impossible
Primal unbounded no upper bound dual infeasible
Primal finitely optimal finite objective value dual finitely optimal
Primal infeasible dual infeasible or unbounded

Example

Infeasible Primal Infeasible Dual

Infeasible Primal Unbounded Dual

Unbounded Primal Infeasible Primal

297.1.7. Strong and Weak Duality

Problem Type	Duality	Weak Duality	Strong Duality
Min Primal Max Dual
Max Primal Min Dual

297.1.8. Complimentary Slackness

Slack variables of the dual LP

and are primal and dual optimal iff they are feasible and

Proof

We have

Therefore iff , i.e., and are primal and dual optimal according to strong duality.

Note that iff for all as and
If a dual (primal) constraint is nonbinding, the corresponding primal (dual) variable is zero

Example

If optimal solution:

Similarly, for an optimal solution:

Let be primal optimal, we have . Let’s find the dual optimal solution without solving the LP.

According to complimentary slackness imply since:

The two dual functional equalities are reduced to:

Solving the above equaltions results in and .

is then guaranteed to be dual optimal

()

If a primal solution is positive, the dual slack must be zero and vis versa.

If:

: dual constraint is tight (equality holds)
: dual constraint is slack (inequality not binding)

297.1.9. Shadow Prices

What if I have an additional unit of a particular resource?

For each resource there is a maximum price we are willing to pay for one additional unit

Definition: Shadow Price

For an LP that has an optimal colution, the shadow price of a constraint if the amount the objective value increases when the RHS of that constraint increases by 1, assuming the current optimal basis remains optimal

Sign or Shadow Price

Objective Function	Constraint
Objective Function
max		Free
min		Free

If shifting a constraint does not affect the optimal solution, the shadow price is zero. Shadow prices are zero for constraints that are nonbinding at the optimal solution.

Finding all shadow prices:

: number of constraints

Example

The solution to the dual program is the shadow price of the primal

What are the shadow prices?

Solve the dual LP

The dual optimal solution is

So shadow prices are 4 and 0 respectively

The shadow price is the absolute increase on the objective value given an increase of 1 on the RHS values

Instead of solving LPs (one for each constraint increase by 1), we can just solve the dual LP