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

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

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

Here is a screenshot with

The next screenshot shows additional options of Solver. You can display this window by pressing

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 sumsfor mines |

40 | 10 | x12 | x13 | 10 |

110 | x21 | x22 | x23 | 0 |

100 | x31 | x32 | 20 | 20 |

Allocation sumsfor 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.

## 0 comments:

## Post a Comment