3.4: Linear Programming - Minimization Applications
- Page ID
- 147292
\( \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 this section, you will learn to:
- Formulate minimization linear programming problems.
- Graph feasible regions for minimization linear programming problems.
- Determine optimal solutions for minimization linear programming problems.
Before you get started, take this prerequisite quiz.
1. Graph this system of inequalities:
\(\left\{\begin{array} {l} x+3y\geq6\\y>\dfrac{1}{3}x-1\end{array}\right.\)
- Click here to check your answer
-
If you missed this problem, review Section 2.3. (Note that this will open a different textbook in a new window.)
2. Graph this system of inequalities:
\(\left\{\begin{array} {l} y\geq 2x+1\\y\geq-3x+6\\x\geq0\\y\geq0\end{array}\right.\)
- Click here to check your answer
-
(The solution is in the upper center region.)
If you missed this problem, review Section 2.3. (Note that this will open a different textbook in a new window.)
Minimization linear programming problems are solved in much the same way as the maximization problems.
For the standard minimization linear program, the constraints are of the form \(ax + by ≥ c\), as opposed to the form \(ax + by ≤ c\) for the standard maximization problem. As a result, the feasible solution extends indefinitely to the upper right of the first quadrant, and is unbounded. But that is not a concern, since in order to minimize the objective function, the line associated with the objective function is moved towards the origin, and the critical point that minimizes the function is closest to the origin.
However, one should be aware that in the case of an unbounded feasible region, the possibility of no optimal solution exists.
Minimization Linear Programming Problems
- Define the unknowns.
- Write the objective function that needs to be minimized.
- Write the constraints.
- For standard minimization linear programming problems, constraints are of the form: \(ax + by ≥ c\)
- Since the variables are non-negative, include the constraints: \(x ≥ 0\); \(y ≥ 0\).
- Graph the constraints.
- Shade the feasible region.
- Find the corner points.
- Find the value of the objective function at each corner point to determine the corner point that gives the minimum value.
- State the answer to the original question.
At a university, Professor Symons wishes to employ two people, John and Mary, to grade papers for his classes. John is a graduate student and can grade 20 papers per hour; John earns $15 per hour for grading papers. Mary is a post-doctoral associate and can grade 30 papers per hour; Mary earns $25 per hour for grading papers. Each must be employed at least one hour a week to justify their employment.
If Prof. Symons has at least 110 papers to be graded each week, how many hours per week should he employ each person to minimize the cost?
Solution
1. We define the unknowns:
- Let the number of hours per week John is employed = \(x\).
- and the number of hours per week Mary is employed = \(y\).
2. Write the objective function. We are trying to minimize cost, so the function should represent the total cost. In this case, cost is given by:
\[C = 15x + 25y \nonumber \]
3. Find the constraints.
- The fact that each must work at least one hour each week results in the following two constraints:
\[\begin{array}{l}
x \geq 1 \\
y \geq 1
\end{array} \nonumber \]
Note that this already includes or covers the usual constraints that \(x\) and \(y\) are non-negative, so we don't need to include additional inequalities to state this.
- We are limited by the minimum number of papers that must be graded. Since John can grade 20 papers per hour and Mary 30 papers per hour, and there are at least 110 papers to be graded per week, we get
\[20x + 30y ≥ 110 \nonumber\]
- The problem has been formulated as follows.
\[\begin{array}{ll}
\textbf { Minimize } & \mathrm{C}=15 \mathrm{x}+25 \mathrm{y} \\
\textbf { Subject to: } & \mathrm{x} \geq 1 \\
& \mathrm{y} \geq 1 \\
& 20 \mathrm{x}+30 \mathrm{y} \geq 110
\end{array} \nonumber\]
4. Next, we graph all constraints:
5. Determine the feasible region.
Note that this feasible region extends indefinitely up and to the right. This region is called unbounded as it extends without an upper bound. (In practicality, a maximum number of hours for each employee would prevent this, if we had been given this information in this problem.)
6. Determine the corner points of the feasible region.
7. Substitute these points in the objective function to see which point gives us the minimum cost each week. The results are listed below.
| Critical points | Cost = \(15x + 25y\) |
| (1, 3) | C = 15(1) + 25(3) = $90 |
| (4, 1) | C = 15(4) + 25(1) = $85 |
8. The point (4, 1) gives the least cost, and that cost is $85. Therefore, we conclude that in order to minimize grading costs, Professor Symons should employ John 4 hours a week, and Mary 1 hour a week at a cost of $85 per week.
Professor Hamer is on a low cholesterol diet. During lunch at the college cafeteria, he always chooses between two meals: pasta or tofu. The table below lists the amount of protein, carbohydrates, and vitamins each meal provides along with the amount of cholesterol he is trying to minimize. Mr. Hamer needs at least 200 grams of protein, 960 grams of carbohydrates, and 40 grams of vitamin C for lunch each month. He plans to eat lunch in the cafeteria at least 20 times. How many days should he have the pasta meal, and how many days the tofu meal so that he gets the adequate amount of protein, carbohydrates, and vitamins and at the same time minimizes his cholesterol intake?
|
PASTA |
TOFU |
|
|
PROTEIN |
8g |
16g |
|
CARBOHYDRATES |
60g |
40g |
|
VITAMIN C |
2g |
2g |
|
CHOLESTEROL |
60mg |
50mg |
Solution
1. We define the unknowns as follows.
- Let the number of days Mr. Hamer eats pasta = \(x\).
- Let the number of days Mr. Hamer eats tofu = \(y\).
2. The objective function represents the quantity to be minimized. Since he is trying to minimize his cholesterol intake, our objective function represents the total amount of cholesterol C provided by both meals.
\[C = 60x + 50y \nonumber \]
3. Write all constraints.
- He needs to include a minimum amount of protein. The total amount of protein provided by both meals is
\[8x + 16y ≥ 200 \nonumber \]
- Additionally, he needs to include a minimum amount of carbohydrates . The total amount of carbohydrates is
\[60 x+40 y \geq 960 \nonumber\]
- Similarly, he needs to include a minimum amount of vitamins. The total amount of vitamin C is
\[2 x+2 y \geq 40 \nonumber\]
- Finally, he needs to eat at least 20 meals in the cafeteria. Therefore
\[ x+y \geq 20 \nonumber\]
- He cannot eat a negative number of meals, so x and y are both non-negative:
\[x ≥ 0 \text{, and } y ≥ 0 \nonumber\]
- We summarize all information as follows:
\[\begin{array}{ll}
\textbf { Minimize } & \mathrm{C}=60 \mathrm{x}+50 \mathrm{y} \\
\textbf { Subject to: } & 8 \mathrm{x}+16 \mathrm{y} \geq 200 \\
& 60 \mathrm{x}+40 \mathrm{y} \geq 960 \\
& 2 \mathrm{x}+2 \mathrm{y} \geq 40 \\ & \mathrm{x}+ \mathrm{y} \geq 20 \\
& \mathrm{x} \geq 0 ; \mathrm{y} \geq 0
\end{array} \nonumber\]
4. We graph the constraints. As this particular graph has many inequalities, graphing all of them gets quite cluttered. The graph below shows the OPPOSITE of each inequality, leaving the feasible region as the void or unshaded portion of the graph.
Also note that the line \(2x+2y = 40\) appears to be missing. This is because it is mathematically equivalent to the line \(x+y=20\). In essence, the blue line above is "hidden" underneath the red line.
5. Determine the feasible region.
6. Determine the corner points of the feasible region.
7. Substitute these points in the objective function to see which point gives us the smallest value. The results are listed below.
| Critical points | Carbohydrates = \(60x + 50y\) |
| (0, 24) | C = 60(0) + 50(24) = 1200 |
| (8, 12) | C = 60(8) + 50(12) = 1080 |
| (15, 5) | C = 60(15) + 50(5) = 1150 |
| (25, 0) | C = 60(25) + 50(0) = 1500 |
8. The point (8, 12) gives the least cholesterol, which is 1080 mg. This states that for every 20 meals, Professor Hamer should eat the pasta meal 8 days and the tofu meal 12 days.
We must be aware that in some cases, a linear program may not have an optimal solution.
- A linear program can fail to have an optimal solution is if there is not a feasible region. If the inequality constraints are not compatible, there may not be a region in the graph that satisfies all the constraints. If the linear program does not have a feasible solution satisfying all constraints, then it can not have an optimal solution.
- A linear program can fail to have an optimal solution if the feasible region is unbounded.
- The two minimization linear programs we examined had unbounded feasible regions. The feasible region was bounded by constraints on some sides but was not entirely enclosed by the constraints. Both of the minimization problems had optimal solutions.
- However, if we were to consider a maximization problem with a similar unbounded feasible region, the linear program would have no optimal solution. No matter what values of x and y were selected, we could always find other values of \(x\) and \(y\) that would produce a higher value for the objective function. In other words, if the value of the objective function can be increased without bound in a linear program with an unbounded feasible region, there is no optimal maximum solution.
Although the method of solving minimization problems is similar to that of the maximization problems, we still feel that we should summarize the steps involved.
Minimization Linear Programming Problems
- Define the unknowns.
- Write the objective function that needs to be minimized.
- Write the constraints.
- For standard minimization linear programming problems, constraints are of the form: \(ax + by ≥ c\)
- Since the variables are non-negative, include the constraints: \(x ≥ 0\); \(y ≥ 0\).
- Graph the constraints.
- Shade the feasible region.
- Find the corner points.
- Find the value of the objective function at each corner point to determine the corner point that gives the minimum value.
- State the answer to the original question.