4: Linear Programming
- Page ID
- 40863
\( \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}\)1. Linear Programming (An Example)
Maximize
\[P = 2x + 5\]
subject to the constraints
\(x + 3y \leq 15\)
\(4x + y \leq16\)
\(x \geq 0\)
\(y \geq 0\)
First we graph the system of inequalities.
-
For
\(x + 3y = 15\)
we use \((0,5)\) and \((15,0)\) and note that the arrows point towards \((0,0)\). -
For
\(4x + y = 16\)
we use \((0,16)\) and \((4,0)\) and note that the arrows point towards \((0,0)\). -
\(x \geq 0\) and \(y \geq 0\) constrain the region in the first quadrant.
We have a closed and bounded region (closed means that all the boundary lines are solid). We now need to find the largest value that
\[P = 2x + 5y\]
gives when \((x,y)\) is inside the region. Lets try some guesses.
-
If \( P = 0\) we can graph
\(2x + 5y = 0 \)
and note that the graph is a line that intersects the region. -
If \( P = 1\) we can graph
\(2x + 5y = 1 \)
and note that the graph is a straight line that intersects the region. Notice also that these lines are parallel. -
If \(P = 10\), we again get a parallel line that intersects the region.
-
If \(P = 30\), we get a parallel line that does not intersect the region. Therefore, \(P\) must be smaller than 30.
We are searching for the parallel line that is farthest from the origin that intersects the region. this occurs at the corner point \((3,4)\).
2. The Big Theorem
Theorem: Fundamental Theorem of Linear Programming
If a linear programming problem has a solution, then the solution always occurs at a corner point. If two adjacent corner points give solutions, then every point on the line segment connecting them also give that solution. If the profit function is
\(P = ax + by \)
then if the region is bounded, then \(P\) obtains both a maximum and a minimum.
-
If \(a\) and \(b\) are positive, then \(P\) will always have a minimum in the region if the region lies entirely within the first quadrant.
Step by Step Process
-
Graph the region and list the corner points in a table. You find the corner points by using matrices. Note if the region is bounded, or if we are looking for a minimum and that region is restricted to the first quadrant.
-
In the second column evaluate the Profit function
-
If we are looking for a maximum, circle the largest number in the profit column. If there is a unique maximum then this is the solution. If there are two maxima, then the entire line segment between the two points gives a solution. If we are looking for a minimum, then circle the smallest number in the profit column, and proceed as before.
\[80x + 50y \]
subject to the constraints
\(2x + y \leq 80\)
\(x + y \leq 50\)
\(x \geq 0\)
\(y \geq 0\)
We graph the equations and notice that there are three easy to find corner points
\((0,0), (40,0), (0,50)\)
The forth corner point is at the intersection of the two lines. The matrix is
| \(A =\) |
|
Note that the determinant is
\(2 - 1 = 1 \)
so that a solution exists. We use a calculator to find
| \(A^{-1} =\) |
|
Hence the solution is
\((30,20)\)
Now construct a profit table:
| Point | \(80x + 50y\) |
| \((0,0)\) | 0 |
| \((40,0)\) | 3,200 |
| \((0,50)\) | 2,500 |
| \((30,20)\) | 3,400 |
Since the largest number is 3,400, we can conclude that the maximum occurs at the point \((30,20)\) with a value of 3,400.
3. Linear Programming Applications
Solomon manufactures parabolic skis and conventional skis. The manufacturing process is done first at the fabricating department and then at the finishing department. The fabricating department has at most 108 labor hours per day available while the finishing department has at most 24 labor hours available per day. The parabolic ski requires 6 labor hours at the fabricating department and one labor hour at the finishing department. The conventional ski requires 4 labor hours at the fabricating department and one labor hour at the finishing department. Solomon makes a $40 profit on its parabolic skis and $30 on its conventional skis. How many of each type of ski should be manufactured each day to realize a maximum profit.
Harveys is planning to add an additional room to its casino. The casino consists of card tables and slot machines. On an average day, a slot machine makes $2,000, while a card table makes $30,000. The total square feet available at Harveys' new casino room for gaming is 3,000 square feet and the total number of additional employees allowed by the gaming commission is 45. If a slot machine occupies 6 square feet and requires one employee per 12 machines and a card table occupies 54 square feet and requires three employees per two tables, how many slot machines and how many card tables should be put into the new casino room in order to maximize profit? What is the maximum Profit? (Smaller tables are permitted)
A veterinarian wishes to prepare a supply of dog food by mixing Purina Big chunks and Alpo Meaties. The mixture is to contain at least 50 units of carbohydrates, at least 36 units of protein, and at least 40 units of fat. The Big Chunks contain 3 units of carbohydrates per pound, 3 units of protein per pound, and 2 units of fat per pound. The Meaties contain 5 units of carbohydrates per pound, 4 units of protein per pound, and 8 units of fat per pound. The veterinarian can purchase the Big Chunks for 44 cents per pound and the Meaties for 80 cents per pound. How many pounds of each dog food should be mixed in order to meet the dietary requirements at the least cost?