Welcome to
an Introduction to Linear programming.
Let's begin by looking at an example.
Consider a company that manufactures
and sells two camping lights.
They sell one light with disposable batteries for $5,
and a second light for $10 with rechargeable batteries.
However, due to limited resources,
the production of the two lights
have the following restrictions.
They must produce at least
five lights with disposable batteries,
but no more than 15 per day.
The number of lights per day with rechargeable batteries
produced must be greater than or equal to
the number of lights with disposable batteries.
And finally, the number of lights
with rechargeable batteries produced
must be no more than 20 per day.
We're going to determine how many of each light
should the company produce and sell
to maximize their revenue per day, and also,
what is that maximum revenue per day.
So, our first step to solve this type of problem
will be to define our variables,
which represent the unknowns.
So, we'll go ahead and let x be equal to
the number of lights with disposable batteries,
which, notice how, sell for $5,
and we'll let y equal the number of lights
with rechargeable batteries, which we can see, sell for $10.
Our ultimate goal here is to maximize the revenue,
under these given restrictions or constraints,
so our revenue equation R,
would be equal to five x plus 10y.
Remember, the number of lights with disposable batteries
sell for $5 each, and the lights with rechargeable batteries
sell for $10 each, so this is our revenue equation,
also known as the Objective Equation,
and that'll represent the constraints or restrictions.
We'll have several inequalities.
So, it says here, they must produce at least five lights
with disposable batteries, but no more than 15 per day,
which means x, the number of lights
with disposable batteries,
must be greater than or equal to five,
and less than or equal to 15.
Next, the number of lights per day
with rechargeable batteries produced
must be greater than or equal to
the number of lights with disposable batteries,
and therefore, y must be greater than or equal to x.
Remember, y is the number of lights
with rechargeable batteries.
And then, finally,
the number of lights with rechargeable batteries
must be no more than 20 per day,
which means, y must be less than or equal to 20.
So, this is all the given information from our problem.
So linear programming, or linear optimization
is a method used to try to maximize or minimize a quantity
given by a linear equation,
under certain restrictions or constraints,
which is what we had in the previous problem.
A linear programming problem always consists of number one,
a linear function called an objective function
that we are trying to maximize or minimize,
so in our previous example, R equals five x plus 10y,
is our objective function, which we're trying to maximize.
A linear programming problem also has
a system of linear inequalities, called the constraints.
In our case, we had x is greater than or equal to five,
and less than or equal to 15, as well as,
y must be greater than or equal to x,
and y must be less than or equal to 20.
So, these are the constraints,
and the solution to this system of inequalities, here,
is called the feasible region.
So, for the next step, we'll graph the feasible region
by determining the solution to the system of inequalities.
And to save some time, I've already graphed this,
which we see here.
This green region here is the feasible region.
Let's review how this is found.
Because we have four inequalities here,
we would graph all four inequalities,
and look for the region that is shaded four times.
So, for this first inequality,
x is greater than or equal to five,
because of the equal part, we'd have
this solid vertical line, here at x equals five,
and because this x is greater than or equal to five,
we would shade to the right of this vertical red line.
Next, we have x also has to be less than or equal to 15,
so we'd graph the vertical line, x equals 15,
which is this red vertical line, and because we have
x is less than or equal to 15, we would shade to the left,
or in this direction here.
Next, we have y is greater than or equal to x.
If we begin by graphing a line, y equals x,
which, if we want, we can write as y equals one x plus zero,
which tells us the y-intercept is zero,
and the slope is one.
So, this should be the line, y equals x,
but because the inequality is
y is greater than or equal to x,
we would shade above the blue line, or this half plane here.
And then, finally, we have y is less than or equal to 20.
Well, y equals 20 would be this horizontal blue line,
and because we have y is less than or equal to 20,
we would shade below this horizontal line.
So, the region that's shaded four times,
or the region that satisfies
all these inequalities at the same time,
once again, is this region here.
Called the feasible region.
Now, the most important idea about linear programming,
is the Fundamental Theorem of Linear Programming,
which states, if the maximum or minimum exist
for the linear programming problem,
it occurs at a vertex of the feasible region,
which, in our case, means,
the value of x and y that'll maximize our revenue
would have to be one of the corners,
or vertices of our feasible region,
which should be this point, this point,
this point, or this point, so now,
we find the coordinates of these four points,
sub those x and y values into our revenue equation,
and whatever coordinates give us the largest revenue
would be the value of x and y
that would maximize the revenue from the given constraints.
Now, many times, we do have to solve a system of equations
in order to find the coordinates of these vertices,
but notice, in this case,
we can easily determine the coordinates from the graph.
Notice how this point would have coordinates five, five.
This point would have coordinates 15, 15.
This point would have coordinates 15, 20.
And this point would have coordinates five, 20.
In our next several examples, though,
we will have, we will have to,
in the next few examples though,
we will have to use algebra
in order to find the coordinates of these vertices.
So now, we'll substitute the x and y values
into our revenue equation to determine
how many of each flashlights
the company should produce and sell to maximize the revenue.
When we have a function in terms of two variables,
sometimes, we'll see it written in this form here.
So, for R of five, five,
we'll substitute five for x and five for y,
which would give us five times five
plus 10 times five.
Well, this would be 25 plus 50 or 75.
So, this tells us that if the company
produces and sells five of each flashlight,
the revenue would be $75 per day.
For R of five, 20, we would have
five times five,
plus 10 times 20.
Well, five times five is 25.
10 times 20 is 200, so we have 225.
Next we have, R of 15, 20,
so we'd have five times 15,
plus 10 times 20,
so this would be 75 plus 200, or 275.
And then, finally, R of 15, 15.
We have five times 15, plus 10 times 15,
which would be 75 plus 150, or 225.
So, notice how we have the largest revenue per day, here,
at $275 per day.
Let's go ahead and label the units here.
And this maximum revenue occurs
when the company produces and sells
15 lights with disposable batteries,
and 20 lights with rechargeable batteries.
So, let's go ahead and summarize this.
To maximize revenue at $275 per day,
the company should produce and sell
15 lights with disposable batteries,
and 20 lights with rechargeable batteries.
Before we go,
let's summarize the steps of linear programming.
Step one, we define the variables.
Step two, we write the objective function, and state
whether the goal is to maximize or minimize the function.
Step three, we write the constraints,
which gives us a system of inequalities.
Step four, we graph the constraints
to determine the feasible region.
Remember, the feasible region is the solution to
the system of inequalities, given by the constraints.
Step five, we identify the vertices of the feasible region.
And then, finally, step six,
we test the vertices in the objective function
to determine the maximum or minimum function value.
So, I hope you found this introduction helpful.
We'll take a look at some more examples
in the next several videos.