Linear Optimization

Sometimes we have a problem where our choices are restricted by some linear inequalities, and we want to maximize or minimize some other linear expression within those restrictions. The process of setting up and solving this kind of problem is called linear optimization.


The baker’s dilemma

A baker wants to make brownies and chocolate chip cookies, but he’s running low on sugar and butter. He wants to know how many cookies and brownies he should bake in order to make the most profit. To solve his problem, he uses linear optimization.

He decides to let $b$ be the number of batches of brownies he bakes, and $c$ be the number of batches of chocolate chip cookies. Each batch of brownies uses 4 cups of sugar. Each batch of cookies uses 2 cups of sugar. So, the amount of sugar he’ll use is $4b+2c$. The baker only has 520 cups of sugar, so he knows that $4b+2c≤520$.

Each batch of brownies uses 1.5 cups of butter and each batch of cookies uses 3 cups of butter. So, the amount of butter he’ll use is $1.5b+3c$. The baker has 420 cups of butter. Write an inequality for the number of cups of butter that he can use.
Each batch of cookies takes 3 cups of butter. Does the baker have enough butter to make 150 batches of cookies?
On the grid to the left you can see the graph of the system of inequalities for this problem. The dark blue region is the solution set of this system. The point $(0,150)$ represents making 0 batches of brownies and 150 batches of cookies. Is $(0,150)$ in the solution set?
What does the point $(80,100)$ represent? batches of brownies
batches of cookies
What is the maximum number of batches of cookies that he can bake?
For every batch of brownies that the baker bakes, he makes \$2.00 in profit. The baker makes \$1.80 in profit for every batch of cookies that he bakes. So, his profit is represented by $P=2b+1.8c$. Use this equation to find the profit the baker will make if he bakes 20 batches of brownies and 0 batches of cookies.

Click . The black line is a graph of a fixed profit level, $P=2b+1.8c$. $P$ is set to 40, so if the baker makes brownies and cookies corresponding to any point on the black line, he will make \$40 in profit. Use the slider to make $P$, the profit, larger and notice how the line moves.

The baker wants to make the most profit using the sugar and butter that he has. This means that he wants $P$ to be as large as it can be while the line for $P$ still intersects the solution set. What is the maximum profit he can make? Remember that the points on the edges are in the solution set.
How many batches of brownies and cookies should he make to get this profit? (That is, what are the coordinates of the point of intersection?) batches of brownies
batches of cookies

The coffee beans

A coffee distributor wants to make a blend of coffee using a mix of premium and regular 10-pound bags of coffee beans. She has high standards for the blend she wants to make. She also wants to minimize her cost while keeping her high standards, so she uses linear optimization. She lets $p$ be the number of bags of premium beans and $r$ be the number of bags of regular beans.

Each 10-pound bag of premium coffee contains 6 lbs. of Colombian coffee beans. Each 10-pound bag of regular coffee contains 3 lbs. of Colombian coffee beans. So, the amount of Colombian beans in her blend is $6p+3r$. The distributor wants her blend to contain at least 360 pounds of Colombian beans, so $6p+3r≥360$.

Each 10-pound bag of premium coffee contains 4 lbs. of Sumatra coffee beans. Each 10-pound bag of regular coffee contains 1 pound of Sumatra coffee beans. So, the amount of Sumatra beans in her blend is $4p+r$. The distributor wants her blend to contain at least 180 pounds of Sumatra beans. Write an inequality that represents this constraint.
Click to see the graph of the system of inequalities for this problem. The dark blue region is the solution set of this system. The point $(0,180)$ represents using 0 bags of premium and 180 bags of regular coffee beans. What does the point $(60,0)$ represent? bags of premium coffee beans
bags of regular coffee beans
What does the point $(30,60)$ represent? bags of premium coffee beans
bags of regular coffee beans
Which of these three points, $(0,180)$, $(60,0)$, and $(30,60)$, do you think will minimize the cost? (Just make a guess.)
Each bag of premium beans costs \$6 and each bag of regular coffee costs \$2. So, the cost to the distributor is $C=6p+2r$. Click . The black line is a graph of a fixed cost amount, $C$. $C$ is set to 75, so if she uses bags of premium and regular coffee corresponding to any point on the black line, her cost will be \$75. To satisfy the inequalities, the line needs to intersect the solution set of the inequalities (the dark blue region). What is the least value $C$ can have in the dark blue region?
Does $C$ increase or decrease as it moves farther into the dark blue region?
How many 10-pound bags of premium and regular coffee should the distributor use to minimize her cost? bags of premium coffee beans
bags of regular coffee beans
Was your guess above correct?

Oak and maple

A company that makes bookcases and desks out of oak and maple has a limited amount of each kind of wood. Also, the company’s employees are available to work a set number of hours every week. This company wants to know how many bookcases and desks it should make to maximize its profits. They decide to use linear optimization to solve this problem.

First, they define their variables. They let $b$ be the number of bookcases that are made in a week and $d$ be the number of desks that are made. Each bookcase uses 2 board-feet of oak and each desk uses 1 board-foot of oak. So, the amount of oak that will be used is $2b+d$. Every week they get a supply of 1000 board-feet of oak, so $2b+d≤1000$.

Each bookcase uses 1 board-foot of maple and each desk uses 2 board-feet of maple. So, the amount of maple that will be used is $b+2d$. The company gets a supply of 1000 board feet of maple every week. Write an inequality for the amount of maple that can be used in a week.
Click to see the graph of the system of 2 inequalities. The dark blue region is the solution set of this system. Is $(325,300)$ in the solution set of this system?
Do you think that $(325,300)$ will satisfy the first inequality? Will it satisfy the second inequality? (You should be able to answer this question without any work.)
First?
Second?
It takes 3 hours of labor to make a bookcase and 3 hours of labor to make a desk. Write an expression for the amount of labor needed to make $b$ bookcases and $d$ desks.
Every week the company has 1800 hours of labor available. Write an inequality describing the amount of labor that can be utilized during the week.
Click to see the graph of this system of 3 inequalities. The solution set to these three inequalities — that is, the region where all three of their graphs overlap — is the olive region. Is the point $(325,300)$ in the olive solution set?
What is the maximum number of desks that the company can make? (That is, how high is the highest point in the olive solution set?) desks
The point $(0,0)$ is one of the five corners of the olive solution set. What are the coordinates of the other four corners?
The company makes \$20 in profit for each bookcase and \$30 in profit for each desk. Write an equation for the profit the company makes from making $b$ bookcases and $d$ desks.
Click . The black line is a graph of a fixed profit level, $P$. To satisfy the inequalities, the line needs to intersect the solution set of the inequalities (the olive region). Slide $P$ to find the profit at each of the corners of the olive region.
At which corner point is the profit maximized?
Slide $P$. Can $P$ have a higher value than the one you found above for any point that satisfies the constraints of this problem (is in the olive region)?
What is the maximum profit the company can make?
How many bookcases and desks should the company make to maximize its profit? bookcases
desks