Linear Programming and Sensitivity Analysis

Introduction

Linear programming (LP) is a mathematical approach for allocating scarce resources among competing activities. It is widely used in production planning, logistics, workforce scheduling, portfolio selection, marketing, procurement, and capacity management. An LP model translates a managerial problem into three components: decision variables, an objective function, and constraints.

The central managerial question is usually: “What combination of activities gives the best achievable result, given limited resources?” The result may be maximum profit, minimum cost, minimum delivery time, or maximum service coverage. Sensitivity analysis then examines how the recommended solution changes when profits, costs, resource limits, or other assumptions change.

LP is especially valuable in business analytics because it connects quantitative models with operational decisions. However, its recommendations are meaningful only when the variables, data, assumptions, and interpretation are carefully validated.

Learning Objectives

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

1. Formulate objective functions and constraints from business descriptions.
2. Explain feasible regions, corner-point solutions, slack, surplus, and binding constraints.
3. Solve two-variable linear programs graphically.
4. Describe the role of simplex-based and software solver methods.
5. Interpret optimal solutions, shadow prices, reduced costs, and allowable ranges.
6. Use sensitivity analysis to support managerial decisions.
7. Recognize assumptions, limitations, ethical issues, and implementation risks in LP models.

1. The Structure of a Linear Programming Model

A linear programming model contains:

• Decision variables: unknown quantities to be determined.
• Objective function: a linear expression to maximize or minimize.
• Constraints: linear restrictions imposed by resources, requirements, or policy.
• Parameters: known numerical coefficients such as unit profit, processing time, or resource availability.
• Non-negativity restrictions: normally, decision variables cannot be negative.

A general maximization model can be written as:

subject to:

Here, x_j is decision variable j, c_j is its objective coefficient, a_ij is the amount of resource i used by one unit of activity j, b_i is the available amount of resource i, and Z is the objective value. The coefficients must have compatible units. For example, if x_j is measured in products, a_ij may be machine-hours per product, and b_i must be machine-hours.

The word “linear” means that variables appear only to the first power, variables are not multiplied by one another, and coefficients are constant. Thus, 3x + 2y is linear, whereas xy, x², and a profit coefficient that depends on quantity are not linear without further approximation.

1.1 Formulating Decision Variables

Variable definitions should be precise and measurable. “Produce product A” is incomplete unless the time period and unit are specified. A stronger definition is: “Let x equal the number of Product A units produced during the next week.”

Poorly defined variables create ambiguity about inventory, timing, divisibility, and product quality. If products must be whole units, an integer programming model may be required rather than an ordinary LP.

1.2 Formulating the Objective Function

The objective expresses the quantity to optimize. If product A contributes $40 per unit and product B contributes $30 per unit, then the weekly contribution is:

The coefficients should represent the relevant contribution, not necessarily selling price. If variable cost differs by product, contribution may be calculated as selling price minus variable cost. Fixed costs that do not change with the decision do not affect the optimal mix, although they matter for total profit reporting.

1.3 Formulating Constraints

Constraints represent limited resources or required conditions. A capacity constraint generally has the form:

A minimum requirement uses ≥, while an exact balance uses =. Examples include:

• Machine capacity: 2x + 3y ≤ 120.
• Minimum service level: x + y ≥ 50.
• Budget balance: 8x + 5y ≤ 400.
• Workforce composition: x ≥ 0.4(x+y).

The last expression can be rearranged into the linear form 0.6x − 0.4y ≥ 0.

2. Feasible Regions and Graphical Solution

For a two-variable LP, each constraint can be represented on a coordinate plane. The set of all points satisfying every constraint, including non-negativity, is the feasible region. A point in this region is a feasible solution; a point outside it violates at least one constraint.

For a maximization or minimization LP with a nonempty, bounded feasible region, at least one optimal solution occurs at a corner point, also called an extreme point. This is the basis of the graphical method and the geometric foundation of the simplex method.

Consider the illustrative model:

subject to:

