Book summary “Introduction to operations research”: summary

Introduction

You face complex decisions every day when allocating scarce resources across competing organizational activities. Modern systems involve countless variables, conflicting objectives, and high uncertainty that overwhelm human intuition. Operations research combines scientific methods, mathematical modeling, and analytics to optimize these choices.

Frederick S. Hillier presents a comprehensive framework for solving large-scale organizational problems through rigorous quantitative analysis. You will trace the historical roots of the discipline from military planning to contemporary big data environments. The text details foundational optimization techniques, linear programming, network models, and advanced probabilistic systems.

• How do you formulate real-world challenges into mathematical models?
• What algorithms compute optimal solutions for resource allocation?
• How do you account for risk, uncertainty, and dynamic change?

1. Overview of Operations Research and Analytics

As organizations grew larger and more specialized after the industrial revolution, components developed autonomous goals working at cross purposes, making resource allocation difficult. British and U.S. military services recruited scientists to conduct research on operations, leading to successes in the Air Battle of Britain using radar, winning the Battle of the North Atlantic through convoy management, and assisting the Island Campaign.

Operations research emerged from World War II military planning and evolved into a comprehensive decision science that coordinates organizational activities using interdisciplinary teams.

Origins and Nature of Operations Research

Operations research abstracts the essence of real problems into mathematical models, tests hypotheses via model validation, and searches for optimal solutions. Because problems span diverse aspects of an organization, full-scale OR studies require a team with collective training in fields such as mathematics, statistics, data science, economics, business administration, computer science, and engineering.

Operations research teams developed effective methods for using radar to win the Air Battle of Britain and managed convoy and antisubmarine operations to win the Battle of the North Atlantic.

The Nine Phases of an OR Study

Properly defining the problem is a crucial first step because you advise management and must align objectives with the broader goals of the entire organization. Practical problems are initially vague. You must identify the true decision maker, determine precise objectives and constraints, and avoid suboptimization where a solution benefits only one component of the organization at the expense of the whole.

Mathematical models abstract the essence of a problem into quantitative expressions. They provide concise structures, reveal cause-and-effect relationships, and bridge the gap to high-powered computer algorithms. Postoptimality analysis and sensitivity analysis evaluate how optimal solutions change when model parameters are varied under different assumptions.

A full-fledged operations research study follows a sequence of nine overlapping phases ranging from problem definition to final implementation:

• Define the problem of interest.
• Gather and organize relevant data.
• Use descriptive analytics to analyze big data.
• Use predictive analytics to analyze big data.
• Formulate a mathematical model to begin applying prescriptive analytics.
• Learn how to derive solutions from the model.
• Test the model.
• Prepare to apply the model.
• Implementation.

2. Linear Programming Foundations and Applications

Linear programming is a mathematical modeling technique designed to find the optimal allocation of limited resources among competing activities. You use linear functions to describe problems where decision variables represent activity levels. The objective is to maximize or minimize a performance measure subject to resource and operational constraints.

Linear programming models rely strictly on the foundational assumptions of proportionality, additivity, divisibility, and certainty.

Proportionality ensures the contribution of each activity is directly proportional to its level. Additivity requires that total contribution equals the sum of individual activities. Divisibility permits fractional values for decision variables, and certainty assumes parameters are known constants.

Wyndor Glass Co. produces new windows and glass doors across three plants, seeking the optimal production rates to maximize total weekly profit. Product 1 profit is 3 thousand dollars per batch, product 2 profit is 5 thousand dollars per batch, and plant 3 available hours are 18 hours per week.

Assumptions and Graphical Solutions

Problems with two decision variables can be solved graphically by identifying the feasible region and evaluating corner-point feasible solutions. You can apply this method directly to your own models by following these exact steps:

• Construct a two-dimensional graph with decision variables as axes
• Draw boundary lines for each restriction and identify the first quadrant nonnegativity area
• Determine the feasible region containing all permissible values
• Move a ruler with fixed objective function slope through the feasible region in the direction of improving performance
• Stop at the last point passing through the feasible region to identify the optimal solution

