maths.free › Algebra › 5. Algebra › Linear Programming

Linear Programming

Compose an objective function to be minimized or maximized.

Learning Objectives

After completing this section, you should be able to:

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

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.

Composing an Objective Function for Selling Two Products

Try it.

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.

Solution

Let $x$ represent the number of scarves sold, and let $y$ represent the number of sweaters sold. Let $P$ represent profit. Since each scarf has a profit of $8 and each sweater has a profit of $10, the objective function is $P=8x+10y$.

Composing an Objective Function for Production

Try it.

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.

Solution

Let $x$ equal the number of widgets made; let $y$ equal the number of wadgets made; let $T$ represent total time. The objective function is $T=24x+32y$.

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.

Representing the Constraints for Selling Two Products

Try it.

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.

Solution

Let $x$ represent the number of scarves sold, and let $y$ represent the number of sweaters sold. There are two constraints: the number of items the business can make in a day (a maximum of 8) and the number of bags of knitting wool they can use per day (a maximum of 27). The first constraint (total number of items in a day) is written as: \[x+y\le 8\]

Since each scarf takes 3 bags of knitting wool and each sweater takes 4 bags of knitting wool, the second constraint, total bags of knitting wool per day, is written as: \[3x+4y\le 27\]

In summary, here are the equations that represent the new business:

$P=8x+10y$; This is the profit equation: The business makes $8 per scarf and $10 per sweater.

\[\begin{array}{lll}x+y & \le & 8 \\ 3x+4y & \le & 27\end{array}\]

Condensed — the full section is in OpenStax Contemporary Mathematics.

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.

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.

Condensed — the full section is in OpenStax Contemporary Mathematics.

Key Concepts

Linear programming is a mathematical technique to solve problems involving finding maximums or minimums where a linear function is limited by various constraints.
An objective function is a linear function in two or more variables that describes the quantity that needs to be maximized or minimized.
In linear programming, a constraint is a restriction that affects the maximum or minimum values of an objective function.
Through the creation of objective functions and restraints, a linear system can be developed and solved through linear programming.

Projects

Go to your favorite coffee shops and find out what a same sized drink costs at each. You can do something similar for pizza as well. Find the unit rate (i.e., price per ounce or price per square inch). For example, go to your favorite coffee place and find the price per units on all their large coffee drinks. Or go to your favorite pizza place and compare prices of all their extra-large pizzas (by price per square inch). Write a report on the best deals.

Rather than comparing prices of different, but same sized drinks (or pizzas), compare unit prices of the same drinks but of different sizes. Find out what the best bargain is based on price per ounce, price per square inch, etc. For example, compare the prices of your favorite soft drink sold at a local store, but in various sizes (i.e., 12-ounce can, 16-ounce bottle, 20-ounce bottle, 1-liter bottle, and multipacks). Or go to a pizza place and find out what the best bargain is on their menu, based on price per square inch of pizza. Write a report on the best deals.

Go to the websites of different cell phone companies and compare their plans. Write a report on “the best deals. "Best Deals” doesn’t necessarily mean “cheapest.” You will need to look at what each company provides concerning restrictions (constraints) on minutes to talk. What are the constraints on the cell phone coverage for each company? Do they cover your area of the country well? Do they cover the entire United States well, or at least areas where you will be travelling? Is this coverage 5G, or is it less? Can you add a phone easily? Can you bring your previous phone number to this plan? The possibilities of constraints affecting each plan are several. So your task is to determine which plan is best, based on not only cost but also all constraints you deem important.

Practice (5)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

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.

发送答案

Let $x$ represent the number of scarves sold, and let $y$ represent the number of sweaters sold. Let $P$ represent profit. Since each scarf has a profit of $8 and each sweater has a profit of $10, the objective function is $P=8x+10y$.
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.

发送答案

Let $x$ equal the number of widgets made; let $y$ equal the number of wadgets made; let $T$ represent total time. The objective function is $T=24x+32y$.
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.

发送答案

Let $x$ represent the number of scarves sold, and let $y$ represent the number of sweaters sold. There are two constraints: the number of items the business can make in a day (a maximum of 8) and the number of bags of knitting wool they can use per day (a maximum of 27). The first constraint (total number of items in a day) is written as: \[x+y\le 8\]
Since each scarf takes 3 bags of knitting wool and each sweater takes 4 bags of knitting wool, the second constraint, total bags of knitting wool per day, is written as: \[3x+4y\le 27\]
In summary, here are the equations that represent the new business:
$P=8x+10y$; This is the profit equation: The business makes $8 per scarf and $10 per sweater.
\[\begin{array}{lll}x+y & \le & 8 \\ 3x+4y & \le & 27\end{array}\]
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.

发送答案

Let $x$ equal the number of widgets made; let $y$ equal the number of wadgets made. Based on the long-term demand, we know the factory must produce a minimum of 12 widgets and 10 wadgets per day. We also know because of storage limitations, the factory cannot produce more than 20 widgets per day or 17 wadgets per day. Writing those as inequalities, we have:
$x\ge 12$
$y\ge 10$
$x\le 20$
$y\le 17$
The number of widgets made per day must be between 12 and 20, and the number of wadgets made per day must be between 10 and 17. Therefore, we have:
$12\le x\le 20$
$10\le y\le 17$
The system is:
$T=24x+32y$
$12\le x\le 20$
$10\le y\le 17$
$T$ is the variable for time; it takes 24 minutes to make a widget and 32 minutes to make a wadget.
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.

