Graphical Mixed Max Min Problems
Graphical Mixed Max Min Problems
For graphical problems, maximization and minimization use the same feasible region. Only the direction of improvement changes.
Method
- Draw the feasible region once.
- List vertices.
- Evaluate the objective at every vertex.
- For max, choose the largest value.
- For min, choose the smallest value.
Worked example
Feasible region:
\[x_1+2x_2\le2,\] \[-x_1+2x_2\le2,\] \[x_2\ge0.\]Vertices:
\[(-2,0),\quad (2,0),\quad (0,1).\]For
\[\max 2x_1+x_2,\]values are $-4,4,1$, so
\[x^*=(2,0),\qquad z^*=4.\]For
\[\min 2x_1+x_2,\]values are $-4,4,1$, so
\[x^*=(-2,0),\qquad z^*=-4.\]Exam warning
If the objective line is parallel to an active edge, the optimum may be an entire edge, not a single point.
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.