Greff
Greff
Optimization Problems
Teylor Greff
Mathematics Department
Whitman College
May 2016
Abstract: Do we actually need calculus to solve maximum/minimum
problems? Optimization problems are explored and solved using the AM/GM
inequality and Cauchy Schwarz inequality, while simultaneously finding trends
and evolutions in these optimization problems as we look at a textbooks
ranging from 1902 − 2015.
Contents
1 Introduction 3
1
4.2.2 Specific Solution . . . . . . . . . . . . . . . . . . . . . 19
4.2.3 Similar Problem Examples . . . . . . . . . . . . . . . . 19
4.3 Post Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.3.1 Generalized Solution . . . . . . . . . . . . . . . . . . . 20
4.3.2 Specific Solution . . . . . . . . . . . . . . . . . . . . . 21
4.3.3 Similar Problem Examples . . . . . . . . . . . . . . . . 21
6 The CS Inequality 25
6.1 Formal Proof - CS . . . . . . . . . . . . . . . . . . . . . . . . 25
8 Historical Bit 29
8.1 Economic/Medical/Physical Problems . . . . . . . . . . . . . . 29
9 Conclusion 30
2
1 Introduction
The focus of this paper is optimization problems in single and multi-variable
calculus spanning from the years 1900 − 2016. The main goal was to see if
there was a way to solve most or all optimization problems without using any
calculus, and to see if there was a relationship between this discovery and
the published year of the optimization problems. The primary method used
to accomplish this was the Arithmetic Mean/Geometric Mean inequality,
but upon further exploration, the Cauchy Schwarz inequality and other
generalized solutions proved to be incredibly helpful as well. This paper
lays out how these problems are solved, gives examples of similar problems,
and also explores the historical evolution of these problems.
Since the diameter of the circle is a + b, its radius is (a + b)/2. The red
line represents the arithmetic mean of a and b.
3
A C P B
a b
A C P B
a b
Therefore, the altitude is the geometric mean shown in blue, and is clearly
less than the hypotenuse.
4
D
AM GM
A C P B
a b
5
showing that the result is true when n = 2. Now suppose the result is
valid for some positive integer p ≥ 2. Let b1 , b2 , ..., bp , bp+1 be positive real
numbers that are not all equal and satisfy b1 b2 · · · bp bp+1 = 1. Without loss
of generality, we may assume that the numbers are in increasing order, that
is, b1 ≤ b2 ≤ · · · ≤ bp ≤ bp+1 . By the assumptions on these numbers, we
must have b1 < 1 < bp+1 . Since the conclusion of the lemma is assumed to
be true when n = p, we consider the product (b1 bp+1 )b2 · · · bp = 1, which is a
product of p numbers. If all of these numbers are equal (and thus all equal
1), then
b2 + b2 + · · · + bp = p − 1 and b1 + bp+1 > 2
(the inequality follows from the first part of the proof) and it follows that
b1 + b2 + · · · + bp + bp+1 > p + 1.
b1 bp+1 + b2 + · · · + bp > p
6
Now, suppose for n ≥ 2, all ak ’s are positive, and that not all of ak ’s are
1
equal to each other. If we let r = (a1 a2 ...an ) n , we get the following result,
a1 a2 an a1 a2 · · · an
··· = = 1.
r r r rn
By the lemma, it follows that,
a1 a2 an
+ + ··· + > n.
r r r
Multiplying through by r and dividing by n, we find that,
a1 + a2 + · · · + an 1
> r = (a1 a2 · · · an ) n . [7]
n
This completes the proof.
7
river
x x
maximize xy subject to 2x + y = 2.
we can take the derivative and set it equal to zero to find our maximal points:
1
0 = 2 − 4x and hence x = .
2
We have thus shown for the fencing to have maximum area, it will have a
width of 1/2 miles, and length of 1 mile.
maximize xy subject to 2x + y = 2.
2x = 1 = y.
8
We have thus shown that the maximum area of the landowners fencing has
length of 1/2 miles, and width of 1 mile.
Fence problems, such as this one, give a good idea of how to apply the
AM/GM inequality to optimization problems. However, as we will see in the
next section, some care is needed when applying it, as not all problems work
out as cleanly as this one.
9
conditions. The following example shows a problem that can occur when
using the AM/GM inequality. It often can appear unhelpful if used carelessly.
We will show what must occur in order for the AM/GM inequality to solve an
optimization problem correctly by first showing what goes wrong if applied
carelessly, and then showing how to carefully apply it.
Example 9. Divide the number 20 into two parts such that the product of
one part by the square of the other part shall be a maximum. [8]
However, we notice that this states a maximum value for xy, when we are
looking for a maximum value of x2 y. This is where the inequality appears
unhelpful. Fortunately, there is a way to work around this as shown below.
We notice that this states the maximum value for x2 y is 32000/27 and this
value is attained when
1 20
x= = y.
2 3
Thus, we have shown that the maximum product of x2 y is when y = 20/3 ≈
13.33 and x = 40/3 ≈ 6.67.
10
This same idea will appear in many optimization problems when using the
AM/GM inequality. In order to solve these problems correctly, we must make
sure that the AM/GM is maximizing the quantity desired. The constraint
must multiply through to the get the value being maximized or vice versa.
In situations where both the constraint and the max/min function contain
addition, the AM/GM proves to be unhelpful. This will further be explored
in the Non-AM/GM Generalized Problems section.
Example 11. Divide the number 10 into two parts such that the square of
one part multiplied by the cube of the other shall be a maximum. [12]
3.3.1 Application
Example 12. Determine the ratio of significant dimensions so as to attain
the maximum volume of a cone in a sphere. [6]
11
h
Suppose that R is the radius of the sphere. Let h and r be the height
and radius of the cone, respectively. We want to maximize the volume V
of the cone, where V = πr2 h/3. Referring to the figure, we note that h
will be larger than R when the volume of the cone is maximized. By the
Pythagorean Theorem,
(h − R)2 + r2 = R2 and thus h2 + r2 = 2Rh.
The problem of maximizing the volume of the cone can now be reduced to
the following:
2r2
maximize r2 h subject to 2h + = 4R.
h
By the AM/GM inequality, we find that
2r2 √
3
3
1 4R 32
2
4R = h + h + 2
≥ 3 2r h and hence r h ≤ = R3 .
h 2 3 27
The maximum value for r2 h is thus 32R3 /27 and this value is attained when
4R 2r2
h= = .
3 h
√
Since h2 = 2r2 , the ratio of height to radius for the optimal cone is 2. We
have thus shown that the maximum volume of a cone inscribed in a sphere
of radius R is
1 2 π 32 8 4 3
πr h = · R3 = · πR ,
3 3 27 27 3
that is, the maximal cone occupies 8/27 of the volume of the entire sphere.
12
3.3.2 Similar Problem Examples
Example 13. Find the maximum right cylinder that can be inscribed in a
sphere of radius a. [12]
3.4.1 Application
Example 14. A rectangular building is being designed to minimize heat loss.
The east and the west walls lose heat at a rate of 10 units/m2 per day, the
north and south walls at a rate of 8 units/m2 per day, the floor at a rate of
1 unit/m2 , and the roof at a rate of 5 units/m2 per day. The volume must
be exactly 4000 m3 . Find the dimensions that minimize heat loss. [9]
u
5 m2
u
10 m2
h 8 u
m2 y
Suppose that x is the length of the box, y is the width of the box and h
is the height of the box. We want to minimize the heat loss function, f (x),
where f (x) = 20hy + 16xh + 6xy. The problem of minimizing the heat loss
can be reduced to the following:
13
Since it follows that y = 8/3h from 20hy = 16xh = 6xy, the minimum value
is thus attained when
p
(20h)(8/3h) ≥ 3 1920(4000)2 .
Solving for h we find the optimal box to have h ≈ 7.6, y = 20.4 and x = 25.5.
Another interesting thing to note is the use of economic ideas in this calculus
problem. Looking through old books, economic and medical applications
did not begin appearing until around the 1970’s when calculus became a
requirement for other disciplines besides just mathematics. Further exploration
of this will be shown in the Historical Bit section of this paper.
14
generalized to a simple solution. If a student was able to recognize a problem
as a “Triathalon” Problem, they could plug into the generalized solution
without using any calculus. One of these problems is shown below, first
using calculus, then using the generalized solution on a “different” problem.
Example 17. A man who can row at a speed of 4 miles per hour and run at
a speed of 6 miles per hour wishes to reach the point P from a boat at point
B as shown in the figure below in the least amount of time as possible. Find
the distance AP that the man must run on the beach. [8]
B
√ x
2
b
+
b2
C x P
A a−x
15
√
9x2 = 2 102 + x2 ,
5x2 = 400,
√
x = 80.
We have shown√to minimize the time to get from B to P is by traveling to
the point
√ A at 80 miles from point C. The distance from C to P is thus
10 − 80 ≈ 1.056 miles.
While this result is correct, we can make it much simpler for later similar
problems by generalizing the solution.
r 2 x2 = s 2 x2 + s 2 b 2 ,
s 2 b2
x2 = ,
r 2 − s2
sb
x= √ .
r 2 − s2
What is perhaps the most interesting result about this is that a does not
appear in our general equation, suggesting that after a certain point, no
matter how long a is, the person should still always arrive at the same point.
Also note r > s. Further, any problem set up in a similar manner can simply
applied with the above equation. An example of this is shown below.
Example 18. It is known that homing pigeons fly faster over land than over
water. Assume that they fly 10 meters per second over land, but only 8 meters
per second over water. If a pigeon is located at the edge of a straight river
500 meters wide and must fly to its nest, located 1300 meters away on the
opposite side of the river. What path would minimize its flying time? [5]
16
B
√ x
130
2
0
+
b = 500
50
0
C x 2 N
A a−x
Once we use the Pythagorean Theorem to find that a = 1200, all we have
to do is plug into the general equation,
(1/10)(500) 2000
x= p = .
(1/8)2 − (1/10)2 3
Therefore, the bird should fly to a point A, which is 2000/3 ≈ 666.67 meters
east of point C to minimize their time.
Example 20. A man is in a boat 2 miles from the nearest point on the coast.
He is to go to a point Q, 3 miles down the coast and 1 mile inland. If he can
row at 2 miles per hour and walk at 4 miles per hour, toward what point on
the coast should he row in order to reach point Q in the least time? [2]
17
4.2 Pipe Corridor Problem
The Pipe Corridor problem is another frequently used problem, especially in
later textbooks. Again, we can find a generalized solution so that once we
know how to identify a Pipe Corridor problem, we can simply plug into our
generalized result.
Example 21. Find the length of the longest thin, rigid pipe that can be
carried from one 10 foot wide corridor to a similar corridor at right angles
to the first. Assume that the pipe has negligible diameter. [5]
B
x
y a
p
Since x = by/ y 2 − a2 , we want to minimize L, but find the longest pipe,
by
L(y) = p + y.
y 2 − a2
We can take the derivative and set equal to zero to find our minimal points:
a2 b
L0 (y) = 1 − = 0,
(y 2 − a2 )(3/2)
18
(y 2 − a2 )(3/2) = a2 b,
p
y = a4/3 b2/3 + a2 .
Much like the “Triathlon Problem,” any problem with a similar set-up can
be plugged into the above equation. We will now solve the original problem
given the equation obtained.
Example 23. Two posts, one 8 feet high and the other 12 feet high, stand
15 ft apart. They are to be supported by wires attached to a single stake at
ground level, the wires running to the tops of the posts. Where should the
stake be placed, to use the least amount of wire? [13]
19
b
a
x (c − x)
c
t b
a s
x (c − x)
t −b
We are looking for the shortest distance between these two points as we
are trying to minimize the amount of wire used. Finding the slope between
the two points, and plugging into point slope form gives:
∆y a+b a+b
= = ,
∆x 0−c c
20
a+b
y=− x + a.
c
Finding where this line intersects the x axis gives the desired result.
a+b
0=− + a,
c
ac
x= .
a+b
Example 25. Two towns, located on the same side of a straight river, agree
to construct a pumping station and filtering plant at the river’s edge, to be
used jointly to supply the towns with water. If the distances of the two towns
from the river are a and b and the distance between them is c, show that the
sum of the lengths√ of the pipe lines joining them to the pumping station is at
least as great as c2 + 4ab. [4]
21
more complex story problems including Triathlon, Pipe Corridor, and Post
Problems. What we find is that while later books appear to include more
complex examples, when reduced down to what they are maximizing/minimizing
and their constraints, we see that they are in fact the same problem. Below
are two examples of problems and how they evolved from their early format.
2y + x = 20
y
y
2y + x = 20
Suppose that y is the length of the corner square, x is the distance between
the y’s. The problem of maximizing the volume of the box can now be
reduced to the following:
Example 27. Divide the number 20 into two parts such that the product of
one part by the square of the other part shall be a maximum. [8]
22
We are trying to maximize the product considering the following:
While at first glance, these problems appear very different, they are
reduced down to the same problem. From here, each problem can easily
be solved using the AM/GM inequality. Another example of a problem we
saw evolve twice from 1900 − 2016 is shown below.
Example 29. A right triangle in the first quadrant has two coordinate axes as
sides and the hypotenuse passes through the point (10, 10). Find the vertices
of the triangle such that the length of the hypotenuse is a minimum. [8]
D (10, 10)
Without much effort, we can recognize this problem is the same problem
as the Pipe Down the Corridor problem that we solved earlier. The following
figure shows where the similarities occur.
23
b = 10
B B
D(10, 10) D
a = 10
A A
Further, we can look at yet another problem that appears different, but
is actually the same as these two problems.
Example 30. A 5-ft fence stands 4-ft from a high wall. How long is the
shortest ladder that can reach from the ground outside the fence to the wall?
[10]
4 x A
24
6 The CS Inequality
In addition the AM/GM inequality, the Cauchy Schwarz Inequality also has
some useful applications when it comes to optimization problems. It can be
used in some situations where the max/min and constraint involve addition,
as the AM/GM inequality is not useful in problems such as these. We will
begin by proving the inequality, looking at a typical application of the CS
inequality, and then an example of an optimization problem that can be
solved using the CS inequality.
Equality holds if and only if either there exists a real number k such that
x1 = ky1 , x2 = ky2 ,...,xn = kyn , or there exists a real number m such that
y1 = kx1 , y2 = kx2 ,...,yn = kxn .
Proof. If Y = 0, then both sides are 0, so the equation holds with equality.
In this case Y = 0 = X. Now suppose that Y 6= 0 and t is any real number.
Then n
X
0≤ (xi − tyi )2
i=1
n
X n
X n
X
= x2i − 2t 2
xi y i + t yi2
i=1 i=1 i=1
25
= |X|2 − 2(X · Y )t + t2 |Y |2 .
The last expression is a second-degree polynomial p in t. From the quadratic
formula, the zeros of p are
p
(X · Y ) ± (X · Y )2 − |X|2 |Y |2
t= .
|Y |2
Hence,
(X · Y )2 ≤ |X|2 |Y |2 ,
because if not, then p would have two distinct real zeros and therefore be
negative between them, contradicting the inequality. Taking square roots
yields the inequality if Y 6= 0.
If X = tY , then |X · Y | = |X||Y | = |t||Y |2 , so equality holds. Conversely, if
equality holds, then p has the real zero t0 = (X · Y )/|Y |2 , and
n
X
(xi − t0 yi )2 = 0.
i=1
Therefore, X = t0 Y . [11]
Example 34. What is the minimum value of x2 +9y 2 given that 4x+9y = 36?
[4]
26
Recognizing that 4x + 9y = 4x + 3(3y), and plugging into the inequality,
√ p
4x + 3(3y) ≤ 42 + 32 x2 + (3y)2 ,
362 ≤ 25(x2 + 9y 2 ),
362
≤ x2 + 9y 2 .
25
Therefore, the minimum value of x2 + 9y 2 subject to 4x + 9y = 36 is
approximately 51.84. From the CS inequality, we know:
x = 4t, 3y = 3t.
16y + 9y = 36,
36 144
y= , x= .
25 25
Example 35. A length of wire 28 feet long is cut into two pieces. One piece
is bent into a 3 : 4 : 5 right triangle and the other piece is bent into a square.
Find the minimum combined area of the two shapes. [13]
27
4x 5x
y
3x y
Let y be the side length of the square, and x be the multiple of the
3 : 4 : 5 triangle. We know that the perimeter of the above figures add to
the following:
12x + 4y = 28,
3x + y = 7,
and that the combined area of the triangle and square that we are trying to
minimize is as follows:
(3x)(4x)
+ y2,
2
6x2 + y 2 .
Recognizing, √
6 √
3x + y = 6x + y,
2
then plugging into the CS inequality gives:
√ s √
2
6 √ 6
q √
2
, 1 h 6x, y ≤ +1 2 6x + y 2 ,
2 2
√
6 √
r
5p 2
, 1 h 6x, y ≤ 6x + y 2 ,
2 2
r
5p 2
3x + y ≤ 6x + y 2 ,
2
7 p
p ≤ 6x2 + y 2 ,
5/2
28
98
≤ 6x2 + y 2 .
5
Therefore, the minimum value of the area of the triangle and the square is
19.6 ft 2 .
8 Historical Bit
Looking through a hundred years of calculus problems proved to be extremely
interesting for a multitude of reasons. As was referenced in the “Problems
that Have Evolved” section, we saw a few problems that in the early 1900’s
were given in a particular way and more recently have been worded differently.
We found these problems particularly interesting, as it appears as the years
go on the authors are trying to express how calculus is useful in more
real world type problems. Also, as touched on earlier, the implementation
of other disciplines also became very evident as the years went by in the
texts. The more recent textbooks included more economic, physical, and
medical problems, we suspected as calculus became a requirement for more
disciplines. Listed below are a few examples of these problems. Another
aspect that was especially interesting to look at was the introductions of
each of these books. One of the books stated in the introduction,“In this
calculus book for young men...” Clearly, in more recent calculus books this
would not be an acceptable introduction, so seeing that mindset being phased
out after the 1913 textbook was also a neat progression to see.
29
9 Conclusion
While we got a good grasp on what the AM/GM inequality is, and when it
can be used there is still more to learn. We did many optimization problems
using this technique, however there are so many more problems out there.
Becoming familiar with more of these problems, and learning small tricks
to make the equality work would only continue to happen with exploration.
Further, a look at a few more Cauchy Schwarz inequality applications would
be an interesting direction for further research. Lastly, looking at how
optimization problems were solved before calculus existed would bring about
some unexpected results as well.
References
[1] S. Grossman Calculus Second Edition, New York, 1981.
[5] Robert Ellis, Denny Gulick. Calculus One and Several Variables
University of Maryland, Maryland 1991.
30
[10] Flanders, Prince. something 1978
31