80  Operations Research

80.1 Concept

Operations Research (OR) = the application of advanced analytical methods — mathematical modelling, statistics, optimisation — to help make better decisions. OR was born in WWII Britain (1937) for military problems (radar deployment, convoy sizing). Pioneers: P.M.S. Blackett (Britain), George Dantzig (Simplex 1947), L.V. Kantorovich (Linear programming 1939, Nobel 1975), Herbert Simon (decision theory).

80.2 Phases of an OR Study (Wagner / Taha)

TipOR study phases
  1. Define the problem and objectives.
  2. Construct the model — mathematical formulation.
  3. Solve the model — algorithm.
  4. Test the model — validation.
  5. Implement the solution.
  6. Maintenance — control and update.

80.3 Types of Models

TipOR model types
  • By structure: Iconic · Analog · Mathematical · Simulation.
  • By certainty: Deterministic · Stochastic.
  • By behaviour: Static · Dynamic.
  • By method: Analytical · Heuristic · Simulation.

80.4 Linear Programming (LP)

Linear Programming (LP) — optimise a linear objective subject to linear constraints. George Dantzig invented the Simplex Method (1947). L.V. Kantorovich (1939) independently developed LP in USSR; Nobel 1975 with Koopmans.

80.4.1 LP Formulation

\[\text{Max/Min } Z = c_1 x_1 + c_2 x_2 + ... + c_n x_n\]

subject to constraints and non-negativity (xᵢ ≥ 0).

80.4.2 LP Methods

TipLP solution methods
  • Graphical (2 variables).
  • Simplex Method (Dantzig).
  • Two-Phase / Big M (for ≥ constraints).
  • Revised Simplex.
  • Dual Simplex.
  • Interior-point methods (Karmarkar 1984).
  • Modern solvers: CPLEX, Gurobi, LINDO, Excel Solver.

80.5 Duality and Sensitivity Analysis

TipDuality

Every LP has a dual. - Primal max ↔︎ Dual min. - Shadow prices — value of additional unit of resource. - Sensitivity analysis — range of c, b.

80.6 Transportation Problem

TipTransportation

Move from m sources to n destinations minimising cost. - Initial solutions: North-West Corner · Least Cost · Vogel’s Approximation Method (VAM). - Optimality: MODI / U-V Method · Stepping Stone. - Balanced vs unbalanced problems.

80.7 Assignment Problem

TipAssignment problem

Assign n jobs to n machines (or workers) 1-to-1. - Hungarian Method (Kuhn 1955) — based on König’s theorem. - Solves in polynomial time.

80.8 Game Theory

TipGame theory
  • John von Neumann & Oskar Morgenstern (1944) — Theory of Games and Economic Behavior.
  • John Nash — Nash equilibrium (1950); Nobel 1994.
  • Zero-sum vs non-zero-sum.
  • Pure vs mixed strategies.
  • Minimax / Maximin.
  • Saddle point.
  • Dominance rules.
  • Prisoner’s dilemma.

80.9 Queuing Theory

TipQueuing
  • A.K. Erlang (1909) — pioneered while at Copenhagen Telephone.
  • Notation Kendall’s: A/B/c/K/N/D (arrival/service/servers/capacity/population/discipline).
  • M/M/1 — Poisson arrival, Exponential service, 1 server.
  • Little’s Law: L = λW (jobs in system = arrival rate × waiting time).
  • Indian application: bank counters, telecom switches.

80.10 Inventory Models

TipInventory models
  • EOQ (Economic Order Quantity) — F.W. Harris 1913.
    • \(EOQ = \sqrt{\frac{2DS}{H}}\)
  • EPQ (Economic Production Quantity).
  • Newsvendor Model — single period.
  • (s, S) policy — periodic review.
  • (Q, R) policy — continuous review.
  • ABC classification (Pareto).
  • JIT / Kanban.

80.11 Network Analysis

TipNetwork OR
  • Shortest Path — Dijkstra · Bellman-Ford.
  • Maximum Flow — Ford-Fulkerson · Edmonds-Karp.
  • Minimum Spanning Tree — Kruskal · Prim.
  • CPM / PERT — project networks (Topic 77).
  • Travelling Salesman Problem (TSP) — NP-hard.
  • Vehicle Routing Problem (VRP).

