Optimization and Mathematical Programming

Introduction and Context

Organizations routinely allocate scarce resources among competing uses. A manufacturer decides which products to produce with limited labor and machine time; a bank allocates capital under regulatory constraints; a logistics firm routes shipments through a network; and a public agency balances cost, service quality, equity, and environmental objectives. Optimization provides a disciplined way to represent these decisions and identify the best feasible alternative according to an explicitly stated objective.

Mathematical programming is the general framework for expressing such decisions through variables, an objective function, and constraints. The value of the framework is not merely computational. Formulating a model requires managers to clarify what is controllable, what is scarce, what outcomes matter, and which assumptions are acceptable. The resulting solution must therefore be interpreted in organizational and ethical context rather than accepted mechanically.

This chapter develops linear programming (LP), integer and mixed-integer programming, goal programming, and important network models. It also explains shadow prices, reduced costs, sensitivity analysis, model validation, and the responsible use of optimization software.

Learning Objectives

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

1. Formulate linear, integer, mixed-integer, and goal-programming models.
2. Explain feasible solutions, optimality, binding constraints, slack, and surplus.
3. Solve and interpret small LP models graphically and computationally.
4. Interpret shadow prices, reduced costs, and sensitivity ranges.
5. Apply transportation, assignment, shortest-path, and maximum-flow models.
6. Evaluate assumptions, uncertainty, implementation risks, and ethical implications.

1. The Architecture of an Optimization Model

A mathematical programming model normally contains four elements:

• Decision variables: controllable quantities, such as units produced or shipments dispatched.
• Objective function: a measure to maximize or minimize.
• Constraints: restrictions imposed by resources, policies, technology, or demand.
• Parameters: known or estimated coefficients, such as unit profit, processing time, or capacity.

A general optimization model can be written as:

Here, x is the vector of decision variables, f(x) is the objective, g_i(x) represents constraint functions, b_i is the requirement or capacity for constraint i, and X specifies domain restrictions such as nonnegativity or integrality. Linear programming is the special case in which the objective and constraints are linear and variables are continuous.

Formulation discipline

A reliable formulation follows this sequence:

1. Define the decision in words.
2. Establish the time period, units, and organizational scope.
3. Identify the objective and its direction.
4. Translate each physical or policy restriction into an equation or inequality.
5. Add domain restrictions.
6. Test the model with extreme or boundary cases.
7. Verify the solution against the original business problem.

Unit consistency is essential. If a variable represents units of product, then a coefficient such as labor hours per unit must multiply that variable, and the right-hand side must be labor hours available. Mixing dollars, thousands of dollars, hours, and minutes can produce a numerically feasible but operationally meaningless model.

2. Linear Programming

A standard maximization LP is:

The coefficient c_j is the contribution of activity j to the objective; 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 x_j is the activity level. The model assumes proportionality, additivity, divisibility, certainty of parameters, and a linear objective. These assumptions are useful approximations, not universal truths.

A feasible solution satisfies every constraint and domain restriction. The feasible region is the set of all feasible solutions. An optimal solution is a feasible solution with the best objective value. An LP with a nonempty bounded feasible region has at least one optimum. Under linearity, at least one optimum occurs at an extreme point (corner point) of the feasible region. If the objective is parallel to a binding edge, multiple optimal solutions may exist.

A model may be infeasible, unbounded, or have multiple optima. These are model diagnoses, not merely software messages. Infeasibility may indicate contradictory policies or unrealistic requirements; unboundedness often indicates a missing constraint; multiple optima indicate managerial flexibility.

Worked example: product mix

A firm produces desks (D) and tables (T). Each desk contributes $60 and uses 4 carpentry hours and 2 finishing hours. Each table contributes $50 and uses 3 carpentry hours and 4 finishing hours. Weekly capacities are 240 carpentry hours and 160 finishing hours. The model is:

The intercepts are 60 desks when T = 0 and 40 tables when D = 0. The intersection of the two resource constraints is found by solving:

Multiplying the second equation by 2 gives 4D + 8T = 320. Subtracting the first equation gives 5T = 80, so T = 16. Substitution gives 2D + 64 = 160, hence D = 48. The objective values at relevant corners are:

Thus the continuous LP recommends 48 desks and 16 tables, with contribution of $3,680. Both resource constraints bind: 4(48) + 3(16) = 240 and 2(48) + 4(16) = 160.

The example illustrates why checking only the single-product alternatives is insufficient. The optimal mix uses both products and exploits the interaction between scarce resources.

Graphical and computational solution

