Graphical Method

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

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$.

Evaluate $z$ at each vertex:

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.