运筹学与供应链管理-第5讲ppt58.ppt

《运筹学与供应链管理-第5讲ppt58.ppt》由会员分享，可在线阅读，更多相关《运筹学与供应链管理-第5讲ppt58.ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五讲第五讲Transportation and Network ModelsIntroductionSeveral specific models(which can be used as templates for real-life problems)will be introduced.TRANSPORTATION MODELTRANSPORTATION MODEL ASSIGNMENT MODELASSIGNMENT MODEL NETWORK MODELSNETWORK MODELS IntroductionTRANSPORTATION MODELTRANSPORTATION MO

2、DEL ASSIGNMENT MODELASSIGNMENT MODEL Determine how to send products from various sources 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 com

3、puters NETWORK MODELSNETWORK MODELS Involve the movement or assignment of physical entities(e.g.,money).Transportation ModelAn 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

4、diesel motors used by the UPSs are produced in the US,shipped to 3 harbors and then sent 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

5、next slide:DemandSupplyAssembly PlantAssembly PlantNo.of Motors RequiredNo.of Motors Required(1)Leipzig400(2)Nancy 900(3)Liege200(4)Tilburg500 2000Harbor Harbor No.of Motors AvailableNo.of Motors Available(A)Amsterdam500(B)Antwerp700(C)Le Havre800 2000BalancedBalancedGraphical presentation ofLe Havr

