Linear programming formulation and graphical method

Why it matters

Linear programming (LP) is the workhorse of production planning: product mix, machine loading, blending, cutting and transport decisions are all LPs. Before any algorithm can help, the shop-floor problem has to be translated correctly into variables, an objective and constraints. The graphical method then shows, for two variables, exactly why LP optima sit at corner points, which is the idea every later method (simplex, duality, sensitivity) builds on.

Key ideas

Formulation in three steps.

1. Decision variables — what the manager actually controls, with units (e.g. x₁ = units of product A per week). Define them before writing anything else.
2. Objective function — a linear expression to maximise (profit, contribution) or minimise (cost, time).
3. Constraints — linear limits on resources (machine hours, material, labour, demand) written as ≤, ≥ or =, plus the non-negativity conditions x ≥ 0.

Assumptions of LP. Proportionality (profit and resource use grow linearly with each variable), additivity (no interaction terms), divisibility (variables may take fractional values) and certainty (all coefficients known and constant). If divisibility fails, the problem becomes an integer programme.

Graphical method (two variables).

• Draw each constraint as a line by taking its intercepts, then shade the side that satisfies the inequality (test with the origin if it is not on the line).
• The intersection of all shaded sides with x₁, x₂ ≥ 0 is the feasible region. It is always a convex set; it can be bounded (a polygon), unbounded, or empty.
• Corner-point theorem: if an LP has a finite optimum, at least one corner (extreme point) of the feasible region is optimal. So evaluate Z at every corner, or slide an iso-profit (iso-cost) line Z = k parallel to itself until it last touches the region.

Special cases you must recognise.

• Alternative (multiple) optima — the objective line is parallel to a binding constraint edge; every point on that edge is optimal.
• Unbounded solution — the region is open in the direction of improvement (maximisation over a region extending to infinity). A minimisation over an unbounded region can still have a finite optimum.
• Infeasible problem — the constraints have no common point.
• Redundant constraint — a constraint that does not touch the feasible region; removing it changes nothing.

Connection to later topics. Corner points of the graph are exactly the basic feasible solutions the simplex method moves between; slack in a constraint at the optimum is what duality and sensitivity analysis interpret as an unused resource with zero shadow price.

Formulas

• Objective: Max (or Min) Z = c₁x₁ + c₂x₂ + … + cₙxₙ
• Constraints: aᵢ₁x₁ + aᵢ₂x₂ + … + aᵢₙxₙ (≤, =, ≥) bᵢ, i = 1 … m
• Non-negativity: xⱼ ≥ 0
• Intercepts of a constraint line: x₁ = bᵢ / aᵢ₁ (when x₂ = 0), x₂ = bᵢ / aᵢ₂ (when x₁ = 0)
• Iso-profit line slope: dx₂/dx₁ = −c₁ / c₂

Symbols: xⱼ = level of activity j (units, kg, hours… as defined); cⱼ = profit or cost per unit of xⱼ (₹/unit); aᵢⱼ = amount of resource i used per unit of xⱼ (e.g. h/unit); bᵢ = amount of resource i available or required (e.g. h). These hold under the four LP assumptions above.

Worked examples

Example 1 (standard product mix). A shop makes doors (x₁) and windows (x₂) with profits ₹3 thousand and ₹5 thousand per unit. Plant 1 has 4 h, Plant 2 has 12 h and Plant 3 has 18 h available per week. A door uses 1 h in Plant 1 and 3 h in Plant 3; a window uses 2 h in Plant 2 and 2 h in Plant 3.

1. Model: Max Z = 3x₁ + 5x₂ subject to x₁ ≤ 4, 2x₂ ≤ 12, 3x₁ + 2x₂ ≤ 18, x₁, x₂ ≥ 0.
2. Lines: x₁ = 4; x₂ = 6; 3x₁ + 2x₂ = 18 with intercepts (6, 0) and (0, 9).
3. Corner points: (0, 0), (4, 0), (4, 3) from x₁ = 4 and 3x₁ + 2x₂ = 18 → 2x₂ = 6, x₂ = 3; (2, 6) from x₂ = 6 and 3x₁ + 12 = 18 → x₁ = 2; (0, 6).
4. Z values: 0, 12, 27, 36, 30 (₹ thousand).
5. Optimum: x₁ = 2 doors, x₂ = 6 windows, Z = ₹36 thousand per week. Plants 2 and 3 are fully used; Plant 1 has 2 h of slack.

Example 2 (GATE-type minimisation). A feed is blended from ingredient A (₹20/kg) and B (₹30/kg). Each kg of A gives 2 units of protein and 1 unit of fat; each kg of B gives 1 unit of protein and 3 units of fat. A batch needs at least 8 units of protein and 9 units of fat. Find the cheapest blend.

1. Let x₁, x₂ = kg of A and B. Min Z = 20x₁ + 30x₂ subject to 2x₁ + x₂ ≥ 8, x₁ + 3x₂ ≥ 9, x₁, x₂ ≥ 0.
2. The region lies above both lines and is unbounded, but costs are positive, so a finite minimum exists.
3. Corner points: (0, 8) on the x₂-axis; (9, 0) on the x₁-axis; intersection: x₁ = 9 − 3x₂ → 2(9 − 3x₂) + x₂ = 8 → 18 − 5x₂ = 8 → x₂ = 2, x₁ = 3.
4. Costs: Z(0, 8) = ₹240; Z(3, 2) = 60 + 60 = ₹120; Z(9, 0) = ₹180.
5. Optimum: 3 kg of A and 2 kg of B, minimum cost ₹120 per batch, with both nutrient constraints binding.
6. Check with the iso-cost slope: −20/30 = −0.667 lies between the constraint slopes −2 and −1/3, so the intersection, not an axis point, is optimal.

Common mistakes

• Writing the objective before defining variables and units, then mixing per-hour and per-unit data.
• Shading the wrong side of a ≥ constraint; always test a point such as the origin.
• Missing a corner point where a constraint meets an axis, or forgetting x ≥ 0.
• Declaring a minimisation "unbounded" just because the region is unbounded; only the direction of improvement matters.
• Assuming the optimum is unique: if the objective line is parallel to a binding edge there are infinitely many optima with the same Z.
• Rounding a fractional LP optimum to integers and assuming it is still optimal — that needs integer programming.

For GATE PI

• Two-variable LPs with three or four constraints: find the optimal Z or the optimal point by corner-point evaluation (quick NAT questions).
• Identify special cases: alternative optima, unbounded, infeasible, redundant constraint.
• Formulation from a short word problem (product mix, blending) and recognising which constraints are binding.
• Practise solving 2×2 line intersections fast and checking the answer with the iso-profit slope.

Quick check

1. Max Z = 2x₁ + 3x₂ subject to x₁ + x₂ ≤ 4, x₁, x₂ ≥ 0. What is the optimal Z?
2. Can a minimisation LP with an unbounded feasible region have a finite optimum?
3. Max Z = x₁ + x₂ subject to x₁ + x₂ ≤ 5, x₁, x₂ ≥ 0. How many optimal solutions are there?
4. Which LP assumption is violated if machines can only be bought in whole numbers?

Answers: 1. 12 at (0, 4). 2. Yes, if the objective does not improve indefinitely in the open direction (e.g. positive costs). 3. Infinitely many — every point on the edge x₁ + x₂ = 5. 4. Divisibility.