发送答案

Step 1: Compose an objective function to be minimized or maximized. From , the objective function is $P=8x+10y$.
Step 2: Compose inequalities representing the constraints of the system. From , the constraints are $x+y\le 8$ and $3x+4y\le 27$.
Step 3: Graph the system of inequalities representing the constraints. Using methods discussed in Graphing Linear Equations and Inequalities, the graphs of the constraints are shown below. Because the number of scarves ($x$) and the number of sweaters ($y$) both must be non-negative numbers (i.e., $x\ge 0$ and $y\ge 0$), we need to graph the system of inequalities in Quadrant I only. shows each constraint graphed on its own axes, while shows the graph of the system of inequalities (the two constraints graphed together). In , the large shaded region represents the area where the two constraints intersect. If you are unsure how to graph these regions, refer back to Graphing Linear Equations and Inequalities.
Step 4: Find the value of the objective function at each corner point of the graphed region. The “graphed region” is the area where both of the regions intersect; in , it is the large shaded area. The “corner points” refer to each vertex of the shaded area. Why the corner points? Because the maximum and minimum of every objective function will occur at one (or more) of the corner points. shows the location and coordinates of each corner point.
Three of the four points are readily found, as we used them to graph the regions; the fourth point, the intersection point of the two constraint lines, will have to be found using methods discussed in Systems of Linear Equations in Two Variables, either using substitution or elimination. As a reminder, set up the two equations of the constraint lines: \[\begin{array}{lll}3x+4y & = & 27 \\ x+y & = & 8\end{array}\]
For this example, substitution will be used. \[\begin{array}{lll}x+y & = & 8 \\ y & = & 8-x\text{.}\end{array}\]
Substituting $8-x$ into the first equation for $y$, we have \[\begin{array}{lll}3x+4(8-x) & = & 27 \\ 3x+32-4x & = & 27 \\ -x & = & -5 \\ x & = & 5\end{array}\]
Now, substituting the 5 in for $x$ in either equation to solve for $y$. Choosing the second equation, we have: \[\begin{array}{lll}5+y & = & 8 \\ y & = & 3\end{array}\]
Therefore, $x=5$, and $y=3$.
To find the value of the objective function, $P=8x+10y$, put the coordinates for each corner point into the equation and solve. The largest solution found when doing this will be the maximum value, and thus will be the answer to the question originally posed: determining the number of scarves and sweaters the new business should make each day to maximize their profit.
Corner ($x$, $y$) Objective Function $P=8x+10y$
$(0,0)$ $P=8(0)+10(0)=0$
$(0,6.75)$ $P=8(0)+10(6.75)=67.5$
$(5,3)$ $P=8(5)+10(3)=40+30=70$
$(8,0)$ $P=8(8)+10(0)=64$
The maximum value for the profit $P$ occurs when $x=5$ and $y=3$. This means that to maximize their profit, the new business should make 5 scarves and 3 sweaters every day.

Symbols used here

imaginary unit
i² = −1.

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

\pm

plus or minus
Both signs at once: x = 3 ± 2 means 5 and 1.

\neq

not equal
The two sides are different.

\sqrt{x},\ \sqrt[n]{x}

square root, n-th root
The non-negative number whose square (n-th power) is x.

|x|

absolute value / modulus
Distance from zero: |−3| = 3. For a complex number, distance from the origin.

\log_b x,\ \ln x

logarithm, natural log
The exponent b must be raised to for x; ln uses base e.

\mathbb{N},\ \mathbb{Z},\ \mathbb{Q},\ \mathbb{R},\ \mathbb{C}

number sets
Naturals, integers, rationals, reals, complex numbers.

How to: Linear Programming

Compose an objective function to be minimized or maximized.
Compose inequalities representing a system application.
Apply linear programming to solve application problems.
linear programming
objective function
constraint
Linear programming is a mathematical technique to solve problems involving finding maximums or minimums where a linear function is limited by various constraints.
An objective function is a linear function in two or more variables that describes the quantity that needs to be maximized or minimized.

Questions people ask

What does it mean to solve an equation?

To find every value of the unknown that makes both sides equal. Each step is an operation applied to both sides that keeps the solution set the same, until the unknown stands alone.

Why do I sometimes get two answers?

A quadratic can cross the axis twice, so it can have two solutions. A degree-n polynomial has up to n. The graph shows where each one comes from.

How do I know whether to factor or use the quadratic formula?

Try factoring for a few seconds: look for two numbers that multiply to a·c and add to b. If nothing obvious appears, the discriminant b² − 4ac tells you how many real roots there are, and the formula finds them without guessing.

试试你自己试试

Parts of this page are adapted from OpenStax Contemporary Mathematics (CC BY-NC-SA 4.0). Condensed and re-explained here; errors are ours.

Corner (\(x\), \(y\))	Objective Function \(P=8x+10y\)
\((0,0)\)	\(P=8(0)+10(0)=0\)
\((0,6.75)\)	\(P=8(0)+10(6.75)=67.5\)
\((5,3)\)	\(P=8(5)+10(3)=40+30=70\)
\((8,0)\)	\(P=8(8)+10(0)=64\)

Learning Objectives

Compose an Objective Function to Be Minimized or Maximized

Composing Inequalities Representing a System Application

Applying Linear Programming to Solve Application Problems

Key Concepts

Projects

Practice (5)

Symbols used here

How to: Linear Programming

Questions people ask

试试你自己试试

更多 Algebra