Duality, Sensitivity and Post-Optimal Analysis

Introduction

Linear programming (LP) is often introduced as a method for finding an optimal plan. In managerial practice, however, the optimal solution is only the beginning of analysis. Managers also need to know the value of scarce resources, the effect of changing prices or capacities, the consequences of introducing new activities, and whether the recommendation remains valid when assumptions change. Duality, sensitivity analysis, and post-optimal analysis provide this broader perspective.

Every LP has an associated second model called its dual. The original model is the primal. The dual provides an alternative economic interpretation of the same decision problem: primal variables generally represent activity levels, whereas dual variables represent implicit values assigned to resources or constraints. The dual is especially useful for interpreting opportunity costs, validating solutions, and analysing policy alternatives.

Sensitivity analysis studies how changes in coefficients affect the optimal solution. Post-optimal analysis extends this investigation after an optimal solution has already been obtained. These techniques are central to responsible managerial use of optimisation because model data are rarely known with complete certainty.

Learning Objectives

After studying this chapter, you should be able to:

1. Construct the dual of a linear-programming model in standard and non-standard forms.
2. Explain weak duality, strong duality, and complementary slackness.
3. Interpret shadow prices, reduced costs, and slack or surplus values.
4. Use sensitivity ranges to evaluate changes in objective coefficients and right-hand-side values.
5. Analyse the entry of new activities, changes in resource availability, and simultaneous changes.
6. Apply post-optimal analysis to managerial resource and policy decisions.
7. Recognise the assumptions and limitations of sensitivity reports generated by LP software.

1. The Primal–Dual Relationship

Consider the maximisation problem

Here, x is an n×1 vector of activity levels, c is the vector of unit contributions, A is the matrix of resource requirements, and b is the vector of available resources. The dimensions and units must be consistent: each element of Ax has the same resource unit as the corresponding element of b, while cᵀx has units of total contribution or profit.

Its dual is

The dual contains one variable yᵢ for each primal constraint and one constraint for each primal variable. The coefficient matrix is transposed; the primal objective coefficients become dual right-hand-side values, and the primal right-hand-side values become dual objective coefficients.

Economic interpretation

Suppose the primal chooses products and the constraints represent labour, material, and machine capacity. A dual variable yᵢ is an imputed value per unit of resource i. The dual seeks the least total imputed value of available resources while ensuring that every product’s resource valuation is at least its contribution:

Thus, the dual constraint for product j states that the value of resources consumed by one unit of product j must cover that product’s contribution. If it did not, the resource valuation would understate the economic worth of that activity.

The table applies directly to the displayed standard form. Other combinations of inequality direction and variable restrictions require the sign rules discussed below.

2. Constructing Dual Models

A reliable construction procedure is:

1. Write the primal clearly and identify whether it is a maximisation or minimisation problem.
2. Create one dual variable for every primal constraint.
3. Create one dual constraint for every primal variable.
4. Transpose the coefficient matrix.
5. Exchange the primal objective coefficients and right-hand-side values.
6. Determine signs from the directions of constraints and variable restrictions.
7. Check economic units and feasibility.

For the standard maximisation form, all primal constraints are ≤ and all primal variables are non-negative. If a primal constraint is an equality, its associated dual variable is unrestricted in sign. If a primal constraint is ≥ in a maximisation model, its dual variable is non-positive. Conversely, for a standard minimisation model with ≥ constraints and non-negative variables, dual variables are non-negative and dual constraints are ≤.

A primal variable that is unrestricted in sign produces an equality constraint in the dual. A primal variable constrained to be non-positive produces a dual constraint with the opposite inequality direction from the non-negative case.

Example: model construction

A firm chooses quantities x₁ and x₂:

Let y₁ and y₂ be the values of the two resources. The dual is

The first dual constraint values the resources required by one unit of activity 1; the second does the same for activity 2.

3. Weak Duality and Strong Duality

Weak duality

For any feasible primal solution x and feasible dual solution y in the standard max–min pair,

The result follows because Ax ≤ b, y ≥ 0, and Aᵀy ≥ c. Multiplying Ax ≤ b by y gives yᵀAx ≤ yᵀb; multiplying Aᵀy ≥ c by x ≥ 0 gives xᵀAᵀy ≥ xᵀc. Since yᵀAx = xᵀAᵀy, the inequality follows.

Weak duality has an important managerial meaning. Any feasible dual solution is an upper bound on the maximum primal contribution. Any feasible primal solution is a lower bound on the minimum dual resource valuation.

Strong duality

If both problems have feasible finite optima, then their optimal objective values are equal:

where Z is the optimal primal value and W is the optimal dual value. Strong duality does not imply that the primal and dual solutions are identical; they generally have different dimensions and interpretations. It states that their optimal values coincide.

If the primal is unbounded in a maximisation problem, the dual is infeasible. If the dual is unbounded in a minimisation problem, the primal is infeasible. These relationships help diagnose modelling errors, although infeasibility and unboundedness should also be investigated directly.

4. Complementary Slackness

Complementary slackness links primal and dual optimal solutions. For the standard pair, x and y are optimal if they are feasible and satisfy

and

The first condition says that either a resource has positive shadow value or it has unused capacity, but not both. The second says that either an activity is produced or its dual constraint is exactly binding; an activity with a positive reduced-cost disadvantage cannot be used in an optimum.

Consequences include:

• If primal constraint i has slack, then yᵢ = 0.
• If yᵢ > 0, the corresponding primal constraint is binding.
• If xⱼ > 0, the corresponding dual constraint is binding.
• If a dual constraint is strict, the corresponding primal variable is zero.

Complementary slackness is useful for recovering a dual solution from a known primal solution, verifying solver output, and explaining why apparently profitable activities are excluded.

5. Shadow Prices and Reduced Costs

Shadow prices

The shadow price of resource i is the marginal change in the optimal objective value caused by a one-unit increase in bᵢ, provided the current optimal basis remains valid:

This is a local marginal value, not necessarily the value of a large change. It has units of objective contribution per unit of resource. A zero shadow price usually indicates that the resource is nonbinding, although degeneracy can require careful interpretation.

For a capacity increase Δbᵢ within the allowable range,

The result is valid only if other relevant assumptions and the optimal basis remain unchanged.

Reduced costs

For a non-basic variable xⱼ = 0 in a maximisation problem, the reduced cost can be written as

At a feasible optimum, rⱼ ≤ 0. It measures how much the objective coefficient cⱼ must improve before the activity can become attractive, under the current basis. A reduced cost of −5 means that the unit contribution would need to increase by 5, from cⱼ to cⱼ + 5, before the current solution can potentially admit that activity. If the variable is positive, its reduced cost is zero in a non-degenerate optimal solution.

Reduced cost is not a direct measure of total profitability and should not be interpreted independently of the model’s units, basis, and coefficient assumptions.

6. Sensitivity Analysis

Sensitivity analysis distinguishes two major changes:

1. Objective-coefficient changes: changes in unit profits, costs, prices, or contribution margins.
2. Right-hand-side changes: changes in resource availability, demand requirements, minimum service levels, or policy limits.

Changes in objective coefficients

A sensitivity report commonly provides an allowable increase and allowable decrease for each objective coefficient. Within the interval

the current basis remains optimal. The variable values therefore remain unchanged, although the objective value changes according to the new coefficients.

If several objective coefficients change simultaneously, the one-at-a-time ranges are not sufficient. A common sufficient condition is the 100-percent rule:

When this condition holds, the current basis remains optimal. Failure of the rule does not prove that the basis changes; it means that further analysis is required.

Changes in right-hand-side values

For a right-hand-side change Δbᵢ within its allowable range, the current basis remains feasible and optimal, and

provided the objective coefficients and matrix A remain fixed and the changed right-hand side preserves the stated basis conditions. The solution quantities may change even though the basis remains the same. Therefore, a shadow-price calculation can update the objective value but does not by itself provide every new variable value.

If multiple right-hand sides change, the resulting basic solution should be recomputed or checked using the basis inverse. Let B be the matrix of basic-variable columns. Then

and after a change Δb,

The basis remains feasible only if the required sign conditions on x_B(new) continue to hold.

Binding and nonbinding constraints

A binding constraint has zero slack (or zero surplus, where appropriate). Its shadow price may be positive or negative depending on the model and constraint orientation. A nonbinding ≤ constraint in a standard maximisation model has positive slack and a zero shadow price. Increasing its right-hand side does not improve the objective locally because that resource is not limiting the current plan.

7. Worked Example: Resource Valuation

Return to the model

At the intersection of both constraints,

Solving gives x₁ = 10 and x₂ = 20. The objective value is

Both resources are binding. The dual constraints are also binding because x₁ and x₂ are positive:

Solving gives y₁ = 50/3 ≈ 16.67 and y₂ = 10/3 ≈ 3.33. The dual objective is

This confirms strong duality. The first resource has a marginal value of approximately 16.67 contribution units per additional resource unit, while the second has a marginal value of approximately 3.33, within the relevant sensitivity ranges.

If one additional unit of the first resource is acquired, and the basis remains valid, the objective increases by approximately 16.67. Paying more than this amount per additional unit would not be justified by the current model, although strategic, risk, and fixed-cost considerations may alter the final decision.

8. Post-Optimal Questions

A manager commonly asks the following questions:

Should additional capacity be purchased?

Compare the purchase price with the shadow price, ensuring that the proposed quantity lies within the allowable range. If the purchase exceeds the range, solve the revised LP or perform a parametric analysis.

Should an unselected product be introduced?

Examine its reduced cost. For a maximisation model, an activity with a negative reduced cost must improve its unit contribution by at least the absolute reduced cost before it can become competitive under the current basis. Its introduction may also require new constraints, setup costs, labour qualifications, or demand limits, none of which are captured by the reduced cost alone.

What if demand changes?

Demand constraints may be upper bounds, lower bounds, or equalities. Changing them can alter both feasibility and resource values. A demand increase is beneficial only if the associated contribution exceeds the opportunity cost of the additional resources and does not create an undesirable policy outcome.

What if a new technology changes resource use?

A change in A is more fundamental than a change in b or c. Standard sensitivity ranges for objective coefficients and right-hand sides do not generally apply. The model should normally be re-solved, or a structured parametric analysis should be performed.

9. Illustrative Case: Capacity Policy at Meridian Foods

Background. Meridian Foods produces institutional meal packs using mixing and packaging capacity. The operations team uses an LP to select weekly product quantities. A current solution produces two products and fully uses packaging capacity, while mixing capacity has unused time.

Problem. A supplier offers additional packaging capacity at a fixed per-hour price. The operations manager must decide whether to accept it. Marketing also proposes increasing the contribution margin of the product currently not produced.

Analysis. The solver reports a positive shadow price for packaging and a zero shadow price for mixing. The packaging shadow price is 12 monetary units per hour, with an allowable increase of 100 hours. The supplier offers 60 hours at 8 monetary units per hour. The marginal net benefit is therefore 12 − 8 = 4 monetary units per hour, and the proposal appears attractive within the sensitivity range. The total estimated improvement is 60 × 4 = 240 monetary units.

The unproduced product has a reduced cost of −6. Its contribution margin would need to rise by 6 monetary units per pack before it could enter the current basis. Marketing’s proposed increase is only 4, so the current solution remains preferable under the local analysis.

Approach and solution. Management accepts the capacity offer provisionally, confirms that the 60-hour purchase is within the allowable range, and then re-solves the model because supplier costs and operational constraints may interact. The marketing proposal is rejected unless additional strategic benefits justify a full model revision.

Outcome. The analysis separates two decisions: purchasing a scarce resource is worthwhile because its price is below its shadow value; improving a non-selected product by less than its reduced-cost threshold is insufficient under current conditions.

Learning points. Shadow prices support capacity procurement, reduced costs support product and pricing decisions, and sensitivity ranges should be treated as local validity conditions rather than permanent forecasts.

10. Limitations, Governance and Contemporary Practice

LP sensitivity analysis relies on linearity, divisibility, known coefficients, stable technology, and an objective that accurately represents organisational priorities. It does not automatically address integer decisions, fixed setup costs, nonlinear economies, uncertainty, behavioural responses, or multiple conflicting objectives.

Degeneracy can produce multiple optimal solutions and unstable-looking shadow-price reports. Alternative optima mean that more than one activity plan achieves the same objective value. A zero reduced cost for a non-basic variable can signal such an alternative optimum. Solver tolerances and scaling may also create small numerical discrepancies.

Sensitivity reports should therefore be governed through:

• documentation of data sources, units, dates, and assumptions;
• explicit separation of model results from managerial judgement;
• scenario analysis for plausible demand, price, and capacity conditions;
• independent checks of feasibility and units;
• review of fairness, service, safety, labour, and environmental effects;
• version control and reproducibility of model files and input data.

Modern optimisation systems can automate scenario generation and use AI to identify influential parameters or suggest alternative scenarios. Such tools do not remove the need for human validation. An AI-generated scenario may inherit biased data, omit a regulatory constraint, or present a locally valid marginal value as if it were a long-term forecast. Governance should require transparent assumptions, audit trails, sensitivity to model misspecification, and approval by accountable decision-makers.

Best-Practice Workflow

1. Formulate and dimension-check the primal model.
2. Construct and interpret the dual.
3. Solve the primal and verify feasibility.
4. Use complementary slackness to validate primal–dual consistency.
5. Examine slacks, shadow prices, reduced costs, and allowable ranges.
6. Test realistic one-at-a-time and simultaneous scenarios.
7. Re-solve whenever changes exceed validity ranges or alter A, integrality, or model structure.
8. Communicate results with units, assumptions, uncertainty, and managerial caveats.
9. Monitor actual outcomes and update the model when operating conditions change.

Chapter Summary

Duality provides a second, economically meaningful representation of every appropriately formulated linear programme. In a standard maximisation problem, the primal allocates activities and the dual assigns values to scarce resources. Weak duality establishes bounds, while strong duality states that feasible finite optimal primal and dual objective values are equal. Complementary slackness explains the connection between unused resources, positive shadow prices, active activities, and binding dual constraints.

Shadow prices measure local marginal values of right-hand-side resources, and reduced costs indicate the objective-coefficient improvement required for excluded activities to become competitive. Sensitivity analysis identifies ranges within which the current basis remains valid. Right-hand-side changes can be evaluated using shadow prices and basis calculations; objective changes require attention to allowable coefficient ranges and simultaneous-change rules. Changes to the technology matrix, integrality, or model structure generally require re-optimisation.

For managers, these tools support capacity procurement, pricing, product selection, policy design, and scenario analysis. Their conclusions remain conditional on data quality, linearity, basis validity, and ethical and operational constraints. Sound practice combines solver output with transparent assumptions, scenario testing, governance, and professional judgement.

Key Terms

Dual model: The optimisation model associated with a primal model, with interchanged roles for constraints and variables.

Primal model: The original linear-programming formulation of a decision problem.

Shadow price: The marginal change in the optimal objective value from a one-unit right-hand-side change within a valid range.

Reduced cost: The objective-coefficient disadvantage of a non-basic variable relative to the current dual valuation.

Complementary slackness: Conditions linking primal slack and dual variables, and primal variables and dual slack.

Weak duality: The principle that every feasible primal objective is bounded by every feasible dual objective in the appropriate direction.

Strong duality: The equality of optimal primal and dual objective values when both have finite feasible optima.

Binding constraint: A constraint satisfied at equality at a solution.

Nonbinding constraint: A constraint with positive slack or surplus.

Slack: Unused amount of a ≤ constraint.

Surplus: Amount by which the left side exceeds a ≥ constraint.

Basic variable: A variable associated with a column in the current simplex basis.

Non-basic variable: A variable set to a bound, commonly zero, in the current basis.

Allowable increase: Maximum coefficient or right-hand-side increase preserving the current basis under stated conditions.

Allowable decrease: Maximum coefficient or right-hand-side decrease preserving the current basis under stated conditions.

Sensitivity analysis: Study of how parameter changes affect an optimisation solution.

Post-optimal analysis: Investigation conducted after an optimal solution has been obtained.

Alternative optimum: More than one feasible solution achieving the same optimal objective value.

Degeneracy: A basic feasible solution in which one or more basic variables are at a bound, commonly zero.

