Linear programming: graphical and simplex methods

Why it matters

A plant has limited machine hours, labour, material and budget, and many products competing for them. Linear programming (LP) finds the product mix, blend or allocation that maximises profit or minimises cost while respecting every limit — for example how many of each component variant to machine on shared CNC centres, or how to mix steel scrap to hit a chemistry at least cost. LP formulation, graphical solution and simplex reasoning are regular GATE questions, and LP is the parent of the transportation and assignment models in the next topic.

Key ideas

Formulating an LP.

1. Decision variables — the quantities you control (x₁ = units of product 1 per week, …).
2. Objective function — a linear expression to maximise (profit) or minimise (cost).
3. Constraints — linear inequalities or equations for each limited resource or requirement.
4. Non-negativity — x_j ≥ 0. LP assumes proportionality and additivity (linear), divisibility (fractional values allowed) and certainty (all coefficients known). If variables must be whole numbers, it becomes integer programming.

Graphical method (two variables). Plot each constraint as a line and shade the side that satisfies it. The overlap is the feasible region, which is always a convex set. The corner-point theorem: if an optimum exists, at least one optimum lies at a vertex (corner) of the feasible region. Either evaluate Z at every corner, or slide an iso-profit line (Z = constant) outward until it last touches the region.

Special cases.

• Infeasible — constraints contradict; no feasible region.
• Unbounded — the region extends without limit in the direction of improvement.
• Multiple (alternative) optima — the objective line is parallel to a binding constraint edge; every point on that edge is optimal.
• Redundant constraint — does not touch the feasible region.
• Degeneracy — more constraints pass through a vertex than needed; in simplex a basic variable becomes zero and cycling is possible.

Simplex method. An algebraic walk from vertex to adjacent vertex, improving Z at each step.

• Convert to equations: add a slack variable to each ≤ constraint (unused resource), subtract a surplus and add an artificial variable for each ≥ constraint, add an artificial for each = constraint. Artificials are driven out by the Big-M penalty or the two-phase method.
• Start at the origin with slacks as basic variables.
• Entering variable (maximisation, with the Z-row written as Z − Σc_j x_j = 0): the most negative coefficient in the Z-row.
• Leaving variable: minimum ratio of RHS to the positive entries in the entering column (minimum-ratio test keeps the solution feasible).
• Pivot to make the entering column a unit vector; repeat until no Z-row coefficient is negative — then the solution is optimal.
• A zero Z-row coefficient for a non-basic variable at optimum signals alternative optima; no positive entry in the entering column signals an unbounded problem; an artificial left in the basis at a positive value signals infeasibility.

Duality and shadow prices. Every LP (primal) has a dual. For a primal "max cᵀx, Ax ≤ b, x ≥ 0", the dual is "min bᵀy, Aᵀy ≥ c, y ≥ 0". At the optimum both objectives are equal. The dual variable y_i is the shadow price of resource i — the increase in optimal Z per extra unit of that resource (valid within a range). It appears in the final simplex Z-row under the slack of that constraint. A resource with spare capacity (non-zero slack) has a zero shadow price (complementary slackness).

Formulas

Max (or Min) Z = c₁x₁ + c₂x₂ + … + cₙxₙ

• Z = objective (₹, h, …); c_j = contribution of one unit of variable j; x_j = decision variables (units).

a_i1·x₁ + a_i2·x₂ + … + a_in·xₙ ≤ b_i, x_j ≥ 0

• a_ij = amount of resource i used per unit of j; b_i = resource available.

a_i·x + s_i = b_i (s_i ≥ 0), a_i·x − e_i + A_i = b_i

• s = slack; e = surplus; A = artificial variable.

Ratio_i = b_i / a_ik for a_ik > 0; leaving row = minimum ratio

• k = entering column.

Dual: Min W = b₁y₁ + … + b_m y_m, Σ a_ij y_i ≥ c_j, y_i ≥ 0; at optimum Z* = W*

Worked examples