For two variables, graphing is valuable for explaining feasibility, binding constraints, and trade-offs. For larger models, the simplex method, interior-point algorithms, and commercial or open-source solvers are used. A solver should be viewed as an implementation of an optimization algorithm, not as a substitute for formulation and validation.

3. Duality, Shadow Prices, and Reduced Costs

Every appropriately structured LP has a related dual model. For the product-mix primal model, the dual assigns a value to each scarce resource:

Here y₁ and y₂ are implicit values per carpentry and finishing hour. Weak duality states that every feasible dual objective value is at least as large as every feasible primal maximization value. At optimality, the values are equal: strong duality.

A shadow price is the marginal change in the optimal objective value caused by a one-unit increase in the right-hand side of a constraint, holding other model elements fixed and remaining within the allowable sensitivity range. In the example, both constraints bind. Solving:

produces y₁ = 13 and y₂ = 4. Thus one additional carpentry hour is worth $13 and one additional finishing hour is worth $4 locally. The dual objective is 240(13) + 160(4) = $3,680, matching the primal optimum.

The interpretation is conditional. A shadow price is not automatically the market price of a resource, nor does it remain valid for large changes. If an additional carpentry hour costs $10, acquiring it is attractive within the valid range because its marginal contribution is $13. If it costs $15, it is not attractive under the model's assumptions.

Complementary slackness links primal and dual solutions:

• If a resource constraint has positive slack, its shadow price is zero in the usual nondegenerate case.
• If a variable is positive, its corresponding dual constraint is binding.
• A zero variable may have a positive reduced cost in a minimization problem, or a negative reduced cost in a maximization problem, depending on convention.

A reduced cost indicates how much an objective coefficient would need to improve before a currently zero variable could enter an optimal basis, subject to the relevant sensitivity conditions. Software reports differ in sign conventions, so the report's definition must always be checked.

Sensitivity analysis

Sensitivity analysis examines how the solution changes when parameters 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.
• Binding status: whether a resource is fully used.
• Slack or surplus: unused capacity or excess above a minimum requirement.

Sensitivity analysis is local and usually assumes one parameter changes at a time. Simultaneous changes can invalidate independent interpretations. When uncertainty is substantial, scenario analysis, stochastic programming, robust optimization, or simulation may be more appropriate.

4. Integer and Mixed-Integer Programming

Continuous LP permits fractional values. That is reasonable for tons of material or hours of aggregate labor, but not for delivery vehicles, projects, employees, or facility-opening decisions. An integer program imposes:

A mixed-integer linear program (MILP) contains both continuous and integer variables. Binary variables satisfy x_j ∈ {0, 1} and represent yes/no decisions.

Typical structures include:

• Fixed-charge decision: y = 1 if a facility opens. If production x is possible only when it opens, use x ≤ My, where M is a valid upper bound.
• Either-or condition: constraints may be activated through binary variables and a sufficiently tight big-M value.
• Logical dependency: if project A is selected, project B must also be selected, represented by x_A ≤ x_B.
• Minimum batch size: x ≥ Ly and x ≤ Uy, where y is binary and L and U are valid lower and upper bounds.

The big-M method must be used carefully. An excessively large M can cause weak bounds, numerical instability, and slow computation. A valid, tight bound derived from business conditions is preferable. Modern solvers also support indicator constraints, which can express logic more transparently.

Integrality and the transportation model

The LP relaxation removes integer restrictions. Its solution provides a bound for a maximization problem and can be fractional. Rounding is not generally valid: it may violate constraints or be far from optimal. Branch-and-bound systematically partitions the feasible region, uses bounds to eliminate subproblems, and proves optimality when the optimality gap is sufficiently small. Cutting planes and presolve techniques strengthen this process.

For some network models, the constraint matrix is totally unimodular. With integer supplies and demands, the LP relaxation then produces integer extreme-point solutions. This explains why standard balanced transportation and assignment models can often be solved as continuous LPs without explicitly imposing integrality.

5. Goal Programming

Many managerial decisions have several objectives that cannot be reduced credibly to one monetary measure. Goal programming handles prioritized or weighted deviations from target levels.

For goal k with target T_k and achieved expression L_k, introduce nonnegative underachievement and overachievement variables d_k⁻ and d_k⁺:

Only the relevant deviation is penalized. For a minimum sales target, underachievement d_k⁻ is usually penalized; for a maximum emissions target, overachievement d_k⁺ is penalized. A weighted goal-programming objective is:

