Unit 01 — Linear Programming

1. What Is Linear Programming? Core syllabus concept

1Understand the Concept

Linear Programming is a mathematical technique for allocating limited resources among competing activities in the best possible way. "Linear" because the relationship between raw materials and consumption is linear; "programming" in the older sense of planning, not computer code Class notes p. 2.

Every LPP has exactly four building blocks. If your answer is missing one, you lose marks — so write all four every single time, with headings:

#	Block	What it is	Why it exists
1	Decision variables	The quantities you control — X₁, X₂, …	They represent the availability/allocation of resources you are choosing.
2	Objective function	Max Z or Min Z, a linear expression in the decision variables	The single thing being optimised — profit, cost, time.
3	Constraints	Linear inequalities/equations limiting the variables	Resources are always constrained — there is never unlimited labour or material.
4	Non-negativity restriction (NNC)	X₁, X₂ ≥ 0	A production model must not give negative output. Stated explicitly, always.

2General mathematical structure

Here cⱼ are the objective coefficients (profit/cost per unit), aᵢⱼ the technological coefficients (how much of resource i one unit of activity j consumes), and bᵢ the RHS or resource availability Notes p. 4.

3The four assumptions that must hold

• Proportionality — doubling an activity doubles its contribution and its resource use. No bulk discounts, no economies of scale.
• Additivity — total profit is the sum of individual profits; activities do not interact.
• Divisibility — variables may take fractional values. When this fails you need Integer Programming — that is exactly why Unit 2 exists.
• Certainty — all coefficients cⱼ, aᵢⱼ, bᵢ are known constants. When you want to test how safe that assumption is, you do sensitivity analysis — concept 6 below.

4Solution vocabulary you must be able to define

Term	Meaning
Feasible solution	A set of values of the decision variables that satisfies all constraints and the non-negativity restriction.
Infeasible solution	A set of values that violates at least one constraint or the NNC p. 3.
Feasible region	The set of all feasible solutions — the shaded polygon in a graphical solution.
Basic solution	For m equations in n variables (n > m), a solution obtained by setting (n − m) variables to zero and solving for the remaining m.
Basic feasible solution	A basic solution that is also feasible. Corner points of the feasible region are exactly the basic feasible solutions — this is why the graphical and simplex methods agree.
Optimal solution	The feasible solution that gives the best (max or min) value of Z.
Unbounded solution	Z can be increased (or decreased) infinitely without violating any constraint.

---

2. Formulating an LPP Core syllabus concept

1The four-step method

Formulation is the single highest-yield skill in this paper: it appeared as a 5-mark question in both 2025-26 papers, and formulation also underlies the Unit 2 and Unit 3 questions. The method never changes Notes p. 8:

Step	What to write	Trap to avoid
1. Decision variables	"Let X₁ be the number of tables to be made", "Let X₂ be the number of chairs to be made"	Never just write "X₁ = tables". State the unit — number of units, litres, hours, boxes.
2. Objective function	Max Z = 200X₁ + 90X₂  (profit)  or  Min Z = … (cost)	Decide Max vs Min from the wording: profit/revenue/contribution → Max; cost/time/waste → Min.
3. Constraints	One inequality per resource, each labelled: "6X₁ + 4X₂ ≤ 1200  (man-hour constraint)"	Getting the direction wrong. Available/capacity/at most → ≤. Requirement/at least/minimum → ≥.
4. Non-negativity	X₁, X₂ ≥ 0	Forgetting it. It is a separate marked line in the synoptic key.

2Worked formulation — chairs and tables

3Formulation patterns that recur

Signal in the question	What it becomes
"total available", "capacity", "not exceed", "at most"	≤ constraint
"must contain at least", "minimum requirement", "no less than"	≥ constraint
"exactly", "all workers must be assigned", "total = "	= constraint
"weekly production cannot exceed 25 units of P1"	A single-variable bound: X₁ ≤ 25 p. 2
Diet / blending / "at least 4000 units of vitamins"	Min objective with ≥ constraints p. 5
Multiple plants × multiple products	Double-subscript variables X₁…X₄, one constraint per plant and per product p. 6

Practice A1–A5 — 5 formulation problems solved step by step →

---

3. Graphical Solution Method Core syllabus concept

1Understand the Concept

The graphical method works for exactly two decision variables. Its value is not that it is practical — it is that it makes visible why the optimum is always at a corner, which is the idea the simplex method automates.

2The six-step procedure

Step	Do this
1	Turn every constraint into an equation (replace ≤ or ≥ with =).
2	Find two points on each line: set X₁ = 0 and solve for X₂, then set X₂ = 0 and solve for X₁. Tabulate them.
3	Plot the lines and shade the feasible region — the area satisfying all constraints simultaneously.
4	Identify every corner point of the feasible region. Where two lines cross, solve the pair simultaneously to get exact coordinates.
5	Evaluate Z at every corner point. Lay it out as a table.
6	Pick the largest Z (Max problem) or smallest Z (Min problem). State the optimal X₁, X₂ and the optimal Z with units.

3Worked example — the tables-and-chairs graph

Practice B1–B4 — 4 graphical problems with full corner-point tables →

---

4. The Five Special Cases Core syllabus concept

1Understand the Concept

Most LPPs have one clean optimum. Five things can go differently — and the exam asks you to recognise which one has happened from a tableau or a graph. Final Exam Q7A was exactly this, for 5 marks QP p. 5. Learn the identification signal for each; that is what is being marked.

