Formula & Method Sheet
Everything you need to reproduce from memory, 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.
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.