Duality, Sensitivity, and Managerial Interpretation

Introduction

Linear programming (LP) is not only a method for identifying an optimal production, allocation, or investment plan. It also provides a systematic language for valuing scarce resources, interpreting constraints, and evaluating how decisions respond to changes in data. The primal model represents the original managerial problem; its dual model assigns implicit values to resources and requirements. Together, they provide two mathematically equivalent perspectives on the same decision system.

Duality is especially important in business analytics because managers rarely ask only, “What is the optimal decision?” They also ask:

• What is the value of one additional unit of capacity?
• Which resources are genuinely scarce?
• How much can a cost or profit coefficient change before the current plan changes?
• Which constraints should be relaxed, renegotiated, or expanded?
• How reliable is the recommendation under alternative scenarios?

This chapter develops primal–dual relationships, weak and strong duality, complementary slackness, shadow prices, reduced costs, and sensitivity analysis. The discussion assumes linear programming with continuous decision variables unless stated otherwise.

Learning Objectives

By the end of this chapter, the reader should be able to:

1. Construct the dual of a linear programming model.
2. Explain weak duality and strong duality and their managerial meaning.
3. Use complementary slackness to connect primal and dual optimal solutions.
4. Interpret shadow prices and reduced costs economically.
5. Conduct coefficient and right-hand-side sensitivity analysis.
6. Distinguish valid local sensitivity conclusions from broader scenario analysis.
7. Communicate optimization results responsibly to managers and stakeholders.

1. The Primal and Dual Perspectives

Consider a maximization problem in standard resource-allocation form:

Here, x is an n-dimensional vector of activity levels, c is the vector of unit contributions or profits, A is an m × n technology matrix, b is the vector of available resources, and Z is total contribution. Each row of A corresponds to a resource constraint, while each column corresponds to an activity or product.

The associated dual is:

The vector y contains one dual variable for each primal constraint. In economic terms, y_i is the imputed value, or shadow price, of one additional unit of resource i. The dual minimizes the total imputed cost of resources while ensuring that the imputed resource cost of every activity is at least its contribution.

A small illustrative model

Suppose a firm produces products A and B. Product A earns £40 and uses 2 machine hours and 1 labour hour. Product B earns £30 and uses 1 machine hour and 2 labour hours. The firm has 100 machine hours and 80 labour hours.

The primal is:

The dual is:

The dual asks: what non-negative machine-hour and labour-hour values make the imputed cost of producing each product at least as large as its contribution, while minimizing the total value assigned to available resources?

2. Constructing a Dual Systematically

For the common primal form below, the transformation is direct:

The sign and inequality rules depend on the primal form. For example, in a maximization problem, a primal “≤” constraint normally produces a non-negative dual variable. A primal equality produces a dual variable unrestricted in sign, while a primal “≥” constraint produces a non-positive dual variable. Similarly, a free primal variable produces an equality in the dual constraint.

These rules are not arbitrary. They ensure that multiplying feasible inequalities and adding them preserves a valid bound on the primal objective.

3. Weak Duality

The theorem

For any feasible primal solution x and feasible dual solution y in the paired forms above:

Thus, every feasible dual solution provides an upper bound on a maximization primal objective. Conversely, every feasible primal solution provides a lower bound on the minimization dual objective.

Proof

Because Ax ≤ b and y ≥ 0, multiplication preserves the inequality:

Because Aᵀy ≥ c and x ≥ 0:

Since yᵀAx = xᵀAᵀy, it follows that cᵀx ≤ bᵀy.

Managerial meaning

Weak duality says that a feasible resource valuation cannot understate the contribution of any feasible operating plan. If a proposed dual valuation implies a total resource value below a feasible primal profit, the valuation is inconsistent with the model. In practice, this provides a useful validation principle: a dual solution is a defensible upper bound only when it satisfies all dual constraints.

4. Strong Duality

The theorem

If a feasible linear programming problem has a finite optimal solution, then its dual also has a finite optimal solution and:

where Z is the optimal primal objective and W is the optimal dual objective.

Strong duality does not mean that the primal and dual decisions are identical. They have different variables and interpretations. It means that the best operational contribution equals the minimum total value assigned to the resources needed to support it.