The first constraint has intercepts (20, 0) and (0, 40). The second has intercepts (50, 0) and (0, 25). The feasible corner points are (0, 0), (20, 0), (10, 20), and (0, 25). The intersection point is obtained by solving:

From the first equation, y = 40 − 2x. Substitution gives x + 2(40 − 2x) = 50, so −3x = −30 and x = 10. Therefore y = 20.

Evaluate the objective at each corner:

The optimal solution is x = 10, y = 20, with objective value $1,000. Both resource constraints are binding at this solution because each is satisfied as an equality.

A graphical solution is useful for teaching and for small models, but it becomes impractical when there are more than two decision variables. Software solvers are then required.

3. Slack, Surplus, and Binding Constraints

A constraint’s unused capacity is called slack. For a “less than or equal to” constraint:

For the optimal solution above:

A constraint with zero slack is binding. A constraint with positive slack is non-binding. Binding constraints identify resources that are fully utilized at the optimum; they often deserve managerial attention.

For a minimum constraint, the analogous quantity is surplus:

A minimum constraint is binding when its surplus is zero. Slack and surplus should be reported in the units of the constraint, such as machine-hours, dollars, kilograms, or employee-hours.

A binding constraint is not automatically a problem. It becomes a managerial concern if additional capacity could improve the objective and can be acquired at an acceptable cost.

4. Special Outcomes in Linear Programming

Infeasibility

An LP is infeasible when no point satisfies all constraints simultaneously. For example, requiring x ≥ 10 and x ≤ 5 creates an infeasible model. In practice, infeasibility may indicate inconsistent policy requirements, inadequate resources, or data-entry errors.

Unboundedness

A maximization model is unbounded if the objective can increase indefinitely while all constraints remain satisfied. This often signals a missing capacity restriction or an incorrect inequality direction. Real business problems are rarely genuinely unbounded.

Multiple optimal solutions

More than one solution may produce the same optimal objective value. Geometrically, this occurs when the objective line is parallel to a binding edge of the feasible region. Managers may then select among alternative optimal plans using criteria not included in the objective, such as workforce stability or supplier relationships.

Degeneracy

A basic feasible solution is degenerate when more constraints are active than are necessary to define the corner. Degeneracy can produce zero-valued basic variables and may complicate interpretation of marginal values, although it does not invalidate the LP solution.

5. Algebraic and Solver-Based Methods

The simplex method moves from one extreme point to another, improving the objective until no adjacent feasible point offers improvement. Modern solvers may use revised simplex, interior-point, or hybrid algorithms. The user generally supplies the model, and the solver returns a solution and diagnostic report.

Common tools include spreadsheet Solver, Python optimization libraries, R packages, and commercial systems. A solver does not decide whether the model represents the organization correctly. It only optimizes the mathematical representation provided.

A disciplined implementation process is:

1. Define variables and units.
2. Enter objective coefficients and constraints.
3. Specify maximization or minimization.
4. Add non-negativity and integrality conditions where required.
5. Solve using an appropriate LP algorithm.
6. Check feasibility and objective calculations independently.
7. Interpret slacks, binding constraints, and sensitivity results.
8. Test the recommendation against operational and ethical realities.

6. Sensitivity Analysis

Sensitivity analysis studies how the optimal solution or objective value responds to changes in model parameters. It is essential because business data are estimates and operating conditions change.

6.1 Objective-Coefficient Sensitivity

An objective coefficient may be a unit profit, cost, revenue, or service value. The allowable increase and allowable decrease describe the range over which a coefficient can change while the current optimal basis remains optimal, assuming other parameters remain unchanged.

For example, if the coefficient of product A is $40 and its allowable range is $35 to $60, the current production structure remains optimal for any coefficient within that interval. The objective value changes, but the quantities may not.

This interpretation must be used carefully. A coefficient outside the range does not necessarily mean the current plan is unusable; it means the solver must reoptimize before a conclusion is drawn.

6.2 Shadow Prices or Dual Values

The shadow price of a resource constraint is the marginal change in the optimal objective value caused by increasing the right-hand side by one unit, within the allowable range and subject to the model’s assumptions.

