Operations Research and Decision Models

Introduction and Context

Industrial engineering concerns the design and improvement of systems that transform materials, information, energy, and human effort into useful products and services. These systems are constrained by limited machines, labor, capital, time, space, and information. Operations research (OR) provides a disciplined way to represent such systems mathematically and identify good, or demonstrably optimal, decisions.

An OR model is a purposeful abstraction. It does not reproduce every feature of reality; it retains features relevant to a decision. A useful model must therefore be mathematically valid, operationally interpretable, and supported by credible data. Optimization is not a substitute for engineering judgment: an optimal solution to an inappropriate model is still a poor decision.

This chapter develops linear programming, integer programming, transportation and assignment models, network optimization, dynamic programming, queuing models, decision analysis, sensitivity analysis, and the use of optimization software. Applications include production planning, machine loading, workforce allocation, logistics, maintenance, project scheduling, and service-system design.

Learning Objectives

After studying this chapter, you should be able to:

1. Formulate objective functions, decision variables, constraints, and parameters for industrial decisions.
2. Solve and interpret linear, integer, transportation, assignment, and network models.
3. Explain dynamic programming and queuing models and identify their assumptions.
4. Evaluate decisions under certainty, risk, and uncertainty.
5. Interpret shadow prices, reduced costs, ranges of optimality, and ranges of feasibility.
6. Use optimization software responsibly, including model validation and sensitivity analysis.
7. Recognize ethical, practical, and data-governance limitations of quantitative decisions.

1. The Operations-Research Modeling Cycle

A robust OR study generally follows this cycle:

1. Problem definition: Specify the decision, system boundary, time horizon, stakeholders, and performance measures.
2. Data collection: Estimate capacities, costs, processing times, demand, probabilities, and quality requirements.
3. Model formulation: Define variables, objective(s), constraints, parameters, and units.
4. Solution: Apply an analytical method or solver.
5. Validation: Test logic, units, extreme cases, historical fit, and operational feasibility.
6. Sensitivity and scenario analysis: Examine how results change when assumptions change.
7. Implementation and control: Assign responsibility, monitor actual performance, and update the model.

A model should distinguish controllable decisions from uncontrollable parameters. For example, production quantities may be decisions, whereas demand and available hours are parameters. A model should also identify hard constraints, which cannot be violated, and soft constraints, which may be violated at a penalty.

A common linear optimization form is:

Here, xⱼ is the level of decision activity j; cⱼ is its contribution to the objective; aᵢⱼ is the amount of resource i used by one unit of activity j; and bᵢ is the availability or requirement of resource i. The coefficients must be dimensionally consistent. If cⱼ is dollars per unit and xⱼ is units, the objective is dollars; if aᵢⱼ is machine-hours per unit and bᵢ is machine-hours, the corresponding constraint is dimensionally valid.

2. Linear Programming

2.1 Assumptions

Linear programming (LP) assumes:

• Proportionality: Resource use and contribution change directly with activity level.
• Additivity: Total resource use is the sum of individual uses; interactions are excluded unless explicitly modeled.
• Divisibility: Decision variables may take fractional values.
• Certainty: Coefficients are treated as known for the modeled period.
• Nonnegativity: Negative production, shipment, or labor levels are normally impossible.

These assumptions are reasonable for many aggregate planning and blending decisions, but not for setup-dependent production, indivisible projects, nonlinear yields, or uncertain demand without additional modeling.

2.2 Formulation example

A machine shop makes standard and precision housings. Profit is $40 per standard housing and $60 per precision housing. Each standard unit uses 2 machining hours and 1 finishing hour; each precision unit uses 3 machining hours and 2 finishing hours. Weekly capacities are 120 machining hours and 70 finishing hours. Let x₁ and x₂ denote weekly production.

The continuous LP has corner-point solutions. The intercepts are (60, 0) and (0, 35). Solving the two binding constraints,

gives x₂ = 20 and x₁ = 30. Profit at (30, 20) is $2,400. Profit at (60, 0) is $2,400 and at (0, 35) is $2,100. Thus, there are multiple optimal solutions along the relevant boundary between (60, 0) and (30, 20), because the objective slope is parallel to that boundary. A solver may report one endpoint or any feasible point on the optimal segment. This example illustrates that an LP optimum need not be unique.

2.3 Solution methods and interpretation

The graphical method is useful only for two decision variables. The simplex method moves between basic feasible solutions, or vertices, and improves the objective until no improving adjacent solution exists. Interior-point methods are important for large sparse models. Modern commercial and open-source solvers also support presolve, scaling, decomposition, and mixed-integer algorithms.

