Skip to content

Lesson 3: The Graphical Method

3.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. Plot a feasible region for a two-variable LP.
  2. State and use the Corner-Point (Extreme-Point) Theorem.
  3. Solve LPs by the corner-point enumeration and iso-profit line methods.
  4. Recognise and diagnose the four special cases: multiple optima, unbounded, infeasible, degenerate.
  5. Identify binding constraints and compute slack and surplus graphically.

3.2 Why the Graphical Method Matters

The graphical method works only for two variables (three at a stretch), so it is useless for real problems. Its value is entirely conceptual: it makes visible the geometry that the simplex method (L04–L05) then executes algebraically in \(n\) dimensions.

\[ \boxed{\ \textbf{Every idea in the simplex method is visible in a two-variable picture. Learn the picture first.}\ } \]

3.3 The Feasible Region

Definition. The feasible region is the set of points satisfying all constraints simultaneously.

Procedure for plotting.

  1. Treat each constraint as an equation and draw the line. For \(a_1x_1 + a_2x_2 = b\), the intercepts are \((b/a_1, 0)\) and \((0, b/a_2)\) — the fastest way to plot.
  2. Determine which side of the line satisfies the inequality. Test the origin \((0,0)\): if it satisfies the inequality, shade the origin's side; otherwise shade the other. (If the line passes through the origin, test any other convenient point.)
  3. The non-negativity constraints \(x_1, x_2 \ge 0\) restrict everything to the first quadrant.
  4. The feasible region is the intersection of all shaded half-planes.

Theorem. The feasible region of an LP is a convex set — a possibly unbounded polygon (a polyhedron).

Proof sketch. Each constraint defines a half-plane, which is convex. An intersection of convex sets is convex. \(\blacksquare\)

Convexity is the crucial property: it guarantees that a local optimum is a global optimum, and it is what makes LP tractable.

3.4 The Corner-Point Theorem

Theorem (Fundamental Theorem of Linear Programming). If an LP has an optimal solution, then at least one optimal solution occurs at an extreme point (corner/vertex) of the feasible region.

Proof sketch. Suppose the optimum \(\vec x^{*}\) is not an extreme point. Then it lies on a segment between two feasible points, \(\vec x^{*} = \lambda\vec u + (1-\lambda)\vec v\) with \(0<\lambda<1\). By linearity,

\[ Z(\vec x^{*}) = \lambda Z(\vec u) + (1-\lambda)Z(\vec v) . \]

If \(Z(\vec u)\ne Z(\vec v)\), one of them exceeds \(Z(\vec x^*)\) — contradicting optimality. So \(Z(\vec u) = Z(\vec v) = Z(\vec x^*)\), and moving along the segment to its endpoint preserves optimality. Repeating reaches an extreme point. \(\blacksquare\)

\[ \boxed{\ \textbf{You need only check the corners — finitely many points instead of infinitely many.}\ } \]

This single theorem is why LP is solvable. The simplex method is nothing more than an intelligent walk from corner to corner.

3.5 Two Solution Methods

Corner-point enumeration

1. Plot the feasible region
2. Identify every corner point (solve pairs of constraint equations)
3. Check each candidate is actually FEASIBLE (satisfies all constraints)
4. Evaluate Z at every feasible corner
5. Pick the best

Step 3 is the one students skip. Intersecting two constraint lines gives a point that may violate a third constraint. Always verify.

The iso-profit (iso-cost) line method

1. Plot the feasible region
2. Draw the line Z = k for an arbitrary convenient k -- an "iso-profit line"
3. Slide it PARALLEL, in the direction of increasing Z (for max)
4. The last point of contact with the feasible region is optimal

Direction of improvement. For \(Z = c_1x_1+c_2x_2\), the gradient \(\nabla Z = (c_1, c_2)\) points in the direction of steepest increase. Slide the line along \(\nabla Z\) to maximise, against it to minimise.

Advantage of the iso-profit method. It reveals why a corner is optimal and makes multiple optima instantly recognisable — the iso-profit line becomes parallel to a constraint edge.

3.6 The Four Special Cases

Case Graphical signature Algebraic signature (L06)
Unique optimum iso-profit line touches one corner all non-basic reduced costs strictly favourable
Multiple optima iso-profit line parallel to an edge a non-basic variable has zero reduced cost at optimality
Unbounded feasible region open in the improving direction no positive entry in the pivot column
Infeasible no common shaded region an artificial variable positive at optimality

