Mathematical Programming Foundations

Introduction and context

Mathematical programming converts managerial choices into a formal optimization model. A decision-maker specifies controllable quantities, a performance criterion, and restrictions imposed by resources, policy, technology, or market conditions. The resulting model can identify an optimal plan, demonstrate that no feasible plan exists, or reveal which scarce resources and assumptions most influence the recommendation.

Linear programming (LP) is the foundational mathematical programming method for prescriptive analytics. It is appropriate when decision variables are continuous or can reasonably be treated as continuous, relationships are linear, and the objective is to maximize or minimize a measurable quantity. LP supports production planning, workforce allocation, transportation, blending, portfolio construction, capacity planning, media selection, and supply-chain design.

The value of LP is not simply the numerical solution. Its greatest managerial value often lies in interpretation: Which constraints are binding? What is the marginal value of an additional resource? Which activities are unattractive at the margin? How robust is the recommendation to changes in prices, capacities, or demand?

Learning objectives

After completing this chapter, you should be able to:

1. Translate a managerial problem into decision variables, an objective function, and constraints.
2. State the assumptions and units underlying a linear programming model.
3. Solve two-variable models graphically and interpret corner-point optimality.
4. Explain feasibility, boundedness, optimality, binding constraints, slack, and surplus.
5. Interpret solver output, including shadow prices, reduced costs, and allowable ranges.
6. Explain the relationship between a primal LP and its dual.
7. Evaluate model limitations, implementation risks, and governance requirements.

1. The anatomy of a linear program

A linear program has four essential components:

• Decision variables: unknown quantities whose values represent decisions.
• Objective function: a linear measure to maximize or minimize.
• Constraints: linear equations or inequalities that define permissible decisions.
• Domain restrictions: usually nonnegativity, integrality, or explicit bounds.

A general maximization model is:

Here, x_j is the amount of activity j; c_j is the objective contribution per unit of activity; a_ij is the amount of resource i consumed by one unit of activity j; b_i is the available amount of resource i; and Z is total objective value. Units must be consistent: if x_j is products per week and c_j is dollars per product, Z is dollars per week.

The matrix form is:

The vector x contains decision variables, c objective coefficients, b resource capacities, and A technological coefficients. This formulation assumes linearity, divisibility of activities, known coefficients, and additive resource use and returns.

Building a model from language

A disciplined formulation follows this sequence:

1. Define the planning horizon, organizational boundary, and units.
2. Define one variable for each genuinely controllable activity.
3. Write the objective in terms of those variables.
4. Translate every relevant limitation into a constraint.
5. Add nonnegativity, upper bounds, or integrality conditions.
6. Check dimensions, signs, omitted activities, and redundant constraints.
7. State assumptions explicitly before solving.

Words such as “at most,” “no more than,” and “capacity” generally imply ≤. “At least,” “minimum,” and “required” imply ≥. “Exactly” implies =. A constraint is meaningful only when its coefficients and right-hand side have compatible units.

Example: product mix

A manufacturer produces desks x₁ and tables x₂. Each desk contributes $40 and uses 4 hours of carpentry and 2 hours of finishing. Each table contributes $30 and uses 2 carpentry hours and 3 finishing hours. Weekly capacities are 40 carpentry hours and 30 finishing hours. The model is:

The objective and constraint coefficients have clear units. For example, 4x₁ represents carpentry hours used by desks, while the right-hand side 40 represents available carpentry hours per week.

2. Feasible regions and graphical solution

For a two-variable LP, each inequality defines a half-plane. Their intersection, together with nonnegativity, is the feasible region. A point is feasible if it satisfies every constraint. A feasible solution is optimal if no other feasible solution produces a better objective value.

To solve graphically, first plot each constraint boundary. For the product-mix model, the intercepts are:

• 4x₁ + 2x₂ = 40: intercepts (10, 0) and (0, 20).
• 2x₁ + 3x₂ = 30: intercepts (15, 0) and (0, 10).

The feasible region lies below both lines in the first quadrant. The intersection of the two boundaries is obtained by solving:

