《运筹学与供应链管理-第5讲ppt58》由会员分享，可在线阅读，更多相关《运筹学与供应链管理-第5讲ppt58（58页珍藏版）》请在金锄头文库上搜索。
1、第五讲Transportation and Network Models,Introduction,Several specific models (which can be used as templates for real-life problems) will be introduced.,TRANSPORTATION MODEL,ASSIGNMENT MODEL,NETWORK MODELS,Introduction,TRANSPORTATION MODEL,ASSIGNMENT MODEL,Determine how to send products from various so
2、urces to various destinations in order to satisfy requirements at the lowest possible cost.,Allocating fixed-sized resources to determine the optimal assignment of salespeople to districts, jobs to machines, tasks to computers ,NETWORK MODELS,Involve the movement or assignment of physical entities (
3、e.g., money).,Transportation Model,An example, the AutoPower Company makes a variety of battery and motorized uninterruptible electric power supplies (UPSs).,AutoPower has 4 final assembly plants in Europe and the diesel motors used by the UPSs are produced in the US, shipped to 3 harbors and then s
4、ent to the assembly plants.,Production plans for the third quarter (July Sept.) have been set. The requirements (demand at the destination) and the available number of motors at harbors (supply at origins) are shown on the next slide:,Demand,Supply,Assembly Plant No. of Motors RequiredLeipzig 400 (2
5、) Nancy 900 (3) Liege 200 (4) Tilburg 5002000,Harbor No. of Motors Available (A) Amsterdam 500 (B) Antwerp 700 (C) Le Havre 8002000,Graphical presentation of,Transportation Model,AutoPower must decide how many motors to send from each harbor (supply) to each plant (demand).,The cost ($, on a per mot
6、or basis) of shipping is given below.,The goal is to minimize total transportation cost.,Since the costs in the previous table are on a per unit basis, we can calculate total cost based on the following matrix (where xij represents the number of units that will be transported from Origin i to Destin
7、ation j):,Transportation Model,Transportation Model,Two general types of constraints.,1. The number of items shipped from a harbor cannot exceed the number of items available.,For Amsterdam: xA1 + xA2 + xA3 + xA4 500,For Antwerp: xB1 + xB2 + xB3 + xB4 700,For Le Havre: xC1 + xC2 + xC3 + xC4 800,Note
8、: We could have used an “=“ instead of “ 400,For Nancy: xA2 + xB2 + xC2 900,For Liege: xA3 + xB3 + xC3 200,Note: We could have used an “=“ instead of “ since supply and demand are balanced for this model.,For Tilburg: xA4 + xB4 + xC4 500,Transportation Model,Two general types of constraints.,Variati
9、ons on the Transportation Model,Suppose we now want to maximize the value of the objective function instead of minimizing it.,In this case, we would use the same model, but now the objective function coefficients define the contribution margins (i.e., unit returns) instead of unit costs.,Solving Max
10、 Transportation Models,When supply and demand are not equal, then the problem is unbalanced. There are two situations:,When supply is greater than demand:,When Supply and Demand Differ,In this case, when all demand is satisfied, the remaining supply that was not allocated at each origin would appear
11、 as slack in the supply constraint for that origin.,Using inequalities in the constraints (as in the previous example) would not cause any problems.,Variations on the Transportation Model,In this case, the LP model has no feasible solution. However, there are two approaches to solving this problem:,
12、1. Rewrite the supply constraints to be equalities and rewrite the demand constraints to be .,Unfulfilled demand will appear as slack on each of the demand constraints when one optimizes the model.,When demand is greater than supply:,Variations on the Transportation Model,2. Revise the model to appe
13、nd a placeholder origin, called a dummy origin, with supply equal to the difference between total demand and total supply.,The purpose of the dummy origin is to make the problem balanced (total supply = total demand) so that one can solve it.,The cost of supplying any destination from this origin is
14、 zero.,Once solved, any supply allocated from this origin to a destination is interpreted as unfilled demand.,Variations on the Transportation Model,Certain routes in a transportation model may be unacceptable due to regional restrictions, delivery time, etc.,In this case, you can assign an arbitrar
15、ily large unit cost number (identified as M) to that route.,This will force one to eliminate the use of that route since the cost of using it would be much larger than that of any other feasible alternative.,Eliminating Unacceptable Routes,Choose M such that it will be larger than any other unit cost number in the model.,Variations on the Transportation Model,Generally, LP models do not produce integer solutions.,The exception to this is the Transportation model. In general:,Integer Valued Solutions,