For the illustrative model, solving the two binding primal equations gives:

From the second equation, x₁ = 80 − 2x₂. Substitution gives 160 − 4x₂ + x₂ = 100, so x₂ = 20 and x₁ = 40. The contribution is:

Both resources are fully used. The dual constraints are also binding because both products are produced:

Solving gives y₁ = 50/3 ≈ 16.67 and y₂ = 20/3 ≈ 6.67. The dual objective is:

Therefore, the optimal primal contribution and dual resource valuation agree.

5. Complementary Slackness

Complementary slackness describes the detailed relationship between optimal primal and dual solutions. For the standard pair, it requires:

The products are zero, so at least one factor in each product must be zero.

Resource interpretation

For each resource i:

• If the resource has unused capacity, then y_i = 0.
• If y_i > 0, the resource must be fully utilized.

A scarce resource can have a positive value only when its constraint is binding. An unused resource has no marginal value within the model because a small increase in its availability cannot improve the objective.

Activity interpretation

For each activity j:

• If x_j > 0, its dual constraint is binding: imputed input cost equals contribution.
• If its dual constraint is slack, the activity is not attractive at the current resource valuations and normally has x_j = 0.

Complementary slackness is useful computationally. If a candidate primal solution has some positive activity, its corresponding dual inequality must hold at equality. Conversely, a positive shadow price requires a fully utilized primal resource.

6. Shadow Prices and Resource Valuation

The shadow price of resource i is the marginal change in the optimal objective value caused by a change in its right-hand side, provided the current optimal basis remains valid:

This is a local result, not a universal prediction for arbitrary changes in b_i. It is valid over the allowable range reported by a sensitivity analysis.

In the example, the machine-hour shadow price is approximately £16.67 per additional hour, and the labour-hour shadow price is approximately £6.67 per additional hour. If one additional machine hour can be purchased for £10, and the change remains within the allowable range, purchasing it increases contribution by approximately £16.67 and creates a net improvement of £6.67. If an additional hour costs £20, it is not financially attractive on the basis of the LP model.

Shadow prices should be interpreted carefully:

1. They are marginal, not average, values.
2. They depend on the current model structure and solution basis.
3. They may change after a sufficiently large capacity change.
4. They are not necessarily observable market prices.
5. They measure opportunity cost within the model, not social or strategic value in general.

A zero shadow price does not necessarily mean a resource is unimportant. It means that, at the margin and under the current model, more of that resource does not improve the objective.

7. Reduced Costs

For a maximization problem with x ≥ 0, the reduced cost of activity j can be written as:

Dual feasibility implies r_j ≤ 0. If x_j > 0, complementary slackness implies r_j = 0. For a currently unused activity, a negative reduced cost indicates that its contribution is below the imputed value of the resources it consumes.

The reduced cost also indicates how much the objective coefficient c_j must improve before the activity can become attractive, subject to the current basis remaining valid. If an unused product has reduced cost −£8, its unit contribution generally must increase by £8 before it can enter the optimal solution, assuming no other relevant data change.

Some software reports reduced costs using the opposite sign convention. Therefore, analysts must inspect the software documentation and interpret the value consistently with the objective direction and variable bounds.

Example

Suppose an unused product uses resources whose dual valuation totals £45 per unit, but its contribution is £37. Then:

The product is economically unattractive at current shadow prices. It would require an increase of £8 in contribution, or an equivalent reduction in imputed resource usage, to become competitive locally.

8. Sensitivity Analysis

Sensitivity analysis investigates how the optimal solution responds to changes in model parameters. It differs from simply solving a new scenario: a sensitivity report explains the range over which the current optimal basis remains valid and identifies marginal effects within that range.

8.1 Right-hand-side sensitivity

Suppose resource availability changes from b_i to b_i + Δb_i. Within the allowable range:

For several simultaneous changes, the appropriate expression is:

provided the combined change remains within the validity region of the current basis. A common practical test is the 100% rule: the sum of the fractions of allowable increases or decreases used by simultaneous changes should not exceed 1. This rule is a conservative screening device and should not replace resolving the model.

8.2 Objective-coefficient sensitivity

