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.

Â