Here, we learn about linear programming, a management science technique that helps a business allocate its resources. Whether those resources are at hand or can be purchased, the goal is to decide on a particular mix of products that will maximize profit or that will operate in ways that cut costs. For example, a large medical center needs to stock resources such as bandages, syringes, and alcohol wipes, as well as have different kinds of laborers, toilet paper, and paper towels available when needed.

The technique is so powerful that it is estimated that much more computer time is used solving linear programming types of problems than for any other purpose for which business managers and decision makers use computers.

Linear programming is an example of “new” mathematics. It came into being, along with many other management science techniques, during and shortly after World War II, in the 1940s. It is quite young as intellectual ideas go. Yet, during its short history, linear programming has changed the way businesses and governments make decisions, from ‘"seat-of-the-pants” methods based on guesswork and intuition to using an algorithm based on available data and guaranteed to produce an optimal decision.

Linear programming is but one operations research tool belonging to a family of tools known as mathematical programming. Another such tool is integer programming. The difference between linear programming and integer programming is that for linear programming, the quantities being studied can take on values such as $\pi =3.14159\dots$ or $7\frac{1}{8}$; in integer programming, the values are confined to whole numbers such as 8, 50, or 1,102,362. Whole numbers are conceptually easier than the broader group consisting of all numbers that can be represented by decimals ($1.32,1.455555\dots$), yet integerprogramming problems have proved much harder to solve.

In the discussions that follow, we often describe “relaxed” versions of integer-programming problems as linear-programming problems. For example, it would make no sense to produce 3.24 dolls to sell. So, strictly speaking, we must find an optimum whole number of dolls to produce. If we are ‘lucky,” the linear-programming problem associated with an integer-programming problem has an integer solution. In this case, we have also found the correct answer to the integer-programming problem. Some other examples that fall into this category are discussed below.

Linear programming has saved businesses and governments billions of dollars. Of all the management science techniques presented in this book, linear programming is far and away the most frequently used. It can be applied in a variety of situations, in addition to the one we study in this chapter. Some of the problems studied in Chapters 1, 2, and 3—for example, the traveling salesman (TSP) and scheduling problems—can be viewed as linear-programming problems. Linear programming is an excellent example of a mathematical technique useful for solving many different kinds of problems that at first do not seem to be similar problems at all. It has been suggested that without linear programming, management science would never have been born as a special branch of knowledge.

Next, we study how to use linear programming to solve a special kind of problem—a mixture problem. Realistic versions of such problems would be much more involved. Our discussion is designed to give you the flavor of what is actually done. Realistic examples of what follows are commonly used in the manufacture of different kinds of breads from the grain flours available, and in the making of different kinds of sausages from meats such as beef and pork.

Mixture problems are widespread because nearly every product in our economy is created by combining resources. A typical example would be how different kinds of aviation fuel are manufactured using different kinds of crude oil.

Let’s analyze small versions of the kinds of problems that might confront a toy or a beverage manufacturer. Both manufacturers can sell many different products on which each company can make a profit. There could be dozens of possible products and many resources. A manufacturer must periodically look at the quantities and prices of resources and then determine which products should be produced in which quantities in order to gain the greatest, or optimum, profit (see Spotlight 4.1). This is an enormous task that usually requires a computer to solve.

What does it mean to find a solution to a linear-programming mixture problem? A solution to a mixture problem is a production policy that tells us how many units of each product to make.

Common Features of Mixture Problems

Although our first mixture problem (Example 1) has only two products and one resource, it does contain the essential features that are common to all mixture problems:

Case Studies in Linear Programming 4.1

The examples we show are not designed to be realistic. Rather, our goal is to demonstrate how ideas whose roots are in basic algebra and geometry can solve, when scaled up to realistic versions, problems that save Americans much time and money and make our government and American businesses more efficient.

Translating Mixture Charts into Mathematical Form

Consider again the mixture chart in Figure 4.1. What can we say about the numbers of skateboards and dolls that might be manufactured? Clearly, we cannot make negative numbers of skateboards or dolls. Because we are using the letter $x$ to represent the number of skateboards we plan to make, we can write down the algebraic expression that $x\ge 0$. Here, we are using the standard symbol $\ge$ for “greater than or equal to.”

Algebraic expressions that involve the symbol $\ge$ or its companion symbols $\le$ (less than or equal to), $>$ (greater than), and $<$ (less than) are known as inequalities. We can also write down an inequality for the $y$ number of dolls we plan to make, based on the fact that we cannot make a negative number of dolls. Thus, we must have $y\ge 0$. We will use the phrase minimum constraints for these two inequalities, $x\ge 0$ and $y\ge 0$, which mean that we cannot manufacture negative numbers of objects.

However, we also have only a limited number of units of plastic available. How can we represent this information? Consulting the mixture table, we see that we need 5 units of plastic for every skateboard we make. Thus, we will need $5x$ (5 times $x$) units of plastic for the $x$ skateboards we make. Similarly, we will need $2y$ (2 times $y$) units of plastic for the $y$ dolls we make. Hence we will need $5x+2y$ units of plastic for the mixture of skateboards and dolls we make. We added the $5x$ and $2y$ because we need to find the total plastic used when we make a mixture of skateboards and dolls.

Reading from the table, we see that we are limited by having only 60 units of plastic. So we can express the resource constraint imposed by the limited number of units of plastic by writing that $5x+2y\ge 60$. Here, we use the symbol for less than or equal to, $\le$, to express the fact that we cannot use more than the amount of plastic we have available.

