WEBVTT
00:00:00.600 --> 00:00:08.720
In this video, we will learn how to find the optimal solution of a linear system that has an objective function and multiple constraints.
00:00:09.280 --> 00:00:15.200
The method that we will use to find this optimal solution is called linear programming.
00:00:16.000 --> 00:00:18.080
Letβs begin by looking at a definition.
00:00:19.240 --> 00:00:32.520
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.
00:00:33.680 --> 00:00:46.640
Letβs consider a linear function that is a function of two variables π₯ and π¦ such that π of π₯, π¦ is equal to ππ₯ plus ππ¦ plus π.
00:00:47.360 --> 00:00:53.120
This is known as the objective function and is defined for all π₯- and π¦-values.
00:00:54.080 --> 00:01:01.200
As stated in the linear programming method, we also include constraints that are represented by linear inequalities.
00:01:02.360 --> 00:01:09.440
For example, we could have that both π₯ and π¦ are greater than or equal to zero.
00:01:10.560 --> 00:01:14.920
We could also have constraints that involve both variables.
00:01:15.960 --> 00:01:20.520
For example, π₯ plus π¦ is less than or equal to five.
00:01:21.520 --> 00:01:33.120
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.
00:01:33.760 --> 00:01:38.400
One way to represent this is to draw a two-dimensional graph.
00:01:38.960 --> 00:01:42.320
We begin by drawing an π₯π¦-plane as shown.
00:01:42.880 --> 00:01:49.640
We can now use the constraints to find an area on the graph that satisfies these.
00:01:50.440 --> 00:01:58.400
Firstly, as π₯ is greater than or equal to zero, we can draw a line at π₯ is equal to zero.
00:01:59.160 --> 00:02:02.080
In this case, this is a solid line.
00:02:02.800 --> 00:02:09.280
However, if the inequality was a strict inequality, π₯ is greater than zero, weβd use a dotted line.
00:02:10.000 --> 00:02:15.880
At this stage, we can either shade out or shade in the region we want.
00:02:16.480 --> 00:02:23.200
We know that any values of π₯ to the left of this vertical line will be outside of our region.
00:02:23.760 --> 00:02:27.040
So in this example, we will shade out the region.
00:02:27.680 --> 00:02:30.480
We can do something similar with our next constraint.
00:02:31.240 --> 00:02:37.760
Since π¦ is greater than or equal to zero, we can draw a line at π¦ equals zero.
00:02:38.400 --> 00:02:42.080
The area below the π₯-axis will not be in our feasible region.
00:02:42.720 --> 00:02:44.600
Letβs now consider the third constraint.
00:02:45.360 --> 00:02:48.120
π₯ plus π¦ is less than or equal to five.
00:02:48.960 --> 00:02:57.120
In order to represent this on our graph, weβll firstly draw the line with equation π₯ plus π¦ equals five.
00:02:57.840 --> 00:03:02.880
Substituting π₯ equals zero into this equation gives us π¦ is equal to five.
00:03:03.480 --> 00:03:07.800
Likewise, when π¦ is equal to zero, π₯ is equal to five.
00:03:08.440 --> 00:03:17.720
We can therefore conclude that the points with coordinates zero, five and five, zero will lie on this line.
00:03:18.640 --> 00:03:25.640
Next, we must determine which area on the graph this linear inequality represents.
00:03:26.320 --> 00:03:30.040
One way of doing this is to make π¦ the subject.
00:03:31.160 --> 00:03:37.600
Subtracting π₯ from both sides of the inequality, we have π¦ is less than or equal to negative π₯ plus five.
00:03:38.560 --> 00:03:44.840
This means that the line drawn has equation π¦ is equal to negative π₯ plus five.
00:03:45.680 --> 00:03:57.800
Therefore, the region where the π¦-coordinate is less than negative π₯ plus five is below the line as this is where the π¦-coordinates are smaller.
00:03:58.680 --> 00:04:02.800
We can therefore shade out the region above the line.
00:04:04.200 --> 00:04:09.480
We now have a region shaded in green that satisfies all three of these constraints.
00:04:10.000 --> 00:04:12.520
This is known as the feasible region.
00:04:13.240 --> 00:04:18.520
And any point outside of this area violates at least one of the constraints.
00:04:19.320 --> 00:04:25.120
Any point inside this feasible region could potentially be an optimal solution for the objective function.
00:04:26.000 --> 00:04:31.840
However, this provides us with a problem, as there are an infinite number of solutions inside this region.
00:04:32.760 --> 00:04:37.800
As a result, this is where an amazing property of this method comes in.
00:04:38.760 --> 00:04:58.680
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.
00:04:59.480 --> 00:05:05.200
These are the only points at which we could have a maximum or minimum value.
00:05:06.240 --> 00:05:10.960
In order to see why this is the case, letβs consider a three-dimensional sketch.
00:05:11.920 --> 00:05:18.280
In general, our objective function takes in two variables, in this case π₯ and π¦.
00:05:19.040 --> 00:05:23.480
And this function outputs some value from them.
00:05:24.200 --> 00:05:25.760
We will call this a π§-value.
00:05:26.520 --> 00:05:30.560
And we can plot this on a π§-axis of our coordinate frame.
00:05:31.520 --> 00:05:41.520
As our objective function has both π₯- and π¦-values, it wonβt be represented by a line, but instead by a plane.
00:05:42.240 --> 00:06:00.960
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.
00:06:01.920 --> 00:06:08.200
This means that π§ could be infinitely positive or infinitely negative.
00:06:08.800 --> 00:06:15.720
However, for any given linear programming problem, only a subset of these π§-values are allowed.
00:06:16.280 --> 00:06:22.160
They are the π§-values that correspond to the π₯- and π¦-values in the feasible region.
00:06:22.840 --> 00:06:28.840
To see what this feasible set of π§-values is, we can project upwards onto the plane.
00:06:29.560 --> 00:06:33.360
When we do this, another triangular region is created.
00:06:34.080 --> 00:06:37.360
But this one follows the slope of our plane.
00:06:37.800 --> 00:06:46.080
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 π§.
00:06:46.720 --> 00:06:52.840
This means that the maximum and minimum solution will occur on one of these vertices.
00:06:53.840 --> 00:07:05.520
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.
00:07:06.560 --> 00:07:07.640
However, this is true.
00:07:08.360 --> 00:07:18.160
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.
00:07:19.360 --> 00:07:26.400
In summary, in order to find an optimal solution, we substitute the coordinates of the vertices of the feasible region into the objective function.
00:07:27.240 --> 00:07:33.520
Doing this for all vertices will enable us to find the maximum and minimum solution.
00:07:34.120 --> 00:07:37.520
Letβs now consider how this works in practice.
00:07:38.840 --> 00:07:59.480
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.
00:08:00.360 --> 00:08:07.800
As well as the information in the question, we are given a graph which shows the feasible region for our constraints.
00:08:08.400 --> 00:08:12.000
There are four such constraints represented by linear inequalities.
00:08:13.480 --> 00:08:22.720
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.
00:08:23.440 --> 00:08:30.360
This is represented by the horizontal line that passes through five on the π¦-axis.
00:08:31.320 --> 00:08:37.320
The inequality π₯ is greater than or equal to zero is represented by the line π₯ equals zero.
00:08:38.400 --> 00:08:49.360
And the feasible region is everything on or to the right of this line, all values of π₯ greater than or equal to zero.
00:08:50.480 --> 00:08:54.800
Finally, we have the line π₯ plus π¦ is equal to nine.
00:08:55.800 --> 00:09:09.640
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.
00:09:10.360 --> 00:09:16.880
If our inequality had just been less than, the feasible region would just be below the line.
00:09:17.640 --> 00:09:25.480
In this question, we are asked to find the minimum and maximum values of the function π is equal to four π₯ minus three π¦.
00:09:26.120 --> 00:09:32.960
And using linear programming, we know that these occur at one of the vertices of our feasible region.
00:09:33.600 --> 00:09:40.560
These three vertices have coordinates zero, five; zero, nine; and four, five.
00:09:41.240 --> 00:09:50.000
It is only at these values that our function can be optimal, i.e., have a minimum or maximum value.
00:09:50.600 --> 00:10:00.560
Substituting π₯ equals zero and π¦ equals five into our function, we have π is equal to four multiplied by zero minus three multiplied by five.
00:10:01.440 --> 00:10:03.360
This is equal to negative 15.
00:10:04.280 --> 00:10:11.320
At the point zero, nine, we have π is equal to four multiplied by zero minus three multiplied by nine.
00:10:11.720 --> 00:10:13.840
This is equal to negative 27.
00:10:14.320 --> 00:10:22.400
Finally, at the vertex of the feasible region, where π₯ equals four and π¦ equals five, we have π is equal to one.
00:10:22.960 --> 00:10:29.440
We now simply choose the minimum and maximum of these three results.
00:10:30.120 --> 00:10:36.120
We see that negative 27 is the minimum value and one is the maximum value.
00:10:36.640 --> 00:10:47.760
The minimum and maximum values of the function π is equal to four π₯ minus three π¦ subject to the given constraints are negative 27 and one.
00:10:48.520 --> 00:10:50.960
We will now look at a second example in context.
00:10:51.640 --> 00:11:05.040
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.
00:11:05.920 --> 00:11:09.240
The company has a budget of 240 dollars.
00:11:10.160 --> 00:11:14.280
Purchasing an undyed shirt costs two dollars.
00:11:15.200 --> 00:11:25.840
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.
00:11:26.640 --> 00:11:33.120
The company only has eight hours to prepare all the shirts for the sale.
00:11:33.960 --> 00:11:42.080
And it takes two minutes to produce a solid-color shirt and 10 minutes to produce a tie-dye shirt.
00:11:43.080 --> 00:12:04.440
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.
00:12:05.040 --> 00:12:13.240
Let π₯ represent the number of solid-color shirts and π¦ represent the number of tie-dye shirts.
00:12:14.040 --> 00:12:18.200
There are three parts to this question, which we will look at shortly.
00:12:19.080 --> 00:12:22.800
Before doing this, letβs consider some of the information we are given.
00:12:23.640 --> 00:12:34.960
There are two types of shirts made by the company, solid-color shirts represented by π₯ and tie-dye shirts represented by π¦.
00:12:35.760 --> 00:12:45.480
We will solve this problem using linear programming by firstly defining an objective function and some constraints in the form of linear inequalities.
00:12:46.160 --> 00:12:48.680
The company is looking to maximize profit.
00:12:49.400 --> 00:13:06.600
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.
00:13:07.160 --> 00:13:12.400
This means that the profit in dollars π is equal to eight π₯ plus 10π¦.
00:13:13.520 --> 00:13:23.560
We can also write this as a function in terms of π₯ and π¦ such that π of π₯, π¦ is equal to eight π₯ plus 10π¦.
00:13:24.360 --> 00:13:29.200
The constraints placed on the company involve both time and money.
00:13:29.760 --> 00:13:40.480
If we consider money first, we are told that the company has a budget of 240 dollars.
00:13:41.400 --> 00:13:59.960
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.
00:14:00.680 --> 00:14:07.120
It therefore costs two dollars 50 to make each solid-color shirt.
00:14:07.920 --> 00:14:15.720
As the company are making π₯ of these, this can be written as 2.5π₯.
00:14:16.400 --> 00:14:22.240
It costs three dollars 50 to make a tie-dye shirt.
00:14:23.000 --> 00:14:27.440
And this can be written as 3.5π¦.
00:14:28.080 --> 00:14:38.560
We know that the sum of these terms must be less than or equal to 240 as the total budget was 240 dollars.
00:14:39.080 --> 00:14:42.200
Letβs now consider the time constraints.
00:14:42.800 --> 00:14:51.320
We are told it takes two minutes to produce a solid-color shirt and 10 minutes to produce a tie-dye shirt.
00:14:52.200 --> 00:14:59.560
The company has eight hours or 480 minutes to prepare all the shirts.
00:15:00.080 --> 00:15:07.880
This can be represented by the inequality two π₯ plus 10π¦ is less than or equal to 480.
00:15:08.680 --> 00:15:13.240
We will now clear some space and consider the three parts of this question.
00:15:14.040 --> 00:15:16.800
The three parts to the question are as follows.
00:15:17.640 --> 00:15:20.560
Which of the following shows the feasible region?
00:15:21.320 --> 00:15:22.520
State the objective function.
00:15:23.440 --> 00:15:28.920
How many of each type of shirt should the company produce to maximize profit?
00:15:29.760 --> 00:15:32.360
We have already answered the second part of this question.
00:15:33.280 --> 00:15:40.400
The objective function or profit function in this question π of π₯, π¦ is equal to eight π₯ plus 10π¦.
00:15:41.480 --> 00:15:59.960
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.
00:16:00.800 --> 00:16:07.640
We know that two π₯ plus 10π¦ must be less than or equal to 480.
00:16:08.480 --> 00:16:12.720
This means that the feasible region lies below this line.
00:16:13.400 --> 00:16:16.080
We can therefore rule out option (B).
00:16:17.000 --> 00:16:24.960
We are also told that 2.5π₯ plus 3.5π¦ is less than or equal to 240.
00:16:25.680 --> 00:16:32.160
The feasible region must therefore also lie below the blue line on our graphs.
00:16:33.080 --> 00:16:35.360
This rules out option (C).
00:16:36.200 --> 00:16:45.760
To decide whether graph (A) or graph (D) is the correct one, we need to consider two further constraints.
00:16:46.640 --> 00:16:54.960
Since we canβt make a negative number of shirts, both π₯ and π¦ must be greater than or equal to zero.
00:16:55.520 --> 00:17:01.560
This means that the feasible region must lie above the π₯-axis and to the right of the π¦-axis.
00:17:02.320 --> 00:17:08.920
We can therefore rule out option (A) as part of the feasible region here occurs when π₯ is less than zero.
00:17:09.440 --> 00:17:14.320
The correct answer to the first part of our question is therefore option (D).
00:17:15.080 --> 00:17:19.880
We will now clear some space and solve the third part of this question.
00:17:20.920 --> 00:17:30.160
We recall that this asked us to work out the number of each type of shirt the company should produce to maximize profit.
00:17:30.800 --> 00:17:39.360
We recall that the profit or objective function was equal to eight π₯ plus 10π¦ and that the feasible region was subject to four constraints.
00:17:40.320 --> 00:17:46.000
We know that the possible maximum values of the function occur at the vertices of the feasible region.
00:17:47.000 --> 00:17:50.360
So we will begin by working out the coordinates of these points.
00:17:51.120 --> 00:17:53.800
Firstly, we have the point zero, zero.
00:17:54.600 --> 00:18:00.240
We know that when a line intersects the π₯-axis, π¦ is equal to zero.
00:18:01.120 --> 00:18:12.520
And substituting this into the equation, 2.5π₯ plus 3.5π¦ equals 240, we find that π₯ is 96.
00:18:13.280 --> 00:18:17.200
So the coordinates of this vertex are 96, zero.
00:18:17.920 --> 00:18:25.880
In the same way, when a line intersects the π¦-axis, our π₯-coordinate is zero.
00:18:26.600 --> 00:18:40.520
Substituting this into the equation two π₯ plus 10π¦ equals 480 gives us π¦ is equal to 48 and another vertex at zero, 48.
00:18:41.280 --> 00:18:46.360
The fourth vertex of our feasible region is the point of intersection of our two diagonal lines.
00:18:47.040 --> 00:18:52.720
One way of working out this point would be to find a solution of the simultaneous equations shown.
00:18:53.600 --> 00:18:55.640
There are many ways of solving these.
00:18:56.400 --> 00:19:00.000
One way would be to multiply the second equation by two.
00:19:00.680 --> 00:19:06.320
This gives us the equation five π₯ plus seven π¦ is equal to 480.
00:19:07.200 --> 00:19:17.960
Rewriting the first equation underneath and then subtracting the two equations, we have three π₯ minus three π¦ is equal to zero.
00:19:18.440 --> 00:19:26.840
Adding three π¦ to both sides of this equation and then dividing through by three, we see that π₯ is equal to π¦.
00:19:27.720 --> 00:19:36.600
We can then substitute this back into our first equation such that two π¦ plus 10π¦ is equal to 480.
00:19:37.280 --> 00:19:43.280
Solving this gives us π¦ is equal to 40 and as π₯ is also equal to this.
00:19:43.960 --> 00:19:48.480
The fourth vertex has coordinates 40, 40.
00:19:49.280 --> 00:19:54.120
We can now substitute each of these coordinates in turn into our objective function.
00:19:55.040 --> 00:20:04.840
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.
00:20:05.520 --> 00:20:16.280
Substituting in the values of π₯ and π¦, the objective function is equal to zero, 480, 768, and 720.
00:20:16.920 --> 00:20:22.160
As the company is trying to maximize the profit, they choose the highest value.
00:20:22.720 --> 00:20:39.480
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.
00:20:40.160 --> 00:20:48.080
Assuming that all the shirts were sold, this would yield a profit of 768 dollars.
00:20:48.840 --> 00:20:52.680
We will now summarize the key points from this video.
00:20:53.560 --> 00:21:02.840
Linear programming is a method to find an optimal solution for a given linear objective function bounded by constraints represented by linear inequalities.
00:21:03.560 --> 00:21:13.200
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.