Optimization and Operations Research

Introduction

Managerial decisions frequently involve allocating scarce resources among competing uses. A hospital must schedule operating theatres, a manufacturer must determine a product mix, a logistics firm must route shipments, and a service organization must decide how much capacity to provide. Optimization and operations research provide systematic methods for making such decisions.

Operations research (OR) applies mathematical models, data, and analytical reasoning to complex decisions. Optimization identifies the best feasible solution according to a specified objective, such as minimizing cost, maximizing contribution, reducing waiting time, or improving service reliability. The quality of an optimization result depends not only on the algorithm but also on the formulation: an inaccurate objective, omitted constraint, or unrealistic assumption can produce a mathematically optimal but managerial poor decision.

This chapter develops linear programming, integer programming, nonlinear programming, sensitivity analysis, duality, transportation and assignment models, inventory models, queuing models, network models, and project scheduling. Emphasis is placed on formulation, interpretation, implementation, and limitations.

Learning Objectives

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

1. Formulate managerial problems as optimization models.
2. Solve and interpret linear programming models using graphical, simplex, and software-based methods.
3. Explain integer and nonlinear programming and select suitable methods.
4. Interpret shadow prices, reduced costs, and sensitivity ranges.
5. Apply transportation, assignment, inventory, queuing, network, and project-scheduling models.
6. Evaluate assumptions, ethical implications, and implementation risks.

1. The Operations-Research Modelling Process

A disciplined OR study normally follows these stages:

1. Problem definition: identify the decision, decision maker, scope, and performance measure.
2. Data specification: collect costs, capacities, demand, processing times, probabilities, and resource requirements.
3. Model formulation: define decision variables, objective function, constraints, and domains.
4. Solution: apply an exact algorithm, heuristic, simulation, or hybrid method.
5. Validation: test whether the model represents the real system adequately.
6. Sensitivity and scenario analysis: assess the effect of uncertain data and assumptions.
7. Implementation and control: communicate the recommendation, monitor outcomes, and update the model.

A model is a simplified representation of reality. It is useful when simplification removes irrelevant detail without removing decision-critical relationships.

2. Linear Programming

2.1 Structure of a linear programme

A linear programming (LP) model has a linear objective, linear constraints, and non-negative or otherwise specified decision variables. Its general maximization form is:

subject to

Here, x_j is the quantity of activity j, c_j is its contribution to the objective, a_ij is the amount of resource i used by one unit of activity j, and b_i is the available amount of resource i. The objective value is Z. Coefficients must be dimensionally consistent: for example, a profit per unit multiplied by units produces monetary profit, while resource-use coefficients multiplied by units produce resource quantities.

Constraints may also be equalities or greater-than constraints. A minimization problem can be converted to an equivalent maximization problem, but software does not require manual conversion.

2.2 Formulation example

A firm produces desks and cabinets. Each desk contributes $80 and each cabinet $60. A desk uses 4 hours of carpentry and 2 hours of finishing. A cabinet uses 3 hours of carpentry and 1 hour of finishing. Weekly availability is 240 carpentry hours and 100 finishing hours.

Let x₁ = desks produced and x₂ = cabinets produced. The model is:

subject to

The objective and constraints express a choice among feasible production plans. The model does not assume that all available resources must be used; unused capacity is allowed unless an equality or other condition requires full utilization.

2.3 Graphical solution and corner-point principle

For two variables, each constraint can be plotted. The feasible region is the intersection of all constraint half-planes and the non-negativity region. A fundamental LP result is the corner-point principle: if an LP has an optimal solution and the feasible region is non-empty and bounded in the relevant direction, at least one optimum occurs at an extreme point (corner) of the feasible region.

For the example, the key intercepts are:

• Carpentry: x₁ = 60 when x₂ = 0, and x₂ = 80 when x₁ = 0.
• Finishing: x₁ = 50 when x₂ = 0, and x₂ = 100 when x₁ = 0.

The two resource boundaries intersect by solving:

From the second equation, x₂ = 100 - 2x₁. Substitution gives 4x₁ + 3(100 - 2x₁) = 240, so x₁ = 30 and x₂ = 40. The feasible corner points are (0,0), (50,0), (30,40), and (0,80). Objective values are respectively $0, $4,000, $4,800, and $4,800. Thus there are multiple optimal solutions: both (30,40) and (0,80) are optimal, as is every feasible point on the line segment between them. This is an example of alternate optima.

2.4 Simplex method and software

The simplex method moves from one basic feasible solution to an adjacent one, improving the objective until no improving adjacent solution exists. Slack variables convert a less-than constraint into an equality; for example:

