0:00

Welcome to week four's Advanced Session on Optimization.

My name is Noah Ganz.

I'm your instructor for week four.

In this advanced session,

we're going to see how to transform an optimization problem that

has a non-linear min statement embedded into it into a linear formulation.

Before we get started, I want to remind you that this is an optional session and

you don't need to look at it.

You only need to look at it if you're curious.

We won't be testing you on this material.

So let's get started.

Here's what we're going to do.

We'll start out by recalling ideas optimization problem for session three.

0:53

We'll also graph the min statement and

we'll see why that min statement is not linear.

Having graphed the min statement,

we can use the graph to see how we can modify the formulation and make it linear.

And having done that, we'll update the algebraic formulation

to make it linear as well, and we'll implement it in Excel.

So let's remember IDEA's problem from session three.

In session three supplier P allowed IDEA to choose its order quantity, Q.

In particular, IDEA could choose a Q anywhere between 4,000 and 10,000 units.

1:31

IDEA had a more complex demand forecast.

For example, if the market were strong, demand would be uniformly distributed from

6,000 to 14,000 units, and in fact we are going to use the strong

part of the demand forecast in our examples today.

1:47

IDEA's revenues and costs for supplier P were as follows.

The sales price of the tent was 150 Euros per unit.

The unit cost was 100 Euros.

And supplier P would charge IDEA a fixed contracting fee

of 100,000 Euros if IDEA were to choose supplier P.

If IDEA were to order quantity Q, and demand turned out to be D,

then it would earn revenue of 150 euros price times the number of units sold,

minus 100 euros unit cost times to number of units ordered,

minus 100,000 euro fixed cost.

Putting it all together, IDEA's profit pi would be 150 times the number of units

sold minus- 100, times the number of units ordered, minus 100,000.

And we can go and take this formulation, and implement it in Excel.

And that's what we're gonna do next.

Now we're in Excel.

The name of this file is IDEA Linear Optimization.xlsx and

you can download it from the Coursera website.

And this first worksheet is a template the way that we've had templates earlier

in the week.

And we're gonna fill it out right now to

formulate an Excel version of IDEA's optimization problem.

3:20

Other problem data are the fixed cost of 100,000 euros,

the unit price of 150 euros, and the unit cost of 100 euros.

The last set of data that we need to fill out are the sample demands and

we'll do that with the Excel random number generator.

Remember, we go to the data tab, and then the data analysis menu item.

We'll double-click the random number generator to

bring up the random number generator.

3:49

And we're going to select one random variable and

generate ten samples, or ten random numbers,

and define it as a uniform distribution.

And, it will be defined between 6,000 and

14,000, with a random seat of one, two, three,

four, and an output range that starts in cell B10.

And then we'll click OK.

And we've generated a set of ten random demands that

are distributed uniformly between 6,000 and 14,000.

That's when the market is strong and let me just format this.

We've recall that by definition the uniform distribution

4:41

generates fractional numbers.

The other thing I want to show you is just a bigger screenshot of the random number

generator dialog box.

So again, we chose one random variable, ten random numbers,

uniform distribution distributed between 6,000 and 14,000 with a random seed one,

two, three, four, and the first the output range was cell B10.

And we got these ten numbers here.

These are all the data that we need, and now for each of the ten samples,

we're going to define the profits.

The revenues are the unit price of 150,

times the minimum of the demand for

that sample, and the order quantity.

5:53

And the profit is the revenue,

minus the fixed costs, minus the variable costs.

And you can see for

a demand of 6,993 IDEA is actually losing money if an order is 10,000 units.

It has revenues of about 1,049,000 Euros.

But it's got costs of about 1.1 million euros.

So it's losing about 51,000 euros.

Having filled out the definition of the profit for

this demand sample, we could just copy the cells down.

6:52

Having defined the profits for each of the ten samples, then we can take the average

of them using the Excel average formula To calculate the average profit.

And you can see for these ten samples, if IDEA had ordered 10,000 units,

it would have earned average profits for the ten samples of about a 162,000 euros.

Of course, if IDEA were to change its order quantities, so for example,

it were to order 9,000 instead of 10,000, you can see, for example,

that the average profits would have been instead about 216,000 euros.

So now we've got the spreadsheet set up, and we need to use Solver.

We're gonna call up Solver and define the decision variable, and the objective, and

the constraints.

So our objective is to maximize the average profit.

7:54

Our decision variable is the order quantity and

we need to add a couple of constraints.

We want to make sure that the order quantity is greater than or

equal to 4,000 units.

And also that the order quantity is less than or

equal to 10,000 units.

The last thing I'll point out is that we're going to use

non-linear because it's a non-linear formulation.

If you try to run it with Simplex OP, as if it were linear,

the solver will cough and complain.

8:32

Before I solve it, I just want to quickly show you,

the solver dialogue box is slightly larger.

So again, the objective was the average profit that was in cell F21.

We're gonna maximize it by choosing values for

the order quantity that was in cell B3.

And we had a couple of constraints that the order quantity had to be less than or

equal to 10,000 units, and the order quantity had to be greater than or

equal to 4,000 units.

And we're gonna use GRG Nonlinear.

So now let's go back here, and take a look at the Solver,

we're all set we're gonna solve it.

9:32

So by decreasing the order quantity, IDEA actually had,

I suppose, less leftover inventory and

had bought less inventory for the same kinds of demands,

and was able to increase its profits.

10:43

We generated those with Excel's random number generator and

we're gonna call the generic sample, Di.

With those data, we can now formulate IDEA's decision problem,

it's decision variable is Q that's the order quantity.

And if I do orders Q and the command sample is Di for

the ith sample, then we can calculate IDEA's profit, and we'll call it pi i.

That's calculated just the way we have before,

that's the 150 euro revenue times the quantity sold.

That's the minimum of the demand Di and Q, minus the hundred year unit cost

times the order quantity Q minus the hundred thousand Euro fixed cost.

With each of those ten defined, we can then calculate the average profit.

We're going to call that pi average.

It's the average over all ten samples.

11:38

Having defined the pi i's and

pi average, we can now fully formulate the algebraic version of the problem.

IDEA's are going to choose and

order quantity Q to maximize the pi average, subject to some constraints.

The first just defines pi average, that's the arithmetic average of the pi i's.

The second set of constraints, and

there are ten of them, defines each of the pi is.

Finally, there's a pair of constraints that limited ideas order

quantities between 4,000 and 10,000 units,

and that's the complete algebraic formulation of the problem.

And we can see embedded in the middle of it are these definitions of pi

i that have the non-linear min functions.

And we wanna see next, what's the problem with the min functions?

So now, let's plot sales as a function of demand in the order quantity.

Along the horizontal axis, we've plotted demand.

And remember, demand can be anywhere between 6,000 and 14,00 units.

And you can see along the horizontal axis, it moves from 6,000 to 8,000

to 10,000, and we've cut if off a little bit before 14,000.

In this example, we're saying the order quantity Q is 8,000.

You can see that Q = 8,000 up in the middle of the chart.

12:56

Along the vertical axis, we've plotted sales, and

sales is just the minimum of the demand and the order quantity.

So S i would be the number of units sold,

if the order quantity were Q, and for demand sample D i.

We can see if demand D i is 6,000, then sales equals 6,000.

If demand D i were 7,000, then sales would be 7,000.

All the way up to 8,000.

But if demand D i were 9,000, then sales would still only be 8,000,

because they're limited by the order quantity, Q equals 8,000.

Remember, S i is the min of D i and Q.

So right at that corner point, and I'll just show you with the cursor or

with the pointer, right at that.

13:48

Order quantity Q of 8,000, when demand equals 8,000,

the blue line that plots sales as a function of demand makes a right turn and

it also has a little corner point that's not even smooth.

The fact that it has a corner, is what makes the problem badly behaved.

And we'd like to fix both problems, the fact that it's not linear, it makes

the right turn, and the fact that on top of it, it's got that little corner point.

And we're gonna do that first of all, by extending the algebraic formulation,

then I'll show you what it looks like on the same plot.

14:35

Here's the original formulation.

We're going to maximize the average profits by average, subject to

a definition of pi average, subject to a definition of each of the pi i's, and

subject to limits on the order quantities, between 4,000 and 10,000 units.

It's the definitions of the pi i's that are problematic because they have the min

functions in them.

15:25

We'll add two constraints for each S i to make sure that each Si is less than or

equal to the minimum of D i or Q.

We'll have a constraint that S i is less than or equal to D i, and

we'll have a constraint, S i is less than or equal to Q.

So we've added 10 decision variables, one S i for

each D i, and 20 constraints, two constraints for each S i.

Notice that those constraints are going to be forcing each S i

to be less than or equal to the minimum of D i and Q.

But it would be feasible to have an Si that's strictly less than the minimum

of Di and Q.

So for example, it could be the case that demands were ten,

the order quantity were 20 and sales were five.

That would be feasible.

Nevertheless, when we maximize pi average,

we're going to be maximizing each of the pi i's.

And when we maximize the pi i it's going to force the S i to be as large

as possible until it hits one of those constraints.

So, in the optimal solution,

the S i is going to behave like it actually equals the minimum of D i and Q.

Rather than it just being less then or equal to Di and Q.

We can see how this works graphically as well.

16:41

This chart has the same exact axes as we used before.

The horizontal axis plots demand from 6,000 all the way up to about 12,000.

The vertical axis is plotting sales.

And sales, we'd like it to be s i is equal to the minimum of d i and q.

The constraints are only going to insure that s i is less than or

equal to the minimum of d i or q.

So let's plot the two constraints.

The first constraint is s i is less than or equal to d i.

And the boundary of that constraint Is a line of slope one,

you can see when DI 6,000 in the lower left then,

SI less than equal to DI is going to limit SI to be below the line of at 6,000.

Same thing at 8,000.

If di were 8000.

Then si is less than or equal to di, is going to limit si to be 8,000.

If di were to be above 8,000, si.

So, for example, 9,000.

Si less than or equal to di, would force si to be less than or equal to 9000.

For each Si, there is a second constraint, Si is left center equal to Q.

And I'm plotting it here for Q = 8,000.

Again, in this case, no matter what Di is,

Si left center equal to Q is going to limit Si to be less center equal to 8,000.

Now we can see how as di changes,

as the demand for the ith sample differs,

a different constraint is going to end up being binding in the optimal solution.

So for example, if di were 7,000, if that sample were 7,000, Si would live there.

And in maximizing Si, Si less than or equal to Di would be binding.

So Si will be push up to 7,000 and then stop in the optimal solution.

If on the other hand, di were 9,000, if demand for

that sample were 9,000, si will leave over here and

in maximizing si in the optimal solution.

The binding constraint would be si less than or equal to q.

19:09

Obeying that min function,

even though we've eliminated the min function from the formulation.

So that's how we're eliminating the min function, which is nonlinear and

it's got the little corner point.

And we've changed the optimization problem into a linear optimization problem.

So now we're ready to take a look at the full linear formulation.

Here's the original formulation.

We're maximizing the average profits.

Subject to the average profits being determined

as the arithmetic average of each of the pi i.

Subject to the definition of each of the pi i is that uses that nonlinear

min function.

And subject to limits on the order quantities.

The linear formulation works like this.

Again, we're gonna maximize the average profits.

Subject to the definition of the average profits is the earth medic mean.

Here though we're going to define each of the pi eyes in terms of the s

eyes you can see each pi eye definition is also a linear constraint and

we're going to add twenty extra constraints.

We're going to add a constraint that each si has to be less than or

equal to each Di.

Each Si is less than or equal to the order quantity Q.

And finally the same limits on ideas order quantity between 4,000 and 10,000 units.

Okay, we're back to the Excel spreadsheet.

Again the file name is Idealinearoptimization.xlsx,

and you can find it on the course or website.

20:56

From supplier p the fix costs is 100,000 euros,

the price is 150 euros per unit and the unit costs is 100 euros per unit.

In this portion of column b we have the ten demand samples from before.

We don't need to generate new ones.

We're going to use an average of the ten profits from these ten demands as before,

but here we've inserted a new column C that is unit sales.

These are our Si's.

And for now just now gonna throw in zeroes for the unit sales.

21:55

All right, the fixed costs are 100,000 as before.

The variable costs are 100 Euros per unit times

the number of units ordered, as before.

And the profits or simply the revenues

minus the fixed cost minus the variable cost.

Here, because the sales are zero,

you can see the profit is -1.1 million Euros.

Because we're just paying the fixed and variable cost but we're not earning

revenue when we optimize the sales numbers will be pushed to be as large as possible.

22:42

So now we're just going to copy.

This is pi one.

Were gonna copy the formula for pi one.

All the way through pi two to pi ten.

And once we have the pie eyes we can calculate the average profit.

And you can see it's blue because it's going to be the objective function.

So now we can go to solver's dialogue box.

23:45

And having selected the decision variables, now we can add constraints.

We know for example, that we want to make sure

that the unit sales are less than or equal to.

For demands and we can just do that by selecting entire ranges.

We also want to make sure that the unit sales are all less than or

equal to the order quantity Q.

24:15

And as before we some constraints on the order quantity.

We want to make sure that the order quantity is greater than or

equal to 4,000.

And that the order quantity is less than or

equal to 10,000.

Okay?

And we want now to select Simplex LP because we're solving this

as a linear optimization problem.

Let me show you a larger version of the solver dialog box so

you can see a little more clearly what I've done.

25:17

The first two constraints just show the upper and

lower limits on the order quantity, Q.

It has to be between 4,000 and 10,000.

The third set of constraints here you can see it's saying that

the SIs, the sales numbers have to be less than or equal to the DIs.

So it's the quantities in column B.

And the last constraint is that the SIs,

the sales quantities have to be less than or equal to Q, that's the quantity in B3.

26:21

The difference in the spreadsheets is really just that this formulation

Is linear, while the previous formulation was non-linear, and

we just got lucky that we're able to solve it with those min functions.

Here, there's no luck involved on.

This is a very stable formulation and

you see now that we can change a non-linear formulation that has min

functions into a linear one by adding decision variables and extra constraints.

So that's it for the spreadsheet and let's go back to the PowerPoint.

26:55

That's all for Advanced Session on Optimization in week 4.

We saw that the min function that was embedded

in IDEA's optimization problem was not linear.

It had a kink where demand equalled order quantity.

So we added extra decision variables in constraints to work around it.

For each demand DI, we added a decision variable SI,

that were the unit sales for that sample.

For each SI, we added a constraint that it would be less than or equal to DI.

So sales would never be more than demand for that sample.

And for each Si we also added the constraint that Si would be less than or

equal to Q, so sales would never be more than the order quantity for that sample.

27:40

When solver maximizes average profit, each Si would be maximized.

And even though it would be feasible to have the unit sales be strictly

below the demand or order quantity, in the optimal solution each SI would

be pushed up and it would behave as if it equalled the minimum of demand and

the order quantity just as in the original formulation.

So we've developed a linear formulation that behaves as if SI

equals the min of DI and Q.