Graphical Problems Without Nonnegativity
Graphical Problems Without Nonnegativity
The exam sometimes gives a two-variable graphical problem without saying $x_1,x_2\ge0$. In that case, the feasible region is not automatically restricted to the first quadrant.
Rule
Only draw the first quadrant if the problem explicitly includes
\[x_1,x_2\ge0.\]If no sign restriction is written, both variables are free and the feasible region may extend into negative coordinates.
Worked example
\[\min -x_1+3x_2\]subject to
\[x_1+x_2\le6,\] \[-2x_1+x_2\le2,\] \[x_1-x_2\le3.\]Boundary intersections:
| Active constraints | Point | Objective |
|---|---|---|
| 1 and 2 | $(4/3,14/3)$ | $38/3$ |
| 1 and 3 | $(9/2,3/2)$ | $0$ |
| 2 and 3 | $(-5,-8)$ | $-19$ |
The minimum is
\[x^*=(-5,-8),\qquad z^*=-19.\]This point would be missed if you incorrectly assumed nonnegativity.
Exam checklist
Before drawing, ask:
- Are $x_1,x_2\ge0$ written?
- Are there lower or upper bounds on only one variable?
- Is the feasible set in the whole plane?
- Could the optimum be outside the first quadrant?
Practice
Solve graphically without assuming nonnegativity:
- $\max -x_1+3x_2$ subject to $3x_1-x_2\le2$, $x_1+x_2\ge3$, $-x_1+2x_2\le6$.
- $\min -x_1+3x_2$ subject to $x_1+x_2\le6$, $-2x_1+x_2\le2$, $x_1-x_2\le3$.
- $\max -\frac12x_1+x_2$ subject to $2x_1+2x_2\le3$, $2x_1-2x_2\le3$, $-2x_1-2x_2\le3$.
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.