Tip:
Highlight text to annotate it
X
We're going to look at the following problem.
Determine the minimum value of -x + 2y
over all values for x and y satisfying the following constraints:
x squared + y squared less than or equal to 5,
x + y greater than or equal to -1,
and x has to be an integer.
There's a simpler way to write down this problem.
That's what we're going to do. So we're going to write this in a different form
without that many words.
So we are minimizing. So we will say min
-x + 2y
subject to
these constraints.
This is the form that most optimization problems
will appear in.
We don't need this big stuff up there anymore, so let's get rid of that.
So how do you tackle a problem like this? We have all kinds of weird constraints.
We're trying to find the minimum value of -x + 2y
subject to all these constraints.
Well, the first thing to do is,
we can just try to sketch
the set
of (x,y) satisfying these constraints and see what they look like.
And then we'll move on from there.
Let's get our
x-y plane in here.
So let's work on the easy constraint first.
We'll look at x + y greater than or equal to -1.
Remember that by the way we
we draw these inequalities.
We first draw the line defined by x + y = -1.
And that line,
as you can see, goes through the
points (0,-1) and (-1,0).
So the line defined by
x + y greater than or equal to -1
is this.
Now, so all the points satisfying x + y greater than or equal to -1
will be over here,
over on this side of the line.
Well because the point (0,0)
satisfies this inequality.
That takes care of that.
Now, we're going to look at the first constraint.
if you look at x squared plus y squared equal to five,
it's just a circle of radius square root of five.
The circle of radius square root of five is about two point something. The radius is
two point something so it's not going to exceed three.
It's going to exceed two but not quite three.
So if we draw this circle,
it would look something like
this. All right.
But we are interested in the points that are less than or equal to five,
x squared plus y squared less than or equal to five.
So we are looking at points that lie inside the circle.
But remember that our points have to satisfy the inequality x + y greater than
or equal to -1.
So we're not looking at everything within the circle.
After drawing these inequalities,
the set of points that satisfy these inequalities
is the shaded yellow region. Ok.
The last thing we have to worry about
is this thing
x being an integer.
x being an integer means x cannot be a fraction.
And if we look at the points within the circle that have integer
x-coordinates,
they are
along
these vertical lines.
So they can pass through
the points
(-2,0)
(-1,0)
(0,0)
(1,0)
and (2,0).
If we're looking at points that satisfy all of these constraints,
they will be
these points here.
And there is one point here.
So what's that point?
That point there is
(-2,1).
So among
all these blue points,
uh... actually, this is not quite right.
The points are here.
The blue points are the points that satisfy all of these inequalities.
So among all these points, we want to find one that minimize
-x + 2y.
Well, how do we figure that out?
Well let's see. We can ask ourselves the following question:
Can -x + 2y be zero
for some (x,y) satisfying all these constraints.
Well, of course it can be zero because
if you plug in (0,0),
(0,0) is one of these blue points,
and it gives the value zero for -x + 2y.
There are also other points
uh... that give zero. For example, if x is 2
and y is 1,
that also gives zero.
and (2,1)
is also one of these blue points.
In fact,
if you draw the line
-x + 2y
equal to 0,
this is what you get.
So this is the line
-x plus
2y
equal to zero.
Now the question is, can we
get something smaller than zero. So we know that there are points, blue points
that give me -x + 2y = 0.
But can we get something even smaller.
if you look at the point, say,
(2,0). So x equal to 2, y equal to 0.
That gives a value -2.
And not only that.
That point is
also one of these blue points. So if you look at
the point (2,0),
it's right here,
then it gives us a value of -2. So we can do better than 0.
If you draw the line
-x + 2y
equal to -2,
this is what we get.
So as you can see,
if we set -x + 2y = -2,
the line also intersects
a blue point.
If we
draw the line -x + 2y = z,
for various values of z,
then we'll have parallel lines
of different positions.
And as z decreases,
the line will actually go that way.
So at z = 0, we have the first line here.
And if z = -2, we have the second line here.
And if we set z to some
even more negative value,
it will go down even further.
if you take a look at this carefully, it looks like we'll meet,
we'll reach the
minimum possible value for z when it
hits the circle right at this blue point.
It looks like
this is where
the z
is at the minimum.
So this point is
(1, -2).
And the value for z that it gives is
-1
plus 2 times -2 equal to -5.
So setting x, y equal to one and
minus two gives the minimum
value for
our problem.
Obviously we solved this using a picture. And some
might object that this is not a rigorous way of doing things.
But for now this is good enough. At least
we an tell
where we look for the optimal solution.
In future videos,
we'll look at how you can actually show
algebraically that
a solution that you have obtained for a linear programming problem
is actually the best possible.
Here, our problem is not a linear programming problem because we have constraints that
involve quadratics like x squared plus y squared,
and integer constraints are not linear constraints.
And for now
we will just be content that we have managed to solve this problem graphically.