Linear Programming

If \(\begin{align*}z = 2x + 5y\end{align*}\), find the maximum and minimum values of \(\begin{align*}z\end{align*}\) given these constraints:

\(\begin{align*}2x - y & \le 12\\ 4x + 3y & \ge 0\\ x - y & \ge 6\end{align*}\)

First, we need to find the solution to this system of linear inequalities by graphing and shading appropriately. To graph the inequalities, we rewrite them in slope-intercept form:

\(\begin{align*}y & \ge 2x - 12\\ y & \ge - \frac{4}{3}x\\ y & \le x - 6\end{align*}\)

These three linear inequalities are called the constraints, and here is their graph:

The shaded region in the graph is called the feasibility region. All possible solutions to the system occur in that region; now we must try to find the maximum and minimum values of the variable \(\begin{align*}z\end{align*}\) within that region. In other words, which values of \(\begin{align*}x\end{align*}\) and \(\begin{align*}y\end{align*}\) within the feasibility region will give us the greatest and smallest overall values for the expression \(\begin{align*}2x + 5y\end{align*}\)?

Fortunately, we don't have to test every point in the region to find that out. It just so happens that the minimum or maximum value of the optimization equation in a linear system like this will always be found at one of the vertices (the corners) of the feasibility region; we just have to figure out which vertices. So for each vertex - each point where two of the lines on the graph cross - we need to solve the system of just those two equations, and then find the value of \(\begin{align*}z\end{align*}\) at that point.

The first system consists of the equations \(\begin{align*}y = 2x - 12\end{align*}\) and \(\begin{align*}y = - \frac{4}{3}x\end{align*}\). We can solve this system by substitution:

\(\begin{align*}- \frac{4}{3}x &= 2x - 12 \Rightarrow -4x = 6x - 36 \Rightarrow -10x = -36 \Rightarrow x = 3.6\\ y &= 2x - 12 \Rightarrow y = 2(3.6) - 12 \Rightarrow y = - 4.8\end{align*}\)

The lines intersect at the point (3.6, -4.8).

The second system consists of the equations \(\begin{align*}y = 2x - 12\end{align*}\) and \(\begin{align*}y = x - 6\end{align*}\). Solving this system by substitution:

\(\begin{align*}x - 6 &= 2x - 12 \Rightarrow 6 = x \Rightarrow x = 6\\ y &= x - 6 \Rightarrow y = 6 - 6 \Rightarrow y = 0\end{align*}\)

The lines intersect at the point (6, 0).

The third system consists of the equations \(\begin{align*}y = - \frac{4}{3}x\end{align*}\) and \(\begin{align*}y = x - 6\end{align*}\). Solving this system by substitution:

\(\begin{align*}x - 6 &= - \frac{4}{3}x \Rightarrow 3x - 18 = -4x \Rightarrow 7x = 18 \Rightarrow x = 2.57\\ y &= x - 6 \Rightarrow y = 2.57 - 6 \Rightarrow y = -3.43\end{align*}\)

The lines intersect at the point (2.57, -3.43).

So now we have three different points that might give us the maximum and minimum values for \(\begin{align*}z\end{align*}\). To find out which ones actually do give the maximum and minimum values, we can plug the points into the optimization equation \(\begin{align*}z = 2x + 5y\end{align*}\).

When we plug in (3.6, -4.8), we get \(\begin{align*}z = 2(3.6) +5(-4.8) = -16.8\end{align*}\).

When we plug in (6, 0), we get \(\begin{align*}z = 2(6) + 5(0) = 12\end{align*}\).

When we plug in (2.57, -3.43), we get \(\begin{align*}z = 2(2.57) + 5(-3.43) = -12.01\end{align*}\).

So we can see that the point (6, 0) gives us the maximum possible value for \(\begin{align*}z\end{align*}\) and the point (3.6, –4.8) gives us the minimum value.

In the previous example, we learned how to apply the method of linear programming in the abstract. In the next example, we'll look at a real-life application.

You have $10,000 to invest, and three different funds to choose from. The municipal bond fund has a 5% return, the local bank's CDs have a 7% return, and a high-risk account has an expected 10% return. To minimize risk, you decide not to invest any more than $1,000 in the high-risk account. For tax reasons, you need to invest at least three times as much in the municipal bonds as in the bank CDs. What's the best way to distribute your money given these constraints?

Let's define our variables:

\(\begin{align*}x\end{align*}\) is the amount of money invested in the municipal bond at 5% return

\(\begin{align*}y\end{align*}\) is the amount of money invested in the bank's CD at 7% return

\(\begin{align*}10000 - x - y\end{align*}\) is the amount of money invested in the high-risk account at 10% return

\(\begin{align*}z\end{align*}\) is the total interest returned from all the investments, so \(\begin{align*}z = .05x + .07y + .1(10000 - x - y)\end{align*}\) or \(\begin{align*}z = 1000 - 0.05x - 0.03y\end{align*}\). This is the amount that we are trying to maximize. Our goal is to find the values of \(\begin{align*}x\end{align*}\) and \(\begin{align*}y\end{align*}\) that maximizes the value of \(\begin{align*}z\end{align*}\).

Now, let's write inequalities for the constraints:

You decide not to invest more than $1000 in the high-risk account - that means:

\(\begin{align*}10000 - x - y \le 1000\end{align*}\)

You need to invest at least three times as much in the municipal bonds as in the bank CDs - that means:

\(\begin{align*}3y \le x\end{align*}\)

Also, you can't invest less than zero dollars in each account, so:

\(\begin{align*}x & \ge 0\\ y & \ge 0\\ 10000 - x - y & \ge 0\end{align*}\)

To summarize, we must maximize the expression \(\begin{align*}z = 1000 - .05x - .03y\end{align*}\) using the constraints:

\(\begin{align*}& 10000 - x - y \le 1000 && && y \ge 9000 - x\\ & 3y \le x && && y \le \frac{x}{3}\\ & x \ge 0 && \text{Or in slope-intercept form:} && x \ge 0\\ & y \ge 0 && && y \ge 0\\ & 10000 - x - y \ge 0 && && y \le 10000 - x\end{align*}\)

Step 1: Find the solution region to the set of inequalities by graphing each line and shading appropriately. The following figure shows the overlapping region:

The purple region is the feasibility region where all the possible solutions can occur.

Step 2: Next we need to find the corner points of the feasibility region. Notice that there are four corners. To find their coordinates, we must pair up the relevant equations and solve each resulting system.

System 1:

\(\begin{align*}y = \frac{x}{3}\!\\ y = 10000 - x\end{align*}\)

Substitute the first equation into the second equation:

\(\begin{align*}\frac{x}{3} &= 10000 - x \Rightarrow x = 30000 - 3x \Rightarrow 4x = 30000 \Rightarrow x = 7500\\ y &= \frac{x}{3} \Rightarrow y = \frac{7500}{3} \Rightarrow y = 2500\end{align*}\)

The intersection point is (7500, 2500).

System 2:

\(\begin{align*}y = \frac{x}{3}\!\\ y = 9000 - x\end{align*}\)

Substitute the first equation into the second equation:

\(\begin{align*}\frac{x}{3} &= 9000 - x \Rightarrow x = 27000 - 3x \Rightarrow 4x = 27000 \Rightarrow x = 6750\\ y &= \frac{x}{3} \Rightarrow y = \frac{6750}{3} \Rightarrow y = 2250\end{align*}\)

The intersection point is (6750, 2250).

System 3:

\(\begin{align*}y = 0\!\\ y = 10000 - x\end{align*}\)

The intersection point is (10000, 0).

System 4:

\(\begin{align*}y = 0\!\\ y = 9000 - x\end{align*}\)

The intersection point is (9000, 0).

Step 3: In order to find the maximum value for \(\begin{align*}z\end{align*}\), we need to plug all the intersection points into the equation for \(\begin{align*}z\end{align*}\) and find which one yields the largest number.

(7500, 2500): \(\begin{align*}z = 1000 - 0.05(7500) - 0.03(2500) = 550\end{align*}\)

(6750, 2250): \(\begin{align*}z = 1000 - 0.05(6750) - 0.03(2250) = 595\end{align*}\)

(10000, 0): \(\begin{align*}z = 1000 - 0.05(10000) - 0.03(0) = 500\end{align*}\)

(9000, 0): \(\begin{align*}z = 1000 - 0.05(9000) - 0.03(0) = 550\end{align*}\)

The maximum return on the investment of $595 occurs at the point (6750, 2250). This means that:

$6,750 is invested in the municipal bonds.

$2,250 is invested in the bank CDs.

$1,000 is invested in the high-risk account.

James is trying to expand his pastry business to include cupcakes and personal cakes. He has 40 hours available to decorate the new items and can use no more than 22 pounds of cake mix. Each personal cake requires 2 pounds of cake mix and 2 hours to decorate. Each cupcake order requires one pound of cake mix and 4 hours to decorate. If he can sell each personal cake for $14.99 and each cupcake order for $16.99, how many personal cakes and cupcake orders should James make to make the most revenue?

There are four inequalities in this situation. First, state the variables. Let \(\begin{align*}p=\end{align*}\) the number of personal cakes and \(\begin{align*}c=\end{align*}\) the number of cupcake orders.

Translate this into a system of inequalities.

\(\begin{align*}2p+1c \le 22\end{align*}\) – This is the amount of available cake mix.

\(\begin{align*}2p+4c \le 40\end{align*}\) – This is the available time to decorate.

\(\begin{align*}p \ge 0\end{align*}\) – You cannot make negative personal cakes.

\(\begin{align*}c \ge 0\end{align*}\) – You cannot make negative cupcake orders.

Now graph each inequality and determine the feasible region.

The feasible region has four vertices: {(0, 0),(0, 10),(11, 0),(8, 6)}. According to our theorem, the optimization answer will only occur at one of these vertices.

Write the optimization equation. How much of each type of order should James make to bring in the most revenue?

\(\begin{align*}14.99p+16.99c=maximum \ revenue\end{align*}\)

Substitute each ordered pair to determine which makes the most money.

\(\begin{align*}(0,0) & \rightarrow \$0.00\\ (0,10) & \rightarrow 14.99(0)+16.99(10)=\$169.90\\ (11,0) &\rightarrow 14.99(11)+16.99(0)=\$164.89\\ (8,6) & \rightarrow 14.99(8)+16.99(6)=\$221.86\end{align*}\)

To make the most revenue, James should make 8 personal cakes and 6 cupcake orders.

Example 1

Graph the solution to the following system:

\(\begin{align*} x-y< -6\\ 2y\ge 3x+17\end{align*}\)

Solution:

First we will rewrite the equations in slope-intercept form in order to graph them:

Inequality 1 \(\begin{align*} x-y &< -6 \quad \text{Solve for y.}\\ -y& < -x -6 \quad \text{Subtract x from each side.}\\ y & > x+6 \quad \text{Multiply each side by -1, flipping the inequality.}\end{align*}\)

Inequality 2 \( \begin{align*} 2y & \geq 3x+17 < \quad \text{Solve for y.} \\ y & \geq \frac{3}{2}x+8.5 < \quad \text{Divide each side by 2.}\end{align*} \)

Graph each equation and shade accordingly: