Lesson Video: Linear Programming Mathematics • First Year of Secondary School

Video Transcript

In this video, we will learn how to find the optimal solution of a linear system that has an objective function and multiple constraints. The method that we will use to find this optimal solution is called linear programming. Let’s begin by looking at a definition.

Linear programming is a method to find an optimal that is a maximum or minimum solution for a given linear objective function bounded by constraints represented by linear inequalities. Let’s consider a linear function that is a function of two variables 𝑥 and 𝑦 such that 𝑓 of 𝑥, 𝑦 is equal to 𝑎𝑥 plus 𝑏𝑦 plus 𝑐. This is known as the objective function and is defined for all 𝑥- and 𝑦-values. As stated in the linear programming method, we also include constraints that are represented by linear inequalities. For example, we could have that both 𝑥 and 𝑦 are greater than or equal to zero. We could also have constraints that involve both variables. For example, 𝑥 plus 𝑦 is less than or equal to five.

Given this objective function and a set of constraints, we need to solve for an optimal solution, which will either maximize or minimize the objective function. One way to represent this is to draw a two-dimensional graph. We begin by drawing an 𝑥𝑦-plane as shown. We can now use the constraints to find an area on the graph that satisfies these. Firstly, as 𝑥 is greater than or equal to zero, we can draw a line at 𝑥 is equal to zero. In this case, this is a solid line. However, if the inequality was a strict inequality, 𝑥 is greater than zero, we’d use a dotted line.

At this stage, we can either shade out or shade in the region we want. We know that any values of 𝑥 to the left of this vertical line will be outside of our region. So in this example, we will shade out the region. We can do something similar with our next constraint. Since 𝑦 is greater than or equal to zero, we can draw a line at 𝑦 equals zero. The area below the 𝑥-axis will not be in our feasible region. Let’s now consider the third constraint. 𝑥 plus 𝑦 is less than or equal to five. In order to represent this on our graph, we’ll firstly draw the line with equation 𝑥 plus 𝑦 equals five. Substituting 𝑥 equals zero into this equation gives us 𝑦 is equal to five. Likewise, when 𝑦 is equal to zero, 𝑥 is equal to five. We can therefore conclude that the points with coordinates zero, five and five, zero will lie on this line.

Next, we must determine which area on the graph this linear inequality represents. One way of doing this is to make 𝑦 the subject. Subtracting 𝑥 from both sides of the inequality, we have 𝑦 is less than or equal to negative 𝑥 plus five. This means that the line drawn has equation 𝑦 is equal to negative 𝑥 plus five. Therefore, the region where the 𝑦-coordinate is less than negative 𝑥 plus five is below the line as this is where the 𝑦-coordinates are smaller. We can therefore shade out the region above the line. We now have a region shaded in green that satisfies all three of these constraints. This is known as the feasible region. And any point outside of this area violates at least one of the constraints.

Any point inside this feasible region could potentially be an optimal solution for the objective function. However, this provides us with a problem, as there are an infinite number of solutions inside this region. As a result, this is where an amazing property of this method comes in. Whenever we have a well-defined feasible region as in this case, then the only points that we need to check for an optimal solution are the vertices of the feasible region, in this case the points with coordinates zero, zero; zero, five; and five, zero. These are the only points at which we could have a maximum or minimum value. In order to see why this is the case, let’s consider a three-dimensional sketch.

In general, our objective function takes in two variables, in this case 𝑥 and 𝑦. And this function outputs some value from them. We will call this a 𝑧-value. And we can plot this on a 𝑧-axis of our coordinate frame. As our objective function has both 𝑥- and 𝑦-values, it won’t be represented by a line, but instead by a plane. In other words, if we were to plot the objective function for all 𝑥- and 𝑦-values, it would be a plane that would look something like this, where the points on this plane represent all 𝑧-values or objective function values for every possible 𝑥 and 𝑦 input combination. This means that 𝑧 could be infinitely positive or infinitely negative. However, for any given linear programming problem, only a subset of these 𝑧-values are allowed. They are the 𝑧-values that correspond to the 𝑥- and 𝑦-values in the feasible region.