Formally, if resource availability is b_i, the shadow price can be represented locally as:

where Z* is the optimal objective value. Units are objective units per unit of resource, such as dollars per machine-hour.

A non-binding “less than or equal to” resource normally has zero shadow price because a small increase provides no immediate benefit. A binding constraint may have a positive shadow price in a maximization model, but binding status alone does not guarantee a positive value.

Suppose a machine-hour constraint has a shadow price of $12 per hour and an allowable increase of 10 hours. An additional 6 hours is worth approximately $72 in improved objective value, provided all other assumptions remain unchanged and the increase stays within the stated range. If the cost of obtaining those hours is less than $72, acquisition may be economically attractive, subject to implementation considerations.

6.3 Reduced Costs

For a variable at zero in an optimal maximization solution, the reduced cost indicates how much its objective coefficient would need to improve before it could enter the solution, under standard solver conventions. In a minimization problem, sign interpretation depends on the convention used by the software.

Because reduced-cost definitions and signs can vary across reports, analysts should read the solver’s documentation. The practical question is: “How much must the contribution of this currently unused activity improve before it becomes attractive?”

6.4 Right-Hand-Side Ranges

A shadow price is a local marginal value, not a universal value for unlimited resource changes. The allowable increase and decrease define the range over which the reported shadow price remains valid without changing the optimal basis. Outside this range, the model should be solved again.

6.5 Simultaneous Changes and the 100 Percent Rule

When several objective coefficients change simultaneously, individual allowable ranges cannot always be applied independently. A common screening rule is:

If the sum is no greater than 1, the current basis is generally expected to remain optimal under the standard sensitivity assumptions. This rule is a screening device, not a substitute for re-solving the model.

7. Worked Sensitivity Interpretation

Assume a solver reports the following for a production model:

The machine and labor constraints are binding. One additional machine-hour is worth approximately $12 within the allowable range, whereas one additional labor-hour is worth approximately $4. If machine capacity can be expanded for $8 per hour, the marginal economic gain exceeds the acquisition cost by approximately $4 per hour. If extra labor costs $6 per hour, it is not attractive based solely on the LP’s marginal value.

Storage has 80 units of slack and a zero shadow price. Expanding storage immediately does not improve the objective because storage is not limiting the current plan. This does not mean storage is unimportant in all circumstances; it means it is not marginally valuable under the current model and solution.

8. Illustrative Case: Northstar Furniture

Background

Northstar Furniture produces desks and bookcases each week. A desk contributes $80 and uses 4 hours of carpentry and 2 hours of finishing. A bookcase contributes $60 and uses 3 hours of carpentry and 3 hours of finishing. Weekly capacity is 240 carpentry hours and 180 finishing hours.

Problem and formulation

Let x be desks produced per week and y be bookcases produced per week.

subject to:

The intersection of the two capacity boundaries is found by solving:

Subtracting the second equation from the first gives 2x = 60, so x = 30. Substitution gives 60 + 3y = 180, hence y = 40. The contribution is:

The plan uses all 240 carpentry hours and all 180 finishing hours. It is therefore a natural candidate for the optimum. Comparing it with the axis corner points confirms the result: 60 desks produce $4,800, while 60 bookcases produce $3,600, and the mixed plan also produces $4,800. In this particular model, the objective is parallel to the binding edge, so there are multiple optimal production combinations between the relevant endpoints. Management may choose the mixed plan because it preserves product variety.

Managerial interpretation

The two resources are both fully utilized, but their marginal values should be obtained from the solver’s dual report rather than inferred solely from binding status. If market demand limits bookcases to 30 units, that demand condition must be added as y ≤ 30, and the model must be re-solved. The original recommendation cannot simply be adjusted informally.

Learning points

1. A clear variable definition makes the model auditable.
2. Resource coefficients must use consistent hours per unit.
3. Binding constraints identify capacity pressure.
4. Multiple optima allow managerial discretion.
5. New business information should be modeled explicitly and re-solved.

This is an illustrative case; the data are fictional and intended for learning.

9. Assumptions and Limitations