Mary's radiation therapy problem is solved graphically using two beams to minimize healthy tissue damage while meeting tumor dosage requirements. The optimal radiation dosage is 7.5 kilorads for beam 1 and 4.5 kilorads for beam 2, giving an objective function value of Z equals 5.25.

Spreadsheet software such as Excel and its Solver tool provide an accessible platform for formulating and solving small linear programming models. Formulations use designated changing cells for decision variables, output cells with formulas like SUMPRODUCT for constraints, and an objective cell targeted for maximization or minimization. You configure Excel Solver by specifying the objective cell, changing cells, and functional constraints with appropriate inequality signs, then select the Simplex LP solving method and ensure non-negativity is enabled before solving.

Applications across Industry

Large-scale linear programming models with thousands of variables and constraints require specialized mathematical modeling languages rather than manual algebraic entry. Worldwide Corporation utilizes a model with 10 plants, 10 machines, 10 products, and 10 months, resulting in 21,000 decision variables and 3,100 functional constraints formulated compactly in MPL.

Swift & Company developed an integrated system of 45 linear programming models to schedule beef-fabrication operations, realizing 12.74 million dollars in the first year. Swift & Company annual sales exceed 8 billion dollars, and their first-year audited benefits totaled 12.74 million dollars.

Automobile Alliance manufactures vehicles in three families at a plant outside Detroit, MI, assembling the Family Thrillseeker and the Classy Cruiser. Rachel Rosencrantz determines optimal monthly production quantities by balancing unit profits against total labor-hour capacities, scarce door components, and maximum demand limits. Family Thrillseeker profit is 3,600 dollars, Classy Cruiser profit is 5,400 dollars, monthly plant capacity is 48,000 labor-hours, and total available doors equal 20,000 units.

3. The Simplex Method and Duality Theory

Linear programming problems are solved efficiently through an algebraic and geometric procedure developed by George Dantzig in 1947. You move systematically along the edges of the feasible region from one corner-point solution to an adjacent one until no improving adjacent solution exists.

The simplex method solves linear programming problems by moving algebraically and geometrically between adjacent corner-point feasible solutions.

The Wyndor Glass Co. problem is solved by moving from (0, 0) to (0, 6) and then to the optimal solution (2, 6) in just three iterations, yielding Z = 36.

To execute this iterative process, you follow specific procedural steps:

• Choose an initial CPF solution
• Perform an optimality test to check if adjacent solutions are better
• Determine the direction of movement along an edge
• Determine where to stop at the first new constraint boundary
• Solve for the intersection of the new constraint boundaries

Nonstandard linear programming models containing equality or greater-than-or-equal-to constraints require artificial variables to generate an initial basic feasible solution. Mary's radiation therapy problem incorporates equality and greater-than-or-equal-to constraints, necessitating artificial variables and yielding an optimal value of Z = 5.25.

You prepare these models for the simplex method by applying concrete adjustments:

• Convert equality constraints or greater-than-or-equal-to constraints using artificial variables
• Replace variables without lower bounds with the difference of two non-negative variables
• Convert minimization problems to maximization by multiplying the objective function by minus one

Duality Theory and Sensitivity Analysis

Every linear programming primal problem has a corresponding dual problem that uses the exact same parameters arranged in transposed locations. The original problem is the primal problem in maximization form, and its counterpart is the dual problem in minimization form.

Every linear programming primal problem has a corresponding dual problem whose optimal values provide economic interpretations and shadow prices.

In the Wyndor Glass Co. final iteration, the primal solution yields Z = 36 and the dual solution yields W = 36 with matching objective values.

Postoptimality analysis evaluates optimal solutions through reoptimization, shadow prices, and sensitivity analysis to test parameter robustness. For the Wyndor Glass Co. problem, the shadow price for Plant 2 production time is 1.5, meaning each additional hour increases total profit by $1,500. Annual sales revenue captured by Samsung Electronics reached $200 million after reducing cycle times using linear programming.

You evaluate model parameters using structured postoptimality steps:

• Identify shadow prices from the coefficients of slack variables in row 0 of the final tableau
• Generate sensitivity reports using spreadsheet solvers to check allowable ranges for objective coefficients and right-hand sides
• Use reoptimization techniques when model parameters change slightly

4. Specialized Linear Programming and Network Optimization

Specialized algorithms streamline transportation, assignment, and network flow problems, while network optimization models govern project management and distribution.

Transportation and Assignment Problems

The transportation problem aims to minimize the total distribution cost of a commodity from multiple sources to multiple destinations while satisfying fixed supplies and demands. It relies on the requirements assumption, where each source has a fixed supply and each destination has a fixed demand, and the cost assumption, which states that distribution costs are directly proportional to the number of units distributed. It requires total supply to equal total demand for feasible solutions to exist.

The P & T Company transports canned peas from three canneries in Bellingham, Eugene, and Albert Lea to four distributing warehouses in Sacramento, Salt Lake City, Rapid City, and Albuquerque, involving 300 total truckloads to be shipped.

The transportation simplex method is a streamlined version of the general simplex method that exploits the special structure of constraint coefficients to eliminate almost the entire simplex tableau. It bypasses artificial variables, calculates dual variable values directly from basic variables to test optimality, and identifies a single chain reaction to determine the entering and leaving basic variables. Every basic solution of a transportation problem contains $m + n - 1$ basic variables.

You construct an initial basic feasible solution using these steps:

• Construct an initial basic feasible solution using a method like the northwest corner rule.
• Derive $u_i$ and $v_j$ by setting $u_i = 0$ for the row with the most allocations and solving $c_{ij} = u_i + v_j$ for basic variables.
• Check if $c_{ij} - u_i - v_j \ge 0$ for all nonbasic variables to test optimality.
• Select the nonbasic variable with the most negative value as the entering basic variable.
• Identify the chain reaction to maintain feasibility and select the donor cell with the smallest value as the leaving basic variable.
• Add the leaving variable's value to recipient cells and subtract it from donor cells to find the new basic feasible solution.

The assignment problem is a special type of transportation problem where assignees are assigned to perform tasks on a one-to-one basis. It assumes the number of assignees equals the number of tasks, each assignee performs exactly one task, and each task is performed by one assignee. Decision variables are binary, taking values of 0 or 1.

Job Shop Company assigns three new machines of different types to four available locations to minimize materials-handling costs, with an optimal machine assignment total cost of $29 per hour.

Network Models and PERT/CPM Scheduling

Network optimization models solve specialized structural problems including shortest paths, maximum flows, and minimum cost flows. Networks comprise nodes, arcs, and directed or undirected paths. Specialized algorithms such as the augmenting path algorithm and the network simplex method efficiently compute optimal flows without invoking the full general simplex method.

Seervada Park is the prototype example used for shortest-path, maximum flow, and minimum spanning tree problems.

Project management techniques like PERT/CPM identify critical paths to optimize total project duration and evaluate potential cost savings from schedule crashing. Network optimization allows calculation of total project duration and identification of critical sequences of tasks, enabling planners to reduce schedules and save specific amounts in project costs.

In problem 10.8-3, the critical path is Start to A to C to E to Finish with a total duration of 12 weeks, and a crashing schedule saves $7,834.

5. Integer Programming and Nonlinear Optimization

Integer programming models incorporate yes/no or discrete decision variables using branch-and-bound and cutting-plane techniques.

You can solve problems where variables are restricted to integers or binary values. California Manufacturing Company is used as the binary integer programming prototype example with 10 million dollars total capital available.

Integer Programming Applications

Binary integer programming problems use 0-1 variables to represent choices. You can handle mutually exclusive alternatives or contingent decisions.

California Manufacturing Co. evaluated building factories in Los Angeles or San Francisco and contingent warehouses using binary variables. The branch-and-bound technique divides a problem into subproblems using a branching tree and fathoms unpromising subsets using LP relaxation bounds.

You apply these steps for binary integer programming:

• Set Z* to minus infinity for maximization initialization.
• Select the most recently created unfathomed subproblem for branching.
• Fix the next variable at 0 or 1 to create two new subproblems.
• Solve the LP relaxation of each new subproblem and round down noninteger Z to obtain the bound.
• Apply fathoming tests and discard subproblems whose bound is less than or equal to Z*.
• Stop when no unfathomed subproblems remain, confirming the current incumbent is optimal.

The California Manufacturing Co. prototype example was solved in four iterations to reach an optimal objective value of 14 million dollars. Constraint programming combines domain reduction, constraint propagation, and global constraints to simplify modeling. An assignment problem with 100 tasks formulated with traditional integer programming requires 10,000 variables and 200 constraints, whereas a constraint programming model requires only 200 variables and 101 constraints.

Nonlinear Programming and Metaheuristics

Nonlinear programming deals with optimization problems where either the objective function or the constraint functions are nonlinear.

Portfolio selection models use nonlinear programming to optimize the trade-off between expected return and risk. Bank Hapoalim used the Opti-Money System decision-support system during 133,000 consultation sessions for 63,000 customers, leading to annual earnings over benchmarks totaling approximately US$244 million and adding over US$31 million to the bank's annual income during the first year.

Simulated annealing mimics physical annealing by accepting nonimproving moves with a probability controlled by a decreasing temperature parameter. United Parcel Service developed the ORION system based on simulated annealing to instantaneously determine delivery van routes, saving the company approximately $350 million annually while managing 55,000 drivers and 1,400 package delivery centers.

6. Probabilistic Models, Queueing, and Inventory Theory

Probabilistic models evaluate stochastic systems under uncertainty, utilizing queueing theory for waiting lines and inventory theory for optimal stock control.

Queueing models describe calling populations, queue disciplines, service times, and arrival rates. Key variations include M/M/s models, finite queue variations, and priority-discipline queueing models. County Hospital and Bank One Corporation are referenced in queueing theory applications. Little's formula establishes fundamental relationships such as $L = \lambda W$ and $L_q = \lambda W_q$.

You can design queueing systems effectively by balancing service capacity costs against customer or internal waiting costs.

• Establish criteria for acceptable waiting levels or assess waiting costs associated with lost productivity.
• Formulate total expected cost as $E(TC) = C_s s + C_w L$.
• Calculate $E(TC)$ for consecutive values of server count $s$ until costs start increasing.

The Acme Machine Shop case used a mean arrival rate $\lambda = 120$ and service rate $\mu = 80$ customers per hour. Clerk cost $C_s = \$20$ per hour and mechanic waiting cost $C_w = \$48$ per hour yielded an optimal configuration using 3 clerks. General Motors used a complex queueing model based on single-server building blocks to optimize production line throughput across plants, yielding over $2.1 billion in documented savings and revenue.

Decision Analysis and Inventory Control

Decision analysis provides a structured framework for choosing actions when outcomes are uncertain and affected by external random factors. The decision maker selects an alternative from a feasible set, while nature chooses a state of nature in a random fashion.

The Goferbroke Company considers drilling for oil or selling its land for $90,000, facing states of nature where the land contains oil or is dry. Bayes' decision rule selects the alternative that maximizes the expected value of the payoff using the best available probability estimates. You can apply this rule using explicit computational steps.

• Calculate the expected value of the payoff for each of the possible decision alternatives using the best available estimates of probabilities.
• Choose the decision alternative with the maximum expected payoff.

Scientific inventory management balances ordering costs and holding costs using economic order quantity and continuous-review models. Deterministic and stochastic continuous-review models determine optimal order quantities $Q$ and reorder points $R$. Kroger Co. and Hewlett-Packard are cited in inventory and supply chain application vignettes.

You can determine optimal batch inventory policies by following specific quantitative steps.

