Contemporary Mathematics

# 5.11Linear Programming

Contemporary Mathematics5.11 Linear Programming

Figure 5.98 The aftermath of an earthquake and tsunami. (credit: modification of work "Earthquake and Tsunami Japan" by Climate and Ecosystems Change Adaptation Research University Network/Flickr, CC BY 2.0)

## Learning Objectives

After completing this section, you should be able to:

1. Compose an objective function to be minimized or maximized.
2. Compose inequalities representing a system application.
3. Apply linear programming to solve application problems.

Imagine you hear about some natural disaster striking a far-away country; it could be an earthquake, a fire, a tsunami, a tornado, a hurricane, or any other type of natural disaster. The survivors of this disaster need help—they especially need food, water, and medical supplies. You work for a company that has these supplies, and your company has decided to help by flying the needed supplies into the disaster area. They want to maximize the number of people they can help. However, there are practical constraints that need to be taken into consideration; the size of the airplanes, how much weight each airplane can carry, and so on. How do you solve this dilemma? This is where linear programming comes into play. Linear programming is a mathematical technique to solve problems involving finding maximums or minimums where a linear function is limited by various constraints.

As a field, linear programming began in the late 1930s and early 1940s. It was used by many countries during World War II; countries used linear programming to solve problems such as maximizing troop effectiveness, minimizing their own casualties, and maximizing the damage they could inflict upon the enemy. Later, businesses began to realize they could use the concept of linear programming to maximize output, minimize expenses, and so on. In short, linear programming is a method to solve problems that involve finding a maximum or minimum where a linear function is constrained by various factors.

## Who Knew?

### A Mathematician Invents a “Tsunami Cannon”

On December 26, 2004, a massive earthquake occurred in the Indian Ocean. This earthquake, which scientists estimate had a magnitude of 9.0 or 9.1 on the Richter Scale, set off a wave of tsunamis across the Indian Ocean. The waves of the tsunami averaged over 30 feet (10 meters) high, and caused massive damage and loss of life across the coastal regions bordering the Indian Ocean.

Usama Kadri works as an applied mathematician at Cardiff University in Wales. His areas of research include fluid dynamics and non-linear phenomena. Lately, he has been focusing his research on the early detection and easing of the effects of tsunamis. One of his theories involves deploying a series of devices along coastlines which would fire acoustic-gravity waves (AGWs) into an oncoming tsunami, which in theory would lessen the force of the tsunami. Of course, this is all in theory, but Kadri believes it will work. There are issues with creating such a device: they would take a tremendous amount of electricity to generate an AGW, for instance, but if it would save lives, it may well be worth it.

## Compose an Objective Function to Be Minimized or Maximized

An objective function is a linear function in two or more variables that describes the quantity that needs to be maximized or minimized.

## Example 5.96

### Composing an Objective Function for Selling Two Products

Miriam starts her own business, where she knits and sells scarves and sweaters out of high-quality wool. She can make a profit of $8 per scarf and$10 per sweater. Write an objective function that describes her profit.

1.
For a fundraiser at school, the Robotics Club is selling bags of apples and bunches of bananas during lunch. They will make a profit of $4 per bag of apples and$6 per bunch of bananas. Write an objective function that describes the profit the Robotics Club will make.

## Example 5.97

### Composing an Objective Function for Production

William’s factory produces two products, widgets and wadgets. It takes 24 minutes for his factory to make 1 widget, and 32 minutes for his factory to make 1 wadget. Write an objective function that describes the time it takes to make the products.

1.
Suppose William has a second factory that can make widgets in 20 minutes and wadgets in 28 minutes. Write an objective function that describes the time it takes to make the products.

## Composing Inequalities Representing a System Application

For our two examples of profit and production, in an ideal world the profit a person makes and/or the number of products a company produces would have no restrictions. After all, who wouldn’t want to have an unrestricted profit? However in reality this is not the case; there are usually several variables that can restrict how much profit a person can make or how many products a company can produce. These restrictions are called constraints.

Many different variables can be constraints. When making or selling a product, the time available, the cost of manufacturing and the amount of raw materials are all constraints. In the opening scenario with the tsunami, the maximum weight on an airplane and the volume of cargo it can carry would be constraints. Constraints are expressed as linear inequalities; the list of constraints defined by the problem forms a system of linear inequalities that, along with the objective function, represent a system application.