Changes in c_j affect the attractiveness of activities. Within the allowable range for which the current basis remains optimal:

• the current activity levels remain unchanged;
• the objective value changes according to the new coefficients;
• the dual prices may remain unchanged;
• outside the range, the optimal basis may change.

For a product currently produced at x_j units, a change Δc_j changes the objective by x_jΔc_j, provided the basis remains valid.

8.3 Constraint and activity classification

Sensitivity reports commonly identify:

8.4 Limits of sensitivity reports

A sensitivity report is local. It usually assumes all other coefficients remain fixed, linearity continues to hold, and the same feasible structure applies. It does not automatically account for:

• fixed costs;
• quantity discounts;
• integer requirements;
• demand saturation;
• competitor reactions;
• uncertain parameter estimates;
• changes in technology;
• multiple optimal solutions;
• degeneracy.

When a change is large, several parameters change simultaneously, or the model is mixed-integer, the analyst should re-solve the model and, where appropriate, perform scenario, stochastic, or robust optimization.

9. Multiple Optima, Degeneracy, and Stability

A linear program can have more than one optimal solution. Geometrically, the objective may be parallel to an edge of the feasible region. In such a case, alternative production plans may achieve the same optimal value. Managers should not automatically treat the solver’s selected plan as uniquely best; implementation risk, workforce stability, customer service, and strategic flexibility may justify another optimum.

Degeneracy occurs when a basic feasible solution has more active constraints than necessary or one or more basic variables equal zero. Degeneracy can make shadow-price interpretation less straightforward and may cause zero changes in the objective for certain basis changes. It also means that allowable ranges can be narrower or more complicated than a simple managerial narrative suggests.

A model may be infeasible if no plan satisfies all constraints, or unbounded if the objective can improve indefinitely. Duality provides diagnostic insight: under standard conditions, primal infeasibility or unboundedness is linked to corresponding properties of the dual. In practice, analysts should inspect conflicting requirements, units, signs, and omitted bounds before drawing business conclusions.

10. An Integrated Managerial Case

Background

The following is an illustrative case. A meal-kit company produces Standard and Premium boxes each week. Standard contributes $18 and uses 1 packing hour and 2 units of chilled storage. Premium contributes $30 and uses 2 packing hours and 1 unit of chilled storage. Weekly capacity is 100 packing hours and 80 storage units.

Model

At the intersection of the two binding constraints:

Solving gives x₁ = 20 and x₂ = 40. The weekly contribution is:

The dual is:

Because both products are produced, both dual constraints bind:

The solution is y₁ = 14 and y₂ = 2. Therefore, packing capacity has a shadow price of $14 per hour, while storage has a shadow price of $2 per unit. The dual objective confirms the primal value:

Decision analysis

If a temporary supplier offers 3 additional packing hours for $10 per hour, the estimated gain is 3 × $14 = $42, while the cost is $30. The purchase appears attractive if the three-hour increase lies within the allowable range and operational assumptions remain valid.

If an additional storage unit costs $5, it should not be purchased merely for short-run contribution because its marginal value is only $2. However, storage may still have strategic value if it reduces spoilage, protects service levels, or enables future products—considerations absent from the current objective.

Suppose a third product contributes $20 but consumes 1 packing hour and 2 storage units. Its imputed resource cost is 1($14) + 2($2) = $18, so its reduced cost is $20 − $18 = $2. This suggests that the current solution may not remain optimal if the product is available, and the model should include it explicitly rather than relying on a reduced-cost interpretation for an omitted activity.

Outcome and learning points

The case demonstrates that the primal identifies the operating plan, while the dual identifies resource priorities. Packing is substantially more valuable than storage at the margin. The result supports capacity-expansion negotiations, but only within the sensitivity range. It does not prove that unlimited packing capacity is worth $14 per hour, nor does it capture service, quality, labour fatigue, or strategic considerations.

11. Implementation and Best Practices

A reliable managerial workflow is:

