Chapter 5: Chapter 5

Solve the given LP problem. 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\) $$ \begin{aligned} \text { subject to } & x+y \geq 2 \\ & x+y \leq 10 \\ & x-y \leq 2 \\ & x-y \geq-2 . \end{aligned} $$

In Exercises 9-22, solve the given standard minimization problem using duality. (You may already have seen some of these in earlier sections, but now you will be solving them using \(a\) different method.) $$ \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} $$

$\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}$

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 \geq-5 $$

$\begin{array}{lr}\text { Minimize } & c=6 x+6 y \\ \text { subject to } & x+2 y \geq 20 \\ & 2 x+y \geq 20\end{array}$ \(x \geq 0, y \geq 0 .\) [HINT: See Example 3.]

In Exercises 9-22, solve the given standard minimization problem using duality. (You may already have seen some of these in earlier sections, but now you will be solving them using \(a\) different method.) $$ \begin{array}{ll} \text { Minimize } & c=3 s+2 t \\ \text { subject to } & s+2 t \geq 20 \\ & 2 s+t \geq 10 \\ & s \geq 0, t \geq 0 . \end{array} $$

$\begin{array}{lr}\text { Minimize } & c=3 x+2 y \\ \text { subject to } & x+2 y \geq 20 \\ & 2 x+y \geq 10\end{array}$ \(x \geq 0, y \geq 0 .\) [HINT: See Example 3.]

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

$\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}$

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