Chapter 4

$$ \begin{array}{ll} \text { Maximize } & p=2 x+y \\ \text { subject to } & x+2 y \leq 6 \\ & -x+y \leq 2 \\ & x \geq 0, y \geq 0 . \end{array} $$

\(\begin{array}{ll}\operatorname{Maximize} & p=x+y \\ \text { subject to } & x+2 y \geq 6 \\ & -x+y \leq 4 \\ & 2 x+y \leq 8 \\ & x \geq 0, y \geq 0 .\end{array}\)

\(\begin{array}{ll}\text { Maximize } & p=2 x+y \\ \text { subject to } & x+2 y \leq 6 \\ -x+y & x+4 \\ & x+y \leq 4 \\ x & \geq 0, y \geq 0 .\end{array}\)

Sketch the region that corresponds to the given inequalities, say whether the region is bounded or unbounded, and find the coordinates of all corner points (if any). $$ 2 x+y<10 $$

$$ \begin{array}{ll} \text { Maximize } & p=x+5 y \\ \text { subject to } & x+y \leq 6 \\ & -x+3 y \leq 4 \\ & x \geq 0, y \geq 0 . \end{array} $$

Solve the LP problems. If no optimal solution exists, indicate whether the feasible region is empty or the objective function is unbounded. Maximize \(\begin{aligned} \text { subject to } & p=x+2 y \\ & x+3 y \leq 24 \\\ & 2 x+y \leq 18 \\ & x \geq 0, y \geq 0 . \end{aligned}\)

Maximize \(p=3 x+2 y\) subject to \(\quad x+3 y \geq 6\) \(-x+y \leq 4\) \(2 x+y \leq 8\) \(x \geq 0, y \geq 0 .\)

Maximize \(\quad p=x\) subject to \(\begin{aligned} x &-y \leq 4 \\\\-x &+3 y \leq 4 \\ & x \geq 0, y \geq 0 . \end{aligned}\)

Sketch the region that corresponds to the given inequalities, say whether the region is bounded or unbounded, and find the coordinates of all corner points (if any). $$ 4 x-y \leq 12 $$

$$ \begin{array}{cc} \text { Minimize } & c=2 s+t+3 u \\ \text { subject to } & s+t+u \geq 100 \\ & 2 s+t \quad \geq 50 \\ & s \geq 0, t \geq 0, u \geq 0 . \end{array} $$

Solve the LP problems. If no optimal solution exists, indicate whether the feasible region is empty or the objective function is unbounded. Minimize \(\quad c=x+y\) subject to \(\begin{aligned} x+2 y & \geq 6 \\ 2 x+y & \geq 6 \\ x \geq 0, y & \geq 0 . \end{aligned}\)

\(\begin{array}{lc}\text { Maximize } & p=12 x+10 y \\ \text { subject to } & x+y \leq 25 \\ & x \quad \geq 10 \\ & -x+2 y \geq 0 \\ x & \geq 0, y \geq 0 .\end{array}\)

\(\begin{array}{ll}\text { Maximize } & p=x-y \\ \text { subject to } & 5 x-5 y \leq 20 \\ & 2 x-10 y \leq 40 \\ & x \geq 0, y \geq 0 .\end{array}\)

Sketch the region that corresponds to the given inequalities, say whether the region is bounded or unbounded, and find the coordinates of all corner points (if any). $$ -x-2 y \leq 8 $$

$$ \begin{array}{ll} \text { Minimize } & c=2 s+2 t+3 u \\ \text { subject to } & s \quad+u \geq 100 \\ & 2 s+t \quad \geq 50 \\ & s \geq 0, t \geq 0, u \geq 0 . \end{array} $$

Solve the LP problems. If no optimal solution exists, indicate whether the feasible region is empty or the objective function is unbounded. \(\begin{aligned} \text { Minimize } & c=x+2 y \\ \text { subject to } & x+3 y \geq 30 \\ & 2 x+y \geq 30 \\ & x \geq 0, y \geq 0 . \end{aligned}\)

\(\begin{array}{cc}\text { Maximize } & p=x+2 y \\ \text { subject to } & x+y \leq 25 \\ y & \geq 10 \\ & 2 x-y \geq 0 \\ & x \geq 0, y \geq 0 .\end{array}\)

\(\begin{array}{ll}\text { Maximize } & p=2 x+3 y \\ \text { subject to } & 3 x+8 y \leq 24 \\ & 6 x+4 y \leq 30 \\ & x \geq 0, y \geq 0 .\end{array}\)

Sketch the region that corresponds to the given inequalities, say whether the region is bounded or unbounded, and find the coordinates of all corner points (if any). $$ -x+2 y \geq 4 $$