where w values express relative importance, provided the scales and units have been considered carefully. In preemptive (lexicographic) goal programming, higher-priority goals are optimized before lower-priority goals. A lower-priority goal cannot trade away a higher-priority achievement. In weighted models, trade-offs are allowed according to weights.

Weights are not automatically equivalent to managerial priorities. A weight of 10 on a percentage goal and 5 on a dollar goal has no meaningful interpretation unless deviations have been normalized. Goal programming is therefore as much a preference-elicitation process as a mathematical technique.

6. Transportation and Assignment Models

Transportation model

A transportation problem distributes supply from origins to destinations at minimum cost. Let x_ij be the quantity shipped from origin i to destination j, c_ij the unit shipping cost, s_i supply at origin i, and d_j demand at destination j.

In a balanced problem, total supply equals total demand and inequalities commonly become equalities. In an unbalanced problem, a dummy origin or destination can represent unused supply or unmet demand, with a deliberately chosen penalty cost. The penalty must reflect the business consequence rather than being an arbitrary number.

Transportation models can be initialized by the northwest-corner, least-cost, or Vogel approximation methods and optimized by methods such as the transportation simplex or general LP/MILP solvers. Dual variables provide economically interpretable origin and destination potentials; their sum relative to a route cost indicates whether a route is attractive in the optimal basis.

Assignment model

The assignment problem allocates each worker, machine, or vehicle to exactly one task, with each task receiving exactly one resource. Let x_ij = 1 if resource i is assigned to task j, and 0 otherwise:

If the numbers of resources and tasks differ, dummy rows or columns can represent unassigned resources or tasks. The Hungarian algorithm solves the classical square assignment problem efficiently, while MILP handles side constraints such as eligibility, workload limits, or team dependencies.

7. Network Optimization

Network models represent nodes and arcs. They are especially useful because their structure supports efficient algorithms and clear visual interpretation.

• Shortest path: minimize total arc cost from an origin to a destination. Dijkstra's algorithm applies when arc costs are nonnegative; Bellman–Ford can handle negative costs but detects negative cycles.
• Maximum flow: maximize flow from a source to a sink subject to arc capacities and flow conservation at intermediate nodes. The max-flow/min-cut theorem states that the maximum feasible flow equals the capacity of the minimum source–sink cut.
• Minimum-cost flow: route a required amount of flow at minimum total cost while observing capacities and conservation.
• Minimum spanning tree: connect all nodes at minimum total edge cost, without requiring a specified source or destination.

For a flow network, conservation at intermediate node i can be expressed as:

where x_ji is inflow and x_ij is outflow. Capacities require 0 ≤ x_ij ≤ u_ij, where u_ij is the capacity of arc (i, j). A common modeling error is to confuse a shortest path, which selects one route, with a maximum-flow model, which can distribute flow across multiple routes.

8. An Applied Case: Regional Distribution Redesign

Background

The following is an illustrative case. Meridian Foods serves three retail regions from two plants. Management is considering whether to open a cross-docking hub, how much to ship along each route, and how to preserve service commitments while controlling logistics cost.

Problem

Plant A can supply 700 pallets weekly and Plant B 500. Regional demand is 400, 450, and 300 pallets. Direct shipping costs per pallet are:

Management also requires at least 150 pallets for Region 3 to originate at Plant B because of product specialization. A proposed hub would incur a fixed weekly cost of $1,200 and reduce selected route costs, but it would require a binary opening decision.

Analysis and approach

The direct-shipping transportation model uses x_ij as pallets from plant i to region j and minimizes total variable cost, subject to plant capacities and regional demand. Since total capacity is 1,200 and total demand is 1,150, the model may leave 50 pallets unused. The specialization requirement is represented by x_B3 ≥ 150.

The hub extension introduces y ∈ {0,1}. If x_h represents hub throughput and the hub can process at most 600 pallets, then x_h ≤ 600y. The objective becomes variable transport cost + 1,200y. If hub use changes route costs, additional flow-balance constraints connect inbound and outbound hub flows. This is a MILP because y is binary.

Before solving, analysts should verify that all costs use the same time basis, that demand is measured in comparable pallets, and that the regional minimum is a genuine requirement rather than an informal preference. They should also test scenarios for demand growth, fuel-price changes, plant disruption, and hub capacity.

Outcome and managerial interpretation

The recommended implementation should not be reported merely as a list of shipment quantities. Management needs the total cost, capacity utilization, unmet-demand status, binding constraints, marginal value of additional plant capacity, and the cost of the specialization rule. If the hub is selected only under high-demand scenarios, a staged or real-options approach may be preferable to an immediate commitment.