Important LP outputs include:

• Slack: Unused amount of a ≤ constraint.
• Surplus: Amount by which a ≥ constraint exceeds its minimum.
• Shadow price (dual value): Marginal change in the optimal objective for a one-unit increase in a constraint’s right-hand side, within the reported validity range.
• Reduced cost: For a variable at zero in a maximization model, the unfavorable objective-coefficient change required before it can enter an optimal basis, subject to solver sign conventions.

A shadow price is not automatically the market price of a resource. It is a local marginal value and is valid only while the basis and other assumptions remain appropriate. If an additional machine hour costs less than its positive shadow price, acquiring it may improve profit, provided the change remains within the allowable range and practical conditions are unchanged.

3. Integer and Mixed-Integer Programming

Integer programming (IP) requires some or all variables to be integers. It is essential when fractional decisions are meaningless, such as the number of machines, operators, trucks, projects, or setup decisions. A binary variable yⱼ takes value 1 if an action occurs and 0 otherwise.

A mixed-integer linear program (MILP) may be written as:

Typical logical constraints include:

• If project A requires project B: x_A ≤ Mx_B, where M is a valid upper bound.
• If exactly one of two alternatives is selected: y₁ + y₂ = 1.
• If at most three facilities are opened: ∑yⱼ ≤ 3.
• Fixed setup cost: objective includes −fⱼyⱼ and production variable xⱼ is linked by xⱼ ≤ Uyⱼ.

The big-M method must use the smallest valid bound M that preserves feasibility. An unnecessarily large M can create numerical instability and weak relaxations.

MILP solvers commonly use branch-and-bound or branch-and-cut. The LP relaxation, obtained by temporarily ignoring integrality, supplies bounds. A solver’s optimality gap measures the difference between the best feasible integer solution and the best bound; a small gap supports a defensible near-optimality claim. A feasible solution is not necessarily optimal merely because a solver stopped at a time limit.

4. Transportation and Assignment Models

4.1 Transportation model

Suppose sources i = 1,…,m supply products to destinations j = 1,…,n. Let xᵢⱼ be the quantity shipped from source i to destination j and cᵢⱼ its unit shipping cost. With supply sᵢ and demand dⱼ:

The balanced case has ∑sᵢ = ∑dⱼ. If supply exceeds demand, add a dummy destination; if demand exceeds supply, add a dummy source. Dummy costs must represent the economic consequence of unused supply or unmet demand, not automatically zero cost.

A basic feasible transportation solution has at most m + n − 1 positive basic allocations, unless degeneracy occurs. The northwest-corner method constructs a feasible starting solution, while the least-cost and Vogel approximation methods often provide better starts. Optimality can be tested using the MODI or u–v method, and large models can be solved directly as LPs.

4.2 Assignment model

Assignment is a special case in which each agent is assigned to exactly one task and each task receives exactly one agent. Let xᵢⱼ = 1 if agent i performs task j, otherwise 0:

The Hungarian algorithm solves the square assignment problem efficiently. A rectangular problem can be balanced with dummy rows or columns. Prohibited assignments should be represented by a carefully chosen large penalty or explicit restrictions; an arbitrary huge number can cause numerical problems.

5. Network Models

Network models represent nodes and arcs. Nodes may be plants, warehouses, machines, or project events; arcs may represent shipments, routes, precedence relationships, or communication links.

Important models include:

• Shortest path: Minimize total distance, time, or cost from an origin to a destination.
• Minimum spanning tree: Connect all nodes at minimum total cost without cycles; useful for infrastructure design.
• Maximum flow: Maximize flow through a capacitated network.
• Minimum-cost flow: Meet supplies and demands at minimum arc cost.
• Critical path: Determine the longest-duration path through a project network; its activities determine minimum project duration under fixed activity times.

For a flow model, conservation at an intermediate node k is typically:

The left side is inflow minus outflow, and the equation applies when node k has neither external supply nor demand. At a source or sink, the right-hand side represents net supply or demand. Network structure often permits specialized algorithms that are faster and more transparent than general-purpose LP methods.

6. Dynamic Programming

Dynamic programming (DP) solves multistage problems by decomposing them into stages and states. The principle of optimality states that, for an appropriate state definition, an optimal policy has the property that whatever the initial state and first decision, the remaining decisions must be optimal for the resulting state.

The general backward recursion is:

Here, Fₜ(s) is the best value from stage t onward when the system is in state s; a is a feasible action; gₜ is immediate cost or reward; Tₜ is the state-transition function; and the terminal value is specified at the final stage. The recursion is valid only when the state contains all information needed to evaluate future decisions; omitting relevant history violates the principle of optimality.

Applications include equipment replacement, inventory control, lot sizing, knapsack selection, and shortest paths. DP can suffer from the curse of dimensionality: the number of states grows rapidly as state variables increase. Approximate dynamic programming and reinforcement-learning methods address some large-state problems but require careful validation and may sacrifice guarantees.

7. Queuing Models

Queuing theory analyzes waiting systems with arrivals, service facilities, queues, and a service discipline such as first-come, first-served. Important performance measures include arrival rate λ, service rate μ per server, expected number in the system L, expected number waiting L_q, time in the system W, and waiting time W_q.

For a stable single-server M/M/1 queue, arrivals are Poisson, service times are exponential, one server operates, and λ < μ. Utilization is ρ = λ/μ, and:

Little’s law applies under broad steady-state conditions:

Units must agree: if λ is customers per hour, W is hours and L is customers. As ρ approaches 1, waiting measures increase sharply. Stability is not the same as good service; a system can be mathematically stable but operationally unacceptable.

For an M/M/c system with c identical servers, stability requires λ < cμ. Exact waiting probabilities use the Erlang-C formulation. Since assumptions about arrival independence, service distributions, finite capacity, and customer behavior are often imperfect, simulation or empirical analysis may be preferable.

8. Decision Analysis Under Certainty, Risk, and Uncertainty

Under certainty, each alternative has a known consequence. Under risk, states of nature have estimated probabilities. Under uncertainty, probabilities are unavailable, disputed, or inappropriate.

A payoff table lists alternatives, states, probabilities, and consequences. Under risk, expected monetary value (EMV) is:

where pⱼ is the probability of state j and v(a,j) is the payoff of alternative a under that state. Choose the alternative with the highest EMV for a risk-neutral decision maker, while recognizing that EMV does not describe risk dispersion or ethical acceptability.

For a cost table, choose the minimum expected cost. Expected opportunity loss is the expected regret relative to the best action in each state. The expected value of perfect information is:

EVPI is nonnegative and sets an upper bound on what perfect information is worth. The expected value of sample information accounts for imperfect information and cannot exceed EVPI.

When probabilities are unavailable, common criteria include:

• Maximax: Choose the alternative with the largest possible payoff; optimistic.
• Maximin: Choose the alternative with the best worst-case payoff; conservative.
• Minimax regret: Minimize the largest regret.
• Laplace: Treat states as equally likely when no probability basis is preferred.
• Hurwicz: Use a weighted combination of best and worst outcomes, with an explicitly stated optimism coefficient.

These are decision philosophies, not universally correct answers. A decision tree is useful when decisions occur sequentially and later information can change the action. Chance nodes show uncertain states; decision nodes show controllable choices. Tree branches must be mutually exclusive and collectively exhaustive.

9. Sensitivity and Scenario Analysis

Sensitivity analysis tests how an optimal solution responds to changes in coefficients, resource availability, demand, or probabilities. One-at-a-time analysis is simple but may miss interactions. Scenario analysis changes a coherent set of assumptions, such as a recession scenario or a supply disruption.

For an LP, the range of optimality describes objective-coefficient changes for which the current basis remains optimal. The range of feasibility describes right-hand-side changes for which the current shadow prices remain valid. These ranges do not guarantee that the same physical plan remains attractive outside them, and simultaneous changes can invalidate separate interpretations.

Useful robustness questions include:

• Does the recommendation remain feasible if capacity falls by 10%?
• How much must demand or price change before another plan becomes preferable?
• Which parameter has the greatest influence on the objective?
• Is the solution highly concentrated in one supplier, machine, or assumption?

When uncertainty is substantial, stochastic programming, robust optimization, simulation, or real-options analysis may be more appropriate than a deterministic LP.

10. Software, Implementation, and Governance

Optimization software separates the model from the solution algorithm. Spreadsheet solvers are convenient for small models; algebraic modeling languages and Python-based tools are useful for larger or repeatable studies; commercial MILP solvers are effective for difficult industrial models. A defensible workflow includes:

1. Document variable definitions, units, objective direction, and every constraint.
2. Build a small test instance with a known answer.
3. Check infeasibility diagnostics and inspect binding constraints.
4. Compare solver output with independent calculations or bounds.
5. Record solver version, data date, tolerances, termination status, and optimality gap.
6. Perform sensitivity, scenario, and implementation checks.