1. Define the decision horizon, objective, activities, and resources.
2. Verify units and ensure coefficients represent the same period and scale.
3. Solve and inspect primal feasibility.
4. Construct or obtain the dual and verify objective agreement.
5. Identify binding constraints and positive shadow prices.
6. Examine reduced costs for excluded activities.
7. Review allowable ranges before making marginal recommendations.
8. Re-solve material scenarios rather than extrapolating local values.
9. Test assumptions with managers and operational experts.
10. Present uncertainty, limitations, and non-financial consequences.

Solver output should never be treated as self-interpreting. A technically correct shadow price can be misleading if a capacity expansion requires a fixed investment, changes quality, or creates a new bottleneck. Good analytics combines mathematical validity with institutional knowledge and transparent governance.

12. Ethical and Governance Considerations

Optimization recommendations can distribute scarce resources among customers, employees, regions, or suppliers. A mathematically optimal allocation may produce unfair outcomes if the objective omits equity, accessibility, or service obligations. Analysts should therefore document:

• who selected the objective and constraints;
• which groups bear the effects of capacity decisions;
• whether data are accurate and representative;
• whether shadow prices are being used outside their validity range;
• whether constraints encode legal, safety, or contractual requirements.

In regulated contexts, the model should preserve auditable records of assumptions, versions, solver settings, and scenario results. Automated or AI-assisted optimization should support, not replace, accountable managerial review. Sensitivity analysis is particularly valuable for identifying decisions that are fragile to estimation error.

Contemporary Extensions

Modern analytics platforms can generate dual values and sensitivity reports automatically, but interpretation remains a human responsibility. In larger systems, dual variables support decomposition methods, including Benders decomposition and column generation. In uncertain environments, robust and stochastic optimization extend the basic framework by representing parameter uncertainty explicitly. In machine-learning-enabled planning, predicted demand may feed the LP, while dual values help assess the economic value of improving forecasts or acquiring information.

These extensions preserve the central insight of duality: every constrained optimization problem contains both an action perspective and a valuation perspective. The action perspective chooses levels of activities; the valuation perspective explains which constraints and opportunities govern that choice.

Chapter Summary

Linear programming has a primal model of activities and a dual model of resource valuation. For a standard maximization problem with ≤ constraints and non-negative variables, the dual is a minimization problem with transposed coefficients. Weak duality establishes that every feasible dual objective is an upper bound on every feasible primal objective. Strong duality states that finite optimal primal and dual objectives are equal.

Complementary slackness links optimal solutions: unused resources have zero shadow prices, positive shadow prices correspond to binding resources, and positive activities have binding dual constraints. Shadow prices measure marginal objective improvement from additional resources within an allowable range. Reduced costs measure the gap between an activity’s contribution and the imputed value of its resources. Sensitivity analysis evaluates local changes in right-hand sides and objective coefficients, but large or simultaneous changes require re-solving and possibly using scenario, stochastic, or robust methods.

Managerial interpretation must account for model assumptions, fixed costs, uncertainty, strategic effects, fairness, and governance. Duality is therefore both a mathematical theorem and a practical framework for resource valuation and decision support.

Key Terms

Duality: The relationship between a primal optimization model and its associated dual model.

Primal: The original linear programming formulation describing operational decisions.

Dual: The paired formulation that assigns values to primal constraints and activities.

Weak duality: The result that every feasible dual value bounds every feasible primal value.

Strong duality: The result that optimal primal and dual objective values are equal under finite feasibility conditions.

Dual variable: A variable in the dual associated with a primal constraint.

Shadow price: The marginal value of relaxing a constraint’s right-hand side.

Complementary slackness: Conditions linking slackness in one model to zero values in the other.

Binding constraint: A constraint satisfied exactly at the solution.

Slack: Unused capacity in a ≤ constraint.

Surplus: Excess above a minimum requirement in a ≥ constraint.

Reduced cost: The difference between an activity’s contribution and the imputed cost of its resources.

Allowable range: Parameter interval over which the current optimal basis remains valid.

Optimal basis: The set of basic variables and active structural relationships defining an LP solution.

Multiple optima: The existence of more than one solution with the same optimal objective value.

Degeneracy: A condition in which a basic feasible solution has unusual active or zero-valued basic variables.

Sensitivity analysis: Study of how optimal results respond to parameter changes.

Opportunity cost: The value of the best alternative use of a scarce resource.