Learning points

1. A transportation model can identify the least-cost allocation, but policy constraints may change the structure and value of routes.
2. A fixed facility cost requires a binary variable; it cannot be represented accurately by a simple per-unit cost.
3. Shadow prices support capacity decisions, but their validity is conditional on sensitivity ranges.
4. Scenario analysis is necessary when demand and costs are uncertain.
5. A mathematically optimal plan may be operationally infeasible if labor, dock scheduling, quality, or contractual conditions were omitted.

9. Technology, Governance, and Responsible Use

Optimization is embedded in enterprise-resource-planning systems, supply-chain platforms, workforce schedulers, spreadsheet add-ins, and cloud analytics services. AI systems can assist with extracting parameters from documents, forecasting demand, proposing formulations, or detecting anomalous solutions. However, generative AI should not be treated as a proof of model correctness. Every generated formulation requires expert review, unit checks, constraint testing, and reproducible documentation.

Governance concerns include:

• Data quality: inaccurate costs or capacities produce precise but misleading recommendations.
• Fairness: workforce or credit-allocation models may disadvantage protected groups through variables or proxy effects.
• Transparency: decision makers should understand objectives, constraints, and exceptions.
• Privacy: individual-level data should be minimized, secured, and processed under applicable law.
• Auditability: versions of data, code, solver settings, and approvals should be retained.
• Human accountability: managers remain responsible for consequential decisions.

Optimization can encode values. For example, a model that minimizes cost without a service constraint may systematically sacrifice remote customers; a staffing model that minimizes labor expense may produce unsafe schedules. Ethical constraints and stakeholder impacts must therefore be considered during formulation, not appended after computation.

10. Best Practices and Limitations

Best practice begins with a clear decision statement and a documented data dictionary. Use realistic bounds, avoid unnecessary big-M values, distinguish hard constraints from soft goals, and retain units in every parameter table. Validate the model through historical back-testing, extreme-case tests, independent recalculation of objective values, and review by subject-matter experts.

Optimization has important limitations. Deterministic models treat uncertain inputs as fixed unless uncertainty is modeled explicitly. Linear relationships may omit economies of scale, congestion, learning, or nonlinear risk. A solver optimizes the stated objective, not the organization's unspoken purpose. Computational optimality also differs from practical optimality when implementation costs, managerial acceptance, or resilience matter.

Useful extensions include robust optimization for protected performance under uncertainty, stochastic programming for decisions made before uncertain outcomes are known, multi-objective optimization for explicit trade-offs, and simulation-optimization when system dynamics are difficult to represent analytically. These approaches increase realism but also require more assumptions, data, and computational governance.

Chapter Summary

Optimization and mathematical programming formalize resource-allocation decisions through decision variables, objectives, constraints, and domain restrictions. Linear programming applies when relationships are linear and variables are divisible. Feasible regions, extreme points, binding constraints, slack, and optimality provide the foundation for interpretation. Duality explains shadow prices and reduced costs, while sensitivity analysis identifies the conditional value of changing resources or objective coefficients.

Integer and mixed-integer models represent indivisible, logical, and fixed-charge decisions. Goal programming manages multiple targets through weighted or lexicographic deviations. Transportation and assignment models allocate supply and resources efficiently, while shortest-path, maximum-flow, minimum-cost-flow, and spanning-tree models address network decisions. In every application, model quality depends on valid data, appropriate assumptions, sensitivity testing, ethical governance, and managerial interpretation.

Key Terms

Decision variable: A controllable quantity determined by the model.

Objective function: Mathematical expression measuring the outcome to maximize or minimize.

Constraint: A mathematical restriction on feasible decisions.

Feasible solution: A solution satisfying all constraints and domain restrictions.

Feasible region: The set of all feasible solutions.

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

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

Surplus: Amount by which a variable exceeds a minimum requirement.

Linear programming: Optimization with linear objective and constraint expressions and continuous variables.

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

Mixed-integer linear programming: A model containing both continuous and integer variables.

Binary variable: A variable restricted to 0 or 1.

Shadow price: Local marginal value of relaxing a constraint's right-hand side.

Reduced cost: Objective-coefficient improvement required for a currently zero variable to become attractive, subject to convention.

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

Goal programming: Method for minimizing weighted or prioritized deviations from targets.

Transportation model: Network allocation model distributing supply to demand points.

Assignment model: One-to-one allocation of resources to tasks.

Network flow: Model of movement through nodes and capacity-limited arcs.

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

Review Questions

Short Answer Questions