6、e(Le Havre(C C)800Antwerp(Antwerp(B B)700Amsterdam(Amsterdam(A A)500SupplySupplyLiege(3)Liege(3)200TilburgTilburg(4)(4)500Leipzig(1)Leipzig(1)400Nancy(2)Nancy(2)900and Demand:Demand:Transportation ModelAutoPower must decide how many motors to send from each harbor(supply)to each plant(demand).The co

7、st($,on a per motor basis)of shipping is given below.TO DESTINATIONTO DESTINATION Leipzig Nancy Liege Leipzig Nancy Liege TilburgTilburgFROM ORIGINFROM ORIGIN (1)(2)(3)(4)(1)(2)(3)(4)(A)Amsterdam(A)Amsterdam 120 130 41 59.50(B)Antwerp(B)Antwerp 61 40 100 110(C)Le Havre(C)Le Havre 102.50 90 122 42 Th

8、e goal is to minimize total transportation costminimize total transportation cost.Since the costs in the previous table are on a per per unit basisunit basis,we can calculate total costtotal cost based on the following matrix(where xij represents the number of units that will be transported from Ori

9、gin i to Destination j):Transportation Model TO DESTINATIONTO DESTINATIONFROM ORIGINFROM ORIGIN 1 2 3 41 2 3 4 A A 120 xA1 130 xA2 41xA3 59.50 xA4 B B 61xB1 40 xB2 100 xB3 110 xB4 C C 102.50 xC1 90 xC2 122xC3 42xC4Total Transportation CostTotal Transportation Cost=120 xA1+130 xA2+41xA3+122xC3+42xC4T

10、ransportation ModelTwo general types of constraintsconstraints.1.The number of items shipped from a harbor cannot exceed the number of items available.For Amsterdam:For Amsterdam:xA1+xA2+xA3+xA4 500 For Antwerp:For Antwerp:xB1+xB2+xB3+xB4 700 For Le Havre:For Le Havre:xC1+xC2+xC3+xC4 800 Note:We cou

11、ld have used an“=“instead of“400 For Nancy:For Nancy:xA2+xB2+xC2 900 For Liege:For Liege:xA3+xB3+xC3 200 Note:We could have used an“=“instead of“since supply and demand are balanced for this model.For For TilburgTilburg:xA4+xB4+xC4 500 Transportation ModelTwo general types of constraintsconstraints.

12、Variations on the Transportation ModelSuppose we now want to maximizemaximize 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.Solv

13、ing Max Transportation ModelsSolving Max Transportation ModelsWhen 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 DifferWhen Supply and Demand DifferIn this case,when all demand is satisfied,the remain

14、ing supply that was not allocated at each origin would appear 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 ModelIn this case,the LP model has no feasible solution.Howev

15、er,there are two approaches to solving this problem: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

16、Transportation Model2.Revise the model to append 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 supplyi

17、ng any destination from this origin is zero.Once solved,any supply allocated from this origin to a destination is interpreted as unfilled demand.Variations on the Transportation ModelCertain routes in a transportation model may be unacceptable due to regional restrictions,delivery time,etc.In this c

18、ase,you can assign an arbitrarily 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 RoutesEliminating Unacceptable RoutesChoo

19、se M such that it will be larger than any other unit cost number in the model.Variations on the Transportation ModelGenerally,LP models do not produce integer solutions.The exception to this is the Transportation model.In general:Integer Valued SolutionsInteger Valued SolutionsIf all of the supplies

20、 and demands in a If all of the supplies and demands in a transportation model have integer values,transportation model have integer values,the optimal values of the decision variables the optimal values of the decision variables will also have integer values.will also have integer values.Variations

21、 on the Transportation ModelAssignment ModelIn general,the Assignment model is the problem of determining the optimal assignment of n“indivisible”agents or objects to n tasks.For example,you might want to assignSalespeople to sales territoriesComputers to networksConsultants to clientsService repres

22、entatives to service callsCommercial artists to advertising copyThe important constraint is that each person or The important constraint is that each person or machine be assigned to machine be assigned to one and only one taskone and only one task.We will use the AutoPower example to illustrate Ass

23、ignment problems.AutoPower AutoPower Europes Auditing ProblemEuropes Auditing ProblemAutoPowers European headquarters is in Brussels.This year,each of the four corporate vice-presidents will visit and audit one of the assembly plants in June.The plants are located in:Leipzig,GermanyLiege,BelgiumNanc

24、y,FranceTilburg,the NetherlandsAssignment ModelThe issues to consider in assigning the different vice-presidents to the plants are:1.Matching the vice-presidents areas of expertise with the importance of specific problem areas in a plant.2.The time the management audit will require and the other dem

25、ands on each vice-president during the two-week interval.3.Matching the language ability of a vice-president with the plants dominant language.Keeping these issues in mind,first estimate the(opportunity)cost to AutoPower of sending each vice-president to each plant.Assignment ModelThe following tabl

26、e lists the assignment costs in$000s for every vice-president/plant combination.PLANTPLANT Leipzig Nancy Liege Leipzig Nancy Liege TilburgTilburg V.P.(1)(2)(3)(4)V.P.(1)(2)(3)(4)Finance(F)Finance(F)24 10 21 11 Marketing(M)Marketing(M)14 22 10 15Operations(O)Operations(O)15 17 20 19 Personnel(P)Perso

27、nnel(P)11 19 14 13 Assignment Model PLANTPLANT Leipzig Nancy Liege Leipzig Nancy Liege TilburgTilburg V.P.(1)(2)(3)(4)V.P.(1)(2)(3)(4)Finance(F)Finance(F)24 10 21 11 Marketing(M)Marketing(M)14 22 10 15Operations(O)Operations(O)15 17 20 19 Personnel(P)Personnel(P)11 19 14 13 Consider the following as

28、signment:Total cost=24+22+20+13=79The question is,is this the least cost assignment?Assignment ModelComplete enumeration is the calculation of the total cost of each feasible assignment pattern in order to pick the assignment with the lowest total cost.Solving by Complete EnumerationSolving by Compl

29、ete EnumerationThis is not a problem when there are only a few rows and columns(e.g.,vice-presidents and plants).However,complete enumeration can quickly become burdensome as the model grows large.Assignment Model1.F can be assigned to any of the 4 plants.2.Once F is assigned,M can be assigned to an

30、y of the remaining 3 plants.3.Now O can be assigned to any of the remaining 2 plants.4.P must be assigned to the only remaining plant.There are 4 x 3 x 2 x 1=24 possible solutions.In general,if there are n rows and n columns,then there would be n(n-1)(n-2)(n-3)(2)(1)=n!(n factorial)solutions.As n in

31、creases,n!increases rapidly.Therefore,this may not be the best method.Assignment ModelFor this model,let xij=number of V.Ps of type i assigned to plant jwhere i=F,M,O,P j=1,2,3,4The LP Formulation and SolutionThe LP Formulation and SolutionNotice that this model is balanced since the total number of

32、 V.P.s is equal to the total number of plants.Remember,only one V.P.(supply)is needed at each plant(demand).Assignment ModelAs a result,the optimal assignment is:PLANTPLANT Leipzig Nancy Liege Leipzig Nancy Liege TilburgTilburg V.P.(1)(2)(3)(4)V.P.(1)(2)(3)(4)Finance(F)Finance(F)24 10 21 11 Marketin

33、g(M)Marketing(M)14 22 10 15Operations(O)Operations(O)15 17 20 19 Personnel(P)Personnel(P)11 19 14 13 Total Cost($000s)=10+10+15+13=48Assignment ModelThe Assignment model is similar to the Transportation model with the exception that supply cannot be distributed to more than one destination.Relation

34、to the Transportation ModelRelation to the Transportation ModelIn the Assignment model,all supplies and demands are one,and hence integers.As a result,each decision variable cell will either contain a 0(no assignment)or a 1(assignment made).In general,the assignment model can be formulated In genera

35、l,the assignment model can be formulated as a transportation model in which the supply at as a transportation model in which the supply at each origin and the demand at each destination=1.each origin and the demand at each destination=1.Assignment ModelCase 1:Supply Exceeds DemandCase 1:Supply Excee

36、ds DemandUnequal Supply and Demand:Unequal Supply and Demand:In the example,suppose the company President decides not to audit the plant in Tilburg.Now there are 4 V.P.s to assign to 3 plants.Here is the cost(in$000s)matrix for this scenario:PLANTPLANT NUMBER OF V.P.s NUMBER OF V.P.sV.P.V.P.1 12 23

37、3 AVAILABLE AVAILABLE F F241021 1 MM142210 1 OO151720 1 P P111914 1No.of V.P.s No.of V.P.s 4RequiredRequired111 3Assignment ModelTo formulate this model,simply drop the constraint that required a V.P.at plant 4 and solve it.Assignment ModelUnequal Supply and Demand:Unequal Supply and Demand:Case 2:D

38、emand Exceeds SupplyCase 2:Demand Exceeds SupplyUnequal Supply and Demand:Unequal Supply and Demand:In this example,assume that the V.P.of Personnel is unable to participate in the European audit.Now the cost matrix is as follows:PLANTPLANT NUMBER OF V.P.sNUMBER OF V.P.sV.P.V.P.1 12 23 34 4 AVAILABL

39、E AVAILABLE F F24102111 1 MM14221015 1 OO15172019 1No.of V.P.s No.of V.P.s 3RequiredRequired1111 4Assignment Model1.Modify the inequalities in the constraints (similar to the Transportation example)2.Add a dummy V.P.as a placeholder to the cost matrix(shown below).PLANTPLANT NUMBER OF V.P.sNUMBER OF

40、 V.P.sV.P.V.P.1 12 23 34 4 AVAILABLE AVAILABLE F F24102111 1 MM14221015 1 OO15172019 1DummyDummy 0 0 0 01No.of V.P.s No.of V.P.s 4RequiredRequired1111 4Zero cost to assign the dummyDummy supply;now supply=demandAssignment ModelIn the solution,the dummy V.P.would be assigned to a plant.In reality,thi

41、s plant would not be audited.Assignment ModelUnequal Supply and Demand:Unequal Supply and Demand:In this Assignment model,the response from each assignment is a profit rather than a cost.Maximization ModelsMaximization ModelsFor example,AutoPower must now assign four new salespeople to three territo

42、ries in order to maximize maximize profitprofit.The effect of assigning any salesperson to a territory is measured by the anticipated marginal increase in profit contribution due to the assignment.Assignment ModelHere is the profit matrix for this model.NUMBER OFNUMBER OF TERRITORY TERRITORY SALESPE

43、OPLE SALESPEOPLESALESPERSONSALESPERSON1 12 23 AVAILABLE3 AVAILABLE A A403020 1 B B182822 1 C C121620 1 D D252427 1No.of No.of 4 SalespeopleSalespeople 1113 RequiredRequiredThis value represents the profit contribution if A is assigned to Territory 3.Assignment ModelThe Assignment ModelCertain assign

44、ments in the model may be unacceptable for various reasons.Situations with Unacceptable AssignmentsSituations with Unacceptable AssignmentsIn this case,you can assign an arbitrarily large unit cost(or small unit profit)number to that assignment.This will force Solver to eliminate the use of that ass

45、ignment since,for example,the cost of making that assignment would be much larger than that of any other feasible alternative.Assignment ModelNetwork ModelsTransportation and assignment models are members of a more general class of models called network modelsnetwork models.Network models involve fr

46、om-to sourcessources and destinationsdestinations.Applied to management logistics and distribution,network models are important because:They can be applied to a wide variety of real world models.Flows may represent physical quantities,Internet data packets,cash,airplanes,cars,ships,products,Zigwell

47、Inc.is AutoPowers largest US distributor of UPS generators in five Midwestern states.Network ModelsA Capacitated Transshipment ModelA Capacitated Transshipment ModelZigwell has 10 BigGens at site 1These generators must be delivered to construction sites in two cities denoted and 343 BigGens are requ

48、ired at site and 7 are required at site 34Network Models1+102543-3-7This is a network diagramnetwork diagram or network flow diagramnetwork flow diagram.Each arrow is called an arcarc or branchbranch.Each site is termed a nodenode.SupplyDemandNetwork Modelscijthe costscosts(per unit)of traversing th

49、e routesuijthe capacitiescapacities along the routesCostsCosts are primarily due to fuel,tolls,and the cost of the driver for the average time it takes to traverse the arc.Because of pre-established agreements with the teamsters,Zigwell must change drivers at each site it encounters on a route.Becau

50、se of limitations on the current availability of drivers,there is an upper bound,uij,on the number of generators that may traverse an arc.Network Models1+102543-3-7c12c23c24c25c34c43c53u12u23u24u25u34u43u53Network ModelsLP Formulation of the ModelNetwork ModelsA Capacitated Transshipment ModelA Capa