I think that most of you have heard about Transportation problem. We have N factories and M mines/producers. Each factory needs and each mine can provide particular amount of resources. We have to transport these resources from mines to factories. What is obvious it costs money and this cost depends on the distance between factories and mines. We have to find such an allocation that will minimize this cost.
In order to solve this problem we can use linear programming and one of the most popular algorithms are simplex or stepping stone algorithm. However, today I will not write directly about them but I will show how to solve this problem in Excel. Yes, I'm talking about good old Excel. Surprised?
Excel has an Add-in called Solver which will do a job for us. I'll explain how to do it using a simple example with 3 factories and 3 mines. Here is a table that shows costs of transport between mines and factories. For example, if we want to move 10 units from Mine 1 to Factory 1 then a cost will be 10 *c11.
We also need another table with supplies and demands. Below is an example. The numbers is the first column shows how many resources each mine can provide and the numbers in the the first row shows how many resources are needed by each factory.
The last row and the last column show sums of allocated resources in each row and in each column. These columns are needed to easily configure Solver. In this example some resources have been already allocated and we need to optimally allocate remaining ones i.e. x12, x13....
We also we have to define limitations and a cost function. The first limitation is that found allocations should be non negative i.e.
x12, x13 ... >= 0
Besides we want to allocate all resources available in mines and each factory should receive required amount of resources i.e.
40 = 10 + x12 + x13
110 = x21 + x22 + x23
100 = x31 + x32 + 20
150 = 10 + x21 + x31
50 = x12 + x22 + x32
50 = x31 + x32 + 20
Because we have a column and a row with allocation sums it will be very easy to enter these allocations into Solver. It is also worth saying that in general these limitations can be different, for example we can have more resources than needed. Of course, in this case formulas above would be also different.
A cost function is also easy. We want to minimise the following sum which is equal to total cost of moving resources from mines to factories:
c11 * 10 + c12 * x12 + c13 * x13 + ....
Now we have everything to solve a problem in Excel. Firstly we have to enable Solver. To do so open Excel options, select Add-ins. Then find Solver on the list and confirm with OK (this procedure can vary in different versions of Excel).
I've already prepared a spreadsheet with all required equations and data for you. You can download it here (you have to download this file locally and do not use online Excel application). To run Solver go to Data tab and select Solver in Analysis category. Then select Solve button and all missing allocations will be populated. Easy, isn't it? Now, a few words about using Solver.
Here is a screenshot with Solver Parameters. A cell in a red circle contains a cost formula. This formula will be minimized (see a green rectangle). Yellow rectangle contains cells that will be modified by an algorithm and finally blue rectangle contains six formulas explained in the previous post.
The next screenshot shows additional options of Solver. You can display this window by pressing Options button in Solver Parameters window. I want to point 2 selected options. Assume Linear Model tells Solver that it deals with linear programming problem and Assume Non-Negative tells Solver that we are interested only in non-negative results.
As you can see much more options are available. I encourage you to experiment with them and also with different costs, limitations, number of mines/factories and problems.
In order to solve this problem we can use linear programming and one of the most popular algorithms are simplex or stepping stone algorithm. However, today I will not write directly about them but I will show how to solve this problem in Excel. Yes, I'm talking about good old Excel. Surprised?
Excel has an Add-in called Solver which will do a job for us. I'll explain how to do it using a simple example with 3 factories and 3 mines. Here is a table that shows costs of transport between mines and factories. For example, if we want to move 10 units from Mine 1 to Factory 1 then a cost will be 10 *c11.
| Transportation Cost | Factory 1 | Factory 2 | Factory 3 |
| Mine 1 | c11 | c12 | c13 |
| Mine 2 | c21 | c22 | c23 |
| Mine 3 | c31 | c32 | c33 |
We also need another table with supplies and demands. Below is an example. The numbers is the first column shows how many resources each mine can provide and the numbers in the the first row shows how many resources are needed by each factory.
The last row and the last column show sums of allocated resources in each row and in each column. These columns are needed to easily configure Solver. In this example some resources have been already allocated and we need to optimally allocate remaining ones i.e. x12, x13....
| Supply\Demand | 150 | 50 | 50 | Allocation sums for mines |
| 40 | 10 | x12 | x13 | 10 |
| 110 | x21 | x22 | x23 | 0 |
| 100 | x31 | x32 | 20 | 20 |
| Allocation sums for factories | 10 | 0 | 20 |
We also we have to define limitations and a cost function. The first limitation is that found allocations should be non negative i.e.
x12, x13 ... >= 0
Besides we want to allocate all resources available in mines and each factory should receive required amount of resources i.e.
40 = 10 + x12 + x13
110 = x21 + x22 + x23
100 = x31 + x32 + 20
150 = 10 + x21 + x31
50 = x12 + x22 + x32
50 = x31 + x32 + 20
Because we have a column and a row with allocation sums it will be very easy to enter these allocations into Solver. It is also worth saying that in general these limitations can be different, for example we can have more resources than needed. Of course, in this case formulas above would be also different.
A cost function is also easy. We want to minimise the following sum which is equal to total cost of moving resources from mines to factories:
c11 * 10 + c12 * x12 + c13 * x13 + ....
Now we have everything to solve a problem in Excel. Firstly we have to enable Solver. To do so open Excel options, select Add-ins. Then find Solver on the list and confirm with OK (this procedure can vary in different versions of Excel).
I've already prepared a spreadsheet with all required equations and data for you. You can download it here (you have to download this file locally and do not use online Excel application). To run Solver go to Data tab and select Solver in Analysis category. Then select Solve button and all missing allocations will be populated. Easy, isn't it? Now, a few words about using Solver.
Here is a screenshot with Solver Parameters. A cell in a red circle contains a cost formula. This formula will be minimized (see a green rectangle). Yellow rectangle contains cells that will be modified by an algorithm and finally blue rectangle contains six formulas explained in the previous post.
The next screenshot shows additional options of Solver. You can display this window by pressing Options button in Solver Parameters window. I want to point 2 selected options. Assume Linear Model tells Solver that it deals with linear programming problem and Assume Non-Negative tells Solver that we are interested only in non-negative results.
As you can see much more options are available. I encourage you to experiment with them and also with different costs, limitations, number of mines/factories and problems.
No comments:
Post a Comment