Graphical solution for maximisation and minimisation up to 3 variables, convex / non-convex hull, alternative solutions, unbounded solutions and non-existing feasible solutions.
The graphical method works only for LPPs with two decision variables (and rarely three, where you plot in 3-D and shade a feasible polyhedron). For more variables the simplex method (Unit 3) is required.
2. Steps in the Graphical Method
Express the problem in standard form (variables non-negative).
Plot each constraint as a straight line in the \(x_1\)-\(x_2\) plane (treat \(\le, \ge\) as equalities for the line).
Identify the feasible region — the set of \((x_1, x_2)\) satisfying all constraints and non-negativity. It is always a convex polygon.
Find the corner points (vertices) of the feasible region.
Evaluate the objective function \(Z\) at each corner point.
The maximum (or minimum) value of \(Z\) gives the optimal solution.
Fundamental theorem of LP: If an LPP has an optimal solution, it is attained at at least one vertex of the feasible region.
3. Convex Set, Convex Hull and Feasible Region
DEFINITIONS
A set \(S\) is convex if for any two points \(P_1, P_2 \in S\), the line segment joining them lies entirely in \(S\). Formally: \(\lambda P_1 + (1-\lambda) P_2 \in S\) for \(0 \le \lambda \le 1\).
The convex hull of a set of points is the smallest convex set containing all of them.
A set is non-convex if some line segment between its points leaves the set.
Why this matters for LPP
Each linear inequality defines a half-plane, which is convex.
Intersection of finitely many half-planes is also convex — so the feasible region of an LPP is always a convex polygon (or polyhedron in higher dimensions).
The optimum lies at a vertex (extreme point) of this convex set.
EXAMPLE 1 — Identifying a convex set
The set \(\{(x, y) : x + y \le 4, x \ge 0, y \ge 0\}\) is a triangular region with vertices (0,0), (4,0), (0,4). It is convex.
EXAMPLE 2 — Non-convex set
The union \(\{x^2 + y^2 \le 1\} \cup \{(x-3)^2 + y^2 \le 1\}\) — two disjoint discs — is non-convex; a line segment between centres of the two discs leaves the set.
Shade feasible region: all \(\le\) constraints + first quadrant.
Vertices of feasible region: \(O(0,0),\; A(4,0),\; B(4,3),\; C(2,6),\; D(0,6)\).
Evaluate Z at each:
Vertex
Z = 3x₁ + 5x₂
O(0, 0)
0
A(4, 0)
12
B(4, 3)
27
C(2, 6)
36 (max)
D(0, 6)
30
Optimal: \(x_1 = 2,\; x_2 = 6,\; Z_{\max} = 36\).
Fig 2.1 — Feasible region for maximisation; optimum at C(2, 6) with Z = 36
5. Worked Example — Minimisation
PROBLEM
Minimise \(Z = 20 x_1 + 10 x_2\) subject to
\(x_1 + 2 x_2 \ge 40\)
\(3 x_1 + x_2 \ge 30\)
\(4 x_1 + 3 x_2 \ge 60\)
\(x_1, x_2 \ge 0\)
Solution
Plot the three lines:
\(x_1 + 2 x_2 = 40\) through (40, 0) and (0, 20)
\(3 x_1 + x_2 = 30\) through (10, 0) and (0, 30)
\(4 x_1 + 3 x_2 = 60\) through (15, 0) and (0, 20)
Feasible region lies above all three lines and in the first quadrant — it's unbounded above and to the right. (The third constraint \(4 x_1 + 3 x_2 \ge 60\) turns out to be redundant: it is satisfied automatically wherever the other two hold.)
Find vertices that border the feasible region:
\(P_1 = (0, 30)\) — where \(3 x_1 + x_2 = 30\) meets the \(x_2\)-axis
\(P_2 = (4, 18)\) — intersection of \(3 x_1 + x_2 = 30\) and \(x_1 + 2 x_2 = 40\)
\(P_3 = (40, 0)\) — where \(x_1 + 2 x_2 = 40\) meets the \(x_1\)-axis
(The points \((6, 12)\) and \((15, 0)\) lie below the line \(x_1 + 2 x_2 = 40\) — e.g. at \((6,12)\), \(x_1 + 2x_2 = 30 < 40\) — so they are infeasible and are not corner points of the region.)
The line \(Z = 4 x_1 + 6 x_2\) is parallel to constraint \(2 x_1 + 3 x_2 = 24\) (both have slope \(-2/3\)). All points on the edge from (12, 0) to (7.2, 3.2) — the intersection of \(2 x_1 + 3 x_2 = 24\) and \(x_1 + 4 x_2 = 20\) — give \(Z = 48\), so there are infinitely many optimal solutions.
6.2 Unbounded Solution
Occurs when the feasible region extends infinitely in the direction of improvement. The objective can be made arbitrarily large (max) or small (min).
The two constraints contradict each other — empty feasible region → no feasible solution exists.
6.4 Redundant Constraint
A constraint that does not affect the feasible region — it lies entirely outside or coincides with the boundary of another. Removing it leaves the optimum unchanged.
7. Quick Summary — Possible Outcomes
Case
Feasible Region
Optimal Solution
Unique optimum
Bounded, single best vertex
Exactly one
Alternative optima
Bounded, objective parallel to an edge
Infinitely many on that edge
Unbounded
Open in direction of improvement
Z → ∞ (or −∞)
Infeasible
Empty (no common point)
None
Key Take-aways
Graphical method works for 2-variable LPPs; the feasible region is always a convex polygon.
Optimum lies at a vertex (corner point) — evaluate \(Z\) at each vertex.
For min problems, the feasible region is usually unbounded (≥-type constraints) but the optimum may still exist at a finite vertex.
Four possible cases: unique, alternative, unbounded, infeasible.
For more than two variables — use the simplex method (Unit 3).