Standard Form Drill Set
Standard Form Drill Set
Course convention:
\[\min c^Tx\quad \text{s.t. } Ax=b,\; x\ge0.\]1. Max with two $\le$ constraints
Original:
\[\max 3x_1+x_2\]subject to
\[x_2\le4,\] \[6x_1+2x_2\le12,\] \[x_2\ge0.\]Here $x_1$ is free because no sign restriction is stated.
Solution: set $x_1=x_1^+-x_1^-$, with $x_1^+,x_1^-\ge0$.
\[\min -3x_1^+ +3x_1^- -x_2\]subject to
\[x_2+s_1=4,\] \[6x_1^+-6x_1^-+2x_2+s_2=12,\] \[x_1^+,x_1^-,x_2,s_1,s_2\ge0.\]2. Mixed $\le$, $\ge$, and $=$
Original:
\[\max x_1-5x_2+4x_3\]subject to
\[3x_1-2x_2+x_3=10,\] \[x_2+2x_3\le5,\] \[3x_1+5x_2+x_3\ge10,\] \[x_1,x_2,x_3\ge0.\]Solution:
\[\min -x_1+5x_2-4x_3\]subject to
\[3x_1-2x_2+x_3=10,\] \[x_2+2x_3+s_1=5,\] \[3x_1+5x_2+x_3-s_2=10,\] \[x_1,x_2,x_3,s_1,s_2\ge0.\]3. Negative RHS
Original:
\[\min 2x_1+x_2\]subject to
\[-x_1+x_2\le-2,\] \[x_1,x_2\ge0.\]Solution: first multiply the constraint by $-1$:
\[x_1-x_2\ge2.\]Then subtract surplus:
\[x_1-x_2-s_1=2,\] \[s_1\ge0.\]4. Free variable
Original:
\[\min x_1+3x_2\]subject to
\[x_1+2x_2=5,\] \[x_2\ge0,\]and $x_1$ is free.
Solution:
\[x_1=x_1^+-x_1^-,\qquad x_1^+,x_1^-\ge0.\]Standard form:
\[\min x_1^+-x_1^-+3x_2\]subject to
\[x_1^+-x_1^-+2x_2=5,\] \[x_1^+,x_1^-,x_2\ge0.\]5. Variable constrained nonpositive
Original:
\[\min x_1-2x_2\]subject to
\[x_1+x_2\le4,\] \[x_1\le0, \qquad x_2\ge0.\]Solution: set $x_1=-y_1$, $y_1\ge0$.
\[\min -y_1-2x_2\]subject to
\[-y_1+x_2+s_1=4,\] \[y_1,x_2,s_1\ge0.\]Practice without solutions
Convert each to standard form.
- $\max 2x_1+x_2$ subject to $x_1+2x_2\le2$, $-x_1+2x_2\le2$, $x_2\ge0$.
- $\min -x_1-x_2$ subject to $-x_1+x_2\le2$, $x_1+x_2\ge1$, $x_1\le1$, $x_1,x_2\ge0$.
- $\max 5x_1-5x_2$ subject to $x_1+x_2+x_3=4$, $-x_1+3x_2-6x_3\le-4$, $-3x_1+4x_2+4x_3\ge2$, $x\ge0$.
- $\min 12x_1+20x_2$ subject to $3x_1-4x_2\ge2$, $6x_1+2x_2\le8$, $5x_1-7x_2=-2$, $x\ge0$.
- $\min 6x_1-7x_2+9x_3$ subject to $3x_1+4x_2+x_3\ge9$, $2x_1+2x_2-5x_3\ge4$, $7x_1+3x_2+4x_3=10$, $x\ge0$.
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.