I want to begin our discussion of linear programming with the kind of problem
that you likely first encountered in a high school Algebra class.
A graduate student is trying to balance work and relaxation.
He finds that eating, sleeping, and
commuting leave him with 14 hours per day remaining.
After two hours of work, he finds that he needs to relax for
a half hour before he can work effectively for another hour.
His advisor,
and probably his mother too, want him to work as much as possible.
We'll let x1 be the number of hours spent working on research, and
let x2 be the number of hours spent relaxing.
Then we can express this graduate student's time management problem
as the following optimization.
We express the fact that he has only 14 hours for
these activities by saying that x1 + x2 is at most 14 and
we express the fact that he feels a need for
half as much relaxation as work after two hours with this constraint here.
Of course, he can't spend negative time on either of these activities, so
we need to add that constraint as well.
The overall goal is to maximize time worked, so we make that our objective
function, and we want to maximize that subject to these constraints.
Now in high school,
your teacher probably asked you to begin by graphing the inequalities.
When we do this,
we see that the constraints generate the following polytope.
Perhaps your highschool teacher didn't use the word polytope, but
that's what this region here is.
Each constraint restricts the solution to half of the plane that's
called a half space, and the polytope is an intersection of half space.
After you graph the region,
the solution can be picked out as one of the vertices.
In this case, it's pretty easy to see that it's this one right here,
which is the intersection of these two constraints.
Maybe if the formula was a little more complicated,
and you weren't sure, you could have tested each one of the vertices and
picked the one with the highest objective value.
Why is the optimal solution at one of the vertices?
Well, remember that in this problem, and in all similar ones from high school,
the objective function, that is, the thing we're optimizing, is linear.
The only thing that matters is how far we can move in a certain direction.
In this case, the x1 direction, but it could be any direction in the plane.
If you like, you can think of there being a giant magnet infinitely far
away, pulling our point x in a certain direction and trying to get it as close
as possible to the magnet, this point must end up at one of the vertices.
If some point of his interior then we can clearly improve
by moving in this direction.
If a point is on the edge, then we can improve by moving along the edge.
The only time we couldn't improve in this way
would be if the edge were perpendicular to the direction we wanted to move in.
Maybe the magnet is actually up here and thus it would turn out that
this point here, in the middle of the edge, is optimal.
But then actually both vertices on either side of this edge
are optimal too.
So if we just want a optimal solution,
it always suffices to just look at the vertices.
Thinking more abstractly,
there isn't always an optimal solution, as there is in this particular case.
If I eliminate this constraint here, like so,
our polytope is unbounded in the gradient direction of our objective.
In this case, we can just keep moving our point x further and
further getting greater and greater values for objective function.
You give me an x, I've got a better one, hence there's no optimal solution.
On the other hand if I put back that constraint and
add another one, we might find that they are contradictory.
There's no way to satisfy them all.
If there are no solutions, there can't be an optimal one.
So those are the three things that can happen.
The constraints can create a bounded region and
we find an optimum inside of there.
The region can be unbounded in which case it's possible
that there in no optimum solution because for
any solution there is always a better one or the region that satisfies
all the constraints can be empty in which case there is no solution at all.