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. We'll then implement the optimization problem in Excel using the min formula. That's exactly what we did in section three. We'll also look at an algebraic version of the formulation, that's the mathematical analog of the Excel spreadsheet formulas. 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. 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. 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. The first cell we'll look at is the Order Quantity Q, and right now we have a default of 10,000 units. That's what IDEA has been ordering before. This will become the decision variable. 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. 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 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. The fixed cost is simply 100,000 euros. The variable cost is the unit cost of 100 times the order quantity. 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. And you can see in every single case the fixed cost by definition stays the same. The variable cost stays the same because we're always ordering 10,000 units. And it's the revenues, and subsequently the profits that change with the demands. 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. 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. 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. And here we are. We can see in fact, that the optimal decision is to order about 7,884 units and the average profit for those 10 demands was almost 240,000 euros. 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. So that's it for Excel spreadsheet one. Or Excel number one. So having implemented a spread sheet formulation of the problem we can develop an algebraic formulation that's the mathematical analog of the spreadsheet. Before we start I want to remind you that our problem data are going to include ten samples of simulated demand. We're gonna call them D1, D2, D3, all the way up to D10. 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. 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. 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. 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. And so you get a sense, graphically, of what's going on. So we can avoid this bad type of non-linearity by extending the algebraic formulation. 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. We'll add 10 decision variables, one for each D i, and we're going to call them S i. Each S i is going to be the number of units sold when the demand sample is D i. And we can rewrite the definitions of the pi is to use the unit sales rather than the min function. So now you can see that those pi i's are linear functions of the S is and the Q. 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. 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. So, as long as Si is less than or equal to both constraints. As it's maximized in the optimal solution, it's going to be living exactly on those dash lines, and it's going to behave exactly, as if it were. 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. We have a template like the first one, although with a little bit of extra space to allow us the extra decision variables for the linear formulation. I want to remind you that the default order quantity was 10,000 units. 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. Okay. And now we can calculate everything else as we did before, except that we're not going to use the min function. So for revenues, we want to say that revenues equal the unit price of $150 times the sales. For that sample. 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. 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. And we'll choose the data tab and then the solver menu item. And we will set the objective function to be the average profit. We're gonna maximize it. You can see that. Here, we now have two sets of decision variables. We have the Q as before. That's the order quantity. And then I'm gonna type a comma that will let me select another set of decision variables. And after the comma I'm going to select the entire range of each of the unit sales, for each of the ten different demand samples. So, that would be S1 through S10. 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. 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. So again, you can see that objective in G21 now was the average profit, we're going to maximize it by choosing values for the decision variables, D3 was the order quantity, Q. And C10 through C19 were the sales for each of the demand samples. 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. Finally here at the bottom we've selected Simplex LP rather than GRG non-linear we are solving the problem as a linear optimization problem. So now we can go back, now that you've seen that, we'll go back and actually solve it. And we get an optimal solution. And as before you can see that the optimal order quantity in cell B3 is about 7,884, that's about exactly about what we had before, 7,884.09. And we have exactly the same profits. 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. 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. 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. And that's just a little example of the art of formulating optimization problems. That's it, and I'll see you soon. Thanks.