To see what this feasible set of 𝑧-values is, we can project upwards onto the plane. When we do this, another triangular region is created. But this one follows the slope of our plane. If we consider the vertices of the feasible region in the 𝑥𝑦-plane, we notice that these project onto the very highest and very lowest values of 𝑧. This means that the maximum and minimum solution will occur on one of these vertices. Whilst this isn’t a conclusive proof that the optimal solution lies at one of the vertices of the feasible region, it at least suggests that this is plausible. However, this is true. Regardless of what kind of plane we have and what angle it takes, when we project the feasible region onto it, one or more of the vertices will represent the optimal solution.

In summary, in order to find an optimal solution, we substitute the coordinates of the vertices of the feasible region into the objective function. Doing this for all vertices will enable us to find the maximum and minimum solution. Let’s now consider how this works in practice.

Using linear programming, find the minimum and maximum values of the function 𝑝 is equal to four 𝑥 minus three 𝑦 given that 𝑥 is greater than or equal to zero, 𝑦 is greater than or equal to zero, 𝑥 plus 𝑦 is less than or equal to nine, and 𝑦 is greater than or equal to five.

As well as the information in the question, we are given a graph which shows the feasible region for our constraints. There are four such constraints represented by linear inequalities. We note that since 𝑦 must be greater than or equal to zero and greater than or equal to five, we only need to consider the second inequality. This is represented by the horizontal line that passes through five on the 𝑦-axis. The inequality 𝑥 is greater than or equal to zero is represented by the line 𝑥 equals zero. And the feasible region is everything on or to the right of this line, all values of 𝑥 greater than or equal to zero.

Finally, we have the line 𝑥 plus 𝑦 is equal to nine. And since 𝑥 plus 𝑦 is less than or equal to nine or 𝑦 is less than or equal to negative 𝑥 plus nine, then the feasible region contains all points on or below this line. If our inequality had just been less than, the feasible region would just be below the line.

In this question, we are asked to find the minimum and maximum values of the function 𝑝 is equal to four 𝑥 minus three 𝑦. And using linear programming, we know that these occur at one of the vertices of our feasible region. These three vertices have coordinates zero, five; zero, nine; and four, five. It is only at these values that our function can be optimal, i.e., have a minimum or maximum value. Substituting 𝑥 equals zero and 𝑦 equals five into our function, we have 𝑝 is equal to four multiplied by zero minus three multiplied by five. This is equal to negative 15. At the point zero, nine, we have 𝑝 is equal to four multiplied by zero minus three multiplied by nine. This is equal to negative 27.

Finally, at the vertex of the feasible region, where 𝑥 equals four and 𝑦 equals five, we have 𝑝 is equal to one. We now simply choose the minimum and maximum of these three results. We see that negative 27 is the minimum value and one is the maximum value. The minimum and maximum values of the function 𝑝 is equal to four 𝑥 minus three 𝑦 subject to the given constraints are negative 27 and one.

We will now look at a second example in context.

A small company dyes shirts to be either solid-color or tie-dye, and they want to decide how many shirts of each color to prepare for an upcoming sale. The company has a budget of 240 dollars. Purchasing an undyed shirt costs two dollars. It costs an additional 50 cents to dye a shirt with a solid color and one dollar 50 to dye a shirt with a tie-dye pattern. The company only has eight hours to prepare all the shirts for the sale. And it takes two minutes to produce a solid-color shirt and 10 minutes to produce a tie-dye shirt. They decide to make a graph to help them maximize profit, given that they make eight dollars profit for each solid-color shirt and 10 dollars profit for each tie-dye shirt. Let 𝑥 represent the number of solid-color shirts and 𝑦 represent the number of tie-dye shirts.

There are three parts to this question, which we will look at shortly. Before doing this, let’s consider some of the information we are given. There are two types of shirts made by the company, solid-color shirts represented by 𝑥 and tie-dye shirts represented by 𝑦. We will solve this problem using linear programming by firstly defining an objective function and some constraints in the form of linear inequalities. The company is looking to maximize profit. And we are told they make an eight-dollar profit for each solid-color shirt and a 10-dollar profit for each tie-dye shirt. This means that the profit in dollars 𝑃 is equal to eight 𝑥 plus 10𝑦. We can also write this as a function in terms of 𝑥 and 𝑦 such that 𝑓 of 𝑥, 𝑦 is equal to eight 𝑥 plus 10𝑦.

