Graphical Solution of LPP

Linear Programming (LP) is a mathematical technique used to find the best possible outcome — such as maximum profit or minimum cost — given a set of constraints expressed as linear inequalities. The graphical method is the most intuitive way to solve a Linear Programming Problem (LPP) when there are exactly two decision variables, say x and y. By plotting each constraint on the coordinate plane, we carve out a region of feasible solutions and then identify the point within that region that optimises our objective function. The power of the graphical approach lies in a fundamental theorem: if an optimal solution to an LPP exists, it always occurs at one of the corner points (vertices) of the feasible region. This means we do not have to check infinitely many points — just the finite list of vertices. This result, called the Corner Point Theorem (or Extreme Point Theorem), transforms the problem from a continuous search into simple arithmetic evaluation. Graphical LP is widely applied in real-world scenarios: a factory deciding how many units of two products to manufacture, a dietician planning a meal with minimum calories while meeting nutritional targets, or a transport company minimising fuel costs across two routes. Mastering this technique builds the foundation for understanding the Simplex Method used for higher-dimensional problems in operations research, economics, and engineering.

Key takeaways
  • Identify Decision Variables
  • Write the Objective Function
  • List and Plot the Constraints
  • Determine the Feasible Region
  • Find the Corner Points (Vertices)
  • Evaluate the Objective Function at Each Vertex
  • Check for Unbounded Feasible Regions

Identify Decision Variables

Define the two quantities you are optimising. Label them x and y. For example, x = number of chairs produced and y = number of tables produced. Both variables typically satisfy x ≥ 0 and y ≥ 0 (non-negativity constraints), confining the problem to the first quadrant.

Write the Objective Function

Express the quantity to be maximised or minimised as a linear function Z = ax + by, where a and b are given constants (e.g., profit per unit). For instance, Z = 5x + 8y means each unit of x yields ₹5 profit and each unit of y yields ₹8 profit.

List and Plot the Constraints

Convert each real-world restriction into a linear inequality, e.g., 2x + 3y ≤ 12. To graph an inequality: (i) replace the inequality sign with '=' and find the x-intercept (set y=0) and y-intercept (set x=0); (ii) draw the line through those two points; (iii) shade the half-plane satisfying the inequality by testing the origin (0,0). Repeat for all constraints and include x ≥ 0, y ≥ 0.

Determine the Feasible Region

The feasible region is the intersection of all shaded half-planes — the set of all (x, y) that satisfy every constraint simultaneously. If this region is non-empty (at least one point satisfies all constraints), a solution exists. The region may be bounded (a closed polygon) or unbounded (extends infinitely in some direction).

Find the Corner Points (Vertices)

List all vertices of the feasible region. These are found by solving pairs of boundary lines simultaneously. For example, if two boundary lines are 2x + 3y = 12 and x + y = 5, solve: subtracting gives x = 3, then y = 2, so the vertex is (3, 2). Include the intercept points with the axes as well.

Evaluate the Objective Function at Each Vertex

Substitute each corner point into Z = ax + by. The Corner Point Theorem guarantees the optimal value occurs at one of these vertices. For maximisation, choose the vertex giving the largest Z; for minimisation, choose the smallest Z. If two adjacent vertices give the same optimal value, every point on the edge connecting them is also optimal (multiple optimal solutions).

Check for Unbounded Feasible Regions

For an unbounded feasible region, a maximum may not exist (Z can grow infinitely). To confirm a minimum exists for a minimisation problem with an unbounded region, check whether any point in the feasible region gives a value of Z smaller than the candidate minimum. If not, the candidate vertex is indeed the optimal solution.

The Key Equation

Z=c1x+c2ysubject toaix+biy≤di,  x≥0,  y≥0Z = c_1 x + c_2 y \quad \text{subject to} \quad a_i x + b_i y \leq d_i,\; x \geq 0,\; y \geq 0
  • Z — Objective Function (depends on context (e.g., ₹, kg)): The quantity to be maximised or minimised.
  • c_1, c_2 — Objective Coefficients (same unit as Z per unit of variable): Profit, cost, or other rate associated with each decision variable.
  • x, y — Decision Variables (units of product, hours, etc.): The quantities we are choosing to optimise; must satisfy x ≥ 0, y ≥ 0.
  • a_i, b_i — Constraint Coefficients (resource units per item): How much of the limited resource each unit of x or y consumes.
  • d_i — Resource Limit (RHS) (total resource units available): The maximum (or minimum) available quantity for the i-th constraint.

Worked Example

Problem. A company makes two products A and B. Each unit of A requires 1 hour of labour and 2 kg of material; each unit of B requires 2 hours of labour and 1 kg of material. Available: 10 hours of labour and 14 kg of material. Profit: ₹30 per unit of A and ₹40 per unit of B. How many units of each should be produced to maximise profit?

Zmax⁡=30(6)+40(2)=260 at (x,y)=(6,2)Z_{\max} = 30(6) + 40(2) = 260 \text{ at } (x,y) = (6,2)

Answer. Produce 6 units of A and 2 units of B for a maximum profit of ₹260.

Figure
Diagram
Graphical Solution of LPPxy2468246810x+2y=102x+y=14(0,0)(7,0)(6,2)★(0,5)Feasible Region
Origins · 1 minGeorge Dantzig and how this was discovered
GD
George Dantzig
1914–2005 · American

George Dantzig invented the Simplex Method in 1947, the foundational algorithm for solving linear programming problems. His work while working for the U.S. Air Force generalised LP to handle any number of variables, going far beyond the two-variable graphical approach and making large-scale industrial optimisation computationally feasible. As a graduate student, Dantzig arrived late to a statistics class and copied two problems from the blackboard, assuming they were homework. He solved them and handed them in — only to discover they were famous unsolved problems in statistics that had stumped mathematicians for years!

  • Formulation of a Linear Programming Problem — Before solving graphically, you must correctly translate a word problem into decision variables, an objective function, and constraints — the essential first step.
  • Feasible Region and Corner Point Theorem — The Corner Point Theorem is the theoretical justification for why checking only vertices of the feasible region is sufficient to find the optimal solution.
  • Graphing Linear Inequalities in Two Variables — Each LPP constraint is a linear inequality; you must be able to graph and shade half-planes correctly to construct the feasible region.
  • The Simplex Method — The Simplex Method extends the corner-point idea of graphical LP to problems with many variables, using algebraic pivoting instead of a graph.