Graphical Drill Set
Graphical Drill Set
For each problem, draw the feasible region, identify vertices, and evaluate the objective at the relevant vertices.
Problems and answers
1. Standard first-quadrant maximum
\[\max x_1+x_2\]subject to
\[x_1+2x_2\le10,\] \[2x_1+x_2\le16,\] \[-x_1+x_2\le3,\] \[x_1,x_2\ge0.\]Answer:
\[x^*=\left(\frac{22}{3},\frac{4}{3}\right),\qquad z^*=\frac{26}{3}.\]2. No nonnegativity stated
\[\min -x_1+3x_2\]subject to
\[x_1+x_2\le6,\] \[-2x_1+x_2\le2,\] \[x_1-x_2\le3.\]Answer:
\[x^*=(-5,-8),\qquad z^*=-19.\]The point is outside the first quadrant. This is the trap.
3. Mixed inequality directions
\[\max -x_1+3x_2\]subject to
\[3x_1-x_2\le2,\] \[x_1+x_2\ge3,\] \[-x_1+2x_2\le6.\]Answer:
\[x^*=(2,4),\qquad z^*=10.\]4. Minimum with lower bounds
\[\min x_1+x_2\]subject to
\[x_1+2x_2\ge4,\] \[x_1+x_2\le5,\] \[x_1,x_2\ge0.\]Answer:
\[x^*=(0,2),\qquad z^*=2.\]5. Larger feasible polygon
\[\max 2x_1+x_2\]subject to
\[-2x_1+x_2\le-1,\] \[x_1-x_2\le3,\] \[4x_1+x_2\le17,\] \[x_2\le5,\] \[-x_1+x_2\le3,\] \[x_1,x_2\ge0.\]Answer:
\[x^*=(3,5),\qquad z^*=11.\]6. Multiple optima
\[\max 3x_1+x_2\]subject to
\[x_2\le4,\] \[6x_1+2x_2\le12,\] \[x_2\ge0.\]Answer:
All points on
\[6x_1+2x_2=12, \qquad 0\le x_2\le4\]are optimal, and $z^*=6$.
7. Infeasible system
\[\max x_1+x_2\]subject to
\[x_1+x_2\le1,\] \[x_1+x_2\ge3.\]Answer: infeasible.
8. Unbounded maximum
\[\max x_1+x_2\]subject to
\[-x_1+x_2\le1,\] \[x_1,x_2\ge0.\]Answer: unbounded above.
9. Whole edge optimal
\[\min -x_1+x_2\]subject to
\[x_1-x_2\le0,\] \[x_2\le1,\] \[x_1,x_2\ge0.\]Answer:
Every point with
\[x_1=x_2,\qquad 0\le x_1\le1\]is optimal, and $z^*=0$.
10. Unbounded because of a recession direction
\[\max -\frac12x_1+x_2\]subject to
\[2x_1+2x_2\le3,\] \[2x_1-2x_2\le3,\] \[-2x_1-2x_2\le3.\]Answer: unbounded above. One improving feasible direction is $d=(-1,1)$.
Exam checkpoint
Practice under exam timing. Write the full pipeline: model, standard form if needed, BFS/reduced costs if asked, simplex iterations if asked, final objective value and interpretation.