A fifth case: degeneracy. More than two constraints pass through the same corner (in 2-D). This causes a basic variable to be zero and can, in principle, cause the simplex method to cycle.

3.7 Solved Problems

Problem 1 — The complete graphical solution

Solve:

\[ \begin{aligned} \max\ & Z = 5x_1 + 4x_2\\ \text{s.t. } & 6x_1 + 4x_2 \le 24\\ & x_1 + 2x_2 \le 6\\ & x_1, x_2 \ge 0 \end{aligned} \]

Solution.

Step 1 — plot the constraint lines.

Line 1: \(6x_1 + 4x_2 = 24\). Intercepts \((4, 0)\) and \((0, 6)\). Line 2: \(x_1 + 2x_2 = 6\). Intercepts \((6, 0)\) and \((0, 3)\).

Step 2 — determine the shaded side. Test \((0,0)\): \(6(0)+4(0) = 0 \le 24\) ✓ and \(0 + 0 = 0 \le 6\) ✓. Both include the origin, so shade towards the origin in each case.

 x2
  6 +\
    | \                    line 1: 6x1+4x2=24
  5 +  \
    |   \
  4 +    \
    |     \
  3 +--__  \
    |     --_\  <-- (3, 1.5)  OPTIMUM
  2 +  FEASIBLE -_\
    |  REGION     \ \
  1 +               \ \
    |                \  \        line 2: x1+2x2=6
  0 +--+--+--+--+--+--\--+--\-- x1
    0  1  2  3  4  5  6

Step 3 — find the corner points.

Corner A: the origin \((0,0)\).

Corner B: \(x_1 = 0\) with the binding constraint. On the \(x_2\)-axis, line 2 gives \(x_2 = 3\) and line 1 gives \(x_2 = 6\). The tighter applies: \((0, 3)\). (Check: \(6(0)+4(3)=12\le24\) ✓.)

Corner C: intersection of the two lines. Solve

\[ \begin{aligned} 6x_1 + 4x_2 &= 24\\ x_1 + 2x_2 &= 6 \end{aligned} \]

Multiply the second by 2: \(2x_1 + 4x_2 = 12\). Subtract from the first:

\[ (6-2)x_1 = 24 - 12 \ \Longrightarrow\ 4x_1 = 12 \ \Longrightarrow\ x_1 = 3 \]
\[ 3 + 2x_2 = 6 \ \Longrightarrow\ x_2 = 1.5 \]

Corner C \(= (3,\ 1.5)\).

Corner D: \(x_2 = 0\). Line 1 gives \(x_1 = 4\); line 2 gives \(x_1 = 6\). The tighter is \((4, 0)\). (Check: \(4 + 2(0) = 4 \le 6\) ✓.)

Step 4 — evaluate the objective.

Corner \((x_1, x_2)\) \(Z = 5x_1 + 4x_2\)
A \((0, 0)\) \(0\)
B \((0, 3)\) \(12\)
C \((3, 1.5)\) \(\mathbf{21}\)
D \((4, 0)\) \(20\)
\[ \boxed{\ x_1^{*} = 3,\quad x_2^{*} = 1.5,\quad Z^{*} = 21\ } \]

Step 5 — slack analysis.

\[ \text{Constraint 1: } 6(3)+4(1.5) = 18+6 = 24 = 24 \ \Rightarrow\ s_1 = 0 \ \textbf{(binding)} \]
\[ \text{Constraint 2: } 3 + 2(1.5) = 3+3 = 6 = 6 \ \Rightarrow\ s_2 = 0 \ \textbf{(binding)} \]

Both resources are fully used — as expected, since the optimum lies at the intersection of both lines. In LP the number of binding constraints at a non-degenerate optimum equals the number of variables (here 2).

Iso-profit check. The objective's slope is \(-c_1/c_2 = -5/4 = -1.25\). Line 1's slope is \(-6/4 = -1.5\); line 2's is \(-1/2 = -0.5\). Since \(-1.5 < -1.25 < -0.5\), the objective's slope lies strictly between the two constraint slopes — confirming a unique optimum at their intersection.

Problem 2 — A minimisation problem with ≥ constraints

Solve:

\[ \begin{aligned} \min\ & Z = 3x_1 + 2x_2\\ \text{s.t. } & x_1 + x_2 \ge 8\\ & 3x_1 + 5x_2 \ge 30\\ & x_1 \le 10,\quad x_2 \le 10\\ & x_1, x_2 \ge 0 \end{aligned} \]

