Problems for Chapter 8

Section 8.4 Problems for Chapter 8

The simplex pivoter may be found here:

Hint.

Exercises Exercises

1.

For each of the linear optimization problems, solve the linear relaxation problem, then use the graphical method to find a solution if we restrict to integer values.

(a)

\begin{align*} \textbf{Maximize: } f(x_1, x_2) = \amp 3x_1+2x_2\\ \textbf{subject to: } 2x_1+4x_2\amp \leq 15\\ 5x_1+3x_2 \amp \leq 22\\ x_1,x_2\amp \geq 0\text{ and integral.} \end{align*}

(b)

\begin{align*} \textbf{Minimize: } g(x_1, x_2) = \amp 10x_1+x_2\\ \textbf{subject to: } 3x_1-2x_2\amp \geq 15\\ 7x_1+4x_2 \amp \leq 50\\ x_1,x_2\amp \geq 0\text{ and integral.} \end{align*}

(c)

\begin{align*} \textbf{Maximize: } h(x_1, x_2) = \amp 5x_1+4x_2\\ \textbf{subject to: } 3x_1+8x_2\amp \leq 13\\ 4x_1-3x_2 \amp \leq 25\\ x_1\amp \geq 0\text{ and } x_1, x_2\text{ are integral.} \end{align*}

2.

Prove or find a counterexample: Let $\x$ be the solution to the linear relaxation to an integer optimization problem, such that $\x$ has only integer coordinates. Then $\x$ is a solution to the original integral problem.

3.

Come up with 2 maximization problems, one two dimensional and one three dimensional, where only integer solutions are sensible, and explain why these problems should be integral problems. Then do the same for two minimization problems.

4.

For each of the following integer optimization problems, find an integral solution using the branch and bound method, and using the cutting plane method.

(a)

\begin{align*} \textbf{Maximize: } f(x_1, x_2) = \amp 5x_1+4x_2\\ \textbf{subject to: } 3x_1+4x_2\amp \leq 10\\ x_1,x_2\amp \geq 0\text{ and integral.} \end{align*}

(b)

\begin{align*} \textbf{Minimize: } g(x_1, x_2) = \amp 3x_1+6x_2\\ \textbf{subject to: } 7x_1+3x_2\amp \geq 40\\ x_1,x_2\amp \geq 0\text{ and integral.} \end{align*}

(c)

\begin{align*} \textbf{Maximize: } h(x_1, x_2) = \amp x_1+x_2\\ \textbf{subject to: } 3x_1+2x_2\amp \leq 5\\ x_2 \amp \leq 2\\ x_1,x_2\amp \geq 0\text{ and integral.} \end{align*}

(d)

\begin{align*} \textbf{Maximize: } \alpha(x,y) = \amp 2x+y\\ \textbf{subject to: } 3x+y\amp \leq 13\\ -x+2y \amp \leq 6\\ x, y\amp \geq 0\text{ and integral.} \end{align*}

(e)

\begin{align*} \textbf{Minimize: } \beta(x,y) = \amp x-y\\ \textbf{subject to: } 3x+4y\amp \leq 6\\ x-y \amp \leq 1\\ x, y\amp \geq 0\text{ and integral.} \end{align*}

(f)

\begin{align*} \textbf{Maximize: } f(x,y) = \amp 8x+3y\\ \textbf{subject to: } 2x+y\amp \leq 13\\ 2x \amp \leq 5\\ x, y\amp \geq 0\text{ and integral.} \end{align*}

(g)

\begin{align*} \textbf{Maximize: } f(x_1,x_2,x_3) = \amp -4x_1+x_2+2x_3\\ \textbf{subject to: } 2x_1+3x_2 \amp \leq 28\\ -x_1+x_3\amp \leq 12\\ x_1, x_2, x_3\amp \geq 0\text{ and integral.} \end{align*}

5.

Solve the following integer optimization problems.

(a)

A potter makes sculptures and bowls out of clay. It takes $8$ hours and $2$ pounds of clay to make a sculpture, $2$ hours and $2$ pounds of clay for a bowl. She has $50$ hours a week and $30$ pounds of clay with which to make things. She can sell sculptures for $$200$ and bowl for $$20\text{.}$ How much of each should she make to maximize revenue?

(b)

A man is preparing food for a party at his house, and is making sure there is enough. A chicken pot pie takes $300$ g of flour and $450$ g of chicken. He air and land wellington takes $240$ g of flour, $150 g$ of chicken and $1000$ g of beef. Evidently he knows no other recipes. He has $2400$ g of flour, $2700$ g of chicken and $6000$ g of beef. The pot pies feed 2 people, the wellington 8. How many of each should he make?

(c)

A family of 12 gnomes have three mines $A, B$ and $C$ from which to dig gems. A gnome digging in mine $A$ can dig up $108$ gems a week, $75$ gems a week in mine $B$ and $120$ gems a week in mine $C\text{.}$ They have a budget of 75 gold pieces a month for operating expenses. A gnome digging in mine $A$ has expenses of $7$ gp a month, $5$ gp a month in mine $B\text{,}$ and $16$ gp a month in mine $C\text{.}$ Due to size limitations, at most 5 gnomes can dig in mine $C\text{.}$ How should this family distribute the gnomes amongst the mines to maximize gem production?

6.

(a)

What do you think would happen if the Gomory Plane Cutting algorithm Definition 8.2.4 was applied to a linear optimization problem where the relaxed problem achieved optimality, but the integral restriction had no solutions?

(b)

Test your conjecture on the following problem:

\begin{align*} \textbf{Maximize: } f(x,y) = \amp 2x+y\\ \textbf{subject to: } 3x+3y\amp \leq 2\\ 4y \amp \geq 1\\ x,y\amp \geq 0\text{ and integral.} \end{align*}

7.

Consider a primal integral linear maximization problem with objective function $f$ such that the integral problem has an optimal solution $\x'\text{.}$ Then for each of the following find a counterexample.

(a)

The linear relaxation of this primal problem also achieves optimality. (Think irrational numbers.)

(b)

Suppose that the linear relaxation also achieves optimality at $\x''\text{,}$ then the integral dual to the original integral max problem must also achieve an optimal solution.

(c)

Suppose that the linear relaxation also achieves optimality at $\x''$ such that $f(\x')< f(\x'')\text{.}$ Suppose the dual to the integral maximization problem achieved optimality at $\y'\text{,}$ and let $\y''$ denote the dual to the relaxation. Then $g(\y')> g(\y'')$ where $g$ is the objective function of the dual.

Prev Top Next