Articles, Blog

K-MOOC Operations Research : Transportation

K-MOOC Operations Research : Transportation


Hello, this is Choi Sung Chul. I will explain Transportation problems of Network Model as the third lecture of the 10th week. Transportation problems are about how to transport the goods where they are needed. So, in a general supply center, I mean from this supply center, the destination is defined. It’s about how to connect them. The connection between them, let’s say the supply center is called i and the demand area is called j, is called xij like this. It also tells you if it supplies or not and how much is supplied continuously. The matter of supply can be solved using a binary method like an assignment problem. So, the general goal of this problem is to meet each requirements. It’s like this. So, what goes from a1 to b1 is x11 or x12. Like this, you can create a network to solve the problems. What we’re going to solve is a power company called Powerco. It’s a power company, and this power company has three power plants. It provides the electricity of power plants to four cities. So, there are one, two, three power plants. I’ll change the color, oops, it’s too light to see. There are one, two, three, four places that need electricity. From this premise, each power plant can provide certain amount of electricity. Here, it’s 35 millions. The next one is 50 millions and the next power plant can provide 40 millions. Therefore, each demand area has fixed maximum demands. Their demands are 45, by the way this is the peak demand, 20, 30 and 30. The prices of transporting from the first power plant to the first demand area is fixed like certain amount of money per 1 million. This is the result of it. To transport from the first power plant to here requires $ 8. The total demand for city1 is 45, so x11 and x12 are like this actually. You can solve these problems like the assignment problems. Write x14 like this. The next ones are x21, x22, x23, x24, x31, x32, x33 and x34. The sum of it is 45 and this one is 20. Likewise, the sum of these should be 35, 50 and so on. In fact, the method of solving the assignment problems and the transportation problems are basically the same. So, how much should it be when you sum it up? It’s about minimizing. The problem is about minimizing the cost and meet the requirements at the same time. This is what happens when you connect them. plant1 and city1 are connected like this. This one has the answer for them. You can solve the problems like this. Actually, it’s not that different from what you learn in the transportation problems. It’s similar to the assignment problem. You can put 1, 2 and 3 here and write 0, 10 and 25. oh, this is wrong because here is city 1. You should put 0, 10 and 25 here like a matrix describing in this way. The mathematization of the problem is like this. Each equation is the constraint of the supply. It means at least less than 35 is possible. the amount of supply that plant1 can provide was 35 millions, so it’s available until this amount. The demands of each one are more than this. More should be provided than the demands. By adding the prices of each one in this way, to minimize them is the key of this problem. Usually the demand and supply are written like this. In fact, Transportation and Assignment problems that we are learning now is a bit different algorithm, which sets BFS, Basic Feasible Solution, in the beginning and Basic Variable. It sometimes sets Basic Variable or Non Basic Variable, but that’s not what we’re going to learn in this lecture. If you are studying about it at school, you will get to learn them in detail. In those cases, you can see the way of applying the algorithm by using certain tables like this. We are going to use the code that we’ve learned from the previous lecture. I’ll show you the method using gurobi code. As you can see, the problem is pretty much the same as we did before. The equation at the top is written like cost_matrix. Here is the requirements for supply and demand. They are the requirements of this and that. This one isn’t need now. You can make the requirements like this. Next, you should create variables first. Variables are the same as before, what’s transporting from the plant is in the form of two dimensional variables. It has X11, x12, x13, and x14 as a variable form and becomes two dimensional array. The name of two dimensional array is variables. So, it starts here and ends there. Between them, there should be a list. It says a column here, it’s not correct. It should be city instead of column. Here is the coefficient value. The constant values are declared in capital. The value of plant is not row, so I”ll write plant here. The city will be increased as moving each plant. It will increase variables in turn. That’s the way to do it. I updated here like this. Second, the constraint is the supply constraint here. The supply constraint has the maximum amount that can provide. As you can see, for each plant, I’ll put it down here. For each plant, I wish there’s a better way to explain this. For each plant, it is and the amount of it provides, which is plant x11. With x11, x12, x13 and x14, I declare these. I use quicksum for them and it’ll be less than 35 which is the first value of plant. The second is, for statement turns back, right? It goes up and plant_number would be from 0 to 1. In fact, I wrote it as 11, but it’s 00 according to the index of the list. so, plant2 goes to the first city, 2 goes to the second city, 2 goes to the third city, and 2 goes to the fourth city. The sum of it will be 50. The sum of these is less than 50, and that’s what you should do here. The demand should be big. As for demand, I told you this before, The amount of demands from each city becomes 45 and there are variables. In plant_number, the first plant_number is the same. Then the plant_number here would be changed. City_number is still there, so city_number is plant1 for 1. City_number is plant 2 for 1 and city_number is 1 plant3 for 1. The sum of these three is the amount of electricity that provides to 1 city. It should be greater than 45. It’s x. In this way, it shows that using quicksum. From here to there, it now adds constraint. If the value comes out by optimizing after this, it means you did it well. This is the result from it. It should be like 12 is 10 and 13 is 25. If it’s in the case of the previous problem, as you can see the answers, You can see that it says 12 is 10 and 13 is 25. 12 is 10, 13 is 25, 21 is 45 and then others are all 0. It shows like 23 is 5. You can get only one answer for it as the previous problem. To make these into one can be possible for you now. You can do that by adding them to the constraint. You can make this like one plant can go from one place to the other one or one place can’t take it from two plants. I hope you to know how to solve transportation problems as adding constraints. We’ve learned a transportation problem. The transportation problem is fundamentally the same as the assignment problem. That’s why it’s not that hard. Later, you can see a slightly more difficult version of the transportation problems with dummy variables. There’re more details in the textbook we’re using, so please have a look at it if you get a chance. The more study, the better you’re going to be. I will see you again next time. Thank you.

Tagged , ,

Leave a Reply

Your email address will not be published. Required fields are marked *