Linear programming: graphical and simplex methods

Why it matters

Product-mix decisions, machine loading, blending, cutting-stock and shipping plans are all "best use of limited resources" problems. Linear programming (LP) turns them into a model that a solver — or you, for two variables, on paper — can solve exactly, and the shadow prices it produces tell a manager what one more machine-hour or tonne of material is worth.

Key ideas

• Formulation. Every LP has three parts:
  • Decision variables x₁ … xₙ — the quantities you control (units of each product, tonnes shipped).
  • Objective function — a linear expression to maximise (profit) or minimise (cost).
  • Constraints — linear inequalities or equalities for resources, demand or policy, plus non-negativity xⱼ ≥ 0.
• Assumptions. Proportionality and additivity (linearity), divisibility (variables may take fractional values — otherwise it is an integer program), certainty (all coefficients known) and non-negativity.
• Feasible region. The set of points satisfying all constraints. It is the intersection of half-spaces, so it is always a convex set (a convex polygon in two variables). If it is non-empty and the objective is bounded, an optimum always occurs at a corner point (vertex) — this is the fundamental theorem that both methods rely on.
• Graphical method (two variables). Plot each constraint as a line, shade the feasible side, find the corner points, and either evaluate Z at each corner or slide an iso-profit line Z = constant parallel to itself until it last touches the region.
• Special cases.
  • Infeasible — the constraints have no common region.
  • Unbounded — the region is open in the direction of improvement, so Z can grow without limit.
  • Multiple (alternative) optima — the objective line is parallel to a binding constraint edge; every point on that edge is optimal.
  • Redundant constraint — one that does not touch the feasible region.
  • Degeneracy — in simplex, a basic variable equals zero (a tie in the ratio test); it can cause cycling.
• Simplex method. An algebraic walk from one corner (basic feasible solution) to a better adjacent corner until no improvement is possible.
  • Convert to standard form: add a slack variable to each ≤ constraint (unused resource), subtract a surplus variable from each ≥ constraint, and add artificial variables for ≥ and = constraints, handled by the Big-M or two-phase method.
  • With m constraints and n variables (including slacks), each corner has m basic variables and n − m non-basic variables set to zero.
  • Entering variable (maximisation): the most negative coefficient in the Z-row (written as Z − c·x = 0). Leaving variable: minimum ratio of RHS to positive entries in the pivot column (minimum ratio test keeps the solution feasible).
  • Optimality: all Z-row coefficients ≥ 0 for a maximisation problem.
  • No positive entry in the pivot column → unbounded. Zero Z-row coefficient for a non-basic variable at the optimum → alternative optima. Artificial variable still positive at the end → infeasible.
• Duality and shadow prices. Each primal LP has a dual; a max problem with ≤ constraints has a min dual with ≥ constraints. At the optimum, primal Z = dual W. The dual variable (shadow price) of a constraint is the rise in optimal Z per unit increase of its right-hand side, valid within a range found by sensitivity analysis. A non-binding constraint (positive slack) has zero shadow price.
• Links. Transportation and assignment problems are special LPs with faster methods; aggregate planning and blending models are LP formulations.

Formulas

• General LP (maximisation form): Max Z = c₁x₁ + c₂x₂ + … + cₙxₙ
• Constraints: aᵢ₁x₁ + aᵢ₂x₂ + … + aᵢₙxₙ ≤ bᵢ, i = 1 … m; xⱼ ≥ 0
  • xⱼ = decision variables (units of activity j); cⱼ = contribution per unit (₹/unit); aᵢⱼ = amount of resource i used per unit of activity j (e.g. h/unit); bᵢ = resource available (e.g. h).
• Standard form with slack: aᵢ₁x₁ + … + aᵢₙxₙ + sᵢ = bᵢ, sᵢ ≥ 0
• Surplus and artificial for ≥ constraint: aᵢ₁x₁ + … − sᵢ + Aᵢ = bᵢ
• Maximum number of basic solutions: C(n, m) = n! / (m!·(n − m)!), n = total variables in standard form, m = constraints.
• Minimum ratio test: θ = min (bᵢ / aᵢₖ) over rows with aᵢₖ > 0, k = entering column.
• Dual of Max Z = cᵀx, Ax ≤ b, x ≥ 0 is Min W = bᵀy, Aᵀy ≥ c, y ≥ 0; at the optimum Z* = W*.
• Complementary slackness: yᵢ·sᵢ = 0 for every constraint.

