Hello, everybody,

welcome back to our course on advanced algorithms and complexity.

Today we're starting a new unit,

we're starting to talk about linear programming problems.

And in particular today we're going to give just a simple example of the sort of

problem that we will be trying to solve during this unit.

So imagine that you're running a widget factory and

you'd like to optimize your production procedures in order to save money.

Now these widgets, you can make them using some combination of machines and workers.

Now you have only 100 machines in stock, so you can't use more than that.

But you can hire an unlimited number of workers.

However, each machine that you're trying to use requires

two workers in order to operate it.

Additional workers can be building things on their own,

but machines they are using require two workers on them.

Now in addition to this,

each machine that you use makes a total of 600 widgets a day.

And each worker that's not currently involved in operating a machine makes

200 widgets a day.

Finally, the total demand for widgets is only 100,000 widgets a day.

So if you make any more than this,

they just won't sell, and that's no good for anybody.

So writing these constraints down in a reasonable way,

if we let W be the number of workers that we have.

And M the number of machines, we have a bunch of constraints.

The number of workers should be non-negative,

the number of machines should be between 0 and 100.

The number of workers needs to be at least twice the number of machines.

And then finally, 100,000 is at least 200 times the number of unoccupied workers.

That's W minus 2M, plus 600 times the number of the machines.

And so these constraints sort of constrain which allowable combinations we can have.

Now we can try and graph these constraints.

So here we've got a plane of possible values of M and

W that satisfy these constraints.

Now if we're just starting where M and W both need to be non negative,

we have this quadrant as the allowable values.

But when we require that M needs to be at least 100,

we're reduced to being in this strip here.

When we look at our constraint based on the total demand,

we find that M + W is at most 500.

And so we're now constrained to this region.

And we add the final constraint that the workers need to be at least

twice the number of machines.

We finally come to this diagram of possible configurations

of machines and workers that we can use.

What's next?

Profit, well suppose that profits are determined as follows.

Each widget that you make earns you a $1 but

each worker that you're hiring costs you $100 a day.

So the total profit that you get, then, in terms of dollars per day.

Well it's number of widgets, 200 workers minus twice machines,

plus 600 times number of machines, minus the total salaries you paid to workers,

100 times the number of workers.

So that's 100 times the number of workers plus 200 times the number of machines.

And if we want to plot that on our graph we can do it as follows.

So these lines that I've drawn are lines of equal profit.

There's a line with $30,000 a day, and then $40,000 a day, and

then $50,000 a day.

And sort of as you go from left to right, or

from bottom to top, you make more profit.

So what we're trying to do now is we're trying to say well,

what can we do to get the most profit?

And it turns out, the best you can do is at this point here.

Note that it's a corner of the allowable region,

it's where we have 100 machines and 400 workers.

And the total profit is $60,000 a day.

Now it's clear from this diagram that this is the best that you can do.

But if you actually want to prove it, there's a clever way you can do that.

So two of the constraints that we have,

one of them is that the number of machines is at most 100.

And another is that 200 times the number of machines plus 200 times

the number of workers is at most 100,000.

Now if we take 100 times the first constraint and add it to a half times

the second constraint, what you find is that 200 times the number of machines

plus 100 times the number of workers has to be at most 60,000.

And that says the profit that we make has to be at most 60,000.

And so this is a very convenient way to prove that the 60,000

that we could attain is actually the best we can do.

So in summary, what we did is we solved

this problem where we maximized this function, 200M + 100W.

Subject to the following list of five constraints.

And because the thing we're trying to maximize is a linear function, and

the constraints we have are linear inequalities,

this makes this an example of the type of problem we're going to be looking at.

That is, a linear program.

So come back next lecture and we'll sort of formally define this problem and

get us started on our investigation.

Introduction

Advanced Algorithms and Complexity

Meet the Instructors