flowchart LR F[Formulate] --> M[Model] M --> S[Solve] S --> T[Test] T --> C[Control] C --> I[Implement] I -. feedback .-> F style F fill:#E3F2FD,stroke:#1565C0 style I fill:#E8F5E9,stroke:#2E7D32
79 Operations Research
79.1 What is Operations Research?
Operations Research (OR) — also called Management Science — is the discipline of applying advanced analytical methods to help make better decisions. The Indian standard text by Hamdy Taha defines OR as “a scientific approach to decision-making that seeks to determine how best to design and operate a system, usually under conditions requiring the allocation of scarce resources” (taha2017?).
TipThree Working Definitions
| Source | Definition | What it foregrounds |
|---|---|---|
| Operational Research Society (UK) | “The application of scientific methods to complex problems arising in the direction and management of large systems.” | Scientific method |
| Hamdy Taha | “A scientific approach to decision-making that determines how best to design and operate a system under scarce resources.” | Optimisation |
| Hillier & Lieberman | “OR adopts the team approach to applied scientific method to a wide variety of problems.” | Multidisciplinary |
79.1.1 Origin
OR emerged during World War II — British military teams tackled radar deployment, U-boat hunting and bomber routing using mathematical and statistical methods. Post-war it spread to industry through pioneers like George Dantzig (linear programming, 1947) and Russell Ackoff.
79.2 OR Methodology — Six Steps
TipSix Steps in an OR Study
| # | Step |
|---|---|
| 1 | Formulate the problem |
| 2 | Construct a mathematical model |
| 3 | Solve the model |
| 4 | Test the model and solution |
| 5 | Establish controls |
| 6 | Implement the solution |
79.3 Linear Programming (LP)
Linear Programming is a mathematical technique for optimising a linear objective subject to linear constraints. The standard form:
\[\text{Maximise (or minimise) } Z = c_1 x_1 + c_2 x_2 + \dots + c_n x_n\]
subject to:
\[a_{11} x_1 + a_{12} x_2 + \dots \leq b_1\] \[a_{21} x_1 + a_{22} x_2 + \dots \leq b_2\] \[\dots\] \[x_1, x_2, \dots \geq 0\]
George Dantzig’s Simplex method (1947) is the foundational algorithm for solving LP problems (dantzig1963?). Modern alternatives include the interior-point method (Karmarkar, 1984).
TipFive Assumptions of LP
| Assumption | What it requires |
|---|---|
| Linearity | All relationships are linear |
| Certainty | All coefficients are known with certainty |
| Divisibility | Variables can take fractional values |
| Non-negativity | Variables ≥ 0 |
| Additivity | Total = sum of individual contributions |
TipCommon LP Solution Methods
| Method | Use |
|---|---|
| Graphical method | Two-variable problems |
| Simplex method | Multi-variable; most-used |
| Big-M method | LP with mixed constraints |
| Two-phase method | LP with artificial variables |
| Revised Simplex | Computational efficiency |
| Interior-point methods | Large-scale problems |
79.4 Special LP Problems
79.4.1 Transportation Problem
The transportation problem finds the least-cost shipment plan from m sources (factories) to n destinations (warehouses) given supply, demand and unit costs.
TipMethods for Transportation Problems
| Method | Description |
|---|---|
| North-West Corner | Initial feasible solution; not optimal |
| Least-Cost Method | Lower-cost cells first |
| Vogel’s Approximation Method (VAM) | Penalty-based; usually closest to optimum |
| MODI / Stepping-stone | Test optimality of an initial solution |
79.4.2 Assignment Problem
A special case of transportation where each source supplies one unit and each destination demands one unit — solved by the Hungarian method (Kuhn, 1955).
79.4.3 Other Special LP Variants
TipOther LP Variants
| Variant | Description |
|---|---|
| Integer programming | Variables must be integers |
| Mixed integer programming | Some integer, some continuous |
| Goal programming | Multiple objectives |
| Dynamic programming | Sequential decisions over stages (Bellman) |
| Non-linear programming | Non-linear objective or constraints |
| Stochastic programming | Random parameters |
79.5 Game Theory
John von Neumann and Oskar Morgenstern’s Theory of Games and Economic Behavior (1944) launched game theory — the study of strategic decisions where outcomes depend on the choices of multiple decision-makers (vonneumann1944?). John Nash extended it with the Nash equilibrium (1950).
TipKey Game-Theory Concepts
| Concept | What it captures |
|---|---|
| Player | Decision-maker |
| Strategy | Plan of action |
| Pay-off | Outcome of a strategy combination |
| Zero-sum game | One’s gain = other’s loss |
| Non-zero-sum game | Joint gains / losses possible |
| Pure strategy | Single best strategy |
| Mixed strategy | Probability distribution over strategies |
| Saddle point | Maximin = Minimax |
| Nash equilibrium | No player can gain by changing alone |
| Dominant strategy | Always best regardless of other’s choice |
| Prisoner’s dilemma | Cooperate-defect game with non-cooperative equilibrium |
79.6 Queueing / Waiting-Line Theory
Agner Krarup Erlang’s work for the Copenhagen Telephone Company (1909) launched queueing theory — the study of waiting lines (erlang1909?). Common notation: M/M/1 (Markov arrivals, Markov service, single server).
TipCommon Queueing Models
| Model | Description |
|---|---|
| M/M/1 | Single server, Poisson arrivals, exponential service |
| M/M/c | Multiple servers |
| M/M/1/K | Single server, finite capacity K |
| M/G/1 | General service-time distribution |
| Tandem queues | Multiple stages |
79.7 Decision Theory
TipDecision-Making Conditions
| Condition | Tools |
|---|---|
| Certainty | LP, transportation, assignment |
| Risk | Expected Monetary Value (EMV), decision trees |
| Uncertainty | Maximax, Maximin, Laplace, Hurwicz, Savage minimax-regret |
| Conflict | Game theory |
The five classical uncertainty criteria — already met in topic 4 — are tools when probabilities cannot be assigned.
79.8 Other OR Techniques
TipOther Operations-Research Techniques
| Technique | Use |
|---|---|
| PERT / CPM | Project scheduling |
| Inventory models | EOQ, ROP, safety stock |
| Markov analysis | State transitions over time |
| Replacement models | When to replace equipment |
| Simulation (Monte Carlo) | Complex stochastic systems |
| Network flows | Maximum flow, shortest path |
| Sequencing | Johnson’s rule |
| Heuristics and Metaheuristics | Genetic algorithms, simulated annealing |
79.9 OR in the Modern Era
Modern OR is increasingly merged with prescriptive analytics in data science:
TipModern OR Trends
| Trend | What it captures |
|---|---|
| Prescriptive analytics | Combine descriptive + predictive + optimisation |
| AI / ML augmentation | Reinforcement learning for decisions; Operations Research + ML |
| Software | CPLEX, Gurobi, AMPL, GAMS, Excel Solver, Python (PuLP, OR-Tools, Pyomo) |
| Optimisation under uncertainty | Robust and stochastic optimisation |
| Real-time / Edge optimisation | Routing, scheduling on the fly |
79.10 Practice Questions
Q 01
Definition
Easy
Operations Research is best described as:
View solution
Correct Option: B
OR = scientific decision-making using mathematical and statistical models. Originated in WWII military operations.
Q 02
Simplex
Medium
The Simplex method for solving linear programming problems was developed by:
View solution
Correct Option: A
George Dantzig developed the Simplex method in 1947. Karmarkar later (1984) developed the interior-point method.
Q 03
Transportation
Medium
Vogel's Approximation Method (VAM) is used to obtain:
View solution
Correct Option: B
VAM uses penalty differences to give an initial feasible solution that is usually close to optimal. MODI / Stepping-stone tests optimality.
Q 04
Game Theory
Medium
Game theory was launched as a formal discipline by:
View solution
Correct Option: B
von Neumann and Morgenstern's 1944 Theory of Games and Economic Behavior. Nash extended it with the equilibrium concept (1950, Nobel 1994).
Q 05
Queueing
Medium
In Kendall notation, "M/M/1" denotes a queue with:
View solution
Correct Option: A
M/M/1: Poisson (Markov) arrivals, exponential (Markov) service, 1 server.
Q 06
LP Assumptions
Medium
Which is NOT an assumption of linear programming?
View solution
Correct Option: C
LP assumes certainty — coefficients are known with certainty. Stochastic optimisation is a separate technique.
Q 07
Bellman
Medium
"Dynamic programming" — for sequential decisions over stages — was developed by:
View solution
Correct Option: B
Richard Bellman (1950s) — dynamic programming and the Bellman equation.
Q 08
Decision Theory
Medium
For decisions under uncertainty (probabilities unknown), which criterion is the optimist's choice?
View solution
Correct Option: B
Maximax — choose the option whose best outcome is best (optimist). Maximin = pessimist; Laplace = equal probabilities; Savage = minimax regret.
ImportantQuick recall
- OR = scientific decision-making using math models. Born in WWII; standard texts: Taha, Hillier-Lieberman.
- Six-step methodology: Formulate → Model → Solve → Test → Control → Implement.
- LP maximises/minimises a linear objective subject to linear constraints. Five assumptions: linearity, certainty, divisibility, non-negativity, additivity.
- Dantzig’s Simplex method (1947); Karmarkar’s interior-point (1984).
- Special LPs: transportation, assignment (Hungarian), integer, goal, dynamic, non-linear, stochastic.
- Transportation methods: NW Corner, Least Cost, VAM; MODI / Stepping Stone for optimality.
- Game Theory (von Neumann & Morgenstern 1944; Nash 1950): zero-sum, mixed strategies, saddle point, Nash equilibrium, prisoner’s dilemma.
- Queueing (Erlang 1909): M/M/1 notation.
- Other OR: PERT/CPM, inventory, Markov, replacement, simulation, network flows, sequencing, heuristics.
- Modern: prescriptive analytics, AI/ML, software (CPLEX, Gurobi, Python OR-Tools).