Linear Programming Optimization with Excel

Okay, I'm going to go through a spreadsheet example of a linear programming optimization problem where we choose the optimal product mix for a relatively simple two product mix. And I'm going to be using Excel Solver to do this. Okay, so optimization is a pretty powerful tool. It can be used in many situations where you're trying to find a scheduling solution. asset allocation, inventory control, and in our situation we're using it to find a product mix, but it can be used in lots of different settings. And this is a linear problem, but you can be shown non-linear problems and Solver can be used to solve those as well. Whether you're using a simple example like I am or a more complex example, these models tend to share many things in common. Alright, so when you're working with optimization problems, you have basically three steps. The first step is the actual model development. Alright, Solver is a really sophisticated tool, but it needs quite a bit of help to do its thing. And so we spent some time building the model. Alright, the second step is actually using Solver. or something like it to find an optimal solution. And then finally you're going to evaluate the solution because recognize that things in the real world may not work out the way they do in a model. Alright, so I've summarized the problem that we're going to be working on. We're going to be finding a profit mix that maximizes our profit and in this production run we're limited to certain resources, alright, and then, yeah, we're going to also tell Solver not to make any negative products, alright, so we're going to put in these non-negativity constraints. Okay, and when you work with a spreadsheet model, you're going to need basically four things in order to formulate something that Solver... can actually solve. Alright, so we're going to need an objective function. And the objective function is the thing that we're trying to maximize or in some cases minimize. Alright, so in our case we're going to try to maximize profit. Alright, but you might be trying to minimize something like cost or even risk if you're talking about asset allocation. Okay, the second thing that these models are all going to need is input variables. So some kind of resources. that are going to be used every time you make something or it could be the resources, dollars that you're trying to allocate to some objective that you're trying to reach. They all have decision variables and that is how many to make. In our case, that's what we're going to be working with, how many to make. But again, if you're talking about assets or something else, it may be allocating dollars. Alright, and then they all have constraints. If you're missing one of these things, you won't be able to implement a model that Solver can solve. Okay, so I'm going to jump right into the model, and I'll move this out of the way. I've actually, whoops, gone a little too far there. I've actually done a fair amount of the work to kind of facilitate this. Alright, so I've sort of set up, you know, based on the inputs that we have, These are going to be our decision variables. I'll go ahead and put in some seed values there. Alright, so basically I'm saying, okay, make one of each. And then below I'm showing that for each unit we make how many of each resource we use and then how much profit we make finally. Now I just need some formulas that sort of tally up when those input... those decision variables change, it sort of tallies up how much I've used. So I have something on the left-hand side of my constraint to compare to the right-hand side. Okay, so the formula that I'm going to use here, I'm basically going to take whatever's in B4, multiply it by what's in B7, and I'm going to add to that whatever's in C4 times C7. Alright, so if we take a look at that, we can see that, okay, if you make one of each, you've used 15 labor hours in doing that, okay? There is a shorthand formula for doing this, and it is the workhorse of these optimization models. It's the sum product function. Okay, so the SUMPRODUCT function does exactly what I just did, but it does it a little more compactly. Alright, and I'm using absolute reference here, so I can just copy the function down. Okay, leave that one relative, and then I can just copy and paste. Alright, and same formula down here. Okay. Alright, so looking at our model, if I just sort of go into this from a simplistic view, I might say, well, I make more if I make the pro, so why wouldn't I just sort of look at something simple like the amount of chips? and use them all up and make pros. Okay. And so when I do that, sometimes that will work out. Okay. But when I do it in this situation, all right, yeah, I get... I get a big profit here, but I've also used more components that are available. So this is not a feasible solution. All right. And with a simple problem like this, right, I can just start sort of by hand backing things out until I find a solution that works. All right. And just finding a solution that works doesn't sort of guarantee me that it's the optimal solution. Okay. So in order to find that, we're going to use Solver. Okay, so I'm going to reset these to zero. I'm going to go to the data tab, and I'm going to launch Solver. Okay, so Solver kind of corresponds to what I was saying earlier, that you need an objective, you need decision variables, and you need the constraints. All right, so the objective here is our... total profit. Okay, so I'll just point and click at that. And you can see that, you know, by default it's maximizing that, but you also have the option to minimize or set it at a specific value. Okay, the next box is by changing variable cells. That's where the decision variables go. Alright, so I'll point, click, and drag on those. Alright, and then it's going to be subject to... to some constraints. Alright, there aren't any now, but basically we're going to say it's subject to all these values being less than or equal to these values. Alright, so I'm going to click add. Alright, and again, I'm going to point, click and drag. And then point, click and drag. and click OK. Alright, so the other constraint that I mentioned, Solver actually knows that this is a pretty common one. Alright, so it has a box down here that we can check to make the unconstrained variables non-negative. That's equivalent to saying these changing cells should not be negative. OK, once that's done we can just click Solve. And if I've set up the model correctly, in a few seconds it will give us a solution. And this is the message we're looking for. Solver has found a solution. Any other message that you see, it probably means you have to go back to the modeling step and try to fix something. A lot of times what you'll see here is Solver couldn't find a solution, the problem is unbounded. Alright, which probably means that... you have made one of your your constraints the inequality sort of point in the wrong direction okay so it does have a solution all right over here on the on the the right of the box you'll see it has some reports that are available you actually have to click on each one of those to make them show up and so you can evaluate the the solution I'll click OK and we can get a quick look at what it came up with for a solution. And so we can see that, yeah, it doesn't tell us to make a thousand pro, all right, and we know it wouldn't have told us that anyway, based on the constraint, it couldn't go past 14,000. All right, but it's told us to make 800 and 200 of the mini, all right, and then we get a profit of 173,400. All right, so now we're going to take a look at how sensitive that is. that solution is to changes in any of the inputs. Okay, so I'm going to start on the first report, the answer report, and it tells you some nice things like when you made the model and how many iterations it had to go through before it found a solution and then how long it took it to find that solution. All right, down below it just tells you, you know, a lot of times you'll set up these models and you'll try to solve them by hand a little bit before you run Solver. for many reasons, but we start at 0, so there's not a lot of information here. We start at 0, we end at 173,400. It also says where the decision variable started and where they ended. One thing to note here is that this problem is being solved as if everything in there is continuous. Obviously, we're not going to make partial tablets. We're not going to use partial resources, all right, but it's often easier to solve these as continuous variables, but then go ahead and interpret some of these reports as needed. Okay, the only other thing it really tells you down here is which variables you used all of, all right, and which you did not. All right, so the ones you used all of, they're called binding. All right, so there was no more left. All right, there was labor hours left. All right, and basically it's saying that even if you hadn't put in the non-negativity constraint, that it would not have made negative or tried to solve this with negative values in either one of those cells. Okay, we're going to move on to the sensitivity report. And I'll zoom in a little bit so you can see it better because this is the one that we probably spend the most time with. It has two sections. It deals with the inputs, the decision variables, and it deals then with the constraints. So if we just look at the input variables, we can sort of see what the optimal solution is. No big mystery there. It has this one column here, reduced cost. It shows that there is zero reduced cost. In a two-product mix. Yeah, you usually don't see a reduced cost. But if I added one product to this, if I had another model of tablet to make and allocate resources to, I might see a reduced cost and probably it would be negative, which would indicate that it would have a negative impact on the objective output, on the objective function. It shows you how much money you make or how much benefit you get from. Each unit you make all right, and then it shows you here. This is the this is the sensitivity part of it It shows you how much more? You could how much more the profit could be on the pro all right and how much less the profit would be on could be? on the pro Until you would get a different optimal solution so in other words I could increase I could increase the amount of profit by up to 2650 or decrease it by Up to $43, and I would still see this same product mix, $800, $200. All right, if I go outside those limits, then I'm going to start seeing a different product mix. All right, and we get similar numbers for the mini. Okay, if I look at the constraint section, all right, it shows you again how much you used. All right, how much the optimal solution used. It has this other column called a shadow price. There isn't one for labor hours used, and that would be true of any constraint that was not binding. All right, so we have some left over, and so there is no shadow price. All right, for the ones that we bumped up against those constraints, there's a shadow price. And for chips, it's 53. And what this is saying is if I had another chip, and if I had another chip, I'd also have to have more electronic components. But if I just had another chip... It would add $53 to that total profit. Alright, and if I had another electronic component, it would add $8.60 to that objective function. Alright, so it basically shows you what a incremental increase in any of these resources, what that would do to the objective function. And it does that while holding everything else constant. Okay? Alright, so no big mystery here. That's what the right-hand side of the constraint looks like. Alright, and then in this allowable increase, you know, since no matter how much labor I added, it wouldn't change the objective function. It's basically telling me I can increase that a lot. That's sort of solver's answer for infinity. They're 1 times 10 to the 30th. It does show you that if I have 400 less hours, more than 400 less hours, then I'd start seeing a shadow price over here. Down here in the allowable increase for chipsets, It shows you that while you could add up to 26 more chips. Alright, so this is where we're looking at that continuous solution again and Sort of you have to recognize that well, I wouldn't use a partial chip Alright, so if I add up to 26 chips I would I would still see for every chip I added I'd get $53.00 alright, and if I decreased it by up to 66 chips, well every unit increase would Every unit decrease would decrease the objective, the total profit by $56, sorry, by $53. Okay, and we get similar numbers for the electronic components, all right. All right, and the last report is the limits report. And this one's pretty straightforward too, like the answer report. It shows you what the final value was, all right. in the decision variables and in the objective function. And then it shows you, well, what would happen to the objective function if I didn't make any of the pros, all right? So if I, instead of making 800, I made none, then the value there would be 27,800, all right? And we get a similar number for the minis. If I don't make any of those, I still get 145,600. Okay, so that's a quick overview of using Solver with a fairly simple linear programming problem.