Worked examples

Example 1 (standard): graphical method A shop makes products P and Q. Profit: ₹30 per P, ₹20 per Q. Machine A: 2 h per P, 1 h per Q, 100 h available. Machine B: 1 h per P, 1 h per Q, 80 h available. Market limit: at most 40 of P.

1. Formulation: Max Z = 30x₁ + 20x₂, subject to 2x₁ + x₂ ≤ 100, x₁ + x₂ ≤ 80, x₁ ≤ 40, x₁, x₂ ≥ 0.
2. Corner points:
   • (0, 0): Z = 0.
   • (40, 0): Z = 1,200.
   • x₁ = 40 with 2x₁ + x₂ = 100 → (40, 20): Z = 1,200 + 400 = 1,600.
   • 2x₁ + x₂ = 100 and x₁ + x₂ = 80 → subtract: x₁ = 20, x₂ = 60 → Z = 600 + 1,200 = 1,800.
   • (0, 80): Z = 1,600.
3. Largest Z is at (20, 60). Machines A and B are fully used; the market limit has slack 20. Answer: Make 20 of P and 60 of Q; maximum profit ₹1,800.

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

1. Standard form: x₁ + s₁ = 4; 2x₂ + s₂ = 12; 3x₁ + 2x₂ + s₃ = 18; Z − 3x₁ − 5x₂ = 0. Initial basis s₁ = 4, s₂ = 12, s₃ = 18, Z = 0.
2. Iteration 1: most negative Z-row coefficient is −5 → x₂ enters. Ratios: row 2: 12/2 = 6; row 3: 18/2 = 9; row 1 has zero in the x₂ column. Minimum is 6 → s₂ leaves. Pivot: x₂ = 6 − 0.5s₂. Updated rows: x₁ + s₁ = 4; 3x₁ − s₂ + s₃ = 6; Z − 3x₁ + 2.5s₂ = 30.
3. Iteration 2: −3 under x₁ → x₁ enters. Ratios: row 1: 4/1 = 4; row 3: 6/3 = 2 → s₃ leaves. x₁ = 2 − (s₃ − s₂)/3. Substituting: Z + 1.5s₂ + 1·s₃ = 36; s₁ = 4 − 2 = 2.
4. All Z-row coefficients are now ≥ 0 → optimal: x₁ = 2, x₂ = 6, s₁ = 2, Z = 3(2) + 5(6) = 36.
5. Shadow prices are the Z-row coefficients of the slacks: y₁ = 0 (constraint 1 has slack 2), y₂ = 1.5, y₃ = 1. Check with duality: W = 4(0) + 12(1.5) + 18(1) = 36 = Z. ✓ Answer: x₁ = 2, x₂ = 6, Z_max = 36; one more unit of resource 2 is worth 1.5 and of resource 3 is worth 1.

Common mistakes

• Choosing the leaving variable with the largest ratio, or including rows with zero or negative pivot-column entries in the ratio test.
• Using the maximisation optimality rule on a minimisation problem (or forgetting to convert Min Z to Max (−Z)).
• Shading the wrong side of a ≥ constraint in the graphical method, or forgetting x, y ≥ 0.
• Reading a corner point off a sketch instead of solving the two line equations exactly.
• Declaring "no solution" when the problem is actually unbounded or has alternative optima.
• Treating a shadow price as valid for any change in the RHS; it holds only within the sensitivity range.

For GATE ME

Typical questions: formulate and solve a two-variable LP graphically and report Z_max or Z_min; identify unbounded, infeasible or multiple-optimum cases from a figure or tableau; read the entering and leaving variables or the optimal solution from a simplex tableau; count basic/non-basic variables; write the dual and use Z* = W*; interpret slack and shadow prices. Practise fast corner-point evaluation and one or two full simplex iterations by hand.

Quick check

1. Why is the feasible region of an LP always convex?
2. In a maximisation tableau, how is the entering variable chosen?
3. What does a zero Z-row coefficient for a non-basic variable at the optimum indicate?
4. A constraint has positive slack at the optimum. What is its shadow price?
5. Max Z = 2x + 3y with x + y ≤ 4, x, y ≥ 0. What is Z_max?

Answers: 1. It is the intersection of half-spaces, each convex. 2. Most negative coefficient in the Z-row. 3. Alternative optimal solutions exist. 4. Zero. 5. 12, at (0, 4).