LP commonly assumes:

• Proportionality: resource use and contribution change directly with activity level.
• Additivity: total resource use equals the sum of activity-level uses; interaction effects are absent.
• Divisibility: fractional quantities are allowed unless integrality is imposed.
• Certainty: coefficients are known and fixed during the planning period.
• Consistency: all relevant activities and constraints are represented.

These assumptions can be unrealistic. Setup costs, volume discounts, overtime premiums, nonlinear demand, learning effects, indivisible workers, and uncertain travel times may require integer, nonlinear, stochastic, or robust optimization. A mathematically optimal solution can be operationally infeasible if it ignores staffing, quality, supplier reliability, or implementation time.

Forecast error is a central limitation. Sensitivity analysis evaluates specified changes but does not automatically model probability distributions or correlated uncertainty. Scenario analysis, simulation, robust optimization, and stochastic programming may be appropriate when uncertainty is substantial.

10. Governance, Ethics, and Contemporary Practice

LP models can influence hiring, scheduling, pricing, healthcare access, and resource allocation. Analysts should document data sources, assumptions, objective definitions, excluded factors, and approval responsibilities. An objective that maximizes profit alone may systematically disadvantage service quality, safety, or vulnerable groups.

Fairness constraints, minimum service requirements, privacy protections, and human review may be needed. Sensitive personal data should not be included unnecessarily. Results should be explainable to decision makers affected by them, and automated recommendations should have an escalation process.

Spreadsheet and cloud-based solvers improve accessibility, while Python, R, and optimization platforms support reproducibility and version control. AI tools can assist with formulation drafts, data preparation, and scenario generation, but generated models must be independently validated. AI does not remove the need for dimensional checks, feasibility testing, sensitivity analysis, and managerial accountability.

Best practices include:

1. State the decision horizon and units.
2. Separate input data from model logic.
3. Validate every coefficient with subject-matter experts.
4. Test extreme and contradictory inputs.
5. Reconcile solver output with an independent calculation.
6. Report ranges and scenarios, not only one point estimate.
7. Record model versions and changes.
8. Explain trade-offs to nontechnical stakeholders.

Chapter Summary

Linear programming provides a structured method for optimizing a linear objective subject to linear constraints. A sound model begins with measurable decision variables, a correctly specified objective, and constraints that represent resource, policy, demand, or service requirements. The feasible region contains all acceptable solutions, and an optimum occurs at an extreme point when standard boundedness conditions hold.

Graphical methods are useful for two-variable models, while simplex-based and interior-point solvers handle larger models. Slack measures unused capacity, surplus measures excess above a minimum requirement, and binding constraints are active at equality. Sensitivity reports provide objective-coefficient ranges, right-hand-side ranges, shadow prices, and reduced costs. These values support decisions about capacity expansion, product profitability, and resource priorities, but they are valid only within stated ranges and assumptions.

LP is a decision-support tool rather than a substitute for judgment. Data quality, uncertainty, integrality, nonlinear effects, ethics, fairness, and implementation constraints must be considered. Responsible analysts combine optimization with validation, scenario analysis, governance, and transparent managerial interpretation.

Key Terms

Decision variable: An unknown quantity selected by the model.

Objective function: A mathematical expression maximized or minimized.

Constraint: A restriction placed on decision variables.

Parameter: A known coefficient or input in a model.

Feasible solution: A solution satisfying every constraint.

Feasible region: The set of all feasible solutions.

Corner point: An extreme point of a feasible region.

Binding constraint: A constraint satisfied exactly at the solution.

Slack: Unused capacity in a less-than-or-equal constraint.

Surplus: Amount by which a minimum constraint is exceeded.

Shadow price: Marginal objective value of one additional unit of a resource.

Reduced cost: Required improvement in an inactive variable’s objective coefficient under solver conventions.

Allowable increase: Permitted parameter increase that preserves the current basis.

Allowable decrease: Permitted parameter decrease that preserves the current basis.

Simplex method: An algorithm that moves among feasible extreme points.

Infeasibility: The absence of any solution satisfying all constraints.

