Transportation Problem - LP Formulation

Welcome! In this video we’ll be discussing the linear programming formulation of the Transportation problem. In a transportation problem the goal is to produce products at supply locations (or origins) and transport them to destinations where they’re demanded at minimum costs. We will be writing an LP formulation for this transportation matrix. The origins are 2 plants at Boston and Toronto with supplies or capacities of 300 and 500 units, while the destinations are 3 distribution centers with demands of 200, 300 and 250 respectively. The costs of transporting a unit of the product from origins to destinations are seen here. For example, it costs $6 to ship a unit of the product from Boston to Distribution centre 2. Now let’s draw a transportation network for this problem. These circles are called nodes for the origins or in this case plants. And these are the nodes for the destinations. Here are the plant capacities and here are the demands at the destinations. Here are the shipping costs from Boston to the distribution centres. And here are the costs from Toronto. The arrows from the origins to the destinations are called arcs. Now let’s define the decision variables for the LP model. Let XB1 = equal the number of units shipped from Boston to DC1 Then XB2 from Boston to DC2, and XB3 from Boston to DC3. Similarly for Toronto we can use XT1, XT2 and XT3. The number of decision variables is simply the number of origins multiplied by the number of destinations. In this case, 2 times 3 which equals 6 decision variables. Now, suppose I don’t like listing every single variables or maybe I just happen to have too many variables, then I can use the short form as follows: Let Xij = # units shipped from Plant i to DC j Where i = B for Boston and T for Toronto and j = 1, 2, 3, for DC1, DC2, and DC3 respectively. Next we state the objective function. Since the objective function is to minimize costs, we write the objective function as follows: Minimize 5 times the number of units shipped from Boston to DC1 + 6 times the number of units shipped to DC2 and so on. Note that every single cost is accounted for in the objective function. For the constraints we need to write one for every node. For Boston’s supply, the total amount shipped to the 3 distribution centers cannot exceed Boston’s capacity which is 300. So we write XB1 + XB2 + XB3 ≤ 300. We do the same for Toronto. XT1 + XT2 + XT3 ≤ 500 Note here that Total Supply exceeds total demand. That is, we will not end up exhausting capacity. And that’s why we use the less than or equal sign. For DC1 node we write XB1 + XT1 = 200 Equality is used because we have a demand here that must be met and we have enough supply to meet it. Similarly for DC2 we have XB2 + XT2 = 300 And for DC3 we have XB3 + XT3 = 250 For non-negativity we can either list all the variables and state that each is greater or equal to 0 or we can simply write Xij ≥ 0 for all i and j. And that’s the LP model. Furthermore, let’s suppose the cost of producing a unit of the product is $20 in Boston and $18 in Toronto. Then we simply add 20 to the shipping cost per unit of products from Boston and add 18 to those from Toronto. The objective function is thus updated accordingly. Note here that if total supply were equal to total demand, we could have used equality for all constraints. We refer to that situation as a balanced transportation problem. This problem however is an unbalanced transportation example where Supply exceeds demand. Moreover, we could also have an unbalanced problem where demand exceeds supply. Consider the following scenario. Suppose demand at Distribution Centre 1 increases to 300 units. Then we have another unbalanced problem with demand exceeding supply. Let’s look at 2 ways to handle this: Since demand now exceeds supply by 50 units, one approach is to add a dummy plant and assign it a supply of 50 units. Note that these 50 units do not exist. So their cost per unit is 0 and their shipping cost is also 0 since they are not going to be shipped at all. We can thus modify our model as follows: Add D for Dummy in the decision variables, add the new costs to the objective function (they really won’t have any impact on total cost). Next we add a constraint for the dummy node, and finally, add the units assumed to be shipped from the Dummy. And again Xij is non-negative for all i and j. At the end of the day demand will not be fully satisfied at some of the distribution centres because the Dummy supplies don’t really exist. Instead of introducing a dummy, let’s now look at another formulation method we can apply. Since demand exceeds supply, all available supply will be used up, so we simply change the ‘less than or equal signs’ here to equal signs. And since demand is not going to be fully met at some of the distribution centres, we change the demand equality signs to ‘less than or equal signs’. And the model is again complete. Now suppose for some reason, we are not allowed to ship from Toronto to DC3. Maybe because the cost is too high or the destination is too far. One way to address that is to simply remove XT3 from the model. But if your model has many variables and you don’t want to be looking for XT3 all over the place, a better way is to add another constraint to the model that states that XT3 = 0. And that addresses the issue. And that’s LP for Transportation problem. Thanks for watching!

Channel: Joshua Emmanuel

Views: 291,968

Rating: 4.9234843 out of 5

Keywords: transportation, Maximize, minimize, lp, problem, model, slack surplus, introduction, linear programme, objective, constraints, nonnegativity, optimal solution, optimization, simplex, binding, standard form, Alternative optimal solutions, Infeasibility, Unboundedness, Redundancy

Id: WZIyL6pcItY

Length: 6min 40sec (400 seconds)

Published: Sat Oct 31 2015