80.12 Simulation

TipSimulation methods
  • Monte Carlo simulation — Stanislaw Ulam, John von Neumann (1940s, Manhattan Project).
  • Discrete-Event Simulation (DES).
  • Agent-based modelling.
  • System Dynamics — Jay Forrester (MIT 1956).
  • Software: Arena, Simul8, AnyLogic, SAS.

80.13 Decision Theory

TipDecision theory
  • Decision under certainty — known outcomes.
  • Decision under risk — known probabilities.
  • Decision under uncertainty — unknown probabilities.
    • Maximax (optimistic).
    • Maximin (pessimistic / Wald).
    • Hurwicz (weighted).
    • Minimax Regret (Savage).
    • Equally Likely / Laplace.
  • Decision Tree — Magee 1964.
  • EVPI — Expected Value of Perfect Information.
  • Bayesian Decision Theory.

80.14 Other OR Techniques

TipOther OR techniques
  • Integer Programming.
  • Goal Programming.
  • Dynamic Programming (Bellman 1957).
  • Non-Linear Programming.
  • Stochastic Programming.
  • Markov Chains.
  • Heuristics & Metaheuristics: GA, SA, Tabu Search, PSO.
  • Combinatorial Optimisation.
  • Constraint Programming.
  • Reinforcement Learning (modern AI/OR overlap).

80.16 Practice Questions

Q 01DantzigMedium

The Simplex Method (1947) is by:

  • AGeorge Dantzig
  • BKantorovich
  • CBellman
  • DErlang
View solution
Correct Option: A
George Dantzig, 1947.
Q 02NashHard

Nash Equilibrium (1950) Nobel was awarded in:

  • A1994
  • B1975
  • C2002
  • D2016
View solution
Correct Option: A
John Nash, Nobel 1994.
Q 03VAMMedium

VAM is used for:

  • AInitial solution of transportation problem
  • BGame theory
  • CQueuing
  • DInventory
View solution
Correct Option: A
Vogel's Approximation Method.
Q 04HungarianMedium

Hungarian Method solves:

  • AAssignment problem
  • BTransportation
  • CQueuing
  • DInventory
View solution
Correct Option: A
Kuhn 1955.
Q 05ErlangMedium

Queuing theory was pioneered by:

  • AA.K. Erlang (1909)
  • BBellman
  • CDantzig
  • DMarkov
View solution
Correct Option: A
Copenhagen Telephone, 1909.
Q 06EOQMedium

EOQ formula is by:

  • AF.W. Harris (1913)
  • BWilson
  • CDantzig
  • DBellman
View solution
Correct Option: A
Ford Whitman Harris, 1913.
Q 07BellmanHard

Dynamic Programming (1957) is by:

  • ARichard Bellman
  • BDantzig
  • CNash
  • DMarkov
View solution
Correct Option: A
Richard Bellman, 1957.
Q 08Little's LawMedium

Little's Law states:

  • AL = λW
  • BL = λ/W
  • CW = λ²
  • Dλ = WL
View solution
Correct Option: A
L = average number; λ = arrival rate; W = waiting time.
Q 09Game theoryMedium

"Theory of Games and Economic Behavior" (1944) is by:

  • Avon Neumann & Morgenstern
  • BNash
  • CSchelling
  • DPareto
View solution
Correct Option: A
1944.
Q 10Monte CarloHard

Monte Carlo simulation was developed during:

  • AManhattan Project (1940s)
  • BWWI
  • CCold War
  • D2000s
View solution
Correct Option: A
Ulam, von Neumann at Los Alamos.
Q 11KarmarkarHard

Interior-point LP method (1984) is by Indian-born:

  • ANarendra Karmarkar
  • BManmohan Singh
  • CCR Rao
  • DMahalanobis
View solution
Correct Option: A
Narendra Karmarkar, AT&T Bell Labs.
Q 12MaximinHard

"Pessimistic" decision criterion is:

  • AMaximin (Wald)
  • BMaximax
  • CHurwicz
  • DLaplace
View solution
Correct Option: A
Wald — Max of Min.
Q 13KantorovichHard

Soviet LP pioneer Kantorovich shared 1975 Nobel with:

  • ATjalling Koopmans
  • BSamuelson
  • CFriedman
  • DSolow