Notice that all the numbers in this inequality can be obtained from a column of the mixture chart. One of the reasons that we construct a mixture chart is that it helps speed up the conversion of the information about the problem we wish to solve into inequalities. The setup phase of a realistic linear programming problem, constructing the mathematical model of a manufacturing situation, is often the hardest and most complex step in getting an answer.

In addition to the resource inequalities (of which realistic problems will often have hundreds), there is one additional algebraic expression, this time an equality, that the mixture table allows us to create. Using the mixture table, we can compute the profit that will be produced when we manufacture different mixtures. For each skateboard, we make a profit of $1, so if $x$ skateboards are made, the profit is $1X$ (1 times $x$). For each doll made, the profit is $0.55. So if $y$ dolls are made, the profit is $0.55y$ (0.55 times $y$). Denoting by $P$ the total profit from making $x$ skateboards and $y$ dolls, we get the equation

Note that unlike the situation for the resources where we got an inequality, here we get an expression for what the profit will be as we vary the numbers of skateboards and dolls manufactured. Our goal is to find which values of $x$ and $y$ (skateboards and dolls) make this profit as large as possible.

Representing the Feasible Region with a Picture

After we have constructed inequalities using a mixture chart or have the inequalities that must be obeyed for a more general linear-programming problem, we can draw a helpful picture to visualize the choices to be made in solving the problem. This picture will show in a convenient way the different choices that are available in solving the linear-programming problem at hand. To get the picture that will help us, we need to draw graphs of the inequalities associated with the linear-programming problem.

To draw the graph of an inequality, let’s first review how to draw the graph of the equation of a straight line. Remember that two points can be used to uniquely determine a straight line. Let’s use the equation associated with the less-than-or- equal-to inequality

namely,

There are two points that are easy to find on this line: the $x$- and $y$-intercepts. When $x=0$, this gives rise to one point on the line, and when $y=0$, we can find another point. (See Figure 4.3.) When $x=0$, if we substitute this value in the equation $5x+2y=60$, we get $5\left(0\right)+2y=60$. Solving this equation, we discover that $y=30$. Similarly, if we substitute $y=0$ in the equation $5x+2y=60$, we get $5x+2\left(0\right)=60$, from which we conclude that $x=12$. We now have two points (0, 30) and (12, 0) that lie on the line $5x+2y=60$.

We are using the usual convention that when we write a pair such as (3, 10), we are describing a point that has $x=3$ and $y=10$. We always list the $x$-value ($x$-coordinate) first in such a pair and the $y$-value ($y$-coordinate) second. Furthermore, when a point ($x,y$) is represented in a diagram, larger values of $x$ are shown farther to the right (east) and larger values of $y$ are shown farther up (north).

Using the two points we found on the line $5x+2y=60$, we can draw the graph shown in Figure 4.3a, where we have also displayed the point (3, 10). How do we know that (3, 10) is not on the line? We can see this by replacing $x$ by 3 and $y$ by 10 in the equation $5x+2y=60$, getting $5\left(3\right)+2\left(10\right)=15+20=35$. To have been on the line, we would have to have had the value 60. Furthermore, we know that the point (3, 10) is below the line $5x+2y=60$ because when $x=3$, and we replace $x$ by this value in the equation $5x+2y=60$, we get $5\left(3\right)+2y=60$, which means that $y=45/2$. Since 45/2 is greater than 10, the y-value for the point (3, 10), we conclude that (3, 10) is below the line.

Now that we know what the graph of the equation $5x+2y=60$ looks like, we can think through where points ($x,y$) that satisfy $5x+2y<60$ are located. The points that are either on the line $5x+2y=60$ or satisfy $5x+2y<60$ will satisfy $5x+2y\le 60$.

Any line, for example, $5x+2y=60$, divides the $\mathrm{xy}$-plane into three parts: those points on the line and the points in one of two half-planes. In one of these halfplanes, we have the points for which $5x+2y<60$, and in the other, we have the points for which $5x+2y>60$. How can we tell which of the two half-planes is above the line $5x+2y=60$ and which is below?

The key is the use of a test point ($x,y$) that is not on the line and whose half-planes we wish to distinguish. We saw above that (3, 10) is not on the line $5x+2y=60$ and is below the line. This enables us to see that the half-plane for which $5x+2y<60$ consists of the points below the line $5x+2y=60$.

To complete the drawing of the points that are feasible for the skateboard and dolls manufacturing problem, we also have to know which points satisfy the constraints that state that the number of skateboards produced $x$ cannot be negative ($x\ge 0$) and the number of dolls produced $y$ cannot be negative ($y\ge 0$). Each of these inequalities corresponds to a half-plane, and we can again test which of the half-planes associated with the line $x=0$ is determined by $x\ge 0$.

This can be done using the point (3, 10) as a test point again. Because $x=3$ is greater than 0, $x\ge 0$ determines the half-plane to the right of the line $x=0$ (the y-axis). Similarly, using the point (3, 10), we see that because $y=10$ is greater than 0, $y\ge 0$ determines the half-plane above the line $y=0$ (the x-axis).

Putting this information together leads us to the conclusion that the collection of points ($x,y$) that meets the three inequalities involved ($x\ge 0,y\ge 0,5x+2y\le 60$) corresponds to the shaded region in Figure 4.3b. Remember that when graphing equations, lines with equations like $x=2$ are vertical lines, whereas those like $y=4$ are horizontal lines.

Note that since the minimality conditions are always present in the kind of linear-programming problems we are dealing with, the points that are feasible for these problems are always in the upper right region (quadrant) that is created by the x-axis and y-axis. Next, we draw the feasible region for the clothing manufacturing problem.

Self Check 1