Robust optimization: Optimization designed to remain effective under parameter uncertainty.

Review Questions

Short Answer Questions

1. What is the economic interpretation of a dual variable in a resource-constrained maximization model?
2. State the weak-duality relationship for a standard primal–dual pair.
3. What does complementary slackness imply about an unused resource?
4. Define the reduced cost of a non-negative activity in a maximization problem.
5. Why should a shadow price not be extrapolated indefinitely beyond its allowable range?

Long Answer Questions

1. Derive the dual of a maximization LP with ≤ constraints and explain the correspondence between primal and dual elements.
2. Explain weak and strong duality, including their managerial significance.
3. Discuss complementary slackness and show how it can be used to verify an optimal primal–dual pair.
4. Compare shadow prices, reduced costs, slacks, and allowable ranges in a sensitivity report.
5. Critically evaluate the limitations of using LP sensitivity analysis for strategic business decisions.

Analytical / Application Questions

1. A resource has a shadow price of $12 per unit, and a supplier offers five additional units at $9 each. What assumptions must be checked before accepting the offer, and what is the estimated marginal net benefit if the sensitivity range is valid?
2. An unused activity has contribution $46 and an imputed resource cost of $52. Interpret its reduced cost and identify two managerial actions that could make it competitive.
3. A planning model has two binding constraints and a proposed simultaneous change to both resource limits. Design a procedure for deciding whether to use the existing sensitivity report or re-solve the model, including operational and governance checks.

Multiple Choice Questions with Answers

Question 1

In a standard maximization primal with Ax ≤ b and x ≥ 0, the dual objective is to:

A. Maximize cᵀx

B. Minimize bᵀy

C. Minimize cᵀy

D. Maximize bᵀx

Correct Answer: B. Minimize bᵀy

Question 2

Weak duality implies that for feasible solutions of the standard pair:

A. cᵀx ≥ bᵀy

B. cᵀx = bᵀy always

C. cᵀx ≤ bᵀy

D. Both objectives must be zero

Correct Answer: C. cᵀx ≤ bᵀy

Question 3

If a primal resource constraint has positive slack at optimum, complementary slackness implies that its shadow price is:

A. Positive

B. Negative

C. Equal to the resource quantity

D. Zero

Correct Answer: D. Zero

Question 4

In the meal-kit case, the optimal production quantities were:

A. 20 Standard and 40 Premium

B. 40 Standard and 20 Premium

C. 50 Standard and 30 Premium

D. 30 Standard and 50 Premium

Correct Answer: A. 20 Standard and 40 Premium

Question 5

For an unused activity in a maximization problem, a reduced cost of −$8 generally means that:

A. Its contribution must decrease by $8

B. Its contribution must increase by $8 to become competitive locally

C. Its resource use must increase by $8

D. Its activity level is already optimal and positive

Correct Answer: B. Its contribution must increase by $8 to become competitive locally

Question 6

Strong duality states that, when finite optimal solutions exist:

A. The primal has a larger objective value

B. The dual has a larger objective value

C. The primal and dual optimal objective values are equal

D. Both models have identical decision variables

Correct Answer: C. The primal and dual optimal objective values are equal

Question 7

A shadow price is most appropriately interpreted as:

A. The average historical cost of a resource

B. The marginal objective improvement from relaxing a constraint within a valid range

C. The market price in every possible circumstance

D. The fixed cost of establishing a resource

Correct Answer: B. The marginal objective improvement from relaxing a constraint within a valid range

Question 8

In the illustrative product example, if an activity contributes $37 and its imputed resource cost is $45, its reduced cost is:

A. −$8

B. $8

C. $82

D. −$37

Correct Answer: A. −$8

Question 9

If both primal activities are produced at an optimum, complementary slackness generally requires their corresponding dual constraints to be:

A. Infeasible

B. Binding

C. Strictly negative

D. Unrestricted in sign

Correct Answer: B. Binding

Question 10

A large simultaneous change in several model parameters should generally be handled by:

A. Extrapolating one shadow price indefinitely

B. Ignoring the objective coefficients

C. Re-solving the model and checking assumptions

D. Setting all dual variables to zero

Correct Answer: C. Re-solving the model and checking assumptions