It can be used in many situations where you're trying to find a scheduling solution. asset allocation, inventory control, and in our situation we're using it to find a product mix, but it can be used in lots of different settings. And this is a linear problem, but you can be shown non-linear problems and Solver can be used to solve those as well.

Whether you're using a simple example like I am or a more complex example, these models tend to share many things in common. Alright, so when you're working with optimization problems, you have basically three steps. The first step is the actual model development.

Alright, Solver is a really sophisticated tool, but it needs quite a bit of help to do its thing. And so we spent some time building the model. Alright, the second step is actually using Solver.

or something like it to find an optimal solution. And then finally you're going to evaluate the solution because recognize that things in the real world may not work out the way they do in a model. Alright, so I've summarized the problem that we're going to be working on.

We're going to be finding a profit mix that maximizes our profit and in this production run we're limited to certain resources, alright, and then, yeah, we're going to also tell Solver not to make any negative products, alright, so we're going to put in these non-negativity constraints. Okay, and when you work with a spreadsheet model, you're going to need basically four things in order to formulate something that Solver... can actually solve.

Alright, so we're going to need an objective function. And the objective function is the thing that we're trying to maximize or in some cases minimize. Alright, so in our case we're going to try to maximize profit.

Alright, but you might be trying to minimize something like cost or even risk if you're talking about asset allocation. Okay, the second thing that these models are all going to need is input variables. So some kind of resources. that are going to be used every time you make something or it could be the resources, dollars that you're trying to allocate to some objective that you're trying to reach. They all have decision variables and that is how many to make.