Example 1 (standard) — graphical product mix. A shop machines two bracket types. Profit ₹40 per A and ₹30 per B. Machining: 2 h per A, 1 h per B, 100 h available. Assembly: 1 h each, 80 h available. At most 40 A can be sold.

1. Max Z = 40x₁ + 30x₂, subject to 2x₁ + x₂ ≤ 100, x₁ + x₂ ≤ 80, x₁ ≤ 40, x₁, x₂ ≥ 0.
2. Corners: (0, 0); (40, 0); x₁ = 40 with 2x₁ + x₂ = 100 → (40, 20); 2x₁ + x₂ = 100 with x₁ + x₂ = 80 → x₁ = 20, x₂ = 60 → (20, 60); (0, 80).
3. Z: 0; 1,600; 2,200; 2,600; 2,400.

Answer: make 20 A and 60 B for a profit of ₹2,600. Machining and assembly are binding; the demand limit has slack 20.

Example 2 (GATE level) — simplex with shadow prices. Max Z = 3x₁ + 5x₂ subject to x₁ ≤ 4, 2x₂ ≤ 12, 3x₁ + 2x₂ ≤ 18, x ≥ 0.

1. Add slacks: x₁ + s₁ = 4, 2x₂ + s₂ = 12, 3x₁ + 2x₂ + s₃ = 18; Z-row: Z − 3x₁ − 5x₂ = 0. Start: s₁ = 4, s₂ = 12, s₃ = 18, Z = 0.
2. Iteration 1: entering x₂ (−5 most negative). Ratios: 12/2 = 6, 18/2 = 9 → s₂ leaves. Then x₂ = 6 − s₂/2, constraint 3 becomes 3x₁ − s₂ + s₃ = 6, and Z = 30 + 3x₁ − 2.5s₂.
3. Iteration 2: entering x₁ (coefficient −3 in the Z-row). Ratios: 4/1 = 4 (row 1), 6/3 = 2 (row 3) → s₃ leaves. x₁ = 2 + s₂/3 − s₃/3.
4. Z = 30 + 3(2 + s₂/3 − s₃/3) − 2.5s₂ = 36 − 1.5s₂ − s₃. No variable can increase Z, so this is optimal.
5. Solution: x₁ = 2, x₂ = 6, s₁ = 4 − 2 = 2, Z = 36. Shadow prices: 0 for constraint 1, 1.5 for constraint 2, 1 for constraint 3.
6. Dual check: W = 4(0) + 12(1.5) + 18(1) = 36 = Z*.

Answer: x₁ = 2, x₂ = 6, Z = 36.*

Common mistakes

• Shading the wrong side of a constraint; test with the origin when it is not on the line.
• Missing a corner (especially where a constraint meets an axis) when evaluating Z.
• Taking the minimum ratio over negative or zero entries; only positive entries count.
• Choosing the most positive Z-row entry for entering when the row is written as Z − Σc_j x_j = 0; sign conventions differ between textbooks (C_j − Z_j form), so be consistent.
• Assuming the optimum is unique when the objective is parallel to a binding edge.
• Reading the shadow price of a slack (non-binding) resource as non-zero.

For GATE ME

Expect formulation of a small product-mix problem, graphical solution with corner points, identifying unboundedness, infeasibility and alternative optima, and reading a simplex tableau (entering/leaving variable, optimality, shadow price). Questions on the number of basic variables (equal to the number of constraints) and on primal–dual relationships also appear. Practise drawing quick sketches and checking corner points.

Quick check

1. Max Z = 2x + 3y, x + y ≤ 4, x, y ≥ 0. Optimum?
2. In a maximisation simplex tableau, which variable enters?
3. What does a zero Z-row entry for a non-basic variable at the optimum indicate?
4. How many basic variables does an LP with 3 constraints (after adding slacks) have?
5. A resource has slack at the optimum. What is its shadow price?

Answers: 1. Z = 12 at (0, 4). 2. The one with the most negative Z-row coefficient (Z − Σc_j x_j = 0 form). 3. Alternative optimal solutions. 4. Three. 5. Zero.