Case	What it means	Signal in the simplex tableau	Signal on the graph
1. Unique optimum	Exactly one optimal solution.	All Cⱼ − Zⱼ < 0 for non-basic variables (Max problem).	Objective line touches the region at exactly one corner.
2. Multiple optimal solutions	More than one combination gives the same best Z. Management gets a free choice.	A non-basic variable has Cⱼ − Zⱼ = 0 in the optimal table.	Objective line is parallel to a binding constraint — it touches along a whole edge.
3. Unbounded solution	Z can grow infinitely. Always means the problem was formulated wrongly — no real business earns infinite profit.	No positive replacement ratio — all ratios are negative or infinite, so there is no outgoing variable.	Feasible region is open in the direction of improvement.
4. Infeasible solution	No point satisfies all constraints at once.	An artificial variable stays in the basis at a non-zero value when the optimality condition is already met.	No common shaded region exists.
5. Degenerate solution	A basic variable equals zero. Causes cycling risk.	At least one basic variable has value 0 in the Quantity column — caused by a tie in the replacement ratio.	Three or more constraints pass through the same corner point.

2The class example for each case

Practice D1–D4 — identify the case from four tableaux →

---

5. The Simplex Method Core syllabus concept

1Understand the Concept

The graphical method dies at three variables. The simplex method is an algebraic procedure that walks from one basic feasible solution (corner point) to a better adjacent one, and stops when no further improvement is possible.

2Step 1 — convert inequalities into equations

Constraint type	Add	Meaning
≤	+ Slack variable (S)	The unused amount of that resource.
≥	− Surplus variable, then + Artificial variable (A)	Surplus = the amount by which you exceed the requirement. The artificial variable only exists to give a starting basis.
=	+ Artificial variable (A)	Again purely to start the algorithm.

Setting X₁ = X₂ = 0 then gives the initial basic feasible solution: the slack variables equal the RHS values, and Z = 0 Notes p. 25.

3Step 2 — the tableau vocabulary

Term	What it is
Cⱼ row	Objective coefficient of each variable.
Basic variables	The variables currently in the solution (non-zero). Listed down the left.
Quantity (Qty) column	The current values of the basic variables — and Z at the bottom.
Zⱼ row	For each column: Σ (C of basic variable × that column's entry in the row).
Cⱼ − Zⱼ (index row)	Net contribution per unit if that variable enters the solution. This row drives every decision.
Key/pivot column	The entering variable — most positive Cⱼ − Zⱼ (Max problem).
Replacement ratio	Qty ÷ corresponding pivot-column entry, computed for every row.
Key/pivot row	The leaving variable — smallest non-negative replacement ratio.
Pivot element	The number where the pivot row and pivot column intersect.

4Step 3 — the iteration loop

Practice C1–C2 — two full simplex runs, every tableau shown →

---

6. Duality in Linear Programming Core syllabus concept

1Understand the Concept

Every LPP (the primal) has a mirror-image partner (the dual). If the primal asks "what production plan maximises profit given these resources?", the dual asks "what is each resource worth?" — and its optimal variable values are exactly the shadow prices of the primal. That is why duality and sensitivity analysis are taught together.

2The conversion procedure

Step	Rule
1. Canonical form first	For a Max primal, every constraint must be ≤. For a Min primal, every constraint must be ≥. Multiply a wrong-way inequality by −1 to flip it. Split every = constraint into two: one ≤ and one ≥ (then flip the ≥ one).
2. Flip the objective	Max primal → Min dual. Min primal → Max dual.
3. Swap roles	Primal with m constraints and n variables gives a dual with m variables (Y₁…Yₘ) and n constraints.
4. Swap RHS and objective coefficients	The primal's RHS values (b) become the dual's objective coefficients; the primal's objective coefficients (c) become the dual's RHS.
5. Transpose the matrix	Primal rows become dual columns.
6. Flip the constraint direction	Max primal (≤) → dual constraints are ≥. Min primal (≥) → dual constraints are ≤.

3Quick reference — Primal ↔ Dual

Primal (Max)	Dual (Min)
Maximise	Minimise
n variables	n constraints
m constraints	m variables
Objective coefficients (c)	RHS values
RHS values (b)	Objective coefficients
Constraints ≤	Constraints ≥
Coefficient matrix A	Transpose Aᵀ

Practice E1–E5 — 5 primal→dual conversions, hardest last →

---

7. Sensitivity Analysis Core syllabus concept

1Understand the Concept

Sensitivity analysis — also called post-optimality analysis — studies the effect on the optimal solution of changes in the problem's parameters Deck p. 2. It answers two questions:

1. How do changes in the objective function coefficients affect the optimal solution?
2. How do changes in the right-hand-side values of the constraints affect it?

2The four things a report tells you

Term	Definition	How to use it in an answer
Reduced cost	How much the objective coefficient of a currently unused variable must improve before that variable enters the optimal solution.	Reduced cost = 0 ⟹ the variable is in the solution (it is basic, value > 0). Reduced cost ≠ 0 ⟹ the variable is not produced, and its profit must rise by that amount before it would be.
Objective coefficient range	Lower limit = current coefficient − allowable decrease; Upper limit = current coefficient + allowable increase.	As long as the coefficient stays inside the range, the optimal quantities do not change. Crucially — the optimal Z value does change.
Shadow price (dual value)	The improvement in the optimal objective value from a one-unit increase in that constraint's RHS, provided the change stays within the allowable range.	Change in Z = shadow price × change in RHS. Say it in money: "one extra hour of carpentry is worth ₹14.69 of extra profit".
Binding vs non-binding	A constraint is binding when it is fully used up.	Binding: slack/surplus = 0 and shadow price ≠ 0. Non-binding: slack/surplus ≠ 0 and shadow price = 0. Quote both numbers as your evidence.

3The class worked example — advertising spaces

Practice F1–F4 — including a shadow price used beyond its range →