Operations research Study Guide

📖 Core Concepts Operations Research (OR) – Applied‑math discipline that builds mathematical models to aid management and decision‑making. Optimal solution – The feasible decision that maximizes (or minimizes) the objective while satisfying all constraints. Decision‑making problem – Real‑world situation abstracted as variables, an objective function, and constraints. Modeling & Simulation – Use equations or computer experiments to mimic complex systems; queueing theory handles stochastic waiting lines. Optimization families Linear Programming (LP) – Linear objective + linear constraints. Integer Programming (IP) – Same as LP but some/all variables must be integers. Non‑linear Programming (NLP) – At least one nonlinear element. Dynamic Programming (DP) – Breaks a multistage problem into recursively solvable sub‑problems (principle of optimality). Stochastic models – Incorporate random variables (e.g., Markov Decision Processes) to capture uncertainty. Decision‑support tools – AHP (hierarchical criteria), decision analysis (probability‑weighted outcomes), expert systems. --- 📌 Must Remember Simplex algorithm (1947, Dantzig) solves any LP in a finite number of pivot steps. Hungarian method solves the assignment problem in \(O(n^3)\) time. Max‑flow min‑cut theorem: Maximum flow from source to sink equals capacity of the minimum cut separating them. Principle of Optimality (Bellman, 1957) – An optimal policy has the property that whatever the initial state and decision, the remaining decisions constitute an optimal policy for the resulting sub‑problem. Survivorship bias – Ignoring failed/absent cases leads to over‑optimistic conclusions (Wald). Critical path – Longest sequence of dependent tasks; determines minimum project duration. Transportation problem – Balanced supply‑demand network; solved efficiently by network simplex or stepping‑stone method. --- 🔄 Key Processes Simplex Algorithm (LP) Write problem in standard form: \[ \max \; \mathbf{c}^\top \mathbf{x}\quad \text{s.t.}\; A\mathbf{x} = \mathbf{b},\; \mathbf{x}\ge 0 \] Identify a basic feasible solution (BFS) (set of basic variables). Compute reduced costs; if all ≤ 0, current BFS is optimal. Choose entering variable (most positive reduced cost) and leaving variable (minimum ratio test). Pivot to obtain a new BFS; repeat until optimality condition holds. Hungarian Method (Assignment) Subtract row minima from each row, then column minima from each column. Cover all zeros with a minimum number of lines. If number of lines = \(n\), optimal assignment found; else adjust uncovered entries (subtract min uncovered, add to double‑covered) and repeat. Dynamic Programming (Multistage) Define stages and state variables. Write recurrence: \(Vt(s) = \min{a\in A(s)}\{c(s,a) + V{t+1}(s')\}\). Solve backwards from final stage (boundary condition). Extract optimal decisions by policy traceback. Critical Path Method (CPM) List all activities, durations, and dependencies. Perform forward pass to compute earliest start/finish times. Perform backward pass to compute latest start/finish times. Identify activities with zero slack → critical path. --- 🔍 Key Comparisons LP vs IP LP: variables continuous → solution may be fractional. IP: integer restriction → often NP‑hard; need branch‑and‑bound or cutting planes. DP vs Greedy DP: guarantees global optimum when principle of optimality holds. Greedy: makes locally best choice; can fail for problems requiring look‑ahead (e.g., knapsack). Simulation vs Analytical Model Simulation: handles complex, non‑linear, stochastic systems; yields empirical performance metrics. Analytical: closed‑form equations; faster but limited to tractable assumptions. Assignment vs Transportation Assignment: one‑to‑one matching, all supplies/demands = 1. Transportation: many‑to‑many with possibly unequal supply/demand totals. --- ⚠️ Common Misunderstandings Feasibility ≠ Optimality – A solution satisfying constraints isn’t necessarily the best; always check objective value. “Optimal” in stochastic models – Often means expected optimal; variability still exists. Survivorship bias – Ignoring missing data (e.g., only studying returned aircraft) skews results. LP solution is always integer – Only true for totally unimodular constraint matrices; otherwise rounding can violate constraints. --- 🧠 Mental Models / Intuition Water‑pipe analogy for network flow – Flow follows paths like water; the bottleneck (minimum cut) limits total throughput. “Building a staircase” for DP – Solve the top step, then work down, reusing sub‑solutions just as you’d reuse previously built stairs. “Balancing a scale” for LP – Objective pushes one side, constraints are the weight limits; the optimal point is where the push can’t move the scale any further without breaking a weight limit. --- 🚩 Exceptions & Edge Cases Degeneracy in Simplex – Multiple BFS with same objective; may cause cycling → use Bland’s rule. Non‑convex NLP – Local minima trap; need global optimization methods (branch‑and‑bound, heuristic). Integer rounding – Rounding a fractional LP solution can violate constraints; apply cutting planes or branch‑and‑bound instead. Unbalanced transportation – Add dummy source/sink with zero cost to balance supply and demand. --- 📍 When to Use Which | Situation | Recommended Method | |-----------|---------------------| | Linear objective & constraints, large‑scale | Simplex or Interior‑point LP | | Decision variables must be whole numbers (e.g., number of machines) | Integer Programming (branch‑and‑bound) | | Non‑linear objective/constraints, convex | Non‑linear Programming (KKT conditions) | | Multi‑stage decision with clear stage structure | Dynamic Programming | | Matching workers to jobs (one‑to‑one) | Hungarian Method (Assignment) | | Routing many deliveries, distance minimization | Traveling Salesman / Vehicle Routing Heuristics | | Evaluating waiting lines or service facilities | Queueing Theory or Simulation | | Uncertain demand or parameters | Stochastic Models (Markov Decision Processes, Monte Carlo) | | Complex hierarchical criteria (e.g., cost vs. safety) | Analytic Hierarchy Process (AHP) | --- 👀 Patterns to Recognize Zero‑slack activities → likely on the critical path. All‑positive reduced costs → LP solution already optimal. Tight constraints (binding) → often the “bottleneck” resources. Cyclic dependencies in project networks → indicate invalid schedule (need to break cycles). Sparse constraint matrix → favorable for network simplex or specialized algorithms. --- 🗂️ Exam Traps Choosing “maximization” vs “minimization” – A question may state “minimize cost” but the LP formulation is written as a maximization; watch the sign. Confusing feasible region with optimal point – Distractors often present a feasible solution that looks “nice” but isn’t the best objective value. Assuming LP solution is integer – If the matrix isn’t totally unimodular, fractional solutions are normal; an integer answer is a trap. Misreading the direction of a cut in max‑flow problems – The min‑cut capacity equals max flow only when source‑sink partition is correctly identified. Over‑applying DP – Some problems violate the principle of optimality (e.g., path‑dependent costs); greedy or other methods may be required. Survivorship bias example – Selecting only successful case studies and ignoring failures leads to overly optimistic conclusions. ---