Dividing the first equation by 2 gives 2x₁+x₂=20, so x₂=20-2x₁. Substitution into the second equation yields 2x₁+3(20-2x₁)=30, hence -4x₁=-30, x₁=7.5, and x₂=5. The relevant corner points are (0, 0), (10, 0), (7.5, 5), and (0, 10).

Evaluate the objective at each point:

Therefore, the optimal production plan is 7.5 desks and 5 tables, with weekly contribution of $450. Both resource constraints bind at this solution: carpentry use is 4(7.5)+2(5)=40, and finishing use is 2(7.5)+3(5)=30. If products must be whole units, this LP solution is not automatically implementable; an integer programming model may be required.

The corner-point theorem states that, when a linear program has an optimal solution and a nonempty feasible region, at least one optimal solution occurs at an extreme point, or corner, of the feasible region. This theorem justifies evaluating corners in a two-variable model and underlies the simplex method in higher dimensions. If the objective is parallel to a binding edge, multiple optimal solutions may exist.

3. Feasibility, optimality, and special outcomes

A model is feasible if at least one assignment satisfies all constraints. It is infeasible when restrictions conflict. For example, x≥10 and x≤5 cannot both hold. Infeasibility is not a computational nuisance; it indicates that requirements, capacities, or data must be reviewed.

A model is unbounded when the objective can improve indefinitely within the stated feasible region. In a profit-maximization model, unboundedness commonly indicates a missing capacity, demand, or sign restriction. It may also be legitimate in an abstract model, but it is rarely a credible business result.

A solution is optimal when it satisfies all constraints and has the best objective value among all feasible solutions. A solver may also report alternate optima, where different plans have exactly the same objective value. Managers can then choose among them using risk, fairness, stability, or implementation criteria not included in the primary objective.

Slack, surplus, and binding constraints

For a ≤ resource constraint, slack is unused capacity:

For a ≥ requirement, surplus is the amount by which the requirement is exceeded:

A constraint is binding when its slack or surplus is zero. A nonbinding resource has positive unused capacity in a maximization problem with a ≤ constraint. Binding does not mean that the constraint is necessarily problematic; it means that it limits the current solution at the margin.

In the product-mix example, both constraints bind. At point (10, 0), carpentry binds but finishing has 10 hours of slack: 30−2(10)=10. This distinction is important because marginal capacity value is generally associated with binding constraints, not unused resources.

4. Computational solution and solver practice

Real models may contain thousands of variables and constraints, so graphical methods are mainly for insight and validation. Spreadsheet solvers, algebraic modeling languages, and optimization libraries commonly implement the simplex method, interior-point methods, or hybrid algorithms.

A reliable computational workflow is:

1. Model specification: document variables, units, objective direction, constraints, and assumptions.
2. Data preparation: validate coefficients, capacities, prices, and time periods; identify missing or extreme values.
3. Implementation: keep input data separate from formulas and use meaningful variable names.
4. Solve and diagnose: inspect solver status, feasibility residuals, objective value, and variable values.
5. Validate independently: substitute the solution into every constraint and recompute the objective.
6. Perform sensitivity and scenario analysis: vary material assumptions and assess stability.
7. Communicate: report recommendations, resource use, economic interpretation, and limitations.

Solver status must be read before accepting a solution. “Optimal” under the implemented model does not mean “managerially correct.” A solver cannot detect an incorrectly entered unit, omitted constraint, biased objective, or invalid business assumption.

5. Shadow prices and marginal managerial value

The shadow price of a constraint is the marginal change in the optimal objective value caused by increasing its right-hand side by one unit, provided the change remains within the solver’s allowable sensitivity range and the current basis remains valid. For a maximization problem with resource capacity b_i, it is commonly expressed as:

Here, Z^* is the optimal objective value. Units are objective units per unit of resource, such as dollars per carpentry hour. The interpretation is local, not universal: it applies only while relevant assumptions and basis conditions remain valid.

For the product-mix example, the two binding constraints have shadow prices y₁ and y₂ satisfying:

Solving gives y₁=7.5 and y₂=5. Thus, within the appropriate sensitivity ranges, one additional carpentry hour is worth $7.50 in maximum contribution, while one additional finishing hour is worth $5. These are opportunity values, not necessarily supplier prices. If an extra carpentry hour costs $6, acquiring it may improve contribution by approximately $1 net, subject to the allowable range and operational feasibility.