## Example 5.98

### Representing the Constraints for Selling Two Products

Two friends start their own business, where they knit and sell scarves and sweaters out of high-quality wool. They can make a profit of $8 per scarf and$10 per sweater. To make a scarf, 3 bags of knitting wool are needed; to make a sweater, 4 bags of knitting wool are needed. The friends can only make 8 items per day, and can use not more than 27 bags of knitting wool per day. Write the inequalities that represent the constraints. Then summarize what has been described thus far by writing the objective function for profit and the two constraints.

1.
For a fundraiser at school, the Robotics Club is selling bags of apples and bunches of bananas during lunch. They will make a profit of $4 per bag of apples and$6 per bunch of bananas. Due to school health regulations, the club is allowed to have only 20 bags and bunches of fruit on school grounds each day to sell. Another regulation: the container where the Robotics Club keeps the fruit has a maximum weight capacity of 70 pounds. Each bag of apples weighs 3 pounds, while each bunch of bananas weighs 5 pounds. Write the inequalities that represent these constraints. Then summarize the equations that represent this system.

## Example 5.99

### Representing Constraints for Production

A factory produces two products, widgets and wadgets. It takes 24 minutes for the factory to make 1 widget, and 32 minutes for the factory to make 1 wadget. Research indicates that long-term demand for products from the factory will result in average sales of 12 widgets per day and 10 wadgets per day. Because of limitations on storage at the factory, no more than 20 widgets or 17 wadgets can be made each day. Write the inequalities that represent the constraints. Then summarize what has been described thus far by writing the objective function for time and the two constraints.

1.
Suppose a second factory can make widgets in 20 minutes and wadgets in 28 minutes. Research for this factory indicates that long-term demand for products from this second factory will result in average sales of 15 widgets per day and 13 wadgets per day. Because of limitations on storage at his factory, no more than 22 widgets or 19 wadgets can be made each day. Write the inequalities that represent the constraints. Then summarize what has been described thus far by writing the objective function for time and the two constraints.

## Applying Linear Programming to Solve Application Problems

There are four steps that need to be completed when solving a problem using linear programming. They are as follows:

Step 1: Compose an objective function to be minimized or maximized.

Step 2: Compose inequalities representing the constraints of the system.

Step 3: Graph the system of inequalities representing the constraints.

Step 4: Find the value of the objective function at each corner point of the graphed region.

The first two steps you have already learned. Let’s continue to use the same examples to illustrate Steps 3 and 4.

## Example 5.100

### Solving a Linear Programming Problem for Two Products

Three friends start their own business, where they knit and sell scarves and sweaters out of high-quality wool. They can make a profit of $8 per scarf and$10 per sweater. To make a scarf, 3 bags of knitting wool are needed; to make a sweater, 4 bags of knitting wool are needed. The friends can only make 8 items per day, and can use not more than 27 bags of knitting wool per day. Determine the number of scarves and sweaters they should make each day to maximize their profit.

1.
For a fundraiser at school, the Robotics Club is selling bags of apples and bunches of bananas during lunch. They will make a profit of $4 per bag of apples and$6 per bunch of bananas. Due to school health regulations, the club is allowed to have only 20 bags and bunches of fruit on school grounds each day to sell. Another regulation: the container where the Robotics Club keeps the fruit has a maximum weight capacity of 70 pounds. Each bag of apples weighs 3 pounds, while each bunch of bananas weighs 5 pounds. Determine the number of bags of apples and the number of bags of bananas the Robotics Club should sell each day to maximize their profit.

## People in Mathematics

### Leonid Kantorovich

Leonid Vitalyevich Kantorovich was born January 19, 1912, in St. Petersburg, Russia. Two major events affected young Leonid’s life: when he was five, the Russian Revolution began, making life in St. Petersburg very difficult; so much so that Leonid’s family fled to Belarus for a year. When Leonid was 10, his father died, leaving his mother to raise five children on her own.

Despite the hardships, Leonid showed incredible mathematical ability at a young age. When he was only 14, he enrolled in Leningrad State University to study mathematics. Four years later, at age 18, he graduated with what would be equivalent to a Ph.D. in mathematics.