where s₁ is unused carpentry capacity. Modern solvers use revised simplex, interior-point, branch-and-bound, and presolve procedures. A manager need not perform tableaus manually, but should understand formulation, solver status, feasibility, optimality, and interpretation.

Important outcomes include:

• Infeasible: no solution satisfies all constraints.
• Unbounded: the objective can improve indefinitely under the stated model.
• Optimal: a best feasible solution has been identified.
• Multiple optima: more than one solution has the same best objective value.

3. Integer and Mixed-Integer Programming

LP permits fractional values. This is inappropriate when variables represent indivisible items, such as aircraft, projects, employees, vehicles, or facility openings. Integer programming requires selected variables to take integer values:

A binary variable satisfies y_k ∈ {0,1}, where 1 means that an action is selected and 0 means it is not. A fixed-charge decision can be modelled by:

where x is activity level, y is a binary activation variable, and M is a valid upper bound on x. If y = 0, then x = 0; if y = 1, activity can occur up to M. A value of M that is excessively large weakens computation, so it should be based on defensible bounds.

Common logical constraints include:

• If project A is selected, project B must also be selected: y_A ≤ y_B.
• Exactly one option is selected: ∑ y_j = 1.
• At most one option is selected: ∑ y_j ≤ 1.

Mixed-integer programming (MIP) combines continuous and integer variables. Branch-and-bound solves a continuous relaxation, branches on fractional variables, and uses bounds to eliminate subproblems. The reported optimality gap measures the difference between the best known feasible solution and the best bound; a small gap may be acceptable when exact proof is computationally expensive.

4. Nonlinear Optimization

Nonlinear programming (NLP) contains nonlinear objective functions or constraints. A general constrained problem is:

where x is the vector of decision variables. Nonlinearity may represent economies of scale, congestion, risk, diminishing returns, or physical relationships.

For an unconstrained differentiable problem, a necessary first-order condition for an interior local optimum is:

A sufficient condition for a global minimum is that f is convex over a convex feasible set. For a twice-differentiable function, a positive semidefinite Hessian is a standard test for convexity, although global analysis may require domain knowledge.

For constrained problems, the Lagrangian is:

where λ_i and μ_k are multipliers. The Karush–Kuhn–Tucker conditions provide necessary conditions under suitable constraint qualifications and become sufficient for convex optimization. NLP methods include gradient methods, sequential quadratic programming, and interior-point methods. Nonconvex models may have several local optima; a solver's local solution is not automatically globally optimal.

5. Sensitivity Analysis and Duality

An optimization result is a recommendation, not a permanent truth. Sensitivity analysis examines how the solution changes when coefficients, capacities, or requirements change.

5.1 Shadow prices

The shadow price of a resource constraint is the marginal change in the optimal objective value from increasing the right-hand side by one unit, within the allowable sensitivity range and with all other data fixed. For a maximization model with resource i, it is commonly denoted y_i. If y_i = 25, one additional unit of the resource is worth $25 at the margin, provided the change remains within the relevant range.

A nonbinding constraint has positive slack. Under standard LP assumptions, its shadow price is zero because a small increase in an already unused resource does not improve the objective. A binding constraint may have a zero or positive shadow price, depending on the model.

5.2 Reduced costs and ranges

The reduced cost of a variable currently at zero indicates how much its objective coefficient must improve, in the appropriate direction, before it can enter an optimal basis. Allowable increase and decrease ranges describe changes for which the current basis remains optimal; they do not guarantee that the same production quantities remain unchanged in every interpretation.

The dual of a primal LP provides economically interpretable resource valuations. For the primal maximization model with ≤ constraints and non-negative variables, a corresponding dual is:

Weak duality states that every feasible dual objective is at least as large as every feasible primal maximization objective. Strong duality states that, when both have finite optima, their optimal objective values are equal. Complementary slackness links unused resources with zero dual values and positive activity with tight corresponding dual inequalities.

Sensitivity analysis becomes unreliable when several coefficients change simultaneously, when integer variables are present, or when uncertainty is substantial. Re-solving scenarios is then preferable.

6. Transportation and Assignment Models

6.1 Transportation model

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

subject to

In a balanced model, total supply equals total demand and inequalities may be equalities. If totals differ, a dummy origin or destination can represent surplus or unmet demand, with carefully chosen penalty costs. Feasible initial solutions can be generated by the northwest-corner, least-cost, or Vogel approximation methods; optimality can be tested by MODI or solved directly as an LP.

6.2 Assignment model

Assignment is a special transportation problem in which each agent is assigned to exactly one task and each task receives exactly one agent. With cost c_ij and binary variable x_ij:

The Hungarian algorithm solves the balanced assignment problem efficiently. Maximization can be converted to minimization by subtracting each benefit from the largest benefit in the matrix. Prohibited assignments require a sufficiently large penalty or explicit exclusion.

7. Inventory Models

Inventory decisions balance ordering or setup cost, holding cost, stockout risk, and service expectations.

7.1 Economic order quantity

Under the basic deterministic EOQ assumptions—constant known demand, instantaneous replenishment, no shortages, constant unit price, and no quantity discounts—the annual relevant cost is:

where D is annual demand in units per year, S is ordering cost per order, H is annual holding cost per unit, and Q is order quantity. Differentiating and setting the derivative to zero gives:

The result has units of units per order. The number of orders per year is D/Q*, and cycle time is approximately Q*/D years when demand is continuous.

For example, if annual demand is 10,000 units, ordering cost is $50, and annual holding cost is $2 per unit, then:

The EOQ is a benchmark, not a universal policy. Lead time, safety stock, quantity discounts, perishability, and demand uncertainty require extensions.

7.2 Reorder point and safety stock

With constant demand rate d units per day and lead time L days, the deterministic reorder point is:

If demand during lead time is normally distributed with standard deviation σ_LT, a common service-level policy is:

where μ_LT is mean lead-time demand and z is the standard-normal quantile associated with the target cycle service level. This formula assumes an appropriate normal approximation and a specified interpretation of service level.

8. Queuing Models

Queuing theory studies congestion and waiting. A queue consists of arrivals, a waiting discipline, one or more servers, and a service process. The notation M/M/1 describes Poisson arrivals, exponentially distributed service times, and one server.

Let λ be the mean arrival rate and μ the mean service rate, both in customers per unit time. Utilization is:

For a stable M/M/1 system, λ < μ and therefore ρ < 1. Key steady-state measures are:

Here, L is the expected number in the system, L_q the expected number waiting, W the expected time in the system, and W_q the expected waiting time. Little's law links these measures generally under stable long-run conditions:

The M/M/1 formulas require the stated assumptions and long-run steady state. Real systems may have finite populations, balking, priorities, non-Poisson arrivals, or multiple servers. Increasing capacity reduces waiting but may be uneconomic; the managerial decision compares the cost of capacity with the cost of delay and lost demand.

9. Network Models

A network represents nodes connected by arcs. In a shortest-path problem, arc lengths may represent distance, time, or cost. Dijkstra's algorithm is appropriate when all arc lengths are non-negative. It repeatedly labels the unsettled node with the smallest temporary distance and permanently settles it, updating adjacent nodes.

A minimum-spanning-tree problem connects all nodes with minimum total link cost and no cycles. Kruskal's algorithm adds the least-cost edge that does not create a cycle; Prim's algorithm grows a tree from a selected node.

Maximum-flow models determine the greatest flow from a source to a sink subject to arc capacities. The max-flow/min-cut theorem states that maximum feasible flow equals the capacity of a minimum source–sink cut. Network models are useful for distribution, telecommunications, energy, emergency evacuation, and project precedence.

10. Project Scheduling: CPM and PERT

The critical path method (CPM) represents activities and precedence relationships. For each activity, forward-pass calculations determine earliest start and finish; backward-pass calculations determine latest start and finish. Total slack is:

where ES and EF are earliest start and finish, and LS and LF are latest start and finish. Activities with zero total slack form a critical path. Delaying a critical activity delays project completion unless corrective action changes the network.

PERT incorporates uncertainty using optimistic time a, most likely time m, and pessimistic time b. The expected activity time is:

The commonly used activity variance is:

The approximate project completion probability uses the critical-path mean and standard deviation, assuming activity-time independence and a reasonably valid normal approximation:

where T is the deadline, μ_P is expected critical-path duration, and σ_P is its standard deviation. If critical paths can change substantially under uncertainty, simple PERT estimates may be misleading; simulation is preferable.

11. Integrated Illustrative Case: Regional Medical Supplies Network

This is a fictional illustrative case.

Background

MedSupply operates two distribution centres and serves three hospitals. Centre A can supply 600 cases weekly and Centre B 400 cases. Hospital demand is 300, 350, and 250 cases. Unit transport costs are:

Total supply is 1,000 and demand is 900, so 100 cases are surplus. Management wants to minimize transport cost while retaining a 95% probability of avoiding stockouts. It also plans a new cross-dock project.

Problem and approach

The transportation model minimizes shipment cost. Since supply exceeds demand, a dummy destination with demand 100 and zero disposal value can absorb surplus, or a holding/disposal penalty can be assigned if surplus has an economic cost. The model should not silently force all supply to hospitals.

For inventory, each hospital's reorder point is based on lead-time demand and safety stock. If Hospital 2 has mean lead-time demand of 120 cases, standard deviation 20, and a 95% cycle service target with z ≈ 1.645, then:

The policy is to reorder when inventory position reaches approximately 153 cases, subject to review of batch sizes and perishability.

For the cross-dock, CPM identifies activities: site approval (4 weeks), design (3 weeks after approval), procurement (5 weeks after design), construction (8 weeks after approval), and commissioning (2 weeks after procurement and construction). The longest precedence path determines the baseline completion time. A manager can then evaluate whether expediting a critical activity is worth its additional cost.

Outcome and learning points

The integrated analysis separates decisions that are often confused. Transportation determines current allocation; inventory determines protection against uncertain demand and lead time; project scheduling determines future capacity. Shadow prices can indicate whether an additional distribution-centre capacity unit is more valuable than a transport contract. Scenario analysis should test demand surges, vehicle disruption, and supplier delays.

The case demonstrates that optimization is not a substitute for managerial judgment. Service equity, emergency priority, product expiry, labour agreements, and patient safety may require constraints or policies not captured by transport cost alone.

12. Governance, Ethics, Technology, and Contemporary Practice

Optimization systems influence employees, customers, patients, and communities. Ethical practice requires transparency about objectives, data sources, constraints, and trade-offs. A model that minimizes cost while systematically reducing service to remote communities may be efficient in a narrow sense but unacceptable under organizational values or public obligations.

Important governance practices include:

• document assumptions, data provenance, and model versions;
• test for discriminatory effects and service inequity;
• preserve human oversight for high-impact decisions;
• distinguish recommendations from automated actions;
• monitor model drift and unexpected outcomes;
• provide appeal and exception processes;
• protect confidential and personal data.

Contemporary OR increasingly combines mathematical optimization with forecasting, simulation, machine learning, digital twins, and real-time data. Machine-learning forecasts can supply demand estimates, while optimization converts forecasts into decisions. However, forecast error, biased historical data, adversarial conditions, and opaque models can undermine the result. A practical architecture separates prediction, optimization, simulation validation, and human governance.

13. Best Practices and Limitations

A professionally credible optimization study should:

1. Define the decision horizon and units clearly.
2. Use explicit variable definitions and traceable data.
3. Include only constraints that represent real requirements.
4. Validate extreme cases and compare with current practice.
5. Report feasibility, objective value, binding constraints, and unused capacity.
6. Conduct one-way and multi-parameter scenario analysis.
7. Quantify uncertainty rather than presenting false precision.
8. Provide implementable recommendations, not only solver output.
9. Reassess the model after operational changes.

Limitations include uncertain parameters, aggregation, linearity assumptions, behavioural responses, computational complexity, and objective-function bias. Integer models may be difficult to solve at scale; nonlinear models may have local optima; queueing formulas may poorly represent irregular operations; and project schedules may ignore resource constraints. When exact optimization is impractical, heuristics and metaheuristics can provide good solutions, but their quality should be assessed through bounds, benchmarks, repeated runs, or simulation.

Chapter Summary

Optimization and operations research support structured resource-allocation and process-design decisions. Linear programming models use linear objectives and constraints and are interpreted through feasible regions, corner points, simplex methods, and solver status. Integer and mixed-integer models represent indivisibilities and logical conditions, while nonlinear programming captures relationships such as congestion and diminishing returns.

Duality gives economic meaning to resource constraints through shadow prices, reduced costs, and complementary slackness. Sensitivity analysis identifies the consequences of changing coefficients and capacities, although re-solving is necessary when changes are large or integer decisions are involved. Transportation and assignment models allocate supply and tasks efficiently. EOQ and reorder-point models balance inventory costs and service protection. Queuing models quantify congestion, and network algorithms solve shortest-path, spanning-tree, and flow problems. CPM and PERT support project planning under deterministic and uncertain activity times.

Effective OR is both technical and managerial. Formulation quality, data validity, uncertainty analysis, ethical governance, human oversight, and implementation discipline determine whether a mathematically elegant solution produces responsible organizational value.

Key Terms

Operations research: Analytical discipline that supports decisions using models, data, and systematic reasoning.

Optimization: Selection of the best feasible alternative according to an objective.

Decision variable: Unknown controllable quantity determined by a model.