Unboundedness: An objective that can improve indefinitely within the model.

Degeneracy: An extreme point with more active restrictions than necessary.

Integer programming: Optimization requiring some variables to take integer values.

Sensitivity analysis: Study of solution responses to parameter changes.

Review Questions

Short Answer Questions

1. What are the three essential structural components of a linear programming model?
2. Distinguish between slack and surplus.
3. What does it mean for a constraint to be binding?
4. Why are graphical methods limited for large LP models?
5. What is the managerial meaning of a shadow price?

Long Answer Questions

1. Explain how a business narrative is translated into decision variables, an objective function, and constraints. Illustrate with a production example.
2. Describe the graphical solution procedure for a two-variable maximization problem, including intercepts, feasible-region identification, corner-point evaluation, and interpretation.
3. Explain the assumptions of proportionality, additivity, divisibility, and certainty. Give one practical limitation associated with each.
4. Compare objective-coefficient sensitivity, right-hand-side sensitivity, shadow prices, and reduced costs.
5. Discuss why an optimal solver result may still be unsuitable for implementation.

Analytical / Application Questions

1. A company earns $50 per unit of A and $40 per unit of B. A uses 2 labor hours and 1 machine-hour; B uses 1 labor hour and 2 machine-hours. Weekly availability is 100 labor hours and 80 machine-hours. Formulate the LP and determine the intersection of the two resource boundaries.
2. A binding capacity constraint has a shadow price of $15 per unit and an allowable increase of 20 units. Should the company buy 12 additional units at $10 each? State the assumptions required for your conclusion.
3. A solver reports a positive slack of 500 kilograms for a raw-material constraint and zero slack for labor. Explain which resource is immediately limiting, what additional raw material is worth at the margin, and what further information is needed before expanding labor capacity.

Multiple Choice Questions with Answers

Question 1

Which expression is a valid linear objective function?

A. Z = 5x + 3y

B. Z = xy + 4

C. Z = x² + y

D. Z = 5^y + x

Correct Answer: A. Z = 5x + 3y

Question 2

A constraint has 25 units of capacity, of which 18 are used. What is its slack?

A. 7 units

B. 18 units

C. 25 units

D. 43 units

Correct Answer: A. 7 units

Question 3

What does a zero slack value indicate for a standard capacity constraint?

A. The constraint is infeasible

B. The constraint is binding

C. The objective is unbounded

D. The variable must be integer

Correct Answer: B. The constraint is binding

Question 4

A resource has a shadow price of $8 per hour. Within its allowable range, what is the approximate value of 4 additional hours?

A. $2

B. $12

C. $32

D. $64

Correct Answer: C. $32

Question 5

Which condition describes an infeasible LP?

A. The objective has multiple optima

B. No point satisfies all constraints

C. A resource has positive slack

D. A variable has value zero

Correct Answer: B. No point satisfies all constraints

Question 6

Which assumption allows fractional production quantities in an ordinary LP?

A. Certainty

B. Additivity

C. Divisibility

D. Proportionality

Correct Answer: C. Divisibility

Question 7

For the model Maximize Z = 40x + 30y with constraints 2x + y ≤ 40 and x + 2y ≤ 50, what is the objective value at (x,y) = (10,20)?

A. $700

B. $800

C. $1,000

D. $1,200

Correct Answer: C. $1,000

Question 8

A non-binding less-than-or-equal-to resource constraint commonly has what shadow price?

A. Zero

B. Always negative

C. Equal to its full capacity

D. Equal to the objective value

Correct Answer: A. Zero

Question 9

What should an analyst generally do when a parameter changes outside its reported sensitivity range?

A. Ignore the change

B. Assume the same shadow price applies indefinitely

C. Re-solve the model

D. Delete the constraint

Correct Answer: C. Re-solve the model

Question 10

Which issue most directly suggests integer programming rather than ordinary LP?

A. A product contributes profit

B. A machine has limited hours

C. Workers must be scheduled as whole people

D. A firm wants to maximize contribution

Correct Answer: C. Workers must be scheduled as whole people