Hi, I'm Sergei Savin and we're starting session two of the second week of Operations In Linux course. In session one, we have looked at the Zooter example, a resource allocation problem in which limited resources must be allocated among two competing products in the most profitable way. We have identified the three main components of the optimization model, decision variables, an objective function, and constraints. We've also written down an algebraic formulation of the Zooter problem. In this session, we'll create a spreadsheet formulation of the model, and find the best decision using the Solver optimization tool. Okay, in session two, we will take an algebraic model we put together in session one, express it in the spreadsheet terms, and we'll use Solver to optimize it. As a reminder, here's the algebraic model of the Zooter problem. We have the decision variables, R, the number of Razor scooters to produce, and N, the number of Navajo scooters to produce. The objective function, which is the profit 150 times r plus 160 times n that we want to maximize, and the constraints on available resources and our decision variables. As I mentioned, Solver will be our weapon of choice. So what is Solver? Solver is a standard Excel add-in on Windows. And it is available on later versions of Excel for Mac. If you use Mac, we have a link that explains the details for you. If you use Google Sheets, a version of the Solver is available as a so called add-on. Okay, this is my Excel template, zooter_0. It is posted in our site, so you can open it now and follow the steps I'm going through. Here in the zero version we have put in the problem data and also pasted in a copy of the algebraic model. So that it'll be easier to make comparisons between the algebraic and the spreadsheet formulations. We will build the model step by step, and then we will use the Solver to find the best production plan for Zooter. To go over this example, we will use Excel 2013 on the Windows platform. If you're using Mac or Google Sheets instead, you should still look at the steps we're following here first. Before we build the model, let's figure out where to find the Solver. The Solver is called Excel add-in. We're not in Excel 2013, and in this version of Excel, the Solver is located under the tab called Data in the portion of the tab called Analysis. Here's my Solver button. If your setup is just like mine and you see the Solver button there, you're good to go. If you do not see the Solver button, then you should go to File > Options > Add-Ins, and here at the bottom where it says Manage Excel Add-Ins, you click Go. And you want to make sure that the Solver Add-in is checked. You click OK, and the Solver should appear here under the Data tab. In the early versions of Excel, the steps you need to take may be different but in any case just keep in mind that the Solver is an Excel add-in. Find where the add-ins are in your version of Excel and make sure that the Solver is selected. Okay, we're now ready to set up our model. For this first example, we'll proceed in a very detailed manner to make sure that we cover every important aspect of the model's setup and of the Solver functionality. Now we need to translate our algebraic model into a spreadsheet formulation. In other words, we need to describe on the spreadsheet three key components of an optimization model, decision variables, an objective function and constraints. Let's start with the decision variables. In the Zooter problem we have two products, Razor and Navajo scooters. So let's create cells that will hold the values for the numbers of each type of scooter to be produced. Let's say we select cell C10 and D10 for this purpose. C10 will hold the value of the number of Razor scooters to be produced, that is the value of the decision variable R. And D10 will be reserved for the number of Navajo scooters, that is the value of the decision variable N. Let us put the header in cell A10, Units to Make. And let's add some trial values in cell C10 and D10 to make sure that those cells are not empty. So let's consider making 500 units of each scooter type. One last thing, let's highlight the decision variable cells by using the blue color and bold font and by putting a frame around them. Of course, whether you do this embellishment or not is completely up to you. It will not affect the optimization. But if you do, the decision variables will be easily recognizable as soon as the Excel file is opened, and this will make your file easier to navigate. So we have defined the cells to hold our decision variable values. Later we'll point the cells out to Solver and ask the Solver to change the values in cell C10 and D10 to identify the best possible production plan. Okay, we're done with the decision variables and are now ready for the objective function. The objective in this model is the total profit. So we should be able to calculate how much profit Zooter will be making for any values of the decision variables. Now let's calculate and record the profit value corresponding to our production plan of 500 units of each model. Let's select the cell F10 to hold the value of the objective function. That is the total profit value. In the cell F10, we will be writing a formula that calculates the value of the total profit. We start with the equality sign to tell Excel that we have a formula in the cell. Now, for each of 500 Razor scooters, Zooter gets $150. So we multiply 150 by 500, and to that value we must add the profit earned for Navajo scooters. That is 160 times 500. So the total is $155,000. So we have a formula for the objective function cell. This formula will calculate the total profit value for any choice of the decision variables. For example, if we try a production plan of say 600 units of Razors, and 600 units of Navajos, the number in F10 immediately changes to reflect the new profit value. So let's go back and change it to 500 and 500. By the way, if you'd like to see the formula inside a particular cell or edit that formula, you can use a Windows shortcut, F2. So we're in cell F10, and here we see the formula for the objective function. In this problem we have two decision variables. And the calculation of the profit value involves setting two products, the product of the number of Razor scooters and the profit contribution for each Razor scooter, and the product of the number of Navajo scooters, and the profit contribution for each Navajo scooter. But what if our problem contained 1000th of decision variables? Do we still have to write the profit formula as the sum of 1000th of products, one for each decision variable? Fortunately, not. The Excel function sum product allows us to use a kind of shorthand notation in such cases. Here's how the sum product works for the case of two scooter models. We are in the cell F10, and let's replace the current profit formula by its equivalent using sum product function. So we type sum product. Of C9 and D9, our profit contributions. And C10, and D10, our decision variables. The sum production function uses two areas of sales of equal size and multiplies the numbers in the first array by the corresponding numbers in the second array. First number in the first array is multiplied by the first number in the second array. Second number in the first array is multiplied by the second number in the second array. And so on. After that, the sum product simply sums all of those products. So the formula SUMPRODUCT(C9:D9,C10:D10) is exactly the same as the formula C9*C10+D9*D10. And you'll get this same optimization result no matter which one you use. However, there's some product formulas that are a lot more convenient when working with the models with large numbers of variables and large numbers of constraints. You can find more information about the sum product function in the Excel help. Okay, one last thing about the objective function cell. Just like we did for the decision variables cells let's highlight the objective function cell to make sure it stands out visually. Let's change the font color to red and make the font bold. So we're going to change the color to red, make the font bold. And put the thick border. Now every time we open the file, we see the decision variable cells in blue, and the objective function cell in red, so those cells are visually distinguishable from other cells. Later on we will instruct the Solver to change the values in our blue cells, C10 and D10, our decision variables values, to maximize the value in the red cell, F10, our objective function value. Of course, we cannot use just any values in the blue cells, but only those that do not require more resources to produce than what we have. Now that we are done with the decision variables and the objective function, it is time to move on to the constraints. The main constraints in our model express the limited availability of three production resources. Frame Manufacturing hours, Wheels and Deck Assembly hours and QA and Packaging hours. Let's look first at the Frame Manufacturing hours. We need to make sure that whatever production plan we consider, the number of Frame Manufacturing hours used by this plan does not exceed the number of Frame Manufacturing hours available. In the algebraic formulation, the number of Frame Manufacturing hours used by a production plan described by decision variables R and N is equal to four times R plus 5 times N. And the number of available hours is 5,610. Now spreadsheet formulation, cell G14 holds the value of the number of frame manufacturing hours available, 5610. Let us use the cell E14 to calculate the number of Frame Manufacturing hours required by the production plan in cells C10 and D10. For convenience, let us put the header Required Hours in cell E13 above E14. [TYPING]... OK we have two more constraints to convert into a spreadsheet format. The constraint on the number of Wheels and Deck Assembly hours, and the constraint on the number of QA and Packaging hours. If you look at the algebraic formulations of each of those constraints, you will notice that both have a very similar structure to that of the constraint we already dealt with. The constraint on the number of Frame Manufacturing hours. All three constraints have the fallen structure. Expression on the left hand sign of the constraint, the number of required hours, cannot exceed the number on the right-hand side of the constraint, the number of available hours Let's go the cell E-15 and put in the formula that will calculate the number of Wheels and Deck Assembly hours required for any pair of decision variables in cells C-10 and D-10. Just like in the similar calculations for the number of required Frame Manufacturing hours, we need to multiply each decision variable by the number of Wheels and Deck Assembly hours that a respective scooter model uses, and add the resulting products. In other words, the formula that we put in the cell E15 is, SUMPRODUCT of C10:D10, and C15:D15. For the production plan we're currently considering 500 scooters of each scooter model. We have the number of required wheels and deck manufacturing hours as 1750. Similarly, if we use cell E16 to calculate the number of QA and Packaging hours required by the production plan in cells C10 and D10, we will put in the formula, SUMPRODUCT of C10:D10, and C16:D16. As we see the current production plan, where [INAUDIBLE] requires 900 hours of this resource. Okay, what if we have thousands of different resources to keep track of? Do we have to keep going into cells in the E column one by one and type the SUMPRODUCT formula? Fortunately, Excel provides a way of avoiding this by using copy and paste and the so called absolute cell referencing or cell anchoring. Let's compare the formula in the cell E14 to the formulas in the cell E15 and E16 one more time. All three formulas use the SUMPRODUCT of the decision variable cells, C10 and D10. Here's the formula in the cell E14. And the consumption amounts of each respective resource. C14 and D14 for this cell E14. C15 and D15 for the cell E15, and C16 and D16 for the cell E16. So if we would take a formula in the cell E14 and copy and paste it into the cells E15 and E16, we would need to instruct Excel to leave C10 and D10 unchanged during this copy-and-paste operation. And to change C14 and D14 into C15 and D15 and into C16 and D16. The way to accomplish this is to use the absolute cell referencing, or cell anchoring, for the cells C10 and D10 before doing the regular Excel copy and paste operation. Here's how we accomplish this. We go into the cell E14, we highlight cells C10 and D10. And we use the Windows shortcut F4. To put the dollar signs around the addresses for cells, C10 and D10. Those dollar signs instruct Excel not to change the addresses of the cells when doing copy and paste. If I now just copy and paste the formula in E14 into E15 and E16 I get the correct formulas in those cells. So, I'm doing copy and paste. For example, if I now look at the cell E16, I see the formula SUMPRODUCT of C10:D10, and C16:D16, and that's the correct formula. Clearly, using this anchoring technique, I can simply type a formula for the resource consumption of one resource. Incur whatever cells I want in this case, decision variable cells and then just copy and paste the formula to all cells that calculate consumption amounts of all other resources. And it does not really matter, if I have hundreds of those, I can still do it all in one copy and paste operation. You can learn more above the absolute cell referencing using Excel Help. Let's also use a visual queue to indicate that what we want in the optimization is that the values in the cells E14, E15 and E16. To be less than or equal to the values in the cells G14 G15, and G16, so we put the less than equal signs here. This is just a visual embellishment to make sure we can read our file in a easy manner. Okay, we have created cells that hold values of the decision variables, the objective function and the resource consumption values. How will we go about finding the best production plan? In short we want to find the values in the cell C10 and D10, our decision variable cells, that make the value in the cell F10 our objective function cell. As large as possible, while making sure that the values in E14, E15, and E16 do not exceed the values in G14, G15, and G16 respectively. Those are resource constraints. For example, if they produced 500 units of each model, we earn the profit of $155,000 as Excel tells us. And all our resource consumption values stay within allowable ranges. Well, can we make more money by increasing the production? Let's try produce 500 Razor scooters, but 750 Navajo scooters. Our profit jumps to $195,000, but unfortunately, we're run out of Frame Manufacturing and Wheels and Deck Assembly Resources. So we cannot simply implement this production plan. Now let's tone it down to say, 600 hundred Navajo scooters. So our profit goes down to 171,000 and our required number of hours stays within the liable limits. So we can keep checking different values of decision variables, trying to improve the profit while staying within the resource limits. The problem is, if we are trying to do it manually, let me spend to man some other time checking out various possibilities. And even then, we might not find the best production plan, especially if we have to deal with many decision variables. This is where the Solver comes in. It could be impossible for any human to check all possible alternatives just because there could be so many of those alternatives. The Solver though, does a much faster and much more thorough job of checking those alternatives in trying to come up with the best. So let's bring in the Solver. Let's go to Data, click on Solver, the Solver parameters dialog comes up here in the Set Objective part. We click on the cell selection tool and choose the cell F10 to represent our objective. As you can see, the Solver can maximize or minimize the objective. Minimization could be helpful if you're dealing with minimization of the cost or it could select a values of decision variables to produce a desired value of the objective function. In the Zooter problem we maximize profit. So we check max option. Next, we use by changing variables cells to specify where our decision variables are. So we use the cell selection tool again to point to the cells C10 and D10. And we go back and we see that Excel now understands where our decision variables are. Finally, we need to specify to solve where the constraints are. We use subject to the constraints apart and click Add, the dialogue Add Constraint appears. In this dialogue, we use cell reference to select Cells E14, E15, and E16 on the left-hand side of the constraint. We also use constraint part to select the values G14, G15, and G16 on the right hand side of that constraint. So, now we're instructing the Solver to make sure that E14 does not exceed G14, E15 does not exceed G15, and E16 does not exceed G16. Know that we can also specify constraint of equal type or greater equal type and there are other choices here. We'll use one of them later, so let's select our less or equal than sign, let's click OK. You will see that this constraint is added. What is left is adding constraints that tell the Solver that our decision variables must be integer and non-negative. Let's add the integer constraint first, we again click on Add, aelect our decision variable, C10 and D10, and then in the drop down menu, select I and T options. Option, which means integer. So now when we click OK, the Excel solver understands that it must only use integer values in the cells C10 and D10 when it searches for the best production plan. Okay, the last constraint is a non-negativity constraint. And the Solver offers a convenient way of introducing this constraint for over for all decision variables at the same time. All we need to do is to check the box, make all unconstrained variables non-negative. Next we need to select a solving method. Solver offers several choices here with a default being GRG non-linear. One of the choices is LP simplex. This is a solving method that can only be applied to linear models. In other words, the models were the objective function, and the constraints and linear functions of decision variables. So if you are sure that your model is built as a linear model, use this option since it solves linear models very efficiently. If your model is not linear, however, and you're trying to us the LP simplex option, the server will complain. Now, in this discussion, I would like to focus on the details of the modeling process rather than on distinctions between linear and non-linear models. So I would leave this solving method as GRG Non-Linear. This solution method is very general and will allow you to work with many different kinds of models, both linear and non-linear. A word of caution, if you select the GRG non linear method, you do not have to worry about whether your model is linear or non-linear which is a good thing. Since it is a general method of solving optimization problems, it will try to find the best solution for any model you formulate. However, it may not always be able to guarantee that what it finds and gives you as a solution is actually the best possible alternative in every case. In addition, the output of optimization using the GRG nonlinear method, may depend on the trial values of the decision variables. So when optimizing using this method, run it several times with different trial values of the decision variables to see if you can improve the objective function value. Okay, the last stop before optimizing, let's go to Options and make sure that the Ignore Integer Constraints is unchecked. This way we're really making sure that the solver will not try to produce something like 54.6 scooters. We're ready to find the best production plan. Let's click Solve button and make sure that Solver found a solution is displayed in the dialog that appears and it does. Let's click OK, and look at the spreadsheet. Solver recommends producing 840 units of Razor scooters and 450 units of Navajo scooters if Zooter wants to maximize its profit, given the resources the company has. The corresponding profit value is $198,000. Before we leave Excel a few words about solver messages. This time the solver came up with a message, Solver found a solution, this is the message we want to see. I would like to mention two other messengers that we do not want to see. Suppose that we made a mistake in setting up our model and forgot to include one or more important constraints. Let's go to our Solver dialog and wipe out all of our constraints, and then try to optimize our production plan. So we go here and we say Delete. And we say Delete. So we have no constraints. Of course, that's silly, but let's try to solve the model and see what kind of message the Solver comes up with. Well, the solver comes up with a huge red exclamation sign and the message Objective Cell values do not converge. This means that the profit in this model can go to infinity. When you see a message like that when trying to optimize your model, please remember that it most probably indicates you forgot an important constraint. Okay, let's put back our constraints, Solver, Add. This three constraints should be less or equal than this three values, okay. And, let's add integer constraints on our decision variables, so we'll select this and we'll click Int, Integer. And we're back, let's click Solve just to make sure that we get everything right. Here's our optimal solution. Okay, now let's add a constraint that will make it impossible for the Solver to find the values of the decision variables, that will satisfy all of the constraints in the problem. For example right now we want the number of frame manufacturing hours used by the production plan not to exceed 5,610. Suppose we had a constraint that also requires the number of used frame manufacturing hours to be at least 6,000. Of course, these two constraints cannot be satisfied at the same time. But let's see what the Solver tells us when we are trying to solve the model with this constraint added. So we're going to Solver. And we're saying let's add this constraint, let's say the number of required hours of frame manufacturing should be at least greater or equal than 6,000. It's an incompatible constraint with our other constraints, but let's see what this overreaction would be. We'll click Solve and the solver comes up with another red exclamation sign, and a message that it could not find a feasible solution. In other words, it could not satisfy all the constraints at the same time. So when we see one of these messages there's something wrong with our model. Either in the case of the first message we are probably missing an important constraint, given the objective we are trying to optimize, or we have some incompatible constraints in the case of the second message. Let's restore our model to its original state, and solve it one more time to make sure that everything is fine. Let's delete this [INAUDIBLE] constraint. Let's click on Solve, and here we go, we have our optimal solution. This final spreadsheet with comments reflecting the formulas we introduced is posted on our site under the name Zooter. Okay, here's a picture of the optimized spread sheet with formulas. We have the best solution, 840 Razors and 450 Navajos and the best possible profit, $198,000, okay. Let's recap some optimization terms. A particular combination of decision variable values is called solution. A feasible solution is the one that satisfies all constraints. An infeasible solution is the one that violates at least one constraint, no matter which. The Objective Function Value is a number that you will obtain if you plug in decision variable values corresponding to a particular solution into the objective function. Finally, the optimal solution is the best feasible solution. In the Zooter case it has 840 Razor scooters and 450 Navajo scooters. It is possible to have more than one optimal solution but in that case any optimal solution will produce the same objective function value, the best one. In this session, we have used the solver optimization tool to set up and solve Zooter's optimization problem. While doing these, we have learned two approaches that are often useful in setting up spreadsheet optimization models in Excel. They use update some product function and they use of cell anchoring or absolute cell referencing. While details of solver operation may be slightly different in different platforms, for example, Windows versus Mac, the main features of the optimization process are pretty much the same. In particular, we must identify for the solver the main three components of an optimization model. Decision variables, the objective function, and constraints. If you use an Excel format or Google Sheets, have a look at two brief videos we created for you, to go over some minor differences in how optimization problems are set up and solved. Zooter's problem had two decision variables and three resource constraints. Real resource allocation applications may contain hundreds of thousands of variables and constraints or more. Of course, solo will not be able to handle such problems. But, commercial software packages that are powerful enough to deal with problems of this size, will still operate using decision variable, objective function, and constraints just like the solver. The Zooter's problem is a resource location example. In the next session we will look at another popular type of transition problem, one in which supply must meet demand across the network of locations. See you next time.