$$ \begin{array}{ll} \text { Maximize } & p=x+y+z+w \\ \text { subject to } & x+y+z \leq 3 \\ & y+z+w \leq 4 \\ & x+z+w \leq 5 \\ & x+y+w \leq 6 \\ & x \geq 0, y \geq 0, z \geq 0, w \geq 0 \end{array} $$

Solve the LP problems. If no optimal solution exists, indicate whether the feasible region is empty or the objective function is unbounded. Maximize \(\begin{aligned} & p=3 x+y \\ \text { subject to } & 3 x-7 y \leq 0 \\\ & 7 x-3 y \geq 0 \\ & x+y \leq 10 \\ & x \geq 0, y \geq 0 . \end{aligned}\)

\(\begin{array}{ll}\text { Maximize } & p=2 x+5 y+3 z \\ \text { subject to } & x+y+z \leq 150 \\ & x+y+z \geq 100 \\ & x \geq 0, y \geq 0, z \geq 0 .\end{array}\)

\(\begin{array}{ll}\text { Maximize } & p=5 x-4 y+3 z \\ \text { subject to } & 5 x+5 z \leq 100 \\ & 5 y-5 z \leq 50 \\ & 5 x-5 y \leq 50 \\ & x \geq 0, y \geq 0, z \geq 0\end{array}\)

Sketch the region that corresponds to the given inequalities, say whether the region is bounded or unbounded, and find the coordinates of all corner points (if any). $$ 3 x+2 y \geq 5 $$

$$ \begin{array}{ll} \text { Maximize } & p=x+y+z+w \\ \text { subject to } & x+y+z \leq 3 \\ & y+z+w \leq 3 \\ & x+z+w \leq 4 \\ & x+y+w \leq 4 \\ & x \geq 0, y \geq 0, z \geq 0, w \geq 0 . \end{array} $$

Solve the LP problems. If no optimal solution exists, indicate whether the feasible region is empty or the objective function is unbounded. Maximize \(\quad p=x-2 y\) subject to \(\begin{aligned} x+2 y & \leq 8 \\ x-6 y & \leq 0 \\ 3 x-2 y & \geq 0 \\ x \geq 0, y & \geq 0 . \end{aligned}\)

\(\begin{array}{ll}\text { Maximize } & p=3 x+2 y+2 z \\ \text { subject to } & x+y+2 z \leq 38 \\ & 2 x+y+z \geq 24 \\ & x \geq 0, y \geq 0, z \geq 0 .\end{array}\)

\(\begin{array}{ll}\text { Maximize } & p=6 x+y+3 z \\ \text { subject to } & 3 x+y \quad \leq 15 \\ & 2 x+2 y+2 z \leq 20 \\ & x \geq 0, y \geq 0, z \geq 0 .\end{array}\)

Sketch the region that corresponds to the given inequalities, say whether the region is bounded or unbounded, and find the coordinates of all corner points (if any). $$ 2 x-3 y \leq 7 $$

$$ \begin{array}{ll} \text { Minimize } & c=s+3 t+u \\ \text { subject to } & 5 s-t \quad+v \geq 1,000 \\ u-v & \geq 2,000 \\ & \quad s+t \quad \geq 500 \\ & s \geq 0, t \geq 0, u \geq 0, v \geq 0 . \end{array} $$

Solve the LP problems. If no optimal solution exists, indicate whether the feasible region is empty or the objective function is unbounded. Maximize \(\quad p=3 x+2 y\) subject to \(\begin{aligned} 0.2 x+0.1 y & \leq 1 \\ 0.15 x+0.3 y & \leq 1.5 \\\ 10 x+10 y & \leq 60 \\ x \geq 0, y \geq 0 & \end{aligned}\)

\(\begin{array}{ll}\text { Maximize } & p=2 x+3 y+z+4 w \\ \text { subject to } & x+y+z+w \leq 40 \\ & 2 x+y-z-w \geq 10 \\ & x+y+z+w \geq 10 \\ & x \geq 0, y \geq 0, z \geq 0, w \geq 0 .\end{array}\)

\(\begin{array}{ll}\text { Maximize } & p=7 x+5 y+6 z \\ \text { subject to } & x+y-z \leq 3 \\ & x+2 y+z \leq 8 \\ & x+y \quad \leq 5 \\ & x \geq 0, y \geq 0, z \geq 0 .\end{array}\)

$$ \begin{aligned} \text { Minimize } c=5 s+2 u+v \\ \text { subject to } s-t \quad+2 v \geq 2,000 \\ u+v \geq 3,000 \\ s+t & \geq 500 \\ s \geq 0, t \geq 0, u \geq 0, v \geq 0 . \end{aligned} $$