A nonbinding ≤ resource with positive slack typically has shadow price zero in a standard maximization LP: an additional unit does not improve the objective immediately. This does not mean the resource has no strategic value under future scenarios.

6. Reduced costs and activity economics

The reduced cost measures how much an objective coefficient of a variable at zero would need to improve before that variable becomes attractive in the current solution. In a maximization model, a variable with a negative reduced cost is unattractive at the margin under the current basis. If its contribution increases by the absolute value of that reduced cost, it may enter the solution, provided the change remains within the allowable range.

Using dual values y_i, the reduced-cost relationship for activity j is:

Sign conventions in solver reports vary, so the report’s definition must be checked. Under the convention above for a maximization problem, an activity at zero generally has r_j≤0 at optimality. The term ∑_i a_ijy_i is the imputed opportunity cost of the resources consumed by one unit of activity j.

Reduced cost is not the same as profit per unit. It accounts for scarce-resource opportunity costs. It also does not mean that a product has no value; it means it is not selected under the current prices, capacities, and model structure.

7. Duality: a second view of the same decision

Every linear program has a related dual. For the primal maximization model with ≤ constraints and nonnegative variables:

The primal chooses activity levels; the dual assigns implicit prices to resources. Dual feasibility requires that the imputed resource value of every activity be at least its contribution. The dual objective minimizes the total imputed value of available resources while satisfying those activity-value requirements.

Weak duality states that every feasible dual objective value is at least every feasible primal maximization value. Strong duality states that if both problems have finite optimal solutions, their optimal objective values are equal:

For the product-mix example, dual prices 7.5 and 5 produce resource value 40(7.5)+30(5)=450, equal to the primal contribution of $450. This equality provides both an economic interpretation and a powerful validation check.

Complementary slackness links resource use and prices. For a standard primal-dual pair, if a primal constraint has positive slack, its corresponding dual price is zero; if a dual constraint is strictly greater than its primal objective coefficient, the corresponding primal variable is zero. These relationships explain why unused resources generally have no immediate marginal value and why unselected activities have unfavorable reduced economics.

8. Sensitivity analysis and managerial interpretation

Sensitivity analysis examines how the recommendation changes when coefficients or right-hand sides change. Common outputs include:

• Allowable increase/decrease in a right-hand side: the range over which a shadow price remains valid.
• Allowable increase/decrease in an objective coefficient: the range over which the current basis remains optimal.
• Shadow price: marginal objective value of a resource change.
• Reduced cost: marginal improvement required for an inactive variable to become competitive.

Sensitivity ranges are conditional. Changing several parameters simultaneously can invalidate one-at-a-time interpretations. Large changes may alter the active constraints, create a new corner point, or change the optimal basis entirely. Scenario analysis or reoptimization is preferable for substantial changes.

Managers should distinguish three questions:

1. What is optimal now? The current solution answers this under stated data.
2. What is valuable at the margin? Shadow prices and reduced costs answer this locally.
3. What remains robust? Scenario, stress, and uncertainty analysis address this broader question.

9. Illustrative case: allocating a digital advertising budget

Background

A fictional online retailer must allocate a weekly budget of $60,000 between search advertising x₁ and social advertising x₂, measured in thousands of dollars. Search generates an estimated 120 qualified visits per thousand dollars and social generates 90. Campaign policy requires at least $10,000 in social spending, while campaign-management capacity limits search spending to $40,000.

Model

The objective is expected qualified visits per week. The coefficients assume stable average response and no interaction or saturation effects—strong assumptions that must be tested before implementation.

Analysis and solution

Because search produces more expected visits per dollar, the model allocates the maximum permitted search budget: x₁=40. The remaining budget goes to social, giving x₂=20. Expected visits are:

The budget constraint binds. Search capacity is also binding. The social minimum is nonbinding because social spending exceeds its minimum by $10,000. The marginal value of relaxing search capacity is approximately the difference between search’s return and the return of the displaced social spending: 30 qualified visits per additional thousand dollars, while the budget and other constraints remain active. This interpretation is local and depends on the linear response assumption.

