### Linear Programming

A lot of interesting real-world problems can be solved with systems of linear inequalities.

For example, you go to your favorite restaurant and you want to be served by your best friend who happens to work there. However, your friend only waits tables in a certain region of the restaurant. The restaurant is also known for its great views, so you want to sit in a certain area of the restaurant that offers a good view. Solving a system of linear inequalities will allow you to find the area in the restaurant where you can sit to get the best view and be served by your friend.

Often, systems of linear inequalities deal with problems where you are trying to find the best possible situation given a set of constraints. Most of these application problems fall in a category called **linear programming** problems.

**Linear programming** is the process of taking various linear inequalities relating to some situation, and finding the *best* possible value under those conditions. A typical example would be taking the limitations of materials and labor at a factory, then determining the best production levels for maximal profits under those conditions. These kinds of problems are used every day in the organization and allocation of resources. These real-life systems can have dozens or hundreds of variables, or more. In this section, we’ll only work with the simple two-variable linear case.

The general process is to:

- Graph the inequalities (called
**constraints**) to form a bounded area on the coordinate plane (called**the feasibility region**). - Figure out the coordinates of the corners (or vertices) of this feasibility region by solving the system of equations that applies to each of the intersection points.
- Test these corner points in the formula (called the
**optimization equation**) for which you're trying to find the**maximum**or**minimum**value.

#### Finding Maximum and Minimum Values

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.

#### Real-World Application: Stock Market

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.**

#### Real-World Application: Revenue

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

#### 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 &\ge3x+17< \quad \text{Solve for y.}\\
y&\ge\frac{3}{2}x+8.5<\quad \text{Divide each side by 2.}\end{align*}

Graph each equation and shade accordingly:

### Review

Solve the following linear programming problems.

- Given the following constraints, find the maximum and minimum values of \begin{align*}z = -x + 5y\end{align*}: \begin{align*}x + 3y \le 0\!\\ x - y \ge 0\!\\ 3x - 7y \le 16\end{align*}

Santa Claus is assigning elves to work an eight-hour shift making toy trucks. Apprentice elves draw a wage of five candy canes per hour worked, but can only make four trucks an hour. Senior elves can make six trucks an hour and are paid eight candy canes per hour. There’s only room for nine elves in the truck shop, and due to a candy-makers’ strike, Santa Claus can only pay out 480 candy canes for the whole 8-hour shift.

- How many senior elves and how many apprentice elves should work this shift to maximize the number of trucks that get made?
- How many trucks will be made?
- Just before the shift begins, the apprentice elves demand a wage increase; they insist on being paid seven candy canes an hour. Now how many apprentice elves and how many senior elves should Santa assign to this shift?
- How many trucks will now get made, and how many candy canes will Santa have left over?

In Adrian’s Furniture Shop, Adrian assembles both bookcases and TV cabinets. Each type of furniture takes her about the same time to assemble. She figures she has time to make at most 18 pieces of furniture by this Saturday. The materials for each bookcase cost her $20 and the materials for each TV stand costs her $45. She has $600 to spend on materials. Adrian makes a profit of $60 on each bookcase and a profit of $100 on each TV stand.

- Set up a system of inequalities. What \begin{align*}x-\end{align*} and \begin{align*}y-\end{align*}values do you get for the point where Adrian’s profit is maximized? Does this solution make sense in the real world?
- What two possible real-world \begin{align*}x-\end{align*}values and what two possible real-world \begin{align*}y-\end{align*}values would be closest to the values in that solution?
- With two choices each for \begin{align*}x\end{align*} and \begin{align*}y\end{align*}, there are four possible combinations of \begin{align*}x-\end{align*} and \begin{align*}y-\end{align*}values. Of those four combinations, which ones actually fall within the feasibility region of the problem?
- Which one of those feasible combinations seems like it would generate the most profit? Test out each one to confirm your guess. How much profit will Adrian make with that combination?
- Based on Adrian’s previous sales figures, she doesn’t think she can sell more than 8 TV stands. Now how many of each piece of furniture should she make, and what will her profit be?
- Suppose Adrian is confident she can sell all the furniture she can make, but she doesn’t have room to display more than 7 bookcases in her shop. Now how many of each piece of furniture should she make, and what will her profit be?
- Here’s a “linear programming” problem on a line instead of a plane: Given the constraints \begin{align*}x \le 5\end{align*} and \begin{align*}x \ge -2\end{align*}, maximize the value of \begin{align*}y\end{align*} where \begin{align*}y = x + 3\end{align*}.

### Review (Answers)

To view the Review answers, open this PDF file and look for section 7.11.

### Texas Instruments Resources

*In the CK-12 Texas Instruments Algebra I FlexBook® resource, there are graphing calculator activities designed to supplement the objectives for some of the lessons in this chapter. See http://www.ck12.org/flexr/chapter/9617.*