• Choose a management service level $L$.
• Calculate the order quantity $Q$ using the standard EOQ formula.
• Solve for the reorder point $R$ such that the probability of demand during lead time being less than or equal to $R$ equals $L$.

A television manufacturer produces speakers in batches with a setup cost of $\$12,000$, a holding cost of $\$0.30$ per speaker per month, and a demand rate of $8,000$ speakers per month, yielding an optimal batch size of $25,298$ speakers.

7. Markov Decision Processes and Simulation

Markov decision processes optimize multi-stage dynamic systems over time, while computer simulation and variance-reducing techniques imitate complex stochastic operations.

Markov Decision Processes

Markov decision processes allow you to choose actions for each possible state of a Markov chain to optimize long-term performance. Instead of accepting a fixed transition matrix, you introduce decision epochs where an action is chosen from a set of alternatives. This choice affects immediate costs, rewards, and subsequent transition probabilities while maintaining the Markovian property.

A manufacturer classifies a core machine's condition after weekly inspections into one of four states, ranging from operating normal to inoperable. Replacement incurs a total cost of $\$6,000$, consisting of $\$2,000$ in lost production and $\$4,000$ in replacement expenses.

You can efficiently find optimal policies using linear programming by treating randomized policy variables as continuous steady-state probabilities.

• Define decision variables $y_{ik}$ as the steady-state unconditional probability of being in state $i$ and making decision $k$.
• Set up the linear programming objective function to minimize long-run expected average cost.
• Include constraints for probability sums, steady-state balance equations, and non-negativity.
• Solve using the simplex method to derive the optimal deterministic policy.

Applying this linear program yields the optimal policy of doing nothing in states 0 and 1, overhauling in state 2, and replacing in state 3, resulting in an expected average cost of $\$1,667$ per week. Alternatively, you can use the policy improvement algorithm, which alternates between value determination and policy improvement steps until two successive iterations yield identical policies.

Simulation Studies and Variance Reduction

Simulation uses a computer to imitate the operation of stochastic systems over time by generating random events and tracking system performance. You synthesize system components component by component using probability distributions.

• A definition of the state of the system.
• Identify the possible states of the system that can occur.
• Identify the possible events that would change the state of the system.
• A provision for a simulation clock that will record the passage of simulated time.
• A method for randomly generating the events of the various kinds.
• A formula for identifying state transitions that are generated by the various kinds of events.

Crude Monte Carlo simulation can be made vastly more efficient through specialized variance-reducing techniques that decrease estimator variance. Stratified sampling divides a probability distribution into distinct strata and samples critical portions disproportionately heavily to reduce estimator variance.

• Divide the distribution into portions called strata.
• Sample each stratum individually with disproportionately heavy sampling of more critical strata.
• Convert uniform random numbers to the indicated range for the cumulative distribution function.
• Divide the observations from each stratum by its sampling weight before taking the average.

10 Key Ideas

1. Operations research combines scientific methods, mathematical modeling, and analytics to optimize complex organizational choices.
2. Operations research emerged from World War II military planning and evolved into a comprehensive decision science that coordinates organizational activities using interdisciplinary teams.
3. Linear programming models rely strictly on the foundational assumptions of proportionality, additivity, divisibility, and certainty.
4. The simplex method solves linear programming problems by moving algebraically and geometrically between adjacent corner-point feasible solutions.
5. Every linear programming primal problem has a corresponding dual problem whose optimal values provide economic interpretations and shadow prices.
6. Specialized algorithms streamline transportation, assignment, and network flow problems, while network optimization models govern project management and distribution.
7. Integer programming models incorporate yes/no or discrete decision variables using branch-and-bound and cutting-plane techniques.
8. Nonlinear programming deals with optimization problems where either the objective function or the constraint functions are nonlinear.
9. Probabilistic models evaluate stochastic systems under uncertainty, utilizing queueing theory for waiting lines and inventory theory for optimal stock control.
10. Markov decision processes optimize multi-stage dynamic systems over time, while computer simulation and variance-reducing techniques imitate complex stochastic operations.