In our case, that's what we're going to be working with, how many to make. But again, if you're talking about assets or something else, it may be allocating dollars. Alright, and then they all have constraints. If you're missing one of these things, you won't be able to implement a model that Solver can solve.

Okay, so I'm going to jump right into the model, and I'll move this out of the way. I've actually, whoops, gone a little too far there. I've actually done a fair amount of the work to kind of facilitate this. Alright, so I've sort of set up, you know, based on the inputs that we have, These are going to be our decision variables. I'll go ahead and put in some seed values there.

Alright, so basically I'm saying, okay, make one of each. And then below I'm showing that for each unit we make how many of each resource we use and then how much profit we make finally. Now I just need some formulas that sort of tally up when those input... those decision variables change, it sort of tallies up how much I've used. So I have something on the left-hand side of my constraint to compare to the right-hand side.

Okay, so the formula that I'm going to use here, I'm basically going to take whatever's in B4, multiply it by what's in B7, and I'm going to add to that whatever's in C4 times C7. Alright, so if we take a look at that, we can see that, okay, if you make one of each, you've used 15 labor hours in doing that, okay? There is a shorthand formula for doing this, and it is the workhorse of these optimization models. It's the sum product function.

Okay, so the SUMPRODUCT function does exactly what I just did, but it does it a little more compactly. Alright, and I'm using absolute reference here, so I can just copy the function down. Okay, leave that one relative, and then I can just copy and paste. Alright, and same formula down here. Okay.

