Operations Research II
Complete Revision Guide · Dynamic Programming + Core OR Methods
Exam-ready · Theory + Worked Calculations + Formula Reference
Your class-8 file confirmed Dynamic Programming is on the syllabus, so it is covered in full depth below. The other scans were images that couldn't be read directly, so this guide covers the complete standard OR II syllabus — cross-check the topic list against your class titles and weight your revision where your lecturer spent the most time.
1. Dynamic Programming
Dynamic Programming (DP) solves a complex optimization problem by breaking it into a sequence of nested, simpler sub-problems called stages, and solving them one at a time — almost always by working backward from the end of the problem to the beginning. Each stage's solution is reused, so the same sub-problem is never solved twice.
Bellman's Principle of Optimality
An optimal policy has the property that, whatever the initial state and initial decision, the remaining decisions must form an optimal policy with respect to the state produced by the first decision. In short: any tail-end of an optimal path is itself optimal — which is exactly what makes working backward valid.
Vocabulary you must be able to define
| Term | Meaning |
|---|
| Stage ($t$ or $n$) | A point at which a decision is made (e.g. a day of the trip). |
| State ($i$) | The condition the system is in at a stage (e.g. which city you are in). |
| Decision / policy | The choice made at a stage that moves the system to the next state. |
| Return / cost ($c_{ij}$) | The immediate reward or cost of a decision. |
| $f_t(i)$ | The optimal value from state $i$ at stage $t$ to the end of the problem. |
The recursion — the heart of DP
For a minimum-cost (shortest-path) problem the backward recursion is
$$ f_t(i)=\min_{j}\bigl\{\,c_{ij}+f_{t+1}(j)\,\bigr\}, \qquad f_T(\text{end})=0. $$
Here $c_{ij}$ is the immediate cost of moving from state $i$ to state $j$, and $f_{t+1}(j)$ is the already-computed optimal value from $j$ onward. For a maximization problem replace $\min$ with $\max$.
The four features of every DP problem
- The problem splits into stages, with a decision required at each.
- Each stage has a set of states.
- A decision moves the current state to a state of the next stage.
- Given the current state, the optimal remaining decisions are independent of how you got there (the Markovian property / principle of optimality), and a recursion links $f_t$ to $f_{t+1}$.
Worked example — Shortest path (Joe's cross-country trip)
Joe drives from New York (city 1) to Los Angeles (city 10), overnighting with friends. Cities are grouped into stages by how many days of driving remain. Let $f_t(i)$ be the shortest distance from city $i$ to Los Angeles, and $c_{ij}$ the mileage from $i$ to $j$.
Stage 4 — one leg remaining
Only one route from each, so the values are immediate:
$$ f_4(8)=1030\ \text{(Denver→LA)},\qquad f_4(9)=1390\ \text{(San Antonio→LA)}. $$
Stage 3 — apply the recursion
$$ f_3(5)=\min\begin{cases} c_{58}+f_4(8)=610+1030=\mathbf{1640}^{\ast}\\[2pt] c_{59}+f_4(9)=790+1390=2180 \end{cases} $$
$$ f_3(6)=\min\{\,540+1030=\mathbf{1570}^{\ast},\ \ 940+1390=2330\,\} $$
$$ f_3(7)=\min\{\,790+1030=1820,\ \ 270+1390=\mathbf{1660}^{\ast}\,\} $$
Stage 2
$$ f_2(2)=\min\{\,680{+}1640,\ 790{+}1570,\ 1050{+}1660\,\}=\mathbf{2320}^{\ast}\ (2\!\to\!5) $$
$$ f_2(3)=\min\{\,580{+}1640,\ 760{+}1570,\ 660{+}1660\,\}=\mathbf{2220}^{\ast}\ (3\!\to\!5) $$
$$ f_2(4)=\min\{\,510{+}1640,\ 700{+}1570,\ 830{+}1660\,\}=\mathbf{2150}^{\ast}\ (4\!\to\!5) $$
Stage 1
$$ f_1(1)=\min\begin{cases} c_{12}+f_2(2)=550+2320=\mathbf{2870}^{\ast}\\[2pt] c_{13}+f_2(3)=900+2220=3120\\[2pt] c_{14}+f_2(4)=770+2150=2920 \end{cases} $$
Answer. The shortest route is 1→2→5→8→10 (NY → Columbus → Kansas City → Denver → LA), total 2870 miles. You find the route by following the starred arcs forward after solving backward.
Why DP beats brute force. For a larger 7-stage network, enumerating every path needs thousands of additions, whereas DP reuses sub-solutions and needs only about a hundred — the saving grows explosively with problem size.
Knapsack / resource-allocation recursion
Allocate a limited resource (weight $W$, budget) across items to maximise return. Stage = item; state = capacity remaining.
$$ f_n(w)=\max_{0\le x_n\le\lfloor w/w_n\rfloor}\Bigl\{\,r_n x_n+f_{n+1}\!\bigl(w-w_n x_n\bigr)\Bigr\} $$
$r_n$ = return per unit of item $n$, $w_n$ = its weight, $x_n$ = units chosen.
Inventory / production-scheduling recursion
Choose production each period to meet demand $d_t$ at minimum production + holding cost. Stage = period; state = entering inventory $i$.
$$ f_t(i)=\min_{x_t}\Bigl\{\,c(x_t)+h\,i_{t+1}+f_{t+1}(i_{t+1})\Bigr\},\qquad i_{t+1}=i+x_t-d_t\ge 0 $$
$c(x_t)$ = cost of producing $x_t$ units, $h$ = holding cost per unit.
Exam traps: always (1) state the boundary condition $f_T=0$; (2) label stages and states clearly; (3) write the recursion before plugging in numbers; (4) trace the optimal policy forward once the backward pass is done.
2. Transportation Problem
Distribute goods from $m$ supply sources to $n$ demand destinations at minimum total shipping cost. It is a special LP solved in two phases: (A) find an initial basic feasible solution (IBFS), then (B) test and improve it to optimality.
$$ \text{Minimize } Z=\sum_{i=1}^{m}\sum_{j=1}^{n}c_{ij}x_{ij} \quad\text{s.t.}\quad \sum_{j}x_{ij}=a_i,\ \ \sum_{i}x_{ij}=b_j,\ \ x_{ij}\ge 0. $$
Check before you start
Feasible only if total supply = total demand, i.e. $\sum a_i=\sum b_j$. If not, add a dummy row or column with zero costs to soak up the difference. A basic feasible solution must occupy exactly $m+n-1$ cells; fewer means degeneracy (place a tiny $\varepsilon$ to restore the count).
Phase A — obtaining the IBFS
| Method | How it works | Quality |
|---|
| North-West Corner | Start top-left, allocate as much as possible, cross out the satisfied line, move right/down. | Fast, ignores cost — weak start. |
| Least-Cost | Allocate to the lowest-cost cell first, cross out, repeat. | Better. |
| Vogel's (VAM) | Use penalties (below). | Usually best — near optimal. |
Vogel's Approximation Method (VAM)
- For each row and column compute the penalty = (2nd-lowest cost − lowest cost).
- Select the row/column with the largest penalty.
- Allocate the maximum to its lowest-cost cell; cross out the satisfied line.
- Recompute penalties and repeat until all supply/demand is met.
Phase B — optimality test (MODI / u–v method)
- For each occupied cell set $u_i+v_j=c_{ij}$; put $u_1=0$ and solve for all $u_i,\,v_j$.
- For every empty cell compute the opportunity cost $d_{ij}=c_{ij}-(u_i+v_j)$.
- If all $d_{ij}\ge 0$ the solution is optimal.
- Otherwise pick the most negative $d_{ij}$, trace a closed loop (stepping-stone), and shift the smallest allocation around it with alternating $+,-,+,-$ signs.
- Repeat until all $d_{ij}\ge 0$.
$$ d_{ij}=c_{ij}-(u_i+v_j)\ge 0\ \ \forall (i,j)\ \Longrightarrow\ \text{optimal solution}. $$
Maximization (profit) version: convert to a regret matrix by subtracting every entry from the largest entry, then minimise as usual.
3. Assignment Problem
Assign $n$ jobs to $n$ agents on a one-to-one basis at minimum total cost — a special transportation problem in which every supply and demand equals 1. Solved by the Hungarian Method.
Hungarian Method
- Row reduction: subtract each row's minimum from that row.
- Column reduction: subtract each column's minimum from that column.
- Cover all zeros using the minimum number of straight lines.
- If the number of lines $=n$, an optimal assignment exists — select one independent zero per row and column. If lines $
- Find the smallest uncovered value $k$: subtract $k$ from all uncovered entries and add $k$ to entries at line intersections. Return to step 3.
The matrix must be square — add a dummy row/column of zeros if jobs ≠ agents. For a maximization assignment, subtract every element from the matrix maximum (or negate the matrix), then minimise.
4. Network Analysis — CPM & PERT
Project-scheduling models on an activity network. CPM uses deterministic activity times and finds the longest path (= shortest possible project duration). PERT handles uncertain times using three estimates and probability.
Forward and backward pass
| Quantity | Formula |
|---|
| Earliest Start | $ES_j=\max(EF_i)$ over predecessors |
| Earliest Finish | $EF=ES+t$ |
| Latest Finish | $LF_i=\min(LS_j)$ over successors |
| Latest Start | $LS=LF-t$ |
| Total Float | $TF=LS-ES=LF-EF$ |
| Free Float | $FF=ES_{\text{next}}-EF$ |
Critical path
The chain of activities with zero total float. It is the longest path through the network and fixes the minimum project time — any delay on it delays the whole project.
PERT — three time estimates
$$ t_e=\frac{a+4m+b}{6},\qquad \sigma=\frac{b-a}{6},\qquad \sigma^2=\left(\frac{b-a}{6}\right)^{2} $$
$a$ = optimistic, $m$ = most likely, $b$ = pessimistic. The project variance is the sum over critical activities, $\sigma_p^2=\sum\sigma_i^2$, and the probability of finishing by a due date $T_d$ is
$$ Z=\frac{T_d-T_e}{\sigma_p}\ \Longrightarrow\ P(\text{finish by }T_d)=\Phi(Z). $$
Crashing (time–cost trade-off)
$$ \text{Cost slope}=\frac{\text{Crash cost}-\text{Normal cost}}{\text{Normal time}-\text{Crash time}} $$
To shorten the project, crash the critical activity with the lowest cost slope first, then re-identify the critical path and repeat.
5. Game Theory
Two-person zero-sum games: one player's gain equals the other's loss. The row player maximises, the column player minimises, and the payoff matrix records the row player's gains.
Saddle point — pure strategy
$$ \max_i\min_j a_{ij}\ (\text{maximin})=\min_j\max_i a_{ij}\ (\text{minimax})=V. $$
If maximin equals minimax, that cell is the
saddle point and $V$ is the
value of the game; both players use pure strategies.
Dominance (to shrink the matrix)
- Rows: delete a row if each of its entries is $\le$ the corresponding entry of another row.
- Columns: delete a column if each of its entries is $\ge$ the corresponding entry of another column.
Mixed strategy — 2×2 game with no saddle point
For payoff matrix $\begin{pmatrix}a&b\\ c&d\end{pmatrix}$, row plays $(p,1{-}p)$ and column plays $(q,1{-}q)$:
$$ p=\frac{d-c}{(a+d)-(b+c)},\qquad q=\frac{d-b}{(a+d)-(b+c)},\qquad V=\frac{ad-bc}{(a+d)-(b+c)}. $$
Bigger games: reduce with dominance first. A $2\times n$ or $m\times 2$ game can be solved graphically; anything larger is solved by linear programming.
6. Queuing Theory
Waiting-line models. Arrivals are Poisson with rate $\lambda$; service is exponential with rate $\mu$. Kendall notation $A/B/c$ = arrival distribution / service distribution / number of servers. Traffic intensity $\rho=\lambda/\mu$; the system is stable only if $\rho<1$.
Model M/M/1 (single server, infinite queue)
$$ \rho=\frac{\lambda}{\mu},\qquad P_0=1-\rho,\qquad P_n=(1-\rho)\rho^{\,n}. $$
$$ L=\frac{\lambda}{\mu-\lambda},\qquad L_q=\frac{\lambda^{2}}{\mu(\mu-\lambda)},\qquad W=\frac{1}{\mu-\lambda},\qquad W_q=\frac{\lambda}{\mu(\mu-\lambda)}. $$
Little's Law — memorise
$$ L=\lambda W,\qquad L_q=\lambda W_q,\qquad W=W_q+\tfrac{1}{\mu},\qquad L=L_q+\rho. $$
| Symbol | Meaning |
|---|
| $L$ | average number in the system |
| $L_q$ | average number in the queue |
| $W$ | average time in the system |
| $W_q$ | average waiting time in the queue |
| $P_0$ | probability the system is empty |
Model M/M/s (multiple servers)
$$ P_0=\left[\sum_{n=0}^{s-1}\frac{(\lambda/\mu)^{n}}{n!}+\frac{(\lambda/\mu)^{s}}{s!}\cdot\frac{s\mu}{s\mu-\lambda}\right]^{-1},\qquad \rho=\frac{\lambda}{s\mu}. $$
$$ L_q=\frac{P_0\,(\lambda/\mu)^{s}\,\rho}{s!\,(1-\rho)^{2}},\qquad L=L_q+\frac{\lambda}{\mu}. $$
Worked M/M/1. With $\lambda=6/\text{hr}$, $\mu=10/\text{hr}$: $\rho=0.6$, $L=\frac{6}{4}=1.5$, $W=\frac14\text{hr}=15$ min, $L_q=\frac{36}{40}=0.9$, $W_q=\frac{6}{40}=0.15\text{hr}=9$ min, $P_0=0.4$.
7. Inventory Models
Balance ordering cost against holding cost to find the optimal order size. Notation: $D$ = annual demand, $C_o$ = ordering cost per order, $C_h$ = holding cost per unit per year, $p$ = production rate, $d$ = demand rate, $C_s$ = shortage cost per unit per year.
Basic EOQ (no shortages)
$$ Q^{\ast}=\sqrt{\frac{2DC_o}{C_h}},\qquad TC=\sqrt{2DC_oC_h}, $$
$$ N=\frac{D}{Q^{\ast}}\ (\text{orders/yr}),\qquad t^{\ast}=\frac{Q^{\ast}}{D},\qquad ROP=d\times L. $$
$N$ = orders per year, $t^{\ast}$ = cycle time, $ROP$ = reorder point ($L$ = lead time).
EOQ with gradual replenishment (production model, EPQ)
$$ Q^{\ast}=\sqrt{\frac{2DC_o}{C_h}\cdot\frac{p}{p-d}}. $$
EOQ with planned shortages (backorders)
$$ Q^{\ast}=\sqrt{\frac{2DC_o}{C_h}\cdot\frac{C_h+C_s}{C_s}},\qquad S^{\ast}=Q^{\ast}\cdot\frac{C_s}{C_h+C_s}. $$
$S^{\ast}$ = maximum inventory level.
Quantity discounts: compute EOQ at each price break, adjust to the feasible quantity range, then compare
total cost (purchase + ordering + holding) across candidates and choose the lowest.
Worked EOQ. $D=1000$, $C_o=\$50$, $C_h=\$4$: $Q^{\ast}=\sqrt{\tfrac{2(1000)(50)}{4}}=\sqrt{25000}\approx158$ units; $N=1000/158\approx6.3$ orders/yr; $TC=\sqrt{2(1000)(50)(4)}=\$632$.
8. Decision Theory
Choosing among alternatives when the outcome depends on uncertain "states of nature."
Decisions under uncertainty (no probabilities)
| Criterion | Rule |
|---|
| Maximax (optimist) | choose the maximum of each row's maximum |
| Maximin (pessimist) | choose the maximum of each row's minimum |
| Minimax Regret | build a regret table, minimise the maximum regret |
| Hurwicz | $\alpha(\max)+(1-\alpha)(\min)$, pick the largest |
| Laplace | assume equal probabilities, pick the largest average |
Decisions under risk (probabilities known)
$$ EMV(a)=\sum_{s}P(s)\,V(a,s)\ \Longrightarrow\ \text{choose the largest }EMV. $$
$$ EVPI=EV\text{wPI}-\max EMV,\qquad EV\text{wPI}=\sum_{s}P(s)\,\max_a V(a,s). $$
EMV = Expected Monetary Value; EVPI = Expected Value of Perfect Information — the most you would pay for a perfect forecast. The alternative that maximises EMV also minimises the Expected Opportunity Loss (EOL), and $\min EOL = EVPI$.
Worked EMV. Act A pays 200 or −50 under states with probabilities 0.6 / 0.4: $EMV_A=0.6(200)+0.4(-50)=100$. Compare against the other acts and pick the largest.
9. Sequencing & Replacement
Sequencing — Johnson's Rule ($n$ jobs, 2 machines)
- Find the smallest processing time in the whole table.
- If it lies on Machine 1, schedule that job first (leftmost); if on Machine 2, schedule it last (rightmost).
- Remove the job and repeat, filling inward until all jobs are placed.
Then draw a timeline to get the makespan; total elapsed time is minimised by this order.
Replacement of items that deteriorate
Replace at the year $n$ that minimises the average annual cost:
$$ A(n)=\frac{C+\sum_{t=1}^{n}M(t)-S_n}{n}, $$
$C$ = capital cost, $M(t)$ = maintenance in year $t$, $S_n$ = scrap value. For items that fail suddenly (e.g. bulbs), compare group replacement at fixed intervals against individual replacement on failure and choose the cheaper policy.
Dynamic Programming
$$ f_t(i)=\min_j\{c_{ij}+f_{t+1}(j)\},\quad f_T=0. $$
Work backward · principle of optimality · trace the policy forward.
Transportation
Balance $\sum a_i=\sum b_j$ · IBFS by NWC / Least-Cost / VAM · basis has $m+n-1$ cells · optimality by MODI: $d_{ij}=c_{ij}-(u_i+v_j)\ge 0$.
Assignment (Hungarian)
Row-reduce → column-reduce → cover zeros with minimum lines → if lines $
CPM / PERT
$$ t_e=\frac{a+4m+b}{6},\quad \sigma=\frac{b-a}{6},\quad Z=\frac{T_d-T_e}{\sigma_p}. $$
Critical path = zero float = longest path. $TF=LS-ES$.
Game Theory
$$ \text{Saddle: } \max_i\min_j a_{ij}=\min_j\max_i a_{ij};\qquad V_{2\times2}=\frac{ad-bc}{(a+d)-(b+c)}. $$
Queuing (M/M/1)
$$ L=\frac{\lambda}{\mu-\lambda},\quad W=\frac{1}{\mu-\lambda},\quad L=\lambda W,\quad \rho=\frac{\lambda}{\mu},\quad P_0=1-\rho. $$
Inventory (EOQ family)
$$ Q^{\ast}=\sqrt{\frac{2DC_o}{C_h}},\quad TC=\sqrt{2DC_oC_h},\quad ROP=dL. $$
Decision Theory
$$ EMV=\sum_s P(s)V(a,s),\qquad EVPI=EV\text{wPI}-\max EMV. $$
11. High-Yield Exam Questions — Be Ready For These
- State Bellman's principle of optimality and use the backward recursion to solve a shortest-path or resource-allocation problem.
- Explain the four characteristics of a dynamic programming problem (stage, state, recursion, principle of optimality).
- Balance and solve a transportation problem: find the IBFS by VAM, then test optimality with MODI.
- Solve an assignment problem by the Hungarian method (including a maximization or unbalanced case).
- Draw a project network, find the critical path and floats, and compute the PERT completion probability.
- Identify a saddle point; if none, reduce by dominance and solve the $2\times2$ mixed strategy for $p,q,V$.
- Derive and use the M/M/1 results; state and apply Little's Law.
- Derive the EOQ and compute $Q^{\ast}$, cycle time, number of orders, and total cost; handle a discount.
- Apply the uncertainty criteria (maximax, maximin, minimax regret, Hurwicz, Laplace) and compute EMV and EVPI.
- Sequence jobs by Johnson's rule and find the makespan; determine the optimal replacement age.
In the exam always show: formula → substitution → answer with units. The marks live in the method, not just the final number. The moment you receive rough paper, write down the DP recursion, $t_e=\frac{a+4m+b}{6}$, the M/M/1 formulas and the EOQ formula so you never lose them mid-question.
↑ Back to top · Operations Research II revision guide · cross-check topic weighting against your own class notes. Good luck.