Primal Dual Relationship in Linear Programming (LP): Explained

Beginner → intermediate

The dual is a “bound generator” (and often a pricing interpretation)

Think of the dual as assigning a value (price) to each constraint. If the primal is “maximize profit subject to resource limits,” the dual is “minimize total resource cost subject to covering profit coefficients.” Even if you never explicitly write the dual, solvers use dual information to prove optimality and provide sensitivity-like outputs.

Advanced (simplified)

Duality links solver statuses

A key practical implication:

If the primal is unbounded (maximization), the dual is infeasible.
If the dual is unbounded (minimization), the primal is infeasible.

That’s why “unbounded vs infeasible” debugging is often a duality debugging exercise: you’re missing a bound/constraint, or you’ve introduced a contradiction.

Cheat sheet

Most common form (x ≥ 0) with sign rules

There are many equivalent conventions. Below is the most common classroom convention with primal variables constrained x ≥ 0. If you have equalities, free variables, or mixed signs, use the rule table carefully.

Core theorems (plain English)

Weak duality (bound) and strong duality (equality at optimum)

Consider a primal maximization and its dual minimization.

Weak duality:  for any primal-feasible x and dual-feasible y,
               cᵀx ≤ bᵀy

Strong duality: if both problems have optimal solutions,
               max cᵀx = min bᵀy

Weak duality explains why the dual objective is a certificate upper bound on the primal maximum. Strong duality is what lets solvers stop and say “optimal” with a proof.

Linking conditions

When a constraint is slack, its dual price must be zero (and vice versa)

Complementary slackness connects primal constraint slacks with dual variables, and primal variables with dual constraint slacks. In a common max/≤ form:

For each primal constraint i:
  y_i · (b_i − a_iᵀx) = 0

For each primal variable j:
  x_j · ((Aᵀy)_j − c_j) = 0

Interpretation:

• If a primal constraint has positive slack, its dual variable (price) must be 0.
• If a dual constraint is not tight, the corresponding primal variable must be 0.

Interpretation

What dual variables mean in practice

A dual variable is often interpreted as the shadow price of a constraint: the marginal value of relaxing the RHS by 1 unit (within a valid range where the same basis remains optimal).

This is not “always true for any size change,” but it is a very useful local sensitivity interpretation. Example 3 below shows a clean numeric verification.

People ask

What is the primal dual relationship in linear programming?

It’s the link between an LP (primal) and another LP (dual) where feasible solutions bound each other (weak duality), and optimal objective values match when an optimum exists (strong duality). Dual variables often interpret as shadow prices.

People ask

How do you write the dual of a linear programming problem?

You transform constraints into variables and variables into constraints, with directions/signs determined by whether the primal is max/min and whether constraints are ≤, ≥, or =. Use the dual construction table on this page as a checklist.

People ask

What is weak duality in linear programming?

Weak duality says any primal-feasible solution and dual-feasible solution satisfy primal ≤ dual (for primal max / dual min). That means the dual provides a certified bound on the primal objective.

People ask

What is strong duality in linear programming?

Strong duality says that if both problems have optimal solutions, the primal maximum equals the dual minimum. This equality is the “proof” behind solver optimality certificates.

People ask

What is complementary slackness and why is it useful?

Complementary slackness links which constraints are binding to which dual variables are nonzero. It helps you reason about the structure of the optimal solution and is often used to solve small LPs without full simplex pivots.

People ask

How are shadow prices related to the dual problem?

Shadow prices are the optimal dual variables associated with constraints. They measure the marginal objective improvement from relaxing a constraint’s RHS, within a local range. If your model is infeasible or unbounded instead, use Unbounded vs Infeasible LP.

Worked examples

Expand only the example you need

Each example below is collapsible (collapsed by default) to keep the page scannable while remaining fully indexable. You can verify each solution in the LP calculator.

Tooling + learning path

Verify primal and dual side-by-side

You can solve both primal and dual in the Linear Programming calculator and confirm that optimal objective values match (strong duality).

Troubleshooting

Symptom → likely cause → fix

Glossary

• Primal: the original LP you want to solve.
• Dual: a linked LP that provides bounds and often an economic interpretation (prices).
• Weak duality: any primal-feasible objective is bounded by any dual-feasible objective (direction depends on max/min).
• Strong duality: primal and dual optimal objective values are equal when an optimum exists.
• Complementary slackness: conditions linking binding constraints to nonzero dual variables (and vice versa).
• Shadow price (dual value): marginal objective change from a small change in a constraint RHS.
• Reduced cost: simplex quantity tied to dual feasibility; indicates objective sensitivity to increasing a nonbasic variable.