Applied optimization

$\newenvironment {prompt}{}{} \newcommand {\todo }[0]{} \newcommand {\npnoround }[0]{\nprounddigits {-1}} \newcommand {\npnoroundexp }[0]{\nproundexpdigits {-1}} \newcommand {\npunitcommand }[1]{\ensuremath {\mathrm {#1}}} \newcommand {\CancelColor }[0]{} \newcommand {\cancelto }[0]{1} \newcommand {\RR }[0]{\mathbb R} \newcommand {\R }[0]{\mathbb R} \newcommand {\N }[0]{\mathbb N} \newcommand {\Z }[0]{\mathbb Z} \newcommand {\d }[0]{\mathop {}\!d} \newcommand {\l }[0]{\ell } \newcommand {\ddx }[0]{\frac {d}{\d x}} \newcommand {\zeroOverZero }[0]{\ensuremath {\boldsymbol {\tfrac {0}{0}}}} \newcommand {\inftyOverInfty }[0]{\ensuremath {\boldsymbol {\tfrac {\infty }{\infty }}}} \newcommand {\zeroOverInfty }[0]{\ensuremath {\boldsymbol {\tfrac {0}{\infty }}}} \newcommand {\zeroTimesInfty }[0]{\ensuremath {\small \boldsymbol {0\cdot \infty }}} \newcommand {\inftyMinusInfty }[0]{\ensuremath {\small \boldsymbol {\infty -\infty }}} \newcommand {\oneToInfty }[0]{\ensuremath {\boldsymbol {1^\infty }}} \newcommand {\zeroToZero }[0]{\ensuremath {\boldsymbol {0^0}}} \newcommand {\inftyToZero }[0]{\ensuremath {\boldsymbol {\infty ^0}}} \newcommand {\numOverZero }[0]{\ensuremath {\boldsymbol {\tfrac {\#}{0}}}} \newcommand {\dfn }[0]{\textbf } \newcommand {\unit }[0]{\mathop {}\!\mathrm } \newcommand {\eval }[1]{\bigg [ #1 \bigg ]} \newcommand {\seq }[1]{\left ( #1 \right )} \newcommand {\epsilon }[0]{\varepsilon } \newcommand {\phi }[0]{\varphi } \newcommand {\iff }[0]{\Leftrightarrow } \DeclareMathOperator {\arccot }{arccot} \DeclareMathOperator {\arcsec }{arcsec} \DeclareMathOperator {\arccsc }{arccsc} \DeclareMathOperator {\si }{Si} \DeclareMathOperator {\proj }{\vec {proj}} \DeclareMathOperator {\scal }{scal} \DeclareMathOperator {\sign }{sign} \newcommand {\arrowvec }[0]{\overrightarrow } \newcommand {\vec }[0]{\mathbf } \newcommand {\veci }[0]{{\boldsymbol {\hat {\imath }}}} \newcommand {\vecj }[0]{{\boldsymbol {\hat {\jmath }}}} \newcommand {\veck }[0]{{\boldsymbol {\hat {k}}}} \newcommand {\vecl }[0]{\boldsymbol {\l }} \newcommand {\uvec }[1]{\mathbf {\hat {#1}}} \newcommand {\utan }[0]{\mathbf {\hat {t}}} \newcommand {\unormal }[0]{\mathbf {\hat {n}}} \newcommand {\ubinormal }[0]{\mathbf {\hat {b}}} \newcommand {\dotp }[0]{\bullet } \newcommand {\cross }[0]{\boldsymbol \times } \newcommand {\grad }[0]{\boldsymbol \nabla } \newcommand {\divergence }[0]{\grad \dotp } \newcommand {\curl }[0]{\grad \cross } \newcommand {\lto }[0]{\mathop {\longrightarrow \,}\limits } \newcommand {\bar }[0]{\overline } \newcommand {\surfaceColor }[0]{violet} \newcommand {\surfaceColorTwo }[0]{redyellow} \newcommand {\sliceColor }[0]{greenyellow} \newcommand {\vector }[1]{\left \langle #1\right \rangle } \newcommand {\sectionOutcomes }[0]{} \newcommand {\HyperFirstAtBeginDocument }[0]{\AtBeginDocument } \newcommand {\epstopdfsetup }[0]{\setkeys {ETE}} changed the theorem header of amsthm failed\MessageBreak }}} \newcommand {\GetTitleStringSetup }[0]{\setkeys {gettitlestring}} \newcommand {\Sectionformat }[2]{#1}$

Now we put our optimization skills to work.

In this section, we will present several worked examples of optimization problems. Our method for solving these problems is essentially the following:

Draw a picture.: If possible, draw a schematic picture with all the relevant information.
Determine your goal.: We need identify what needs to be optimized.
Find constraints.: What limitations are set on our optimization?
Solve for a single variable.: Now you should have a function to optimize.
Use calculus to find the extreme values.: Be sure to check your answer!

You are making cylindrical containers to contain a given volume. Suppose that the top and bottom are made of a material that is $N$ times as expensive (cost per unit area) as the material used for the lateral side of the cylinder. Find (in terms of $N$ ) the ratio of height to base radius of the cylinder that minimizes the cost of making the containers.

First we draw a picture:

Letting $c$ represent the cost of the lateral side, we can write an expression for the cost of materials: $C = 2\pi crh+\answer [given]{2\pi r^2Nc}.$ Since we know that $V=\pi r^2h$ , we can use this relationship to eliminate $h$ (we could eliminate $r$ , but it’s a little easier if we eliminate $h$ , which appears in only one place in the above formula for cost). We find $\begin{align*} C(r)&=2c\pi r\frac{V}{\pi r^2}+2Nc\pi r^2\\ &=\frac{2cV}{r}+2Nc\pi r^2. \end{align*}$ We want to know the minimum value of this function when $r$ is in $(0,\infty )$ . Setting $C'(r)=\answer [given]{-2cV/r^2+4Nc\pi r} =0$ we find $r=\sqrt [3]{V/(2N\pi )}$ . Since $C''(r)=\answer [given]{4cV/r^3+4Nc\pi }$ is positive when $r$ is positive, there is a local minimum at the critical value, and hence a global minimum since there is only one critical value.

Finally, since $h=V/(\pi r^2)$ ,

$\begin{align*} \frac{h}{r}&=\frac{V}{\pi r^3}\\ &=\frac{V}{\pi(V/(2N\pi))}\\ &=\answer[given]{2N}, \end{align*}$ so the minimum cost occurs when the height $h$ is $2N$ times the radius. If, for example, there is no difference in the cost of materials, the height is twice the radius.

You want to sell a certain number $n$ of items in order to maximize your profit. Market research tells you that if you set the price at $ $1.50$ , you will be able to sell $5000$ items, and for every $10$ cents you lower the price below $ $1.50$ you will be able to sell another $1000$ items. Suppose that your fixed costs (‘‘start-up costs’’) total $ $2000$ , and the per item cost of production (‘‘marginal cost’’) is $ $0.50$ . Find the price to set per item and the number of items sold in order to maximize profit, and also determine the maximum profit you can get.

The first step is to convert the problem into a function maximization problem. The revenue for selling $n$ items at $x$ dollars is given by $r(x) = nx$ and the cost of producing $n$ items is given by $c(x) = 2000+0.5 n.$ However, from the problem we see that the number of items sold is itself a function of $x$ , $n(x) =5000+\frac {1000(1.5-x)}{0.10}$ So profit is give by: $\begin{align*} P(x) &= r(x) - c(x)\\ &= nx - (2000+0.5 n)\\ &=-10000x^2+25000x-12000. \end{align*}$ We want to know the maximum value of this function when $x$ is between 0 and $1.5$ . The derivative is $P'(x)=\answer [given]{-20000x+25000},$ which is zero when $x=1.25$ . Since $P''(x)=-20000<0$ , there must be a local maximum at $x=1.25$ , and since this is the only critical value it must be a global maximum as well. Alternately, we could compute $P(0)=-12000$ , $P(1.25)=3625$ , and $P(1.5)=3000$ and note that $P(1.25)$ is the maximum of these. Thus the maximum profit is $ $3625$ , attained when we set the price at $ $1.25$ and sell $7500$ items.

If you fit the largest possible cone inside a sphere, what fraction of the volume of the sphere is occupied by the cone? (Here by ‘‘cone’’ we mean a right circular cone, i.e., a cone for which the base is perpendicular to the axis of symmetry, and for which the cross-section cut perpendicular to the axis of symmetry at any point is a circle.)

Let $R$ be the radius of the sphere, and let $r$ and $h$ be the base radius and height of the cone inside the sphere. Our goal is to maximize the volume of the cone: $V_c=\pi r^2h/3$ . The largest $r$ could be is $R$ and the largest $h$ could be is $2R$ .

Notice that the function we want to maximize, $\pi r^2h/3$ , depends on two variables. Our next step is to find the relationship and use it to solve for one of the variables in terms of the other, so as to have a function of only one variable to maximize. In this problem, the condition is apparent in the figure, as the upper corner of the triangle, whose coordinates are $(r,h-R)$ , must be on the circle of radius $R$ . Write $r^2 + (h-R)^2=R^2.$ Solving for $r^2$ , since $r^2$ is found in the formula for the volume of the cone, we find $r^2=R^2-(h-R)^2.$ Substitute this into the formula for the volume of the cone to find

$\begin{align*} V_{\text{c}}(h)&=\pi(R^2-(h-R)^2)h/3 \\ &=-{\pi\over3}h^3+{2\over3}\pi h^2R \end{align*}$

We want to maximize $V_{\text {c}}(h)$ when $h$ is between $0$ and $2R$ . We solve $V_{\text {c}}'(h)=\answer [given]{-\pi h^2+(4/3)\pi h R}=0,$ finding $h=0$ or $h=4R/3$ . We compute $V_{\text {c}}(0)=V_{\text {c}}(2R)=0$ and $V_{\text {c}}(4R/3)=(32/81)\pi R^3.$ The maximum is the latter. Since the volume of the sphere is $(4/3)\pi R^3$ , the fraction of the sphere occupied by the cone is $\frac {(32/81)\pi R^3}{(4/3)\pi R^3}=\frac {8}{27}\approx 30\%.$

A power line needs to be run from an power station located on the beach to an offshore facility.

It costs $50/ft. to run a power line along the land, and $130/ft. to run a power line under water. How much of the power line should be run along the land to minimize the overall cost? What is the minimal cost?

There are two immediate solutions that we could consider, each of which we will reject through ‘‘common sense.’’ First, we could minimize the distance by directly connecting the two locations with a straight line. However, this requires that all the wire be laid underwater, the most costly option. Second, we could minimize the underwater length by running a wire all 5000 ft. along the beach, directly across from the offshore facility. This has the undesired effect of having the longest distance of all, probably ensuring a nonminimal cost.

The optimal solution likely has the line being run along the ground for a while, then underwater, as the figure implies. We need to label our unknown distances: the distance run along the ground and the distance run underwater. Recognizing that the underwater distance can be measured as the hypotenuse of a right triangle, we can label our figure as follows

By choosing $x$ as we did, we make the expression under the square root simple. We now create the cost function: $\begin {array}{ccc} \text {Cost} = & & \\ \text {land cost} & + & \text {water cost} \\ \text {\$50}\times \text {land distance} &+& \text {\$130}\times \text {water distance} \\ 50(5000-x) &+& 130\sqrt {x^2+1000^2}.\\ \end {array}$ So we have $c(x) = \answer [given]{50(5000-x)+ 130\sqrt {x^2+1000^2}}.$ This function only makes sense on the interval $[0,5000]$ . While we are fairly certain the endpoints will not give a minimal cost, we still evaluate $c(x)$ at each to verify. $c(0) = 380000 \quad \quad c(5000) \approx 662873.$ We now find the critical points of $c(x)$ . We compute $c'(x)$ as $c'(x) = \answer [given]{-50+\frac {130x}{\sqrt {x^2+1000^2}}}.$ Recognize that this is never undefined. Setting $c'(x)=0$ and solving for $x$ , we have: $\begin{align*} -50+\frac{130x}{\sqrt{x^2+1000^2}} &= 0 \\ \frac{130x}{\sqrt{x^2+1000^2}} &= 50\\ \frac{130^2x^2}{x^2+1000^2} &= 50^2\\ 130^2x^2 &= 50^2(x^2+1000^2) \\ 130^2x^2-50^2x^2 &= 50^2\cdot1000^2\\ (130^2-50^2)x^2 &= 50000^2\\ x^2 &= \frac{50000^2}{130^2-50^2}\\ x &= \frac{50000}{\sqrt{130^2-50^2}}\\ x &= \frac{50000}{120}, \end{align*}$ Evaluating $c(x)$ at $x=416.67$ gives a cost of about $\$370000$ . The distance the power line is laid along land is $5000-416.67 = 4583.33\unit {ft}$ and the underwater distance is $\sqrt {416.67^2+1000^2} \approx 1083\unit {ft}$ .

We now work a similar problem without concrete numbers.

Suppose you want to reach a point $A$ that is located across the sand from a nearby road.

Suppose that the road is straight, and $b$ is the distance from $A$ to the closest point $C$ on the road. Let $v$ be your speed on the road, and let $w$ , which is less than $v$ , be your speed on the sand. Right now you are at the point $D$ , which is a distance $a$ from $C$ . At what point $B$ should you turn off the road and head across the sand in order to minimize your travel time to $A$ ?

Let $x$ be the distance short of $C$ where you turn off, the distance from $B$ to $C$ . We want to minimize the total travel time. Recall that when traveling at constant velocity, time is distance divided by velocity.

You travel the distance from $D$ to $B$ at speed $v$ , and then the distance from $B$ to $A$ at speed $w$ . The distance from $D$ to $B$ is $a-x$ . By the Pythagorean theorem, the distance from $B$ to $A$ is $\sqrt {x^2+b^2}.$ Hence the total time for the trip is $T(x)=\frac {a-x}{v}+\frac {\sqrt {x^2+b^2}}{w}.$ We want to find the minimum value of $T$ when $x$ is between 0 and $a$ . As usual we set $T'(x)=0$ and solve for $x$ . Write $T'(x)=\answer [given]{-1/v+\frac {x}{w\sqrt {x^2+b^2}}} =0.$ We find that $x=\frac {wb}{\sqrt {v^2-w^2}}$ Notice that $a$ does not appear in the last expression, but $a$ is not irrelevant, since we are interested only in critical values that are in $[0,a]$ , and $wb/\sqrt {v^2-w^2}$ is either in this interval or not. If it is, we can use the second derivative to test it: $T''(x) = \answer [given]{\frac {b^2}{(x^2+b^2)^{3/2}w}}.$ Since this is always positive there is a local minimum at the critical point, and so it is a global minimum as well.

If the critical value is not in $[0,a]$ it is larger than $a$ . In this case the minimum must occur at one of the endpoints. We can compute

$\begin{align*} T(0)&={a\over v}+{b\over w} \\ T(a)&={\sqrt{a^2+b^2}\over w} \end{align*}$ but it is difficult to determine which of these is smaller by direct comparison. If, as is likely in practice, we know the values of $v$ , $w$ , $a$ , and $b$ , then it is easy to determine this. With a little cleverness, however, we can determine the minimum in general. We have seen that $T''(x)$ is always positive, so the derivative $T'(x)$ is always increasing. We know that at $wb/\sqrt {v^2-w^2}$ the derivative is zero, so for values of $x$ less than that critical value, the derivative is negative. This means that $T(0)>T(a)$ , so the minimum occurs when $x=a$ .

So the upshot is this: If you start farther away from $C$ than $wb/\sqrt {v^2-w^2}$ then you always want to cut across the sand when you are a distance $wb/\sqrt {v^2-w^2}$ from point $C$ . If you start closer than this to $C$ , you should cut directly across the sand.

With optimization problems you will see a variety of situations that require you to combine problem solving skills with calculus. Focus on the process. One must learn how to form equations from situations that can be manipulated into what you need. Forget memorizing how to do ‘‘this kind of problem’’ as opposed to ‘‘that kind of problem.’’

Learning a process will benefit one far more than memorizing a specific technique.