Solution.

Step 1 — plot. For the \(\ge\) constraints, testing \((0,0)\) gives \(0 \ge 8\) false, so shade away from the origin.

Line 1: \(x_1+x_2 = 8\), intercepts \((8,0)\) and \((0,8)\). Line 2: \(3x_1+5x_2 = 30\), intercepts \((10,0)\) and \((0,6)\).

Step 2 — corner points.

On the \(x_2\)-axis (\(x_1=0\)): need \(x_2\ge8\) and \(5x_2\ge30 \Rightarrow x_2\ge6\). The binding one is \(x_2 \ge 8\). With \(x_2\le10\), the corners are \((0,8)\) and \((0,10)\).

Intersection of lines 1 and 2:

\[ x_1 + x_2 = 8 \ \Rightarrow\ x_1 = 8 - x_2 \]
\[ 3(8-x_2) + 5x_2 = 30 \ \Rightarrow\ 24 + 2x_2 = 30 \ \Rightarrow\ x_2 = 3,\ x_1 = 5 \]

Corner \((5, 3)\). (Check: \(5\le10\) ✓, \(3\le10\) ✓.)

On the \(x_1 = 10\) boundary: \(10 + x_2 \ge 8\) ✓ always, and \(30 + 5x_2\ge30\) ✓ always. So \((10,0)\) and \((10,10)\) are corners.

Step 3 — evaluate.

Corner \(Z = 3x_1+2x_2\)
\((0,8)\) \(\mathbf{16}\)
\((0,10)\) \(20\)
\((5,3)\) \(21\)
\((10,0)\) \(30\)
\((10,10)\) \(50\)
\[ \boxed{\ x_1^{*}=0,\quad x_2^{*}=8,\quad Z^{*}_{\min} = 16\ } \]

Surplus analysis.

\[ \text{Constraint 1: } 0+8 = 8 = 8 \ \Rightarrow\ \text{surplus} = 0 \ \textbf{(binding)} \]
\[ \text{Constraint 2: } 3(0)+5(8) = 40 > 30 \ \Rightarrow\ \text{surplus} = 10 \]

Why the optimum sits on an axis. The cost ratio favours \(x_2\): it costs 2 per unit versus 3, and contributes 1 per unit to constraint 1 (the binding one) — the same as \(x_1\). So \(x_2\) dominates \(x_1\) for satisfying constraint 1, and the optimum uses only \(x_2\).

A common student error: assuming the optimum must be at the intersection \((5,3)\) because "that is where two constraints meet". It is a corner, but not the best one. Always evaluate all corners.

Problem 3 — Multiple optimal solutions

Solve:

\[ \begin{aligned} \max\ & Z = 4x_1 + 3x_2\\ \text{s.t. } & 4x_1 + 3x_2 \le 24\\ & x_1 \le 5, \quad x_2 \le 6\\ & x_1, x_2 \ge 0 \end{aligned} \]

Solution.

Immediate observation. The objective \(4x_1+3x_2\) is identical to the left side of the first constraint. So \(Z \le 24\) always, and \(Z = 24\) whenever constraint 1 is binding.

Corner points.

Corner How obtained \(Z\)
\((0,0)\) origin 0
\((0,6)\) \(x_1=0\), \(x_2=6\) 18
\((1.5, 6)\) \(x_2=6\) ∩ \(4x_1+18=24\) 24
\((5, 1.333)\) \(x_1=5\) ∩ \(20+3x_2=24\) 24
\((5,0)\) \(x_2=0\), \(x_1=5\) 20

Two corners tie at \(Z = 24\).

Therefore every point on the segment between them is also optimal. Parametrise with \(\lambda\in[0,1]\):

\[ \vec x(\lambda) = \lambda(1.5,\ 6) + (1-\lambda)\left(5,\ \tfrac43\right) = \left(5 - 3.5\lambda,\ \ \tfrac43 + \tfrac{14}{3}\lambda\right) \]

Verify at \(\lambda = 0.5\): \(\vec x = (3.25,\ 3.667)\).

\[ Z = 4(3.25) + 3(3.667) = 13 + 11 = \mathbf{24} \ \checkmark \]
\[ \text{Constraint 1: } 4(3.25)+3(3.667) = 24 \le 24 \ \checkmark \]
\[ x_1 = 3.25\le5 \ \checkmark, \qquad x_2 = 3.667\le6 \ \checkmark \]
\[ \boxed{\ \textbf{Infinitely many optimal solutions, all with } Z^{*} = 24.\ } \]

