Operations Research: Optimization, Queueing, and Decision Models

Operations research improves decisions in systems constrained by limited time, money, capacity, and information. It supports routing, scheduling, inventory, staffing, logistics, energy systems, and public services. The discipline combines mathematical models with data and operational knowledge, recognizing that an optimal answer to the wrong model can be harmful. This chapter introduces linear and integer optimization, network flows, queueing, simulation, and decision analysis. The Python laboratory solves small search and queueing examples.

All mathematical expressions appear only in standalone display blocks.

1. Modeling Decisions

An optimization model specifies decision variables, an objective, constraints, and input data. A simple linear program is:

subject to:

The objective may represent cost, delay, emissions, risk, or a weighted combination. Constraints represent physical capacities, policy rules, balance equations, and service requirements. Before solving, modelers should ask whether every critical constraint is represented and whether the objective embeds an acceptable tradeoff.

2. Linear Programming and Duality

Linear programs have a feasible region that is a convex polyhedron. When an optimum exists, a solution can be found at an extreme point. The simplex method moves between candidate vertices; interior-point methods move through the feasible interior.

The dual of a resource-allocation model assigns values to constraints. In a generic form:

subject to:

Dual variables are often interpreted as shadow prices: the marginal change in optimum objective value from relaxing a resource constraint, within a local valid range. A shadow price is not necessarily a market price and can change when the active constraint set changes.

3. Integer and Combinatorial Optimization

Some decisions are indivisible. A facility is built or not; a route is selected or not; a nurse is scheduled on a shift or not. Integer programming introduces conditions such as:

These models can express rich practical choices but are often computationally difficult. Branch-and-bound uses relaxations to rule out regions of the search space. Cutting planes add valid constraints. Heuristics can find useful solutions quickly, though their optimality gap should be reported when possible.

The traveling salesperson problem asks for a shortest cycle visiting each node once. It is a classic example where simple local improvements can work well but may miss the global optimum.

4. Network Models

Networks represent locations as nodes and movement or relationships as arcs. In a minimum-cost flow model, each arc has flow x sub i j and cost c sub i j. Conservation at node i requires:

Positive b sub i denotes supply and negative b sub i denotes demand. Network structure allows specialized efficient algorithms for shortest paths, maximum flow, matching, and transportation.

The maximum-flow minimum-cut theorem links the largest possible source-to-sink flow with the smallest capacity that disconnects source from sink. It has applications in logistics, communication, image segmentation, and assignment.

5. Queueing and Capacity

A queue forms when demand temporarily exceeds service capacity. Important quantities are arrival rate lambda, service rate mu, utilization rho, waiting time, and queue length. In a stable single-server model:

Little's law is remarkably general:

Average number in system L equals throughput times average time in system W. It applies to customers, jobs, packets, patients, and work items when averages are well-defined.

For an idealized M/M/1 queue:

As utilization approaches one, delays grow nonlinearly. This is why systems designed for near-total average utilization can be fragile under ordinary variability.

6. Simulation and Uncertainty

Simulation imitates system operation when analytic formulas are unavailable or simplifying assumptions are unacceptable. Discrete-event simulation advances from event to event, such as arrivals, service completions, and machine failures. It is useful for hospitals, ports, supply chains, and manufacturing lines.

Random-output simulations require replications, warm-up treatment, variance estimates, and sensitivity analysis. A precise simulation estimate can still be wrong if demand distributions, staffing behavior, or routing rules are modeled poorly.

Scenario analysis asks how decisions perform under plausible futures. Robust optimization explicitly seeks solutions that remain acceptable across uncertainty sets. The correct approach depends on whether probability estimates are credible and how severe downside outcomes are.

7. Implementation and Ethics

Decision models can allocate scarce resources and therefore embed consequential values. A dispatch model that minimizes average travel time may systematically underserve remote communities. A scheduling model that maximizes utilization may impose unsafe workloads. Model governance should include stakeholder input, auditability, override procedures, monitoring for distributional effects, and periodic revalidation.

An implementation plan needs data pipelines, operational ownership, exception handling, and feedback from frontline users. A mathematically sound model that cannot be maintained or trusted will not improve the real system.

8. Python Laboratory

from itertools import permutations

def best_route(costs, start=0):
    nodes = [node for node in range(len(costs)) if node != start]
    best_cost, best_path = float("inf"), None
    for order in permutations(nodes):
        path = (start,) + order + (start,)
        cost = sum(costs[path[index]][path[index + 1]] for index in range(len(path) - 1))
        if cost < best_cost:
            best_cost, best_path = cost, path
    return best_cost, best_path

def mm1_wait(arrival_rate, service_rate):
    if arrival_rate >= service_rate:
        raise ValueError("queue is unstable when arrival rate reaches service rate")
    return 1 / (service_rate - arrival_rate)

if __name__ == "__main__":
    matrix = [[0, 4, 6, 7], [4, 0, 3, 5], [6, 3, 0, 2], [7, 5, 2, 0]]
    print("best route:", best_route(matrix))
    print("M/M/1 time in system:", round(mm1_wait(8, 10), 2))

9. Summary

Operations research makes tradeoffs explicit. Optimization identifies efficient choices under stated assumptions, queueing reveals the cost of variability and saturation, and simulation explores dynamics too complex for closed-form analysis. The durable value comes from matching the model to the operating reality and evaluating who benefits, who bears risk, and what happens when conditions change.