Solve the LP problems. If no optimal solution exists, indicate whether the feasible region is empty or the objective function is unbounded. Maximize \(\quad \begin{array}{ll}\text { subject to } & p=x+2 y \\ & 30 x+20 y \leq 600 \\ & 0.1 x+0.4 y \leq 4 \\ & 0.2 x+0.3 y \leq 4.5 \\ & x \geq 0, y \geq 0\end{array}\)

Maximize \(\quad p=2 x+2 y+z+2 w\) subject to \(\quad x+y+z+w \leq 50\) \(2 x+y-z-w \geq 10\) \(\quad x+y+z+w \geq 20\) \(x \geq 0, y \geq 0, z \geq 0, w \geq 0 .\)

\(\begin{array}{ll}\text { Maximize } & p=3 x+4 y+2 z \\ \text { subject to } & 3 x+y+z \leq 5 \\ & x+2 y+z \leq 5 \\ & x+y+z \leq 4 \\ & x \geq 0, y \geq 0, z \geq 0\end{array}\)

Sketch the region that corresponds to the given inequalities, say whether the region is bounded or unbounded, and find the coordinates of all corner points (if any). $$ y \geq 3 x $$

Solve the LP problems. If no optimal solution exists, indicate whether the feasible region is empty or the objective function is unbounded. Minimize \(c=0.2 x+0.3 y\) subject to \(\begin{aligned} 0.2 x+0.1 y & \geq 1 \\\ 0.15 x+0.3 y & \geq 1.5 \\ 10 x+10 y & \geq 80 \\ x \geq 0, y \geq 0 & \end{aligned}\)

\(\begin{aligned} \text { Minimize } & c=6 x+6 y \\ \text { subject to } & x+2 y \geq 20 \\ & 2 x+y \geq 20 \\ & x \geq 0, y \geq 0 . \end{aligned}\)

\(\begin{array}{ll}\text { Maximize } & z=3 x_{1}+7 x_{2}+8 x_{3} \\ \text { subject to } & 5 x_{1}-x_{2}+x_{3} \leq 1,500 \\ & 2 x_{1}+2 x_{2}+x_{3} \leq 2,500 \\ & 4 x_{1}+2 x_{2}+x_{3} \leq 2,000 \\ & x_{1} \geq 0, x_{2} \geq 0, x_{3} \geq 0\end{array}\)

Sketch the region that corresponds to the given inequalities, say whether the region is bounded or unbounded, and find the coordinates of all corner points (if any). $$ \frac{3 x}{4}-\frac{y}{4} \leq 1 $$

$$ \begin{aligned} \text { Minimize } & c=s+t \\ \text { subject to } & s+2 t \geq 6 \\ & 2 s+t \geq 6 \\ & s \geq 0, t \geq 0 . \end{aligned} $$

Solve the LP problems. If no optimal solution exists, indicate whether the feasible region is empty or the objective function is unbounded. Minimize \(\quad \begin{aligned} & c=0.4 x+0.1 y \\ \text { subject to } & 30 x+20 y \geq 600 \\ & 0.1 x+0.4 y \geq 4 \\ & 0.2 x+0.3 y \geq 4.5 \\ & x \geq 0, y \geq 0 \end{aligned}\)

\(\begin{aligned} \text { Minimize } & c=3 x+2 y \\ \text { subject to } & x+2 y \geq 20 \\ & 2 x+y \geq 10 \\ & x \geq 0, y \geq 0 . \end{aligned}\)

\(\begin{array}{ll}\text { Maximize } & z=3 x_{1}+4 x_{2}+6 x_{3} \\ \text { subject to } & 5 x_{1}-x_{2}+x_{3} \leq 1,500 \\ & 2 x_{1}+2 x_{2}+x_{3} \leq 2,500 \\ & 4 x_{1}+2 x_{2}+x_{3} \leq 2,000 \\ & x_{1} \geq 0, x_{2} \geq 0, x_{3} \geq 0\end{array}\)

Sketch the region that corresponds to the given inequalities, say whether the region is bounded or unbounded, and find the coordinates of all corner points (if any). $$ \frac{x}{3}+\frac{2 y}{3} \geq 2 $$

$$ \begin{aligned} \text { Minimize } & c=6 s+6 t \\ \text { subject to } & s+2 t \geq 20 \\ & 2 s+t \geq 20 \\ & s \geq 0, t \geq 0 . \end{aligned} $$

$$ \begin{array}{ll} \text { Minimize } & c=6 s+6 t \\ \text { subject to } & s+2 t \geq 20 \\ & 2 s+t \geq 20 \\ & s \geq 0, t \geq 0 \end{array} $$

Solve the LP problems. If no optimal solution exists, indicate whether the feasible region is empty or the objective function is unbounded. Maximize and minimize \(\quad p=x+2 y\) subject to \(\begin{aligned} & x+y \geq 2 \\ & x+y \leq 10 \\ & x-y \leq 2 \\\ & x-y \geq-2 . \end{aligned}\)