Unit 2: Probabilistic & dynamic models
Operation Research notes · PTU syllabus (BCOM 602-18)
On this page
Unit summary
Many decisions must be made without knowing the future, or against a competitor. This unit covers decision-making under uncertainty (maximin, minimax regret and other criteria), decision trees, game theory — solution of two-person zero-sum games — and an introduction to deterministic and probabilistic dynamic programming.
After this unit you can
- Apply decision criteria under uncertainty and risk
- Draw and solve decision trees
- Solve two-person zero-sum games with pure and mixed strategies
- Explain the principles of deterministic and probabilistic dynamic programming
PTU syllabus topics
- Decision-making under uncertainty (maximin/minimax)
- decision trees
- game theory — solution of two-person zero-sum games
- introduction to deterministic and probabilistic dynamic programming
Maximax
Optimistic: best of the best
Maximin
Pessimistic: best of the worst
Minimax regret
Minimise the largest regret
Laplace
Treat all outcomes as equally likely
Topic 1
Decision-making under uncertainty
- Decision environment: certainty (outcomes known), risk (probabilities known), uncertainty (probabilities unknown), conflict (competitor).
Maximax (optimistic)
Choose the best of the best payoffs
Maximin (pessimistic, Wald)
Choose the best of the worst payoffs
Minimax regret (Savage)
Minimise the maximum opportunity loss
Hurwicz (realism)
α × best + (1 − α) × worst
Laplace (equal likelihood)
Choose highest average payoff
| Strategy | Low demand | Medium | High | Max | Min | Average |
|---|---|---|---|---|---|---|
| Small plant | 20 | 30 | 40 | 40 | 20 | 30 |
| Medium plant | 10 | 40 | 60 | 60 | 10 | 36.7 |
| Large plant | −20 | 30 | 90 | 90 | −20 | 33.3 |
- Maximax → Large; Maximin → Small; Laplace → Medium.
- Under risk: expected monetary value (EMV) = Σ probability × payoff; expected value of perfect information (EVPI) = expected payoff with perfect information − maximum EMV.
Topic 2
Decision trees
A decision tree shows decisions (squares), chance events (circles) and outcomes in sequence; solved by roll-back — compute EMV at chance nodes and choose the best branch at decision nodes.
Example
Launch a product: success (p = 0.6) profit ₹50 lakh, failure (p = 0.4) loss ₹20 lakh → EMV = 30 − 8 = ₹22 lakh. Don't launch: ₹0. Choose launch.
- Useful for multi-stage decisions (test market first, then launch).
Topic 3
Game theory: two-person zero-sum games
A game is a competitive situation where the gain of one player is the loss of the other (zero-sum).
- Terms: players, strategies (pure or mixed), payoff matrix (from the row player's view), value of the game, saddle point.
- Saddle point: an element that is the minimum of its row and the maximum of its column — maximin = minimax; both players use pure strategies.
- 1Check for a saddle point
Pure strategies if maximin = minimax
- 2Apply dominance
Remove dominated rows/columns
- 32 × 2 without saddle point
Odds/algebraic method for mixed strategies
- 42 × n or m × 2
Graphical method or sub-games
- 5Larger games
Linear programming
Probability A plays row 1
p = (d − c) ÷ [(a + d) − (b + c)]
Probability B plays column 1
q = (d − b) ÷ [(a + d) − (b + c)]
Value of the game
V = (ad − bc) ÷ [(a + d) − (b + c)]
Example
Matrix [3 −1; −2 4]: no saddle point. Denominator = (3 + 4) − (−1 − 2) = 10. p = (4 + 2) ÷ 10 = 0.6; q = (4 + 1) ÷ 10 = 0.5; V = (12 − 2) ÷ 10 = 1.
- Dominance rule: a row that is ≤ another row in every column (for the maximising player) can be deleted; a column ≥ another column (for the minimising player) can be deleted.
Topic 4
Dynamic programming
Dynamic programming (Richard Bellman) solves multi-stage decision problems by breaking them into stages, solving each stage optimally and combining them.
- Bellman's principle of optimality: an optimal policy has the property that, whatever the initial state and decision, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.
- Elements: stages, states, decisions, return function, recursive relationship.
- Deterministic DP: next state is known with certainty — shortest route (stagecoach) problem, allocation of resources, production scheduling.
- Probabilistic DP: next state is described by probabilities — inventory with uncertain demand, equipment replacement under risk; objective is expected value.
Example
Stagecoach problem: to find the shortest route through stages, start from the last stage, compute the shortest distance from each node to the destination, and move backwards stage by stage.
Key terms
- Maximin criterion
- Choose the alternative with the best worst-case payoff
- EMV
- Expected monetary value — probability-weighted average payoff
- Saddle point
- Payoff equal to both maximin and minimax
- Mixed strategy
- Playing strategies with given probabilities
- Principle of optimality
- Remaining decisions of an optimal policy are also optimal
Quick revision
- Uncertainty: maximax, maximin, minimax regret, Hurwicz, Laplace.
- Risk: EMV, EVPI; decision trees by roll-back.
- Games: saddle point → pure; else dominance, odds, graphical, LP.
- 2 × 2 formulas for p, q and V.
- DP: stages, states, recursion; deterministic vs probabilistic.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.Distinguish risk and uncertainty.
- Q2.What is the minimax regret criterion?
- Q3.What is EVPI?
- Q4.What is a saddle point?
- Q5.State the dominance principle.
- Q6.State Bellman's principle of optimality.
Long-answer questions
- Q1.Explain decision-making criteria under uncertainty with an example.
- Q2.Explain decision trees with an illustration.
- Q3.Explain the solution of two-person zero-sum games with and without saddle points.
- Q4.Explain deterministic and probabilistic dynamic programming.
Stuck on this unit?
Message SBS on WhatsApp for help with Operation Research, or to ask about studying B.Com at Synetic.