1. What are the four essential elements of a mathematical programming model?
2. Distinguish a binding constraint from a constraint with slack.
3. What does a shadow price measure, and why is its interpretation conditional?
4. Why are binary variables useful in facility-location models?
5. State one important difference between weighted and preemptive goal programming.

Long Answer Questions

1. Explain the assumptions of linear programming and discuss a managerial situation in which each assumption might fail.
2. Describe how duality, complementary slackness, and sensitivity analysis support managerial decision making.
3. Compare continuous LP, integer programming, and mixed-integer programming, including examples of suitable applications.
4. Explain the structure and uses of transportation, assignment, and minimum-cost-flow models.
5. Discuss how ethical, governance, and data-quality issues can affect an apparently optimal model.

Analytical / Application Questions

1. A firm earns $45 per unit of Product A and $70 per unit of Product B. Each A uses 3 machine hours and 2 labor hours; each B uses 4 machine hours and 5 labor hours. Weekly availability is 240 machine hours and 200 labor hours. Formulate the LP, identify the corner-point candidates, and determine the optimal continuous product mix.
2. A service organization must meet a minimum target of 900 customer contacts and a maximum target of 40 overtime hours. Formulate a goal-programming model that gives first priority to contact underachievement and second priority to overtime excess. State which deviation variables are penalized.
3. A distribution manager observes that a solver recommends a fractional number of trucks and leaves a high-cost region underserved. Diagnose two possible modeling causes, propose appropriate constraints, and explain which sensitivity or scenario analyses should be performed.

Multiple Choice Questions with Answers

Question 1

In a linear programming model, what does a binding constraint indicate?

A. The constraint has unused capacity.

B. The constraint is satisfied with equality at the solution.

C. The constraint can be removed without changing feasibility.

D. The constraint must have a negative right-hand side.

Correct Answer: B. The constraint is satisfied with equality at the solution.

Question 2

For the product-mix example in the chapter, what is the optimal continuous solution?

A. 48 desks and 16 tables

B. 60 desks and 0 tables

C. 0 desks and 40 tables

D. 40 desks and 20 tables

Correct Answer: A. 48 desks and 16 tables

Question 3

What is the local interpretation of a shadow price for a resource constraint?

A. The average historical cost of the resource

B. The marginal objective improvement from one additional unit of resource

C. The total objective value divided by resource use

D. The fixed cost of acquiring the resource

Correct Answer: B. The marginal objective improvement from one additional unit of resource

Question 4

Which variable type is most appropriate for a facility-opening decision?

A. Unrestricted continuous variable

B. Nonnegative surplus variable

C. Binary variable

D. Shadow-price variable

Correct Answer: C. Binary variable

Question 5

In goal programming, what equation represents a target with deviation variables?

A. L_k − d_k⁻ − d_k⁺ = T_k

B. L_k + d_k⁻ − d_k⁺ = T_k

C. L_k + d_k⁻ + d_k⁺ = 0

D. L_k × d_k⁻ = T_k

Correct Answer: B. L_k + d_k⁻ − d_k⁺ = T_k

Question 6

Which algorithm is appropriate for a shortest-path problem when all arc costs are nonnegative?

A. Dijkstra's algorithm

B. Hungarian algorithm

C. Northwest-corner method

D. Branch-and-bound only

Correct Answer: A. Dijkstra's algorithm

Question 7

In a balanced transportation problem, what is generally true?

A. Total supply equals total demand.

B. Every route must be used.

C. All shipping costs must be equal.

D. All supplies and demands must be binary.

Correct Answer: A. Total supply equals total demand.

Question 8

Why is simply rounding a fractional LP solution not generally valid for an integer problem?

A. Rounding always increases the objective.

B. Rounding can violate constraints and need not produce an optimal integer solution.

C. Integer models cannot contain costs.

D. Rounding changes all coefficients to zero.

Correct Answer: B. Rounding can violate constraints and need not produce an optimal integer solution.

Question 9

What does complementary slackness imply in the usual LP interpretation?

A. Every constraint must bind.

B. A resource with positive slack generally has zero shadow price.

C. Every variable must be positive.

D. The primal objective must exceed the dual objective.

Correct Answer: B. A resource with positive slack generally has zero shadow price.

Question 10

Which statement best describes sensitivity analysis?

A. It proves that all future parameter values are known.

B. It studies how results change under parameter changes, often within local validity ranges.

C. It replaces the need to validate the model.

D. It applies only to assignment models.

Correct Answer: B. It studies how results change under parameter changes, often within local validity ranges.