The term linear programming was coined in the late 1940s. It describes a relatively young branch of mathematics, compared to subjects such as Euclidean geometry, where the major ideas were already well understood 23 centuries ago. (The Greek mathematician Euclid wrote what can be considered the first geometry textbook about 300 B.C.) Business managers routinely solve linear programming problems for purchasing and marketing strategy, so it is possible that linear programming affects your daily life as much as any other branch of mathematics.
TrailGear would like to maximize its profit from selling hiking boots. The company produces two kinds of hiking boots, a Weekender model, on which it makes $\(8\) profit per pair, and a Sierra model, on which it makes $\(10\) profit per pair. How many of each model should TrailGear produce each week in order to maximize its profit?
If we let \(x\) represent the number of Weekender boots and \(y\) the number of Sierra boots TrailGear produces, then the total weekly profit is given by
\begin{equation*}
P = 8x + 10y
\end{equation*}
This expression for \(P\) is called the objective function. The goal of a linear programming problem is to maximize or minimize such an objective function, subject to one or more constraints.
If TrailGear had infinite resources and an infinite market, there would be no limit to the profit it could earn by producing more and more hiking boots. However, every business has to consider many factors, including its supplies of labor and materials, overhead and shipping costs, and the size of the market for its product. To keep things simple, we will concentrate on just two of these factors.
Each pair of Weekender boots requires \(3\) hours of labor to produce, and each pair of Sierra boots requires \(6\) hours. TrailGear has available \(2400\) hours of labor per week. Thus, \(x\) and \(y\) must satisfy the inequality
In addition, suppose that TrailGearβs suppliers can provide at most \(1000\) ounces of silicone gel each week, with each pair of Weekenders using \(2\) ounces and each Sierra model using \(1\) ounce. This means that
\begin{equation*}
2x + y \le 1000
\end{equation*}
Of course, we will also require that \(x\ge 0\) and \(y\ge 0\text{.}\) These four inequalities are called the constraints of the problem.
Our goal is to find values for \(x\) and \(y\) that satisfy the constraints and produce the maximum value for \(P\text{.}\) We begin by graphing the solutions to the constraint inequalities. These solutions are shown in the shaded region in at right. The points in this region are called feasible solutions because they are the only values we can consider while looking for the maximum value of the objective function \(P\text{.}\)
Verify that the points \((300, 100)\) and \((200, 300)\) represent feasible solutions for the problem above. Show that \((300, 400)\) is not a feasible solution.
The two points \((300, 100)\) and \((200, 300)\) lie within the shaded region above, but \((300, 400)\) does not. We can also verify that the coordinates of \((300, 100)\) and \((200, 300)\) satisfy each of the constraint inequalities.
Determine which of the points \((0, 400)\text{,}\)\((400, 200)\text{,}\)\((500, 0)\text{,}\) and \((500, 400)\) represent feasible solutions for the TrailGear problem.
We cannot check all of the feasible solutions to see which one results in the largest profit. Fortunately, there is a simple way to find the optimal solution.
Suppose TrailGear would like to make \($2000\) on hiking. It could produce \(200\) pairs of Sierra boots, or \(250\) pairs of Weekenders. Or it could produce some of each; for example, \(50\) pairs of Weekenders and \(160\) pairs of Sierra boots. In fact, every point on the line
\begin{equation*}
8x + 10y = 2000
\end{equation*}
represents a combination of Weekenders and Sierra boots that will yield a profit of $\(2000\text{.}\) This line is labeled \(P = 2000\) in the figure below.
If TrailGear would like to make $\(4000\) on boots, it should choose a point on the line labeled \(P = 4000\text{.}\) Similarly, all the points on the line labeled \(P = 6000\) will yield a profit of $\(6000\text{,}\) and so on. Different values of \(P\) correspond to parallel lines on the graph. Smaller values of \(P\) correspond to lines near the origin, and larger values of \(P\) have lines farther from the origin.
\begin{equation*}
C = 3(\alert{0}) + 5(\blert{3}) = 15
\end{equation*}
Another point with the same objective value is \((5, 0)\text{.}\) In fact, all points on the line \(3x + 5y = 15\) have an objective value of \(15\text{.}\) This line intersects the set of feasible solutions in a line segment, as shown in below. Thus, there are infinitely many feasible solutions with objective value \(15\text{.}\)
Points that give an objective value of \(C = 30\) lie on the line \(3x + 5y = 30\text{,}\) as shown in the figure. There are infinitely many feasible solutions that lie on this line; for example, one such point is \((5, 3)\text{.}\)
The line \(3x + 5y = 39\) intersects the set of feasible solutions in only one point, the point \((3, 6)\text{.}\) This is the only feasible solution that yields an objective value of \(39\text{.}\)
The line \(3x + 5y = 45\) includes all points for which \(C=45\text{.}\) This line does not intersect the set of feasible solutions, as we see in the figure. Thus, there are no feasible solutions that result in an objective value of \(45\text{.}\)
Returning to this sectionβs opening Example regarding TrailGear profits for selling hiking boots, find all feasible solutions for which the objective function \(P = 8x + 10y\) has a value of \(5200\text{.}\)
We are only allowed to choose points from the set of feasible solutions. Imagine the parallel lines representing different values of the objective function sweeping across the graph of the feasible solutions. The objective values increase as the lines sweep up across the graph.
What is the last feasible solution the lines intersect before leaving the shaded region? If you study the preceding examples, perhaps you can see that the largest (and smallest) values of the objective function will occur at corner points of the set of feasible solutions. We have not proved this fact, but it is true.
The maximum value of the profit, \(P\text{,}\) corresponds to the topmost line that intersects the region of feasible solutions. This is the line that passes through the vertex where the lines \(~~3x + 6y = 2400~~\) and \(~~2x + y = 1000~~\) intersect, namely the vertex at \((400, 200)\text{.}\) The profit for that point is
\begin{equation*}
P = 8(400) + 10(200) = 5200
\end{equation*}
Each week, the Healthy Food Store buys both granola and muesli in bulk from two cereal companies. The store requires at least \(12\) kilograms of granola and \(9\) kilograms of muesli.
Company A charges $\(15\) for a package that contains \(2\) kilograms of granola and \(1\) kilogram of muesli.
How much should the Healthy Food Store purchase from each company in order to minimize its costs and still meet its needs for granola and muesli? What is the minimum cost?
The Healthy Food Store will have \(2x\) kilograms of granola and \(x\) kilograms of muesli from Company A, and \(3y\) kilograms of granola and \(3y\) kilograms of muesli from Company B. The store requires that
We graph the solutions to the constraint system. The feasible solutions form the shaded region shown below. Any ordered point on this graph corresponds to a way to purchase granola and muesli that meets the storeβs needs, but some of these choices cost more than others.
We know that the minimum cost will occur at one of the vertex points, which are labeled in the figure. The coordinates of \(P\) and \(R\) are easy to see. To find the coordinates of \(Q\text{,}\) we notice that it is the intersection of the lines \(2x + 3y = 12\) and \(x + 3y = 9\text{.}\) Thus, we must solve the system
Subtracting the second equation from the first, we find that \(x=3\text{.}\) Substituting this value into either of the original two equations, we find that \(y=2\text{.}\) Thus the point \(Q\) has coordinates \((3, 2)\text{.}\)
The Healthy Food Store should buy three packages from Company A and two packages from Company B. It will pay $\(95\) for its stock of granola and muesli.
Next, graph the set of feasible solutions. We have already taken care of the constraints \(x\ge 0\) and \(y\ge 0\) by setting Xmin and Ymin to zero. Solve each of the other constraints for \(y\) to get
\begin{align*}
y \amp\ge (12 - 2x)/3\\
y \amp\ge(9 - x)/3
\end{align*}
For each constraint, the set of feasible solutions lies above the boundary line, because \(y\) is greater than the expression in \(x\text{.}\) To shade the regions above the graphs of \(Y_1\) and \(Y_2\text{,}\) move the cursor onto the backslash in front of the equations and press ENTER twice, as shown in figure (a). Then press GRAPH. Your display should look like figure (b).
The feasible solutions lie in the crosshatched region that is shaded with both the vertical and horizontal lines. We will use the calculator to evaluate the objective function at each vertex. First, use the TRACE (or value or intersect feature) to find the coordinates of one of the vertices, say \((0, 4)\text{.}\) Then press 2ndQUIT to get back to the Home screen; enter the formula for the objective function by keying in
\begin{equation*}
15X + 25Y
\end{equation*}
(Enter \(Y\) by pressing ALPHA\(1\text{.}\)) Your calculator has stored the values \(x=0\) and \(y=4\) from the TRACE key, so when you press ENTER, the calculator returns \(100\) for the value of \(C\) at that point. Thus, when \(x=0\) and \(y=4\text{,}\)\(C=100\text{.}\)
Similarly, you can verify that \(C=135\) when \(x=9\) and \(y=0\text{,}\) and that when \(x=3\) and \(y=2\text{,}\)\(C-95\text{.}\) Thus, the minimum cost of \(\$95\) occurs when \(x=3\) and \(y=2\text{.}\)
Graph the line that corresponds to a profit of \(\$8\text{.}\) Find the coordinates of at least one feasible solution that gives a profit of $\(8\text{.}\)
Graph the line that corresponds to a profit of $\(22\text{.}\) Find the coordinates of at least one feasible solution that gives a profit of \(\$22\text{.}\)
The math club is selling tickets for a show by a mathemagician. Student tickets will cost $\(1\) and faculty tickets will cost $\(2\text{.}\) The ticket receipts must be at least \(\$250\) to cover the fee for the performer. An alumna promises to donate one calculator for each student ticket sold and three calculators for each faculty ticket sold. What is the minimum number of calculators that the alumna will donate?
The math department is having a book sale of unwanted textbooks to raise funds for $\(300\) in scholarships. Paperback textbooks will be sold for $\(2\) and the hardcover textbooks will be sold for $\(5\text{.}\) If paperback texts weigh \(2\) pounds each and hardcover books weigh \(3\) pounds each, find the minimum weight of textbooks the department must sell in order to raise its required funds.
Jeannette has \(180\) acres of farmland for growing wheat or soy. Each acre of wheat requires two hours of labor at harvest time, and each acre of soy needs one hour of labor. Jeannette will have \(240\) hours of labor available at harvest time. Find the maximum profit Jeannette can make from her two crops if she can get a profit of $\(36\) per acre for wheat and $\(24\) per acre for soy.
Vassilis has at most $\(10,000\) to invest in two banks. Alpha Bank will pay \(6\%\) annual interest and Bank Beta pays \(5\%\) annual interest. Alpha Bank will only insure up to $\(6000\text{,}\) so Vassilis will invest no more than that with Alpha. What is the maximum amount of interest Vassilis can earn in \(1\) year?
Garyβs pancake recipe includes corn meal and whole wheat flour. Corn meal has \(2.4\) grams of linoleic acid and \(2.5\) milligrams of niacin per cup. Whole wheat flour has \(0.8\) gram of linoleic acid and \(5.2\) milligrams of niacin per cup. These two dry ingredients do not exceed \(3\) cups total. They combine for at least \(3.2\) grams of linoleic acid and at least \(10\) milligrams of niacin. Minimize the number of calories possible in the recipe if corn meal has \(433\) calories per cup and whole wheat flour has \(400\) calories per cup.
Cho requires \(1\) hour of cutting and \(2\) hours of sewing to make a Batman costume. He requires \(2\) hours of cutting and \(1\) hour of sewing to make a Wonder Woman costume. At most \(10\) hours per day are available for cutting and at most \(8\) hours per day are available for sewing. At least one costume must be made each day to stay in business. Find Choβs maximum income from selling one dayβs costumes if a Batman costume costs $\(68\) and a Wonder Woman costume costs $\(76\text{.}\)