Although his primary interests were in pure mathematics, in 1938 he began working on problems in economics. Supposedly, he was approached by a local plywood manufacturer with the following question: how to come up with a work schedule for eight lathes to maximize output, given the five different kinds of plywood they had at the factory. By July 1939, Leonid had come up with a solution, not only to the lathe scheduling problem but to other areas as well, such as an optimal crop rotation schedule for farmers, minimizing waste material in manufacturing, and finding optimal routes for transporting goods. The technique he discovered to solve these problems eventually became known as linear programming. He continued to use this technique for solving many other problems involving optimization, which resulted in the book The Best Use of Economic Resources, which was published in 1959. His continued work in linear programming would ultimately result in him winning the Nobel Prize of Economics in 1975.

80.
Kellie makes tables and chairs. Kellie profits $20 from a table ($t$), and$10 from a chair ($c$). The objective function for profit in this situation is:
1. ${P = 20t - 10c}$
2. ${P = 20c + 10t}$
3. ${P = 20t + 10c}$
4. ${P = 20c - 10t}$
81.
Dave grows wheat ($w$) and barley ($b$) on a farm. Dave expects to profit $150 per acre for wheat and$180 per acre for barley. The objective function for profit in this situation is:
1. ${P = 150w + 180b}$
2. ${P = 150b + 180w}$
3. ${P = 180w + 150b}$
4. ${P = 150w - 180b}$
82.
An antique music store sells two types of vinyl records; 45 rpm records ($f$) and 33 rpm records ($t$). It makes a profit of $2.50 for each 45 rpm record and$6.75 for each 33 rpm record. The objective function for profit in this situation is:
1. ${P = 2.50f + 6.75c}$
2. ${P = 2.50f + 6.75t}$
3. ${P = 2.50t + 6.75f}$
4. None of these
83.
Kellie makes tables and chairs. Kellie profits $20 from a table ($t$), and$10 from a chair ($c$). A table requires 15 board feet of wood, while a chair requires 4 board feet of wood. Kellie has 70 board feet available. What is the constraint inequality in this situation?
1. ${20t + 10c \leq 70}$
2. ${ t + c \leq 70}$
3. ${ 15t + 4c \geq 70}$
4. ${ 15t + 4c \leq 70}$
84.
Kellie makes tables and chairs. Kellie profits $20 from a table ($t$), and$10 from a chair ($c$). The maximum number of tables and chairs Kellie can make in any one day is 12. What is the constraint inequality in this situation?
1. ${t + c \leq 12}$
2. ${ 20t + 10c \leq 12}$
3. ${ 20t + 10c \geq 12}$
4. ${ 20t + 10c \leq 70}$
85.
Dave grows wheat ($w$) and barley ($b$) on a farm. Dave expects to profit $150 per acre for wheat and$180 per acre for barley. The cost of seed is $10 per acre for wheat and$15 per acre for barley. Dave can only afford to spend $945 on seed. What is the constraint inequality in this situation? 1. ${w + b \leq 945}$ 2. ${ 10w + 15b \geq 945}$ 3. ${ 10w + 15b \leq 945}$ 4. ${ 150w + 180w \leq 945}$ 86. Dave grows wheat ($w$) and barley ($b$) on a farm. Dave expects to profit$150 per acre for wheat and $180 per acre for barley. The cost of raising each crop is$30 per acre for wheat and $25 per acre for barley. Dave budgets$1,635 for the raising of both crops. What is the constraint inequality in this situation?
1. ${150w + 180b \leq \text{1,635}}$
2. ${25w + 30b \leq \text{1,635}}$
3. ${w + b \leq \text{1,635}}$
4. ${30w + 25b \leq \text{1,635}}$
87.
Kellie makes tables and chairs. Kellie profits $20 from a table ($t$), and$10 from a chair ($c$). A table requires 15 board feet of wood, while a chair requires 4 board feet of wood. Kellie has 70 board feet available. The maximum number of tables and chairs Kellie can make in any one day is 12. The graph of the system of inequalities representing the constraints is:
88.
Kellie makes tables and chairs. Kellie profits $20 from a table ($t$), and$10 from a chair ($c$). A table requires 15 board feet of wood, while a chair requires 4 board feet of wood. Kellie has 70 board feet available. The maximum number of tables and chairs Kellie can make in any one day is 12. The four corner points of the system are:
1. ${(0, 0), (0, 12), (10, 2), (12, 0)}$
2. ${(0, 0), (0, 12), (2, 10), (4\tfrac{2}{3} , 0)}$
3. ${(0, 0), (17.5, 0), (2, 10), (12, 0)}$
89.
Kellie makes tables and chairs. Kellie profits $20 from a table ($t$), and$10 from a chair ($c$). A table requires 15 board feet of wood, while a chair requires 4 board feet of wood. Kellie has 70 board feet available. The maximum number of tables and chairs Kellie can make in any one day is 12. The maximum profit Kellie can make in one day is:
$220\quad\quad{120}\quad\quad{140}\quad\quad{24}$