Artificial infeasibility may result from inconsistent data, overly restrictive constraints, incorrect signs, or incompatible units. Solver “optimal” status means optimal for the encoded model, not necessarily for the real system.

AI and predictive analytics can improve demand forecasts, maintenance probabilities, and parameter estimation, but predicted values should not be treated as facts. Governance should address data quality, privacy, cybersecurity, explainability, bias, human oversight, and accountability. An allocation model that systematically disadvantages a protected group may be technically optimal yet ethically and legally unacceptable. Constraints can be added for safety, service equity, labor agreements, emissions, and regulatory compliance, but their effects should be made visible rather than hidden in arbitrary penalties.

11. Illustrative Case: Machine Allocation and Delivery Network

Background

The following is a fictional illustrative case. A manufacturer produces two components at Plant A and Plant B and supplies two assembly centers. Component demand is known for the planning week. Each plant has limited machining hours, and shipping costs differ by route.

Problem

Management must decide production quantities and shipments while minimizing machining and transportation cost. A proposed model has products p, plants i, and destinations j. Let xᵢp be production of product p at plant i and yᵢⱼp be shipments from plant i to destination j. Let cᵢp be unit production cost, tᵢⱼp shipping cost, hᵢp machining hours per unit, Hᵢ available hours, and dⱼp destination demand.

If production must occur in whole batches or a plant must be opened, binary variables and linking constraints convert the model to a MILP.

Analysis and approach

The engineering team first verifies that demand units, machining-hour units, and monetary units are consistent. It then solves the LP, examines capacity shadow prices, and tests a 15% demand-increase scenario. The base solution uses the lower-cost plant until its machining capacity becomes binding, then routes remaining demand through the next-lowest total-cost option. The demand scenario reveals that Plant A capacity has a high marginal value, but expanding it requires a capital expenditure greater than the modeled short-run savings. A second scenario adds a supplier-disruption constraint and changes the recommended allocation.

Outcome and learning points

The model does not merely produce shipment quantities; it identifies bottleneck capacity, the economic value of expansion, and the vulnerability of the plan to disruption. Managers combine these results with maintenance windows, quality qualification, labor rules, and customer-service commitments before implementation. The principal lesson is that optimization is a decision-support process: formulation, validation, interpretation, and governance are as important as the solver’s numerical output.

Challenges and Limitations

OR models can create false precision when input data are uncertain. Linear costs may ignore quantity discounts, congestion, learning, setups, and nonlinear quality effects. Integer models can be computationally difficult. Queue formulas may fail when arrivals are bursty or customers abandon the queue. Expected-value decisions can undervalue catastrophic low-probability outcomes. Models can also encourage local optimization: reducing transport cost may increase inventory, emissions, or stockout risk elsewhere.

Best practice is to make assumptions explicit, use ranges rather than unsupported point estimates, involve domain experts, test extreme cases, and monitor outcomes after implementation. Safety-critical or high-impact decisions require human review and a documented escalation path.

Chapter Summary

Operations research converts industrial decisions into structured mathematical models. Linear programming is appropriate when relationships are proportional, additive, divisible, and sufficiently certain. Integer and mixed-integer programming represent indivisible choices, logical conditions, setups, and facility decisions. Transportation and assignment models specialize flow and one-to-one allocation; network models exploit nodes, arcs, capacities, and conservation. Dynamic programming decomposes multistage decisions through states and transitions. Queuing theory quantifies congestion, while Little’s law links average inventory, throughput, and time. Decision analysis compares alternatives under certainty, risk, and uncertainty using payoff tables, EMV, regret, and decision trees. Sensitivity analysis identifies robustness and the value of scarce resources. Software improves computational capability, but model validation, data governance, ethics, and managerial judgment remain essential.

Key Terms

Operations research: Systematic use of mathematical and analytical methods to support decisions.

Decision variable: A controllable quantity selected by the model.

Parameter: A fixed or estimated input to a model.

Linear programming: Optimization with linear objective and constraint relationships.

Feasible solution: A solution satisfying every model constraint.

Shadow price: Marginal objective value of relaxing a constraint within a valid range.

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

Integer programming: Optimization requiring selected variables to be integers.

Binary variable: Variable restricted to 0 or 1.

Mixed-integer linear program: Linear model containing continuous and integer variables.

Transportation model: Minimum-cost flow model from sources to destinations.