Objective function: Mathematical expression representing the criterion to maximize or minimize.

Constraint: Requirement or limitation restricting feasible decisions.

Feasible solution: A decision satisfying all model constraints.

Linear programming: Optimization with linear objective and constraint expressions.

Integer programming: Optimization requiring some or all variables to be integers.

Binary variable: Variable restricted to 0 or 1.

Nonlinear programming: Optimization containing nonlinear objectives or constraints.

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

Reduced cost: Objective-coefficient improvement needed for a nonbasic variable to become attractive.

Duality: Relationship between a primal optimization model and its resource-valuation dual.

Transportation model: Network allocation model distributing supply to destinations.

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

Economic order quantity: Order size minimizing basic ordering and holding costs.

Utilization: Fraction of service capacity occupied, commonly ρ = λ/μ.

Critical path: Longest-duration precedence path determining project completion.

Slack: Permissible delay without changing a specified schedule outcome.

Review Questions

Short Answer Questions

1. What are the four essential components of a linear programming model?
2. Why are binary variables useful in managerial decision models?
3. Define a shadow price and state its usual interpretation.
4. What assumptions underlie the basic EOQ formula?
5. What does utilization mean in an M/M/1 queue?

Long Answer Questions

1. Explain the operations-research modelling process from problem definition through implementation and control.
2. Formulate and discuss a product-mix LP, including the interpretation of binding and nonbinding constraints.
3. Compare linear, integer, and nonlinear programming in terms of representation, solution methods, and managerial use.
4. Explain primal–dual relationships, strong duality, shadow prices, and reduced costs.
5. Compare CPM and PERT and discuss when simulation should replace simple PERT calculations.

Analytical / Application Questions

1. A firm has two products, limited labour and machine hours, and fixed costs for opening a production line. Formulate a mixed-integer model and identify at least two logical constraints.
2. A service centre has arrival rate 18 customers per hour and service rate 24 customers per hour. Calculate utilization, expected number in the system, and expected time in the system using the M/M/1 formulas. Interpret the result and state the model assumptions.
3. A retailer faces uncertain demand, variable lead time, and a high stockout cost. Recommend an inventory policy, identify the data required, and explain how sensitivity or simulation could test the recommendation.

Multiple Choice Questions with Answers

Question 1

Which condition is required for a steady-state M/M/1 queue?

A. λ > μ

B. λ = μ

C. λ < μ

D. λ = 0

Correct Answer: C. λ < μ

Question 2

In a minimization transportation model, what does xᵢⱼ represent?

A. The cost of opening origin i

B. Units shipped from origin i to destination j

C. Demand at origin i

D. Unused capacity at destination j

Correct Answer: B. Units shipped from origin i to destination j

Question 3

If annual demand is 10,000 units, ordering cost is $50, and annual holding cost is $2 per unit, the basic EOQ is approximately:

A. 50 units

B. 224 units

C. 500 units

D. 707 units

Correct Answer: D. 707 units

Question 4

A binary variable is most directly used to represent:

A. A continuously varying quantity

B. A yes-or-no decision

C. A normally distributed error

D. A resource's unit cost

Correct Answer: B. A yes-or-no decision

Question 5

For a maximization LP, a positive shadow price for a resource generally means that:

A. The resource has unused capacity only

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

C. The model is infeasible

D. The resource must be eliminated

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

Question 6

Which algorithm is appropriate for a shortest-path problem when all arc lengths are non-negative?

A. Dijkstra's algorithm

B. Hungarian algorithm

C. Northwest-corner method

D. EOQ algorithm

Correct Answer: A. Dijkstra's algorithm

Question 7

In the basic EOQ model, increasing annual holding cost while other parameters remain fixed will:

A. Increase optimal order quantity

B. Decrease optimal order quantity

C. Have no effect on order quantity

D. Make demand zero

Correct Answer: B. Decrease optimal order quantity

Question 8

In CPM, activities on the critical path generally have:

A. Maximum positive slack

B. Zero total slack

C. Zero duration necessarily

D. No precedence relationships

Correct Answer: B. Zero total slack

Question 9

For an M/M/1 queue with λ = 18 per hour and μ = 24 per hour, utilization is:

A. 0.25

B. 0.50

C. 0.75

D. 1.33

Correct Answer: C. 0.75

Question 10

The assignment model normally requires that:

A. Every agent receives every task

B. Each agent and each task participates in exactly one assignment

C. All costs must be equal

D. Variables must be unrestricted negative values

Correct Answer: B. Each agent and each task participates in exactly one assignment