## Section 5.11 Exercises

For the following exercises, find the value of the objective function at each corner of the graphed region.
1 .
Objective Function $P = 6x + 11y$.
2 .
Objective Function $T = 5x + 3y$
3 .
Objective Function $L = 33x + 45y$
4 .
Objective Function $P = 2t + 4c$
5 .
Objective Function $P = 2.5a + 3.75b$
For the following exercises, write the constraint inequalities. The variables to use are given in parentheses.
6 .
Fernando builds birdbaths $(x)$ and birdhouses $(y)$. Fernando can make a total of 7 birdbaths and birdhouses per day. A birdbath costs $8 to make, while a birdhouse costs$6 to make. Fernando has $48 to spend on building materials for the day. When he sells them, Fernando makes$12 in profit on a birdbath and $9 in profit on a birdhouse. 7 . A fruit pie $(p)$ requires 12 ounces of fruit and 15 ounces of dough; a fruit tart $(t)$ requires 4 ounces of fruit and 3 ounces of dough. There are 72 ounces of fruit and 60 ounces of dough. 8 . One recipe for chocolate cake $(c)$ calls for 9 ounces of chocolate chips and 4 eggs; a recipe for dark chocolate cake $(d)$ requires 12 ounces of chocolate chips but only 3 eggs. There are 90 ounces of chocolate chips and 36 eggs. 9 . To build an outdoor bench $(b)$, a carpenter needs 10 pieces of wood and 26 nails; to build an outdoor chair $(c)$, the carpenter need 8 pieces of wood and 33 nails. There are 92 pieces of wood and 286 nails. For the following exercises, graph each of the system of inequalities from Exercises 6–9. Assume all graphs are in the first quadrant. 10 . Graph of Exercise 6 11 . Graph of Exercise 7 12 . Graph of Exercise 8 13 . Graph of Exercise 9 For the following exercises, use the four steps for solving linear programming problems to solve. 14 . A restaurant sells both regular milk and chocolate milk. To make a glass of regular milk ($x$), it takes 16 ounces of, well, milk. To make a glass of chocolate milk ($y$), it takes 15 ounces of milk and 1 ounce of chocolate flavoring. The restaurant makes a profit of$1.50 per glass on regular milk and $1.00 per glass on chocolate milk. At the beginning of the day, the restaurant has 600 ounces of milk and 24 ounces of chocolate flavoring. To maximize profits, how much of each should they sell that day? 15 . To make a package of all-beef hot dogs ($x$), a factory uses one pound of beef; to make their regular all-meat hot dogs ($y$), they use ½ pound of beef and ½ pound of pork. The profit on the package of all-beef hot dogs is$2.40 per pack; the profit on the all-meat hot dogs is $3.20 per pack. If there are 400 pounds of beef and 250 pounds of pork available, how many of each product should the factory make to maximize their profit? 16 . A toy maker makes two plastic toys, the Ring ($x$) and the Stick ($y$). The toy maker makes$5 per Ring and $4 per Stick. The Ring uses 4 feet of plastic, while the Stick uses 3 feet of plastic. Today the toy maker has 36 feet of plastic available. The toy maker also only makes 10 plastic toys per day. To maximize profit, how many of each toy should the toy maker make? 17 . The toy maker also makes exactly two toys out of wood, the Box ($x$) and the Bat ($y$). The toy maker makes$6 per Box and $7 per Bat. Each Box requires 25 ounces of wood, and each Bat requires 40 ounces of wood. Today the toy maker has 260 ounces of wood available. The toy maker also only makes 8 wooden toys per day. To maximize profit, how many of each wooden toy should the toy maker make? 18 . Sara makes two kinds of kites out of fabric and popsicle sticks. Her Famous Flyer ($x$) needs 2 yards of fabric and 9 popsicle sticks; her Gallant Glider ($y$) needs 3 yards of fabric and 18 popsicle sticks. She makes a profit of$4 on the Famous Flyer and $6 on the Gallant Glider. Today she has 30 yards of fabric and 153 popsicle sticks. How many of each kite should she make to maximize her profit? 19 . Randy’s RV Storage stores two types of Recreational Vehicles (RVs), The Xtra RV ($x$) takes up 400 square feet of space, while the Yosemite RV ($y$) takes up 600 square feet of space. Randy has 55,000 square feet of storage space. By local law, he is only allowed to have a maximum of 100 RVs on his property at any one time. He charges$60 a month to store an Xtra RV, and $80 a month to store a Yosemite RV. How many of each should he store in order to maximize his profit? 20 . A Belgian chocolatier wants to introduce two new chocolate bar creations. The first chocolate bar is called Super Dark ($x$), and it consists of 90 grams of chocolate and 10 grams of sugar. The second chocolate bar is called Special Dark ($y$), containing 80 grams of chocolate and 20 grams of sugar. She calculates that her company will make 1 Euro per bar of Super Dark, and 2 Euros per bar on Special Dark. She first will create some samples to sell out of 1,260 grams of chocolate and 240 grams of sugar. How many of each bar should the chocolatier create to maximize profit? 21 . A juice bottler makes two kinds of specialty juices using different mixtures of pineapple ($x$) and orange ($y$) juices. A 16-ounce bottle of Island Delight has 10 ounces of pineapple juice and 6 ounces of orange juice. A 16-ounce bottle of Sun Fun has 4 ounces of pineapple juice and 12 ounces of orange juice. The bottler makes$1.60 per bottle on Island Delight and $1.20 per bottle on Sun Fun. The amounts of juice available today are 640 ounces of pineapple juice and 768 ounces of orange juice. To maximize profit, how many of each bottle of juice should the juice bottler make? 22 . Fernando builds birdbaths ($x$) and birdhouses ($y$). Fernando can make a total of 7 birdbaths and birdhouses per day. A birdbath costs$8 to make, while a birdhouse costs $6 to make. Fernando has$48 to spend on building materials for the day. When he sells them, Fernando makes $12 in profit on a birdbath and$9 in profit on a birdhouse. Determine how many of each Fernando should make to maximize his profit for the day.
23 .
A farmer grows wheat ($x$) and barley ($y$) on his 500 acres of cropland. He expects to profit $150 per acre for wheat and$180 per acre for barley. The cost of raising each crop (seed, pesticide, etc.) is $60 per acre for wheat and$90 per acre for barley. The farmer can budget \$36,000 for the growing of the crops. To maximize his profit, how many acres of each crop should be grown?
24 .
A company is going to ship food ($x$) and water ($y$) to the victims of a tsunami. Each container of food will feed 8 people for a day, and each container of water will give 12 people their daily water. The food containers each weigh 30 pounds and take up 8 cubic feet of space; each container of water weighs 120 pounds, but takes up only 2 cubic feet of space. The airplanes lined up to carry the supplies to the victims cannot have its cargo exceed 24,000 pounds; also, the total cargo area in the airplanes is 4,000 cubic feet. How many containers of food and water can be sent with each plane shipment that maximizes the shipment?
25 .
Another company will send clothing ($x$) and medical supplies ($y$) to the victims of the tsunami. Each container of clothing contains enough clothing for 12 people; each container of medical supplies can aid 8 people. The clothing containers each weigh 50 pounds and take up 6 cubic feet of space; each container of medical supplies weighs 20 pounds, and takes up 4 cubic feet of space. The airplanes lined up to carry the supplies to the victims cannot have its cargo exceed 24,000 pounds; also, the total cargo area in the airplanes is 3,000 cubic feet. How many containers of clothing and medical supplies can be sent with each plane shipment that maximizes the shipment?
Order a print copy

As an Amazon Associate we earn from qualifying purchases.