Formula & Method Sheet
Everything you need to reproduce from memory for all seven units, on one page — plus the tricks that turn a slow method into a fast one.
The counting rules Highest yield
For an m × n cost matrix (m rows, n columns):
Number of VARIABLES = m × n
Number of CONSTRAINTS = m + n (excluding non-negativity)
BALANCED?
Assignment problem → m = n (rows = columns)
Transportation problem → Σ supply = Σ demand
TO BALANCE
Add a DUMMY row or column on whichever side is short.
All dummy costs = 0. Its supply/demand = the missing quantity.
Worth 2.5 marks in every paper. Variables multiply, constraints add — the two get swapped under pressure more than any other pair on this course.
LPP structure
Optimise Z = c₁X₁ + c₂X₂ + … + cₙXₙ
s.t. aᵢ₁X₁ + aᵢ₂X₂ + … + aᵢₙXₙ (≤ , = , ≥) bᵢ for i = 1…m
and X₁, X₂, …, Xₙ ≥ 0
Four blocks, always written with headings:
1. Decision variables "Let X₁ = number of … "
2. Objective function Max Z (profit) / Min Z (cost)
3. Constraints one per resource, each LABELLED
4. Non-negativity X₁, X₂ ≥ 0
| Wording in the question | Constraint direction |
|---|---|
| available · capacity · not exceed · at most | ≤ |
| requirement · at least · minimum · no less than | ≥ |
| exactly · all must be used · total is | = |
Graphical method
1. Turn each constraint into an EQUATION
2. Two points per line: set X₁ = 0 → get X₂ ; set X₂ = 0 → get X₁
3. Plot, shade the feasible region (test the origin to pick the side)
4. Find every CORNER POINT — solve intersecting pairs simultaneously
5. Evaluate Z at every corner point, in a TABLE
6. Largest Z (Max) or smallest Z (Min) wins.
State X₁, X₂ AND Z with units.
Corner points of the feasible region = the basic feasible solutions. This is why graphical and simplex always agree.
Simplex method
Converting to standard form
| Constraint | Add | Meaning |
|---|---|---|
| ≤ | + Slack S | Unused resource |
| ≥ | − Surplus, + Artificial A | Excess over requirement; A only starts the algorithm |
| = | + Artificial A | Only to start the algorithm |
The loop
Zⱼ = Σ (C of basic variable × that column's entry in the row)
Cⱼ − Zⱼ = net contribution per unit if that variable enters
OPTIMAL when Max problem: all Cⱼ − Zⱼ ≤ 0
Min problem: all Cⱼ − Zⱼ ≥ 0
Entering variable = most positive Cⱼ − Zⱼ → PIVOT COLUMN
Replacement ratio = Qty ÷ pivot-column entry (compute for every row)
Leaving variable = smallest NON-NEGATIVE ratio → PIVOT ROW
Pivot element = intersection of the two
New pivot row = Old pivot row ÷ pivot element
New other row = Old row − (its pivot-column entry × New pivot row)
The five special cases — identification table
| Case | Where to look | What you see |
|---|---|---|
| Unique optimum | Cⱼ − Zⱼ row | All non-basic Cⱼ − Zⱼ strictly < 0 |
| Multiple optima | Cⱼ − Zⱼ row, non-basic column | A non-basic variable has Cⱼ − Zⱼ = 0 |
| Unbounded | Replacement ratio column | No positive ratio — all ∞ or negative; no outgoing variable |
| Infeasible | Basis | An artificial variable stays in the basis at non-zero value when optimality is met |
| Degenerate | Quantity (RHS) column | A basic variable has value 0; caused by a tie in replacement ratios |
The one that decides Q7A: Degenerate = zero in the Quantity column on a basic variable. Multiple optima = zero in the Cⱼ − Zⱼ row on a non-basic variable. Different column, different row.
Duality conversion
STEP 1 Canonical form
Max primal → make every constraint ≤
Min primal → make every constraint ≥
Wrong direction? Multiply the whole row by −1 (coefficients AND RHS).
Equality? Split into ≤ and ≥, then fix the direction. TWO dual variables.
STEP 2 Max ↔ Min (objective flips)
STEP 3 m constraints → m dual variables ; n variables → n dual constraints
STEP 4 Primal RHS → dual objective coefficients
Primal obj → dual RHS
STEP 5 Transpose the coefficient matrix (read DOWN each primal column)
STEP 6 Max primal → dual constraints are ≥ ; Min primal → dual constraints are ≤
| Primal (Max) | Dual (Min) |
|---|---|
| n variables | n constraints |
| m constraints | m variables |
| Objective coefficients c | RHS values |
| RHS values b | Objective coefficients |
| Constraints ≤ | Constraints ≥ |
| Matrix A | Transpose Aᵀ |
Count dual variables before you start: number of primal constraints, with every equality counted twice. Three printed constraints including one equality ⟹ four dual variables.
Sensitivity analysis
Lower limit = Current coefficient − Allowable decrease
Upper limit = Current coefficient + Allowable increase
ΔZ = Shadow price × ΔRHS (valid only inside the allowable range)
BINDING : slack/surplus = 0 AND shadow price ≠ 0
NON-BINDING : slack/surplus ≠ 0 AND shadow price = 0
| Reading | Meaning |
|---|---|
| Reduced cost = 0 | Variable is basic — it is being produced at a positive level. |
| Reduced cost ≠ 0 (say 4) | Variable is not produced. Forcing one unit in would cut profit by ₹4 — equivalently its coefficient must rise by ₹4 to become worth producing. |
| Reduced cost = 0 on a NON-basic variable | Signals alternate optimal solutions. |
| Shadow price | Improvement in Z per one-unit increase in that constraint's RHS. |
| Coefficient inside its range | Optimal quantities unchanged — but Z does change. Recompute it. |
| Coefficient outside its range | Basis may change; the problem must be re-solved. |
Four-step answer template: (1) name the rule — shadow price / allowable range / reduced cost; (2) quote the number from the table; (3) do the arithmetic; (4) one sentence of business meaning.
Integer programming
| Type | Closing line of your answer |
|---|---|
| Pure ILP | X₁, X₂, X₃ ≥ 0 and are integers |
| Mixed ILP | X₁, X₂ ≥ 0 and X₁ is an integer |
| Binary ILP | Xᵢ are binary (0, 1) |
Logical constraints — the translation table
| English | Constraint |
|---|---|
| i and j cannot both be selected | Xᵢ + Xⱼ ≤ 1 |
| Exactly one of i, j | Xᵢ + Xⱼ = 1 |
| i must be done if j is selected | Xⱼ ≤ Xᵢ |
| At least k projects | ΣXᵢ ≥ k |
| At most k projects | ΣXᵢ ≤ k |
| Ship only if facility i is opened (capacity C) | Σⱼ Xᵢⱼ − C·Yᵢ = 0 |
| Produce in batches of 10 | Define X̄ = 10X, X integer |
Transportation & assignment templates
TRANSPORTATION ASSIGNMENT
Xᵢⱼ = quantity shipped i → j Xᵢⱼ = 1 if i assigned to j, else 0
Min Z = ΣΣ cᵢⱼXᵢⱼ Min Z = ΣΣ cᵢⱼXᵢⱼ
Supply: Σⱼ Xᵢⱼ ≤ supplyᵢ Rows: Σⱼ Xᵢⱼ = 1
Demand: Σᵢ Xᵢⱼ = demandⱼ Columns: Σᵢ Xᵢⱼ = 1
Xᵢⱼ ≥ 0 Xᵢⱼ = 0 or 1
Profit variant: when selling prices are given, the cell value becomes
Profit = Selling price(j) − Plant cost(i) − Transport cost(i,j) and the objective flips to Max.
Theory of games Unit 4
Row player = MAXIMISER (cell = row player's gain); column player = MINIMISER
Maximin = max of the row minima Minimax = min of the column maxima
Maximin = Minimax ⟹ saddle point, pure strategies, V = that value (V = 0 ⟹ fair)
Dominance: delete a ROW that is ≤ another row; delete a COLUMN that is ≥ another column
2 × 2 with no saddle point [ a b ; c d ], D = (a + d) − (b + c)
p (row 1) = (d − c)/D q (column 1) = (d − b)/D V = (ad − bc)/D
Formulating from a story: X's gain +k, X's loss −k, the rival's gain −k, random/equal award 0. Unit 4 →
Queuing — M/M/1 Unit 5
λ = arrivals per hour μ = 60 ÷ (service time in minutes) ρ = λ/μ < 1
P₀ = 1 − ρ P(wait) = ρ Pₙ = (1 − ρ)ρⁿ
P(n ≥ k) = ρᵏ P(n > k) = ρᵏ⁺¹ P(n < k) = 1 − ρᵏ
Ls = λ/(μ − λ) Lq = λ²/[μ(μ − λ)]
Ws = 1/(μ − λ) Wq = λ/[μ(μ − λ)] (hours — ×60 for minutes)
Checks: Ls − Lq = ρ Ws − Wq = 1/μ
Cost: waiting cost/day = λ × hours × Wq(min) × cost per minute
Simulation Unit 6
RN range of an outcome = (previous cumulative × 100) to (its cumulative × 100 − 1), starting at 00
Lorry: available = waiting from yesterday + production
shipped = min(capacity, available); waiting = available − shipped; empty = capacity − shipped
Queue: arrival = previous arrival + inter-arrival
start = MAX(arrival, previous end); wait = start − arrival; end = start + service
Profit: price × sold + salvage × unsold − cost × stock − goodwill × shortage
Decision theory Unit 7
| Criterion | Profit table | Cost table |
|---|---|---|
| Laplace | highest row average | lowest row average |
| Optimistic | Maximax | Minimin |
| Pessimistic | Maximin | Minimax |
| Savage (regret) | regret = column max − entry; min of max regrets | regret = entry − column min; same rule |
| Hurwicz (α, default 0.6) | α·max + (1−α)·min, highest | α·min + (1−α)·max, lowest |
EMV = Σ payoff × p EOL = Σ regret × p EPPI = Σ (column best) × p
EVPI = EPPI − best EMV = least EOL
Survey: EV with survey = P(F)·best EMV|F + P(U)·best EMV|U; EVSI = that − best EMV; survey only if EVSI > cost
AHP Unit 7
Scale 1 equal · 3 moderate · 5 strong · 7 very strong · 9 extreme · 2,4,6,8 between
Mirror cell = reciprocal (A vs B = 5 ⟹ B vs A = 1/5)
Priority: divide every entry by its COLUMN total → average each ROW → weights sum to 1
Consistency (optional): CI = (λmax − n)/(n − 1), CR = CI/RI, RI = 0.58 (n = 3), 0.90 (n = 4); CR < 0.10 ✓
Transportation & assignment — solving
Initial solution: NWCR (top-left first) · Least Cost (cheapest cell first) · VAM (largest penalty = gap between two lowest costs)
Occupied cells must be m + n − 1 (fewer ⟹ degenerate, add ε)
MODI: uᵢ + vⱼ = cᵢⱼ on occupied cells (u₁ = 0); dᵢⱼ = cᵢⱼ − uᵢ − vⱼ on empty cells; all dᵢⱼ ≥ 0 ⟹ optimal
Hungarian: row-reduce → column-reduce → cover zeros; lines = n ⟹ optimal
Exam technique
- Q1 is compulsory; choose 4 of the remaining 6. Units 1–3 supply roughly 35 of the 50 marks — pick the questions that play to them.
- "Formulate" means stop at the model. Every formulation question in both papers awarded zero for solving. Time spent solving is time lost.
- Label every constraint. "(carpentry hours)" beside a constraint costs three seconds and makes the marker's job trivial.
- Define variables and state non-negativity — always. Together they are 2 of the 5 marks on a formulation question.
- Show the balance test with both totals. "Σ supply = 75, Σ demand = 85, not balanced" earns more than "not balanced".
- Carry units. ₹28,400 — not 28400.
- Assume and say so. Instruction 7 on both papers is "Assume suitable data if necessary". When a question is ambiguous, write your assumption in one line and proceed.