0:03

In our look at linear regression analysis,

we were able to do a brief review of the mathematical equation of a straight line.

So it seems an opportune moment to perhaps or continue

this discussion by having a little look at the world of linear programming.

Now, don't worry, we're not going to be writing lots of

programming code here but it's just

sort of a historic term used for this very widely used quantitative business model.

So linear programming is a great technique to use if we are

trying to solve constrained optimization problems.

Now, we all come across constrained optimization problems throughout our lives.

For example, as a student,

in a university sitting an examination.

There, you have an objective,

you're trying to optimize the number of marks you get in

that exam paper but you are subjected to various constraints.

Constraints for example about time,

maybe it's a three-hour exam and you cannot write for longer than those three hours.

Constraints, perhaps you don't have access to your books and

your notes if it's a closed book examination.

So then you are trying to gain as many marks as you

can subject to those specific constraints.

As consumers, if you've done Economics 101 somewhere,

you probably learnt about a utility function.

So utility, a term that economists like to use to represent if you like the pleasure,

the satisfaction, the happiness that

consumers get from consuming various goods and services.

So, as we are, perhaps, satisfaction maximizes,

we are trying to make ourselves as happy as possible through

our consumption choices but of course we are constrained by our budget, by our income.

We can't spend more than we earn.

Okay, we could perhaps make things a little more realistic and

assume we have access to credit from a bank.

We have a credit card, say,

we could have loans but nonetheless we are likely to all be credit constrained.

The banks will only lend us so much money.

So linear programming is

a useful statistical technique for solving these constrained optimization problems.

And the term linear programming so derived

because at the heart of many of our models will be various linear equations.

So, this is just to give you a flavor of what is out there.

So let's consider a simple example.

Now, at the start of week six in

our decision making under uncertainty with decision trees,

we have the example of an ice cream manufacturer.

Well, let's keep things with a sort of confectionery flavor.

Let's now consider a chocolate bar manufacturer.

Next time you're in the supermarket look at

the chocolate aisle and you'll see there are a lot of

different types of chocolate bars out

there with various different product characteristics.

So let's imagine, you are

a chocolate bar manufacturer and you have this product mix problem i.e.

you are deciding how many to produce of different types of chocolate bar.

Now, may be a confectioner may have several different chocolate bars in its range.

We'll keep things very simplified and just assume there are only two types

of chocolate bar nominally called let's say A and B.

However, A and B are different types of chocolate bar and

require different inputs in the manufacturing process.

So, imagine to produce these bars,

we need sort of two ingredients,

cocoa and also some machine time to manufacture the chocolate bars.

Okay. This is a deliberate simplification.

We are likely to need many more ingredients maybe some milk,

maybe some sugar, some other additives as well.

But just assume for simplicity cocoa and machine time.

So, chocolate bar A,

let's suppose this requires 10 grams of cocoa but only one minute of machine time.

So this is quite a cocoa-intensive chocolate bar.

Maybe this is solid chocolate.

So a lot of cocoa but they're very easy to manufacture,

I mean, you only need a minute of a machine to produce it.

In contrast, chocolate bar B is perhaps less cocoa-intensive.

Let's imagine we only need five grams of cocoa to produce a type B bar.

But perhaps, its a more complicated thing to produce, it takes longer.

Let's say, it equates to four minutes of machine time in order to produce a type B bar.

So, those are also technical requirements to produce bars A and B.

Now, as far as a constrained optimization problem is concerned,

what constraints might we face?

Well, perhaps this manufacturer has a finite amount of cocoa

available and let's say a finite amount of machine time available.

Let's put some arbitrary numbers to this.

Suppose the firm has access to 2,000 grams of

cocoa and let's say eight hours of machine time.

So in minutes, that would equate to what 480 minutes.

So given those cocoa and machine time constraints,

the firm has to decide how many of type A and type B chocolate bars to produce.

Now, as it's an optimization problem,

the firm must have some criterion,

something it's trying to optimize.

Now, an optimization could mean either

maximizing something or maybe minimizing something.

So, if this thing is a good thing let's say,

like profit and clearly profit is desirable and trying to maximize profit.

If we were trying to optimize something which was a bad like

the costs of production then of course

bad things we want to minimize rather than maximize.

So let's imagine here the chocolate manufacturer is trying to maximize profit,

so of the type A and type B bars,

let's suppose the profit margin is different across these two bars,

such that again, some arbitrary numbers for illustrative purposes.

Suppose chocolate bar A yields 10 pence or 10 cents profit per bar sold,

whereas the bar B which is more intricate.

Remember, let say this can achieve

a higher price and hence a higher profit margin let's say,

of 20 pence or 20 cents,

the currency of your choice.

So we are now in a position to develop and formulate our linear programming model.

So for this, we're going to need to determine our decision variables.

So here, we're trying to decide on the quantity to produce.

So we're not choosing prices,

we're choosing production levels.

So if I want a better notation,

let's use x and y to represent a quantity of

type A chocolate bars and the quantity of type B chocolate bars respectively.

So our goal is to determine the optimal values of x and y,

but optimal in what sense?

Well, if this chocolate manufacturer is profit maximizing,

then the optimal choice of x and y in the profit maximizing sense.

So any linear programming problem is going to need an objective function.

The thing we are either trying to maximize if it's

a good thing or minimize if it's a bad thing.

Say here, a simple profit function would suffice.

So given the profit margins of 10 pence on the type A bar and 20 pence on the type B bar,

you could write our simple objective function as 10x + 20y.

10, the profit margin on a type A bar times

x is quantity produced and hence sold and 20 times y.

20, the profit margin on type B bar times y the number produced and subsequently sold.

So we're trying to choose the values for x and y,

which maximizes this objective function,

this profit function of 10x + 20y.

However, we are faced with some real world constraints.

We have a finite amount of cocoa,

a finite amount of machine time and specific

technical requirements in order to produce a type A and type B chocolate bars.

So now, let's consider our constraint equations for which we have two constraints,

a cocoa constraint and a machine time constraint.

So remembering our requirements,

as far as cocoa is concerned,

a type A bar requires 10 grams of cocoa,

a type B bar requires five grams of cocoa.

So our total cocoa consumption will be drawn from

the cocoa used to produce both type A and type B bars added together.

So, 10x + 5y will be

our total cocoa consumption to produce x units of type A and y units of type B.

So our constraint is that we cannot use more cocoa than we have to begin with.

So we gave that arbitrary amount of 2,000 grams of cocoa.

So our cocoa constraint would be 10x + 5y is equal to 2,000.

We will also have a machine time constraint.

Remember, our requirement of one minute of machine time for type A bars,

four minutes of machine time for type B bars.

And hence, our machine time constraint would be x + 4y is equal to 480.

Note, the coefficient on the x there is equal to 1 because there was

one minute of machine time needed for each type A bar but one times x,

we would simplify as meaning x,

and the 480 represented the number of minutes of machine time available i.e.

eight hours with 60 minutes per hour.

So we need to choose the values of x and y such that we maximize

profit but subject to the constraints being satisfied.

We can't use more cocoa than we have nor can we use more machine time than we have.

So, a linear programming problem such as this can then be solved.

Now, for a very small problem such as this where we only have two products.

It would be possible to solve this using a graphical approach.

However, more generally, with a larger problem,

we may wish to defer to computers to solve these linear programming problems for us.

Well, good news, Microsoft Excel has something called Solver in it,

which is a very useful tool for solving a load of simultaneous equations.

Because even in this simple chocolate bar example,

we do have some two linear equations, those two constraints.

Note, we could easily rearrange those to express these as y as a function of x.

And these two constraints need to hold simultaneously such that software like

Microsoft Excel Solver can solve this set of

simultaneous equations very quickly for us and return the optimal values for x and y.

And indeed, if you look on the online materials,

you'll see an Excel spreadsheet which I've already prepared with this particular problem,

a set up within it and I guide you through

the process of solving this using Excel Solver.

So linear programming problems are a lovely class of modeling technique that

can easily be applied to solving these constrained optimization problems.

Just to give you a little taste of some of

the other quantitative methods which are out there.