Parametric analysis: Systematic examination of an optimisation model across a range of parameter values.

Review Questions

Short Answer Questions

1. What is the economic interpretation of a dual variable in a resource-allocation model?
2. State the weak-duality relationship for a standard maximisation–minimisation pair.
3. What does a zero slack imply about a constraint’s status?
4. Define the reduced cost of a non-basic variable in a maximisation problem.
5. Why must a model usually be re-solved when the technology matrix changes?

Long Answer Questions

1. Explain how to construct the dual of a standard maximisation LP and discuss the role of matrix transposition.
2. Explain strong duality and complementary slackness, including their managerial interpretations.
3. Distinguish shadow prices from reduced costs and illustrate how each supports a different management decision.
4. Discuss the meaning and limitations of allowable increase and allowable decrease in a solver sensitivity report.
5. Explain how degeneracy, alternative optima, and simultaneous parameter changes complicate sensitivity analysis.

Analytical / Application Questions

1. A resource has a shadow price of 18 monetary units per kilogram, and a supplier offers 40 kilograms at 12 monetary units per kilogram. What conditions must be checked before accepting the offer, and what is the estimated marginal net benefit if the offer lies within the valid range?
2. An unproduced activity has a reduced cost of −7 in a maximisation model. Interpret this result and explain what additional information is needed before recommending a price increase for that activity.
3. A manager changes two right-hand-side values and one contribution coefficient simultaneously, with changes exceeding the reported one-at-a-time ranges. Design a defensible post-optimal-analysis procedure for evaluating the revised policy.

Multiple Choice Questions with Answers

Question 1

In the standard primal–dual pair, a primal constraint corresponds to which dual element?

A. A dual variable

B. A dual objective function

C. A primal objective coefficient

D. A dual slack variable only

Correct Answer: A. A dual variable

Question 2

For any feasible standard primal maximisation solution x and feasible dual solution y, which relationship holds?

A. cᵀx ≥ bᵀy

B. cᵀx = 0

C. cᵀx ≤ bᵀy

D. cᵀx is unrelated to bᵀy

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

Question 3

If a resource constraint has positive slack in a standard maximisation model, complementary slackness implies that its dual variable is:

A. Positive

B. Zero

C. Unrestricted

D. Equal to the objective value

Correct Answer: B. Zero

Question 4

A shadow price of 10 monetary units per machine-hour means that, within its valid range, one additional machine-hour will:

A. Reduce the objective by 10 units

B. Increase the objective by approximately 10 units

C. Increase every decision variable by 10 units

D. Make the constraint nonbinding automatically

Correct Answer: B. Increase the objective by approximately 10 units

Question 5

For a non-basic activity in a maximisation model, a reduced cost of −6 generally means its unit contribution must increase by how much before it can become competitive under the current basis?

A. 1 unit

B. 3 units

C. 6 units

D. 12 units

Correct Answer: C. 6 units

Question 6

In the worked example, the optimal quantities are x₁ = 10 and x₂ = 20. What is the objective value?

A. 700

B. 900

C. 1,000

D. 1,200

Correct Answer: C. 1,000

Question 7

In the worked example, which resource has the larger dual value?

A. The first resource, with value approximately 16.67

B. The second resource, with value approximately 16.67

C. Both resources, each with value 10

D. Neither resource, because both are binding

Correct Answer: A. The first resource, with value approximately 16.67

Question 8

If several objective coefficients change simultaneously, what does failure of the 100-percent rule indicate?

A. The model is infeasible

B. The current basis definitely changes

C. Further analysis is required

D. The objective value cannot be calculated

Correct Answer: C. Further analysis is required

Question 9

Which type of change generally requires re-solving rather than directly using ordinary right-hand-side sensitivity ranges?

A. A small change in one resource availability

B. A change in the technology coefficient matrix A

C. A change within an allowable objective range

D. A one-unit increase in a binding resource

Correct Answer: B. A change in the technology coefficient matrix A

Question 10

Strong duality states that, when both problems have finite feasible optima:

A. The primal and dual variables are identical

B. The primal and dual objective values are equal

C. All constraints are nonbinding

D. All reduced costs are positive

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