Governance and decision quality

The retailer should validate visit estimates using experiment or holdout data, distinguish qualified visits from revenue and profit, and account for attribution uncertainty, privacy restrictions, frequency effects, and diminishing returns. A model that maximizes visits may conflict with profitability or customer fairness. If response curves are nonlinear, a piecewise-linear model or nonlinear optimization model may be more appropriate.

Learning points

The case illustrates that LP can make policy restrictions explicit, expose opportunity costs, and support resource negotiations. It also demonstrates that a mathematically optimal allocation is only as credible as its objective, data, constraints, and assumptions.

10. Limitations, extensions, and responsible use

Linearity and divisibility

Real returns may exhibit fixed costs, economies of scale, congestion, or diminishing returns. Binary decisions such as opening a facility or selecting a campaign require mixed-integer programming. Whole-unit products require integer restrictions. These extensions improve realism but increase computational complexity.

Certainty and data quality

Classical LP treats coefficients as known. Forecast error, demand uncertainty, supplier disruption, and changing prices can make a precise optimum misleading. Robust optimization, stochastic programming, simulation, and rolling-horizon reoptimization can address uncertainty, but each introduces assumptions that should be documented.

Multiple objectives

Profit may conflict with service, emissions, risk, equity, or employee welfare. Weighted objectives, goal programming, constraints on minimum service, or Pareto analysis can represent such priorities. Weights should be governed transparently rather than chosen merely to produce a preferred answer.

Ethical and regulatory considerations

Optimization can systematically allocate opportunities or burdens. Data-driven constraints may reproduce historical discrimination, and an apparently neutral objective may disadvantage protected groups. Practitioners should conduct fairness assessments where decisions affect people, protect confidential data, preserve an audit trail, and provide human review for high-impact decisions. Regulatory obligations may require explainability, documentation, non-discrimination, and monitoring after deployment.

Best practices

Use dimensional analysis; document assumptions; validate input data; test alternative objectives; inspect binding constraints; re-solve under plausible scenarios; compare automated recommendations with domain expertise; and monitor realized outcomes. Treat solver output as decision support, not as a substitute for accountability.

Chapter Summary

Linear programming represents decisions with variables, a linear objective, linear constraints, and domain restrictions. A feasible solution satisfies every restriction; an optimal solution is the best feasible solution. In two-variable models, graphical analysis shows the feasible region and the corner-point principle. Slack identifies unused capacity, while binding constraints limit the current plan.

Computational solvers extend LP to large models, but implementation and data validation remain managerial responsibilities. Shadow prices estimate the marginal value of relaxing resource limits, whereas reduced costs describe the improvement needed for inactive activities to become competitive. Duality provides a complementary resource-pricing interpretation, and strong duality equates optimal primal and dual objective values under standard finite conditions. Sensitivity results are local and conditional, so substantial changes require reoptimization or scenario analysis. Finally, linearity, certainty, divisibility, objective selection, fairness, privacy, and governance determine whether an LP recommendation is appropriate for practice.

Key Terms

Decision variable: A controllable quantity whose value is chosen by the model.

Objective function: The mathematical expression measuring what the model maximizes or minimizes.

Constraint: A mathematical restriction on permissible decisions.

Feasible solution: A decision assignment satisfying every constraint and domain restriction.

Feasible region: The set of all feasible decision assignments.

Optimal solution: A feasible solution with the best objective value.

Linear programming: Optimization with linear objective and constraint relationships.

Slack: Unused amount in a ≤ constraint.

Surplus: Amount by which a ≥ requirement is exceeded.

Binding constraint: A constraint with zero slack or surplus at a solution.

Shadow price: Marginal objective value of changing a constraint right-hand side locally.

Reduced cost: Marginal objective-coefficient improvement associated with an inactive variable, subject to sign convention.

Primal: The original LP formulation.

Dual: The associated LP assigning implicit values to primal resources.

Strong duality: Equality of finite optimal primal and dual objective values.

Complementary slackness: Conditions linking primal slack and dual prices or activity levels.

Sensitivity analysis: Study of solution changes under parameter changes.

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

