Graphical Infeasible and Unbounded Drills
Graphical Infeasible and Unbounded Drills
The exam may ask for graphical solution even when no finite optimum exists.
Infeasible
A problem is infeasible when the half-planes have empty intersection.
Example:
\[x_1+x_2\le1, \qquad x_1+x_2\ge3.\]No point can satisfy both.
Unbounded feasible set but finite optimum
A feasible region may be unbounded but still have a finite optimum.
Example:
\[\max 3x_1+x_2\]subject to
\[x_2\le4, \qquad 6x_1+2x_2\le12, \qquad x_2\ge0.\]This region is unbounded to the left, but the maximum is finite.
Unbounded objective
A problem is unbounded when one can move forever in a feasible direction that improves the objective.
Example:
\[\max x_1+x_2\]subject to
\[-x_1+x_2\le1, \qquad x_1,x_2\ge0.\]Moving along $(1,1)$ remains feasible and increases the objective without bound.
Practice
Classify each as finite optimum, infeasible, or unbounded.
- $\max x_1+x_2$ subject to $x_1+x_2\le1$, $x_1+x_2\ge3$.
- $\max x_1+x_2$ subject to $-x_1+x_2\le1$, $x_1,x_2\ge0$.
- $\min x_1+x_2$ subject to $x_1+2x_2\ge4$, $x_1,x_2\ge0$.
- $\max -x_1+x_2$ subject to $x_1+x_2\le1$, $-x_1+x_2\le1$.
Exam checkpoint
For graphical questions, first check whether nonnegativity is explicitly stated. Then draw half-planes, list vertices, evaluate the objective, and state finite optimum, infeasibility, multiple optima, or unboundedness.