3.5: Applications of Linear Programming
- Page ID
- 67079
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)In the previous section we looked at the Simplex method, a procedure for solving linear programming problems with many variables. While this method can be done by-hand, it can easily be automated by a computer. In the remainder of this chapter, we will focus on setting up the objective function and constraints and interpreting the solution, and omit the details of solving.
Example \(\PageIndex{1}\)
A catering company is to make lunch for a business meeting. It will serve ham sandwiches, light ham sandwiches, and vegetarian sandwiches. A ham sandwich has 1 serving of vegetables, 4 slices of ham, 1 slice of cheese, and 2 slices of bread. A light ham sandwich has 2 serving of vegetables, 2 slices of ham, 1 slice of cheese and 2 slices of bread. A vegetarian sandwich has 3 servings of vegetables, 2 slices of cheese. and 2 slices of bread. A total of 10 bags of ham are available, each of which has 40 slices; 18 loaves of bread are available, each with 14 slices; 200 servings of vegetables are available, and 15 bags of cheese, each with 60 slices, are available. Given the resources, how many of each sandwich can be produced if the goal is to maximize the number of sandwiches?
Solution
We wish to maximize the number of sandwiches, so let:
\(x=\) number of ham sandwiches
\(y=\) number of light ham sandwiches
\(z=\) number of vegetarian sandwiches
The total number of sandwiches is given by: \(\quad S=x+y+z\)
The constraints will be given by considering the total amount of ingredients available. That is, the company has a limited amount of ham, vegetables, cheese, and bread.
In total, the company has \(10(40)=400\) slices of ham, \(18(14)=252\) slices of bread.
200 servings of vegetables, and \(15(60)=900\) slices of cheese available. At most, the
company can use the above amounts.
There are two sandwiches that use ham-the first requires 4 slices of ham and the second requires only 2, per sandwich, and the total number of slices of ham cannot exceed 400
\[4 x+2 y \leq 400\nonumber\]
Each sandwich requires 2 slices of bread so:
\[2 x+2 y+2 z \leq 252\nonumber\]
The ham sandwiches have 1 and 2 servings of vegetables, respectively, and the vegetarian sandwich has 3 servings of vegetables. So,
\[1x + 2y + 3z \leq 200\nonumber\]
Both ham sandwiches require one slice of cheese, and the vegetarian sandwich requires two slices of cheese, so,
\[1x + 1y + 2z \leq 900\nonumber\]
Our final setup is:
Maximize: \(S = x + y + z\)
Subject to:
\[ \begin{align*} 4x + 2y & \leq 400 \\ 2x + 2y + 2z &\leq 252 \\ 2x + 2y + 2z &\leq 252\end{align*}\nonumber\]
Solving this, we get
Optimal Solution:
\[S = 126; \quad x = 100, \quad y = 0, \quad z = 26 \nonumber\]
We find that 100 ham sandwiches, 26 vegetarian sandwiches, and 0 light ham sandwiches should be made to maximize the total number of sandwiches made.
Notice that this will effectively use up all of the bread, which is the first to go.
Example \(\PageIndex{2}\)
A factory manufactures three products, A, B, and C. Each product requires the use of two machines, Machine I and Machine II. The total hours available, respectively, on Machine I and Machine II per month are 180 and 300. The time requirements and profit per unit for each product are listed below.
|
|
A |
B |
C |
|---|---|---|---|
|
Machine I |
1 |
2 |
2 |
|
Machine II |
2 |
2 |
4 |
|
Profit |
20 |
30 |
40 |
How many units of each product should be manufactured to maximize profit, and what is the maximum profit?
Solution
As usual, we start by defining our variables:
\(A=\) number of units of product A manufactured
\(B=\) number of units of product B manufactured
\(C=\) number of units of product B manufactured
We are trying to maximize profit. Producing \(A\) units of item A will result in a profit of \(20 A\), producing \(B\) units of item \(B\) will profit \(30 B\), and \(C\) units of item \(C\) will profit \(40 C\), giving our objective function:
\[P=20 A+30 B+40 C\nonumber\]
Next we consider the time available on each machine to establish constraints. Producing A units of item A will require 1A hours on Machine 1, producing B units of item B will require 2B hours, and producing C units of item C will require 2C hours. Together these need to not exceed the 180 hours available. This leads to the constraint:
\[1A + 2B + 2C \leq 180 \nonumber\]
We can construct a similar constraint using the hours on Machine 2:
\[2A + 2B + 4C \leq 300 \nonumber\]
Our final setup is:
Maximize \(P = 20A + 30B + 40C\)
Subject to:
\[\begin{align*} 1A + 2B + 2C &\leq 180\\ 2A + 2B + 4C &\leq 300\\ A \geq 0, \quad B \geq 0, &\; C \geq 0 \end{align*}\nonumber\]
Solving this:
Optimal Solution:
\[P = 3300; A = 120, B = 30, C = 0\nonumber\]
We will maximize profit at $3300 by producing 120 units of item \(A\), 30 units of item \(B\), and no units of item \(C\).
In addition to maximization problems, linear programming can also be used to solve minimization problems. When done by-hand, these would require a modification of the Simplex method shown in the last section, but these problems can be solved by most technologic methods.
Example \(\PageIndex{3}\)
A company is creating a meal replacement bar. They plan to incorporate peanut butter, oats, and dried cranberries as the primary ingredients. The nutritional content of 10 grams of each is listed below, along with the cost, in cents, of each ingredient. Find the amount of each ingredient they should use to minimize the cost of producing a bar containing a minimum of 15g of each ingredient, at least 10g of protein and at most 14g of fat.
|
|
Peanut Butter, 10g |
Oats, 10g |
Cranberries, 10g |
|---|---|---|---|
|
Protein (grams) |
2.5 |
1.7 |
0 |
|
Fat (grams) |
5 |
0.7 |
0.1 |
|
Cost (cents) |
6 |
1 |
2 |
Solution
We start by introducing variables:
\(p =\) number of 10g servings of peanut butter
\(a =\) number of 10g servings of oats
\(c =\) number of 10g servings of cranberries
The total cost, \(C\), of producing the bar, in cents, will be \(C=6 p+1 a+2 c\).
Our first constraints come from the requirement for \(15 \mathrm{~g}\) of each ingredient, which is \(1.5\) servings (1.5 servings at \(10 \mathrm{~g}\) per serving \(=15 \mathrm{~g}\) ). Constructing those constraints \(p \geq 1.5, a \geq 1.5, c \geq 1.5\)
Next we look at the nutritional components. For protein, \(p\) servings of peanut butter will contain \(2.5 p\) grams of protein. Likewise, \(a\) servings of oats will have \(1.7 a\) grams of protein, and \(c\) servings of cranberries will have \(0 c\) grams of protein. Together, these need to be at least 10 grams, giving the constraint \(2.5 p+1.7 a+0 c \geq 10\)
We can construct a similar constraint for fat, in this case noting we want the fat to be at most \(14 \mathrm{~g}\) :
\(5 p+0.7 a+0.1 c \leq 14\)
We can now have our complete problem:
Minimize:
\[C=6 p+1 a+2 c \nonumber\]
Subject to:
\[\begin{align*} 2.5 p+1.7 a+0 c &\geq 10 \\ 5 p+0.7 a+0.1 c &\leq 14 \\ p \geq 1.5, a \geq 1.5, c &\geq 1.5\end{align*}\]
Turning to technology, we get a solution:
Optimal Solution:
\[C=15.6765; \quad p=1.5, \quad a=3.67647, \quad c=1.5\nonumber\]
Interpreting that result, the minimum cost of to produce the bar will be about \(15.7\) cents, by using 15 grams of peanut butter, \(36.8\) grams of oats, and 15 grams of dried cranberries.
Verifying our conditions, we can see that our recipe contains at least \(1.5\) servings of each ingredient. The protein content will be \(2.5(1.5)+1.7(3.68)+0(1.5) \approx 10\) grams.
The fat content will be \(5(1.5)+0.7(3.68)+0.1(1.5) \approx 10.2\) grams.
Exercise \(\PageIndex{1}\)
A factory manufactures three products, \(A, B\), and \(C\). Each product requires a certain number of hours of manufacturing, assembly and finishing time, shown below, along with the total time available and profit. Find production levels to maximize profit.
|
|
A |
B |
C |
Total Hours |
|---|---|---|---|---|
|
Manufacturing |
4 |
5 |
2 |
300 |
|
Assembly |
7 |
4 |
1 |
250 |
|
Finishing |
4 |
5 |
1 |
200 |
|
Profit |
175 |
130 |
40 |
|
- Answer
-
Our problem setup is:
Maximize :
\[P = 175A + 130B + 40C \nonumber\]
Subject to:
\[\begin{align*} 4A + 5B + 2C &\leq 300 \\ 7A + 4B + 1C &\leq 250 \\ 4A + 5B + 1C &\leq 200 \end{align*} \]
Solving this, we get the solution:
Optimal Solution:
\[P = 7907.89; A = 18.4211, B = 5.26316, C = 100\nonumber \]
Rounding down, producing \(A = 18\), \(B = 5\), and \(C = 100\) would use 297 hours of manufacturing, 246 hours of assembly, and 197 hours of finishing and have profit of $7800. We could fiddle with a few other nearby integer solutions:
\(A = 18, B = 5\), and \(C = 101\): Profit $7840
\(A = 18, B = 6\), and \(C = 98\): Profit $7850
\(A = 19, B = 4\), and \(C = 101\): Profit $7885
As you can see, finding optimal integer solutions is a harder problem.
In some cases we have to be clever with how we create our constraints to maintain the correct form of a linear programming problem while still meeting the requirements of the actual application.
Example \(\PageIndex{4}\)
A distribution company needs to ship products from its two warehouses to three retailers. Warehouse A has 1000 products in stock, and Warehouse B has 1200 products. Retailer 1 needs 700 products, Retailer 2 needs 500 products, and Retailer 3 needs 600 products The cost to ship a product from each warehouse to each retailer is shown below. Find the number of products the company should ship from each warehouse to each retailer to minimize shipping costs.
|
|
Retailer 1 |
Retailer 2 |
Retailer 3 |
|---|---|---|---|
|
Warehouse A |
3 |
5 |
6 |
|
Warehouse B |
4 |
7 |
5 |
Solution
To start this problem, we first need to define our variables. Since there are six different routes, we will need to define six variables:
\(A_1=\) the number of products shipped from Warehouse A to Retailer 1
\(B_1=\) the number of products shipped from Warehouse B to Retailer 1
\(A_2=\) the number of products shipped from Warehouse A to Retailer 2
We can similarly define variables \(B_2, A_3\) and \(B_3\).
Our objective function is the total shipping cost. Shipping \(A_1\) items from Warehouse \(A\) to Retailer 1 will cost $3 per item, so a total cost of \(3A_1\). Doing the same for the other variables gives our total cost equation:
\[C = 3{A_1} + 4{B_1} + 5{A_2} + 7{B_2} + 8{A_3} + 5{B_3}\nonumber\]
We know that Warehouse \(A\) has 1000 products in stock, so the total number of items shipped out of Warehouse \(A\) needs to be no more than 1000. Likewise Warehouse B can’t ship more than 1200 items. These give the constraints:
\[\begin{align*}A_1 + A_2 + A_3 \leq 1000 \\ {B_1} + {B_2} + {B_3} \leq 1200\end{align*}\]
Retailer 1 needs 700 products. While is technically a strict equality, we can set it up as an inequality, indicating the total number of product arriving at retailer 1 needs to be at least 700 products. Since we’re minimizing cost, there’s no way we’d end up shipping more than 700 items to the retailer. Setting up this constraint, and similar ones for the other three retailers:
\[\begin{align*} {A_1} + {B_1} \geq 700 \\ {A_2} + {B_2} \geq 500 \\ {A_3} + {B_3} \geq 600 \end{align*}\]
Our final problem setup is:
Minimize:
\[C = 3{A_1} + 4{B_1} + 5{A_2} + 7{B_2} + 8{A_3} + 5{B_3}\nonumber\]
Subject to:
\[ \begin{align*}{A_1} + {A_2} + {A_3} \leq 1000 \\ {B_1} + {B_2} + {B_3} \leq 1200\\ {A_1} + {B_1} \geq 700\\ {A_2} + {B_2} \geq 500 \\ {A_3} + {B_3} \geq 600\\ {A_1} \geq 0,{B_1} \geq 0,{A_2} \geq 0,{B_2} \geq 0,{A_3} \geq 0,{B_3} \geq 0\end{align*}\]
Solving this, we get the solution,
Optimal Solution:
\[C = 7800; A_1 = 500, B_1 = 200, A_2 = 500, B_2 = 0, A_3 = 0, B_3 = 600\nonumber\]
Important Topics of this Section
Setting up the objective and constraint equations for an application
Interpreting the solution to a linear programming question