Robust optimization: Optimization designed to perform acceptably across specified uncertainty.

Review Questions

Short Answer Questions

1. What are the four essential components of a linear programming model?
2. Distinguish a feasible solution from an optimal solution.
3. What does it mean for a resource constraint to be binding?
4. Define a shadow price and state why its interpretation is conditional.
5. What economic information does a reduced cost provide?

Long Answer Questions

1. Explain how a managerial narrative can be translated into variables, an objective function, constraints, and domain restrictions. Include unit checks.
2. Describe the graphical solution method for a two-variable LP and explain the corner-point theorem.
3. Explain primal-dual relationships, weak duality, strong duality, and complementary slackness.
4. Discuss why solver output cannot be accepted without model validation and sensitivity analysis.
5. Evaluate the assumptions and governance risks of using LP for allocating resources that affect people or communities.

Analytical / Application Questions

1. A firm maximizes Z=50x₁+40x₂ subject to 3x₁+2x₂≤36, x₁+2x₂≤20, and x₁,x₂≥0. Identify the corner points and determine the optimal solution.
2. A solver reports that a capacity constraint has 8 units of slack and a shadow price of zero. Explain the result and describe a situation in which the resource could nevertheless become strategically important.
3. A manager proposes increasing a resource by 50 units based on a shadow price calculated for a one-unit change. Critically assess the proposal and recommend an appropriate analytical procedure.

Multiple Choice Questions with Answers

Question 1

Which component specifies what the optimization model seeks to maximize or minimize?

A. Decision variable

B. Objective function

C. Feasible region

D. Slack variable

Correct Answer: B. Objective function

Question 2

In a maximization LP, a constraint with positive slack represents:

A. A fully utilized resource

B. An infeasible requirement

C. Unused capacity

D. An alternate optimum

Correct Answer: C. Unused capacity

Question 3

For the product-mix example, what is the optimal production plan?

A. 10 desks and 0 tables

B. 0 desks and 10 tables

C. 7.5 desks and 5 tables

D. 5 desks and 7.5 tables

Correct Answer: C. 7.5 desks and 5 tables

Question 4

What is the shadow price of carpentry hours in the product-mix example?

A. $2.50 per hour

B. $5.00 per hour

C. $7.50 per hour

D. $10.00 per hour

Correct Answer: C. $7.50 per hour

Question 5

A linear program is infeasible when:

A. Its objective has multiple optima

B. No assignment satisfies all restrictions

C. A resource has positive slack

D. A variable equals zero

Correct Answer: B. No assignment satisfies all restrictions

Question 6

Under the stated primal-dual convention, the dual of a maximization LP with ≤ constraints and nonnegative variables is generally a:

A. Maximization problem with ≤ constraints

B. Minimization problem with ≥ constraints and nonnegative dual variables

C. Minimization problem with equality constraints only

D. Maximization problem with unrestricted dual variables

Correct Answer: B. Minimization problem with ≥ constraints and nonnegative dual variables

Question 7

What does a reduced cost generally indicate for an activity currently at zero in a maximization model?

A. The activity’s total revenue

B. The amount of resource slack

C. The objective-coefficient improvement needed for it to become competitive

D. The total dual objective value

Correct Answer: C. The objective-coefficient improvement needed for it to become competitive

Question 8

In the advertising case, what allocation maximizes expected qualified visits under the stated model?

A. $40,000 search and $20,000 social

B. $20,000 search and $40,000 social

C. $30,000 search and $30,000 social

D. $50,000 search and $10,000 social

Correct Answer: A. $40,000 search and $20,000 social

Question 9

Strong duality states that, when both finite optima exist:

A. The primal objective is always zero

B. The dual objective is strictly larger than the primal objective

C. The primal and dual optimal objective values are equal

D. All constraints must be nonbinding

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

Question 10

Why should a large change in a right-hand side not automatically be evaluated using a reported shadow price?

A. Shadow prices apply only to integer variables

B. The allowable sensitivity range may be exceeded and the optimal basis may change

C. Shadow prices measure objective coefficients, not resources

D. Right-hand sides cannot be changed in an LP

Correct Answer: B. The allowable sensitivity range may be exceeded and the optimal basis may change