Assignment model: One-to-one allocation model.

Network model: Model composed of nodes and arcs representing flows or relationships.

Dynamic programming: Multistage optimization based on states and recursive value functions.

Queuing theory: Study of waiting systems and congestion.

Utilization: Fraction of service capacity demanded, commonly ρ = λ/μ for one server.

Little’s law: Relationship L = λW between average number, throughput, and time.

Expected monetary value: Probability-weighted average payoff.

Sensitivity analysis: Study of solution changes under parameter changes.

Optimality gap: Difference between a feasible integer solution and a bound on the best possible solution.

Review Questions

Short Answer Questions

1. State the proportionality, additivity, divisibility, and certainty assumptions of linear programming.
2. Distinguish a shadow price from a reduced cost.
3. Why are binary variables useful in industrial models?
4. State Little’s law and define its variables.
5. What is the difference between decision-making under risk and under uncertainty?

Long Answer Questions

1. Formulate a production-planning LP and explain the meaning and units of every term.
2. Compare transportation, assignment, and general network models, including one application of each.
3. Explain branch-and-bound for mixed-integer programming and discuss the meaning of an optimality gap.
4. Describe the modeling cycle from problem definition through implementation and control.
5. Explain how shadow prices, ranges of optimality, and ranges of feasibility support capacity decisions.

Analytical / Application Questions

1. A service center receives 18 customers per hour and one server can serve 24 per hour. Assuming an M/M/1 model, calculate ρ, L, L_q, W, and W_q. Interpret the result and discuss whether the assumptions are credible.
2. A firm has three alternatives with payoffs under three states: A = (80, 30, −20), B = (55, 45, 10), and C = (120, 5, −60). Determine the choice under maximax and maximin criteria, and explain why the choices differ.
3. Design a MILP for selecting up to two warehouses, assigning each customer to one open warehouse, and including fixed opening costs. State the variables, objective, key constraints, and at least one data-validation check.

Multiple Choice Questions with Answers

Question 1

Which assumption allows a linear programming variable to take a fractional value?

A. Additivity

B. Divisibility

C. Certainty

D. Nonnegativity

Correct Answer: B. Divisibility

Question 2

In a maximization LP, a positive shadow price for a capacity constraint generally indicates that:

A. The constraint is irrelevant

B. An additional unit of capacity may improve the objective within its valid range

C. The resource must be eliminated

D. The current solution is infeasible

Correct Answer: B. An additional unit of capacity may improve the objective within its valid range

Question 3

Which variable type is most appropriate for representing whether a machine is opened?

A. Continuous variable

B. Integer variable with no upper bound

C. Binary variable

D. Slack variable

Correct Answer: C. Binary variable

Question 4

A balanced transportation problem has:

A. Equal unit shipping costs

B. Equal numbers of sources and destinations

C. Total supply equal to total demand

D. Zero transportation cost

Correct Answer: C. Total supply equal to total demand

Question 5

For a stable M/M/1 queue with λ = 8 customers/hour and μ = 10 customers/hour, utilization ρ equals:

A. 0.20

B. 0.80

C. 1.25

D. 18

Correct Answer: B. 0.80

Question 6

Using Little’s law, if the average arrival rate is 5 jobs per hour and the average time in the system is 2 hours, the average number in the system is:

A. 0.4 jobs

B. 2.5 jobs

C. 7 jobs

D. 10 jobs

Correct Answer: D. 10 jobs

Question 7

Which decision criterion chooses the alternative with the best worst-case payoff?

A. Maximax

B. Maximin

C. Laplace

D. Expected monetary value

Correct Answer: B. Maximin

Question 8

The principle of optimality is fundamental to:

A. Dynamic programming

B. The northwest-corner method

C. The Hungarian algorithm only

D. Little’s law

Correct Answer: A. Dynamic programming

Question 9

An MILP solver stops with a feasible solution and a nonzero optimality gap because of a time limit. The correct interpretation is that:

A. The solution is necessarily infeasible

B. The solution is proven optimal

C. The solution is feasible but optimality is not proven to the stated gap

D. All integer restrictions were ignored

Correct Answer: C. The solution is feasible but optimality is not proven to the stated gap

Question 10

The expected value of perfect information is best described as:

A. The cost of obtaining any forecast

B. The value difference between perfect-information decisions and the best current expected decision

C. The largest possible payoff in a payoff table

D. The average regret under uncertainty

Correct Answer: B. The value difference between perfect-information decisions and the best current expected decision