View solution
Correct Option: A
L.V. Kantorovich & T.C. Koopmans, 1975.
Q 14TSPHard

Travelling Salesman Problem is:

  • ANP-hard
  • BPolynomial
  • CConstant
  • DLinear
View solution
Correct Option: A
NP-hard combinatorial problem.
Q 15MatchHard

Match:

(i) Simplex (a) Bellman
(ii) Dynamic Programming (b) Dantzig
(iii) Queuing (c) Harris
(iv) EOQ (d) Erlang
  • A(i)-(b), (ii)-(a), (iii)-(d), (iv)-(c)
  • B(i)-(a), (ii)-(b), (iii)-(c), (iv)-(d)
  • C(i)-(c), (ii)-(d), (iii)-(b), (iv)-(a)
  • D(i)-(d), (ii)-(c), (iii)-(a), (iv)-(b)
View solution
Correct Option: A
Simplex—Dantzig; DP—Bellman; Queuing—Erlang; EOQ—Harris.

80.16.1 Advanced Format Questions

AR 1Assertion-ReasonHard

A: Simplex method solves LP problems iteratively.
R: It moves from one feasible corner to another improving the objective.

  • ABoth true; R explains A
  • BBoth true; R does not explain A
  • CA true, R false
  • DA false, R true
View solution
Correct Option: A
S 1Statement-basedMedium

OR techniques: (i) LP. (ii) Transportation. (iii) Assignment. (iv) Queuing.

  • AAll four
  • B(i) and (ii) only
  • C(iii) and (iv) only
  • D(i) only
View solution
Correct Option: A
N 1NumericalMedium

EOQ: D = 5,000; S = ₹50; H = ₹4. EOQ =

  • A≈ 354
  • B≈ 200
  • C≈ 500
  • D≈ 1,000
View solution
Correct Option: A
EOQ = √(2×5000×50/4) = √1,25,000 ≈ 354.
N 2NumericalHard

M/M/1: λ = 10/hr; μ = 12/hr. Average number in system L =

  • A5
  • B2
  • C10
  • D12
View solution
Correct Option: A
L = λ/(μ−λ) = 10/2 = 5.

80.17 Quick Recall

ImportantQuick recall
  • OR — WWII Britain 1937; Blackett. Pioneers: Dantzig (Simplex 1947), Kantorovich (LP 1939, Nobel 1975), Bellman (DP 1957), Simon, Karmarkar (interior-point 1984).
  • OR Phases (Wagner/Taha): Define · Model · Solve · Test · Implement · Maintain.
  • Models: Iconic/Analog/Math/Sim; Deterministic/Stochastic; Static/Dynamic.
  • LP: Graphical · Simplex · Two-Phase/Big M · Revised · Dual · Interior-point; solvers: CPLEX, Gurobi, LINDO.
  • Duality, Shadow prices, Sensitivity analysis.
  • Transportation: NW Corner · Least Cost · VAM; MODI / Stepping Stone for optimality.
  • Assignment: Hungarian Method (Kuhn 1955) polynomial.
  • Game theory: von Neumann-Morgenstern 1944 · Nash 1950 (Nobel 1994) · zero/non-zero sum · pure/mixed · minimax · saddle point · Prisoner’s dilemma.
  • Queuing: Erlang (1909) · Kendall A/B/c · M/M/1 · Little’s Law L=λW.
  • Inventory: EOQ Harris 1913 · EPQ · Newsvendor · (s,S) · (Q,R) · ABC · JIT.
  • Network: Dijkstra · Bellman-Ford · Ford-Fulkerson · Kruskal · Prim · CPM/PERT · TSP NP-hard · VRP.
  • Simulation: Monte Carlo (Ulam, von Neumann, Manhattan Project) · DES · ABM · System Dynamics (Forrester 1956) · Arena, AnyLogic.
  • Decision theory: Maximin (Wald) · Maximax · Hurwicz · Minimax Regret (Savage) · Laplace · Decision Tree (Magee 1964) · EVPI · Bayesian.
  • Other: IP · GP · DP · NLP · Stochastic · Markov · GA · SA · Tabu · PSO · Combinatorial · CP · RL.
  • Modern: Prescriptive analytics · Opt-as-a-Service · AI-OR fusion · digital twins · stochastic/robust · quantum · ORSI (India 1957).