The graphical signature. The iso-profit line \(4x_1+3x_2 = 24\) has slope \(-4/3\) — exactly the same as constraint 1. When the objective line is parallel to a binding constraint, it touches an entire edge rather than a single corner.

Why this is good news in practice. Multiple optima give the decision-maker free choice among equally profitable plans, which can then be resolved on secondary criteria the model did not capture — robustness, ease of scheduling, customer preference. Always check for and report alternate optima.

Problem 4 — Unbounded and infeasible problems

Diagnose each:

(a) \(\max\ Z = 2x_1 + 3x_2\) s.t. \(x_1 - x_2 \le 2\), \(x_1 + x_2 \ge 4\), \(x_1,x_2\ge0\) (b) \(\max\ Z = x_1 + x_2\) s.t. \(x_1 + x_2 \le 3\), \(x_1 + x_2 \ge 8\), \(x_1,x_2\ge0\)

Solution.

(a) Unbounded.

Test the ray \(x_1 = t\), \(x_2 = t\) for \(t \ge 2\):

\[ x_1 - x_2 = 0 \le 2 \ \checkmark, \qquad x_1 + x_2 = 2t \ge 4 \ \text{for } t\ge2 \ \checkmark \]

Both constraints hold for all \(t \ge 2\), and

\[ Z = 2t + 3t = 5t \ \longrightarrow\ \infty \ \text{ as } t\to\infty \]
\[ \boxed{\ \textbf{Unbounded — no finite optimum exists.}\ } \]

Graphically: the feasible region extends infinitely to the upper right, and the objective improves in that direction.

What this means in practice. An unbounded LP almost always signals a modelling error — a missing resource limit or a missing capacity constraint. Real profit is never infinite. Look for the constraint you forgot.

(b) Infeasible.

Constraint 1 requires \(x_1+x_2 \le 3\); constraint 2 requires \(x_1+x_2 \ge 8\). Since \(3 < 8\), no point can satisfy both:

\[ 8 \le x_1 + x_2 \le 3 \ \Longrightarrow\ 8 \le 3, \ \textbf{a contradiction.} \]
\[ \boxed{\ \textbf{Infeasible — the feasible region is empty.}\ } \]

Graphically: the two shaded half-planes do not overlap.

What this means in practice. Infeasibility signals over-constrained requirements — demands exceeding capacity, or contradictory policy rules. The practical response is to identify the Irreducible Infeasible Subsystem (the smallest conflicting set of constraints), which commercial solvers report automatically, and then relax one of them.

Detection in the simplex method. Both cases have clean algebraic signatures:

  • Unbounded: the entering column has no positive entry, so the minimum-ratio test fails.
  • Infeasible: an artificial variable is positive at optimality.

Problem 5 — Sensitivity from the graph

For the furniture problem of L01 —

\[ \max\ Z = 450x_1 + 300x_2 \ \text{ s.t. } \ 5x_1+3x_2\le120,\ \ 2x_1+4x_2\le90,\ \ x_1,x_2\ge0 \]

— find the optimum, identify binding constraints, and determine the range over which the profit coefficient of \(x_1\) may vary without changing the optimal corner.

Solution.

Corner points and values.

Corner \((x_1,x_2)\) \(Z\)
\((0,0)\) origin \(0\)
\((0, 22.5)\) finishing binding \(6{,}750\)
\((15, 15)\) both binding \(\mathbf{11{,}250}\)
\((24, 0)\) carpentry binding \(10{,}800\)

(Intersection: from \(2x_1+4x_2=90\), \(x_1 = 45-2x_2\); substituting, \(5(45-2x_2)+3x_2 = 120\) gives \(225 - 7x_2 = 120\), so \(x_2 = 15\) and \(x_1 = 15\).)

\[ \boxed{\ x_1^{*}=15,\ x_2^{*}=15,\ Z^{*} = ₹11{,}250\ } \]

Binding constraints.

\[ 5(15)+3(15) = 120 = 120 \ \Rightarrow\ \textbf{carpentry binding}, \ s_1 = 0 \]
\[ 2(15)+4(15) = 90 = 90 \ \Rightarrow\ \textbf{finishing binding}, \ s_2 = 0 \]

Both resources fully used — no idle capacity anywhere.

Sensitivity of the objective coefficient \(c_1\).

The corner \((15,15)\) stays optimal as long as the iso-profit line's slope lies between the slopes of the two binding constraints.

\[ \text{Slope of carpentry: } -\frac{5}{3} = -1.667 \]
\[ \text{Slope of finishing: } -\frac{2}{4} = -0.5 \]
\[ \text{Slope of the objective: } -\frac{c_1}{c_2} = -\frac{c_1}{300} \]

Condition.

\[ -\frac{5}{3} \ \le\ -\frac{c_1}{300} \ \le\ -\frac{1}{2} \]

Multiplying by \(-1\) (reversing the inequalities):

\[ \frac{1}{2} \ \le\ \frac{c_1}{300} \ \le\ \frac{5}{3} \]
\[ \boxed{\ 150 \ \le\ c_1 \ \le\ 500\ } \]

Interpretation. Table profit may fall as low as ₹150 or rise as high as ₹500 and the firm should still make 15 tables and 15 chairs. Only the value of \(Z\) changes, not the plan.

Verification at the boundaries.

At \(c_1 = 500\): slope \(= -500/300 = -1.667\), exactly the carpentry slope ⟹ multiple optima along the carpentry edge, between \((15,15)\) and \((24,0)\). Check: \(Z(24,0) = 500(24) = 12{,}000\) and \(Z(15,15) = 500(15)+300(15) = 7500+4500 = 12{,}000\) ✓ — they tie, as predicted.

At \(c_1 = 150\): slope \(= -0.5\), the finishing slope ⟹ multiple optima along the finishing edge, between \((0, 22.5)\) and \((15,15)\). Check: \(Z(0,22.5) = 300(22.5) = 6750\) and \(Z(15,15) = 150(15)+300(15) = 2250+4500 = 6750\) ✓.

Why sensitivity analysis matters. Cost and price estimates are never exact. Knowing that the plan survives a \(\pm\) 60 % swing in table profit tells management the recommendation is robust — far more useful information than the point estimate ₹11 250 alone. Sensitivity analysis is developed algebraically in L07.

3.8 Practice Problems

  1. Solve graphically: \(\max\ 3x_1+2x_2\) s.t. \(x_1+x_2\le4\), \(x_1+3x_2\le6\), \(x_1\le3\). [Ans: \((3,1)\), \(Z=11\)]
  2. Solve: \(\min\ 2x_1+3x_2\) s.t. \(x_1+x_2\ge6\), \(2x_1+x_2\ge8\), \(x_1,x_2\ge0\). [Ans: \((6,0)\), \(Z=12\); note the corner \((2,4)\) gives 16 — check all corners]
  3. Show that \(\max\ 2x_1+2x_2\) s.t. \(x_1+x_2\le5\) has multiple optima and describe them.
  4. Diagnose: \(\max\ x_1\) s.t. \(x_1 - x_2 \le 1\), \(x_1,x_2\ge0\). [Ans: unbounded]
  5. Diagnose: \(x_1\ge5\), \(x_1\le3\). [Ans: infeasible]
  6. For Problem 1 above, find the range of \(c_1\) keeping the optimum unchanged.
  7. Explain why an LP optimum can never occur strictly inside the feasible region (unless the objective is constant).

3.9 Summary

  • The feasible region is a convex polyhedron; plot by drawing each constraint as a line and using the origin test to pick the side.
  • Corner-Point Theorem: if an optimum exists, one occurs at an extreme point — so checking finitely many corners suffices. This is the theoretical basis of the simplex method.
  • Two equivalent methods: corner enumeration (evaluate \(Z\) at every feasible corner — always verify feasibility) and the iso-profit line (slide parallel along \(\nabla Z\)).
  • Multiple optima ⟺ the objective line is parallel to a binding constraint ⟺ tied corner values; report them, since they give the decision-maker free choice.
  • Unbounded ⟹ almost always a missing constraint. Infeasible ⟹ over-constrained requirements.
  • Binding constraints have zero slack/surplus; the number of binding constraints at a non-degenerate optimum equals the number of variables.
  • Sensitivity: the optimal corner is unchanged while the objective slope \(-c_1/c_2\) lies between the slopes of the binding constraints — a range, not a point.

Next lesson: L04 — The simplex method: theory.

Practise now: unit1-lp-lab.html → Graphical Solver: enter any two-variable LP, see the shaded region, all corner points, the sliding iso-profit line and the sensitivity ranges computed live.