Graphical Method | Sahithyan's Notes

Suppose a linear program has $n$ decision variables. Then it can be solved graphically using a $\mathbb{R}^n$ space. Hence not suitable for $n > 2$ (or $n > 3$ with computer visualization).

All constraints are plotted on the same $\mathbb{R}^n$ space. Feasible region is the intersection of all constraint half-spaces. Optimal solution occurs at a vertex (and not the interior) of the feasible region. Based on the vertex property.

The vertex is found by moving the objective hyperplane $z = c_1x_1 + \dots + c_nx_n$ across the feasible region. Increase $z$ for maximization, decrease it for minimization. The optimal vertex is the last one the hyperplane touches before leaving the region.

Worked Example

Maximize $z = 3x_1 + 2x_2$ subject to

\begin{aligned} x_1 + x_2 &\le 4 \\ x_1 + 3x_2 &\le 6 \\ x_1, x_2 &\ge 0 \end{aligned}

Solution Reveal Hide

Plot both constraint lines. The feasible region is the polygon with vertices $(0,0)$ , $(4,0)$ , $(3,1)$ , $(0,2)$ . Vertex $(3,1)$ is the intersection of $x_1 + x_2 = 4$ and $x_1 + 3x_2 = 6$ .

The feasible region is bounded by x₁ + x₂ ≤ 4, x₁ + 3x₂ ≤ 6, and the axes. Arrows mark the feasible side of each constraint line. The optimal vertex (3,1) is where the 2 lines intersect.

Evaluate $z$ at each vertex:

Vertex	$z$
$(0,0)$	$0$
$(4,0)$	$12$
$(3,1)$	$11$
$(0,2)$	$4$

Optimal: $x_1 = 4$ , $x_2 = 0$ , $z = 12$ .

Special Cases

Multiple optima
The objective line is parallel to a binding constraint edge. Every point on that edge is optimal.
Unbounded problem
The feasible region extends without limit in the improving direction. No finite optimum exists.
Infeasible problem
The constraint half-planes have empty intersection. No solution exists.