The constraints placed on the company involve both time and money. If we consider money first, we are told that the company has a budget of 240 dollars. We are told that an undyed shirt costs two dollars and that it costs an additional 50 cents to dye a shirt with a solid color and one dollar 50 to dye a shirt with a tie-dye pattern. It therefore costs two dollars 50 to make each solid-color shirt. As the company are making 𝑥 of these, this can be written as 2.5𝑥. It costs three dollars 50 to make a tie-dye shirt. And this can be written as 3.5𝑦. We know that the sum of these terms must be less than or equal to 240 as the total budget was 240 dollars.

Let’s now consider the time constraints. We are told it takes two minutes to produce a solid-color shirt and 10 minutes to produce a tie-dye shirt. The company has eight hours or 480 minutes to prepare all the shirts. This can be represented by the inequality two 𝑥 plus 10𝑦 is less than or equal to 480. We will now clear some space and consider the three parts of this question.

The three parts to the question are as follows. Which of the following shows the feasible region? State the objective function. How many of each type of shirt should the company produce to maximize profit?

We have already answered the second part of this question. The objective function or profit function in this question 𝑓 of 𝑥, 𝑦 is equal to eight 𝑥 plus 10𝑦. In the first part of this question, we’re given four graphs with the straight lines 2.5𝑥 plus 3.5𝑦 equals 240 and two 𝑥 plus 10𝑦 equals 480 drawn on them. We know that two 𝑥 plus 10𝑦 must be less than or equal to 480. This means that the feasible region lies below this line. We can therefore rule out option (B).

We are also told that 2.5𝑥 plus 3.5𝑦 is less than or equal to 240. The feasible region must therefore also lie below the blue line on our graphs. This rules out option (C). To decide whether graph (A) or graph (D) is the correct one, we need to consider two further constraints. Since we can’t make a negative number of shirts, both 𝑥 and 𝑦 must be greater than or equal to zero. This means that the feasible region must lie above the 𝑥-axis and to the right of the 𝑦-axis. We can therefore rule out option (A) as part of the feasible region here occurs when 𝑥 is less than zero. The correct answer to the first part of our question is therefore option (D).

We will now clear some space and solve the third part of this question. We recall that this asked us to work out the number of each type of shirt the company should produce to maximize profit. We recall that the profit or objective function was equal to eight 𝑥 plus 10𝑦 and that the feasible region was subject to four constraints. We know that the possible maximum values of the function occur at the vertices of the feasible region. So we will begin by working out the coordinates of these points. Firstly, we have the point zero, zero. We know that when a line intersects the 𝑥-axis, 𝑦 is equal to zero. And substituting this into the equation, 2.5𝑥 plus 3.5𝑦 equals 240, we find that 𝑥 is 96. So the coordinates of this vertex are 96, zero.

In the same way, when a line intersects the 𝑦-axis, our 𝑥-coordinate is zero. Substituting this into the equation two 𝑥 plus 10𝑦 equals 480 gives us 𝑦 is equal to 48 and another vertex at zero, 48. The fourth vertex of our feasible region is the point of intersection of our two diagonal lines. One way of working out this point would be to find a solution of the simultaneous equations shown. There are many ways of solving these. One way would be to multiply the second equation by two. This gives us the equation five 𝑥 plus seven 𝑦 is equal to 480.

Rewriting the first equation underneath and then subtracting the two equations, we have three 𝑥 minus three 𝑦 is equal to zero. Adding three 𝑦 to both sides of this equation and then dividing through by three, we see that 𝑥 is equal to 𝑦. We can then substitute this back into our first equation such that two 𝑦 plus 10𝑦 is equal to 480. Solving this gives us 𝑦 is equal to 40 and as 𝑥 is also equal to this. The fourth vertex has coordinates 40, 40.

We can now substitute each of these coordinates in turn into our objective function. It is important to note here that any of these points could be the optimal solution and it will not necessarily be the point of intersection we have just found. Substituting in the values of 𝑥 and 𝑦, the objective function is equal to zero, 480, 768, and 720. As the company is trying to maximize the profit, they choose the highest value. Since 𝑥 represents the number of solid-color shirts and 𝑦 the number of tie-dye shirts, producing 96 solid-color shirts and zero tie-dye shirts would maximize the profit. Assuming that all the shirts were sold, this would yield a profit of 768 dollars.

We will now summarize the key points from this video. Linear programming is a method to find an optimal solution for a given linear objective function bounded by constraints represented by linear inequalities. We saw that the area bounded by the constraints is the feasible region and that optimal solutions are found at the vertices of this region.