Alright, so looking at our model, if I just sort of go into this from a simplistic view, I might say, well, I make more if I make the pro, so why wouldn't I just sort of look at something simple like the amount of chips? and use them all up and make pros. Okay.

And so when I do that, sometimes that will work out. Okay. But when I do it in this situation, all right, yeah, I get... I get a big profit here, but I've also used more components that are available. So this is not a feasible solution.

All right. And with a simple problem like this, right, I can just start sort of by hand backing things out until I find a solution that works. All right. And just finding a solution that works doesn't sort of guarantee me that it's the optimal solution. Okay.

So in order to find that, we're going to use Solver. Okay, so I'm going to reset these to zero. I'm going to go to the data tab, and I'm going to launch Solver.

Okay, so Solver kind of corresponds to what I was saying earlier, that you need an objective, you need decision variables, and you need the constraints. All right, so the objective here is our... total profit. Okay, so I'll just point and click at that.

And you can see that, you know, by default it's maximizing that, but you also have the option to minimize or set it at a specific value. Okay, the next box is by changing variable cells. That's where the decision variables go.

Alright, so I'll point, click, and drag on those. Alright, and then it's going to be subject to... to some constraints.

Alright, there aren't any now, but basically we're going to say it's subject to all these values being less than or equal to these values. Alright, so I'm going to click add. Alright, and again, I'm going to point, click and drag.

And then point, click and drag. and click OK. Alright, so the other constraint that I mentioned, Solver actually knows that this is a pretty common one.

Alright, so it has a box down here that we can check to make the unconstrained variables non-negative. That's equivalent to saying these changing cells should not be negative. OK, once that's done we can just click Solve. And if I've set up the model correctly, in a few seconds it will give us a solution.

And this is the message we're looking for. Solver has found a solution. Any other message that you see, it probably means you have to go back to the modeling step and try to fix something.

A lot of times what you'll see here is Solver couldn't find a solution, the problem is unbounded. Alright, which probably means that... you have made one of your your constraints the inequality sort of point in the wrong direction okay so it does have a solution all right over here on the on the the right of the box you'll see it has some reports that are available you actually have to click on each one of those to make them show up and so you can evaluate the the solution I'll click OK and we can get a quick look at what it came up with for a solution. And so we can see that, yeah, it doesn't tell us to make a thousand pro, all right, and we know it wouldn't have told us that anyway, based on the constraint, it couldn't go past 14,000.

All right, but it's told us to make 800 and 200 of the mini, all right, and then we get a profit of 173,400. All right, so now we're going to take a look at how sensitive that is. that solution is to changes in any of the inputs. Okay, so I'm going to start on the first report, the answer report, and it tells you some nice things like when you made the model and how many iterations it had to go through before it found a solution and then how long it took it to find that solution. All right, down below it just tells you, you know, a lot of times you'll set up these models and you'll try to solve them by hand a little bit before you run Solver.

for many reasons, but we start at 0, so there's not a lot of information here. We start at 0, we end at 173,400. It also says where the decision variable started and where they ended. One thing to note here is that this problem is being solved as if everything in there is continuous. Obviously, we're not going to make partial tablets.

We're not going to use partial resources, all right, but it's often easier to solve these as continuous variables, but then go ahead and interpret some of these reports as needed. Okay, the only other thing it really tells you down here is which variables you used all of, all right, and which you did not. All right, so the ones you used all of, they're called binding. All right, so there was no more left.

All right, there was labor hours left. All right, and basically it's saying that even if you hadn't put in the non-negativity constraint, that it would not have made negative or tried to solve this with negative values in either one of those cells. Okay, we're going to move on to the sensitivity report. And I'll zoom in a little bit so you can see it better because this is the one that we probably spend the most time with. It has two sections.

It deals with the inputs, the decision variables, and it deals then with the constraints. So if we just look at the input variables, we can sort of see what the optimal solution is. No big mystery there.

It has this one column here, reduced cost. It shows that there is zero reduced cost. In a two-product mix. Yeah, you usually don't see a reduced cost. But if I added one product to this, if I had another model of tablet to make and allocate resources to, I might see a reduced cost and probably it would be negative, which would indicate that it would have a negative impact on the objective output, on the objective function.

It shows you how much money you make or how much benefit you get from. Each unit you make all right, and then it shows you here. This is the this is the sensitivity part of it It shows you how much more? You could how much more the profit could be on the pro all right and how much less the profit would be on could be? on the pro Until you would get a different optimal solution so in other words I could increase I could increase the amount of profit by up to 2650 or decrease it by Up to $43, and I would still see this same product mix, $800, $200.

All right, if I go outside those limits, then I'm going to start seeing a different product mix. All right, and we get similar numbers for the mini. Okay, if I look at the constraint section, all right, it shows you again how much you used.

All right, how much the optimal solution used. It has this other column called a shadow price. There isn't one for labor hours used, and that would be true of any constraint that was not binding.

All right, so we have some left over, and so there is no shadow price. All right, for the ones that we bumped up against those constraints, there's a shadow price. And for chips, it's 53. And what this is saying is if I had another chip, and if I had another chip, I'd also have to have more electronic components.

But if I just had another chip... It would add $53 to that total profit. Alright, and if I had another electronic component, it would add $8.60 to that objective function.

Alright, so it basically shows you what a incremental increase in any of these resources, what that would do to the objective function. And it does that while holding everything else constant. Okay?

Alright, so no big mystery here. That's what the right-hand side of the constraint looks like. Alright, and then in this allowable increase, you know, since no matter how much labor I added, it wouldn't change the objective function. It's basically telling me I can increase that a lot.

That's sort of solver's answer for infinity. They're 1 times 10 to the 30th. It does show you that if I have 400 less hours, more than 400 less hours, then I'd start seeing a shadow price over here. Down here in the allowable increase for chipsets, It shows you that while you could add up to 26 more chips. Alright, so this is where we're looking at that continuous solution again and Sort of you have to recognize that well, I wouldn't use a partial chip Alright, so if I add up to 26 chips I would I would still see for every chip I added I'd get $53.00 alright, and if I decreased it by up to 66 chips, well every unit increase would Every unit decrease would decrease the objective, the total profit by $56, sorry, by $53.

Okay, and we get similar numbers for the electronic components, all right. All right, and the last report is the limits report. And this one's pretty straightforward too, like the answer report. It shows you what the final value was, all right.

in the decision variables and in the objective function. And then it shows you, well, what would happen to the objective function if I didn't make any of the pros, all right? So if I, instead of making 800, I made none, then the value there would be 27,800, all right?

And we get a similar number for the minis. If I don't make any of those, I still get 145,600. Okay, so that's a quick overview of using Solver with a fairly simple linear programming problem.

Transcript for:Linear Programming Optimization with Excel

Transcript for:
Linear Programming Optimization with Excel