• 1. 第五讲 Transportation and Network Models
    • 2. IntroductionSeveral specific models (which can be used as templates for real-life problems) will be introduced. TRANSPORTATION MODEL ASSIGNMENT MODEL NETWORK MODELS
    • 3. IntroductionTRANSPORTATION MODEL ASSIGNMENT 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 computers …NETWORK MODELS Involve the movement or assignment of physical entities (e.g., money).
    • 4. Transportation ModelAn example, the AutoPower Company makes a variety of battery and motorized uninterruptible electric power supplies (UPS’s). AutoPower has 4 final assembly plants in Europe and the diesel motors used by the UPS’s 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 next slide:
    • 5. DemandSupplyAssembly Plant No. of Motors Required Leipzig 400 (2) Nancy 900 (3) Liege 200 (4) Tilburg 500 2000 Harbor No. of Motors Available (A) Amsterdam 500 (B) Antwerp 700 (C) Le Havre 800 2000Balanced
    • 6. Graphical presentation ofLe Havre (C)800Antwerp (B)700Amsterdam (A)500SupplyLiege (3)200Tilburg (4)500Leipzig (1)400Nancy (2)900andDemand:
    • 7. Transportation ModelAutoPower must decide how many motors to send from each harbor (supply) to each plant (demand). The cost ($, on a per motor basis) of shipping is given below. TO DESTINATION Leipzig Nancy Liege Tilburg FROM ORIGIN (1) (2) (3) (4) (A) Amsterdam 120 130 41 59.50 (B) Antwerp 61 40 100 110 (C) Le Havre 102.50 90 122 42
    • 8. 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 Destination j):Transportation Model
    • 9. TO DESTINATION FROM ORIGIN 1 2 3 4 A 120xA1 130xA2 41xA3 59.50xA4 B 61xB1 40xB2 100xB3 110xB4 C 102.50xC1 90xC2 122xC3 42xC4Total Transportation Cost = 120xA1 + 130xA2 + 41xA3 + … + 122xC3 + 42xC4Transportation Model
    • 10. 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: We could have used an “=“ instead of “<“ since supply and demand are balanced for this model. Transportation Model
    • 11. 2. Demand at each plant must be satisfied. For Leipzig: xA1 + xB1 + xC1 > 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 ModelTwo general types of constraints.
    • 12. Variations on the Transportation ModelSuppose 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 Transportation Models
    • 13. 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 DifferIn this case, when all demand is satisfied, the remaining 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 Model
    • 14. In this case, the LP model has no feasible solution. However, 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 Transportation Model
    • 15. 2. 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 supplying 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 Model
    • 16. Certain routes in a transportation model may be unacceptable due to regional restrictions, delivery time, etc.In this case, 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 RoutesChoose M such that it will be larger than any other unit cost number in the model.Variations on the Transportation Model
    • 17. Generally, LP models do not produce integer solutions. The exception to this is the Transportation model. In general: Integer Valued SolutionsIf all of the supplies and demands in a transportation model have integer values, the optimal values of the decision variables will also have integer values.Variations on the Transportation Model
    • 18. Assignment 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 representatives to service callsCommercial artists to advertising copyThe important constraint is that each person or machine be assigned to one and only one task.
    • 19. We will use the AutoPower example to illustrate Assignment problems.AutoPower Europe’s Auditing ProblemAutoPower’s 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, BelgiumNancy, FranceTilburg, the NetherlandsAssignment Model
    • 20. The 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 demands on each vice- president during the two-week interval.3. Matching the language ability of a vice- president with the plant’s dominant language.Keeping these issues in mind, first estimate the (opportunity) cost to AutoPower of sending each vice-president to each plant.Assignment Model
    • 21. The following table lists the assignment costs in $000s for every vice-president/plant combination. PLANT Leipzig Nancy Liege Tilburg V.P. (1) (2) (3) (4) Finance (F) 24 10 21 11 Marketing (M) 14 22 10 15 Operations (O) 15 17 20 19 Personnel (P) 11 19 14 13 Assignment Model
    • 22. PLANT Leipzig Nancy Liege Tilburg V.P. (1) (2) (3) (4) Finance (F) 24 10 21 11 Marketing (M) 14 22 10 15 Operations (O) 15 17 20 19 Personnel (P) 11 19 14 13 Consider the following assignment:Total cost = 24 + 22 + 20 + 13 = 79 The question is, is this the least cost assignment?Assignment Model
    • 23. Complete 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 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 Model
    • 24. 1. F can be assigned to any of the 4 plants.2. Once F is assigned, M can be assigned to any 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 increases, n! increases rapidly. Therefore, this may not be the best method.Assignment Model
    • 25. For this model, let xij = number of V.P’s of type i assigned to plant j where i = F, M, O, P j = 1, 2, 3, 4The LP Formulation and SolutionNotice that this model is balanced since the total number of V.P.’s is equal to the total number of plants.Remember, only one V.P. (supply) is needed at each plant (demand).Assignment Model
    • 26. As a result, the optimal assignment is: PLANT Leipzig Nancy Liege Tilburg V.P. (1) (2) (3) (4) Finance (F) 24 10 21 11 Marketing (M) 14 22 10 15 Operations (O) 15 17 20 19 Personnel (P) 11 19 14 13 Total Cost ($000’s) = 10 + 10 + 15 + 13 = 48Assignment Model
    • 27. The Assignment model is similar to the Transportation model with the exception that supply cannot be distributed to more than one destination.Relation 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 as a transportation model in which the supply at each origin and the demand at each destination = 1.Assignment Model
    • 28. Case 1: Supply Exceeds DemandUnequal 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: PLANT NUMBER OF V.P.s V.P. 1 2 3 AVAILABLE F 24 10 21 1 M 14 22 10 1 O 15 17 20 1 P 11 19 14 1 No. of V.P.s 4 Required 1 1 1 3 Assignment Model
    • 29. To formulate this model, simply drop the constraint that required a V.P. at plant 4 and solve it.Assignment ModelUnequal Supply and Demand:
    • 30. Case 2: Demand Exceeds SupplyUnequal 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: PLANT NUMBER OF V.P.s V.P. 1 2 3 4 AVAILABLE F 24 10 21 11 1 M 14 22 10 15 1 O 15 17 20 19 1 No. of V.P.s 3 Required 1 1 1 1 4 Assignment Model
    • 31. 1. 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). PLANT NUMBER OF V.P.s V.P. 1 2 3 4 AVAILABLE F 24 10 21 11 1 M 14 22 10 15 1 O 15 17 20 19 1 Dummy 0 0 0 0 1 No. of V.P.s 4 Required 1 1 1 1 4 Zero cost to assign the dummyDummy supply; now supply = demandAssignment Model
    • 32. In the solution, the dummy V.P. would be assigned to a plant. In reality, this plant would not be audited.Assignment ModelUnequal Supply and Demand:
    • 33. In this Assignment model, the response from each assignment is a profit rather than a cost. Maximization ModelsFor example, AutoPower must now assign four new salespeople to three territories in order to maximize profit. The effect of assigning any salesperson to a territory is measured by the anticipated marginal increase in profit contribution due to the assignment. Assignment Model
    • 34. Here is the profit matrix for this model. NUMBER OF TERRITORY SALESPEOPLE SALESPERSON 1 2 3 AVAILABLE A 40 30 20 1 B 18 28 22 1 C 12 16 20 1 D 25 24 27 1 No. of 4 Salespeople 1 1 1 3 Required This value represents the profit contribution if A is assigned to Territory 3.Assignment Model
    • 35. The Assignment ModelCertain assignments in the model may be unacceptable for various reasons. Situations 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 assignment since, for example, the cost of making that assignment would be much larger than that of any other feasible alternative. Assignment Model
    • 36. Network ModelsTransportation and assignment models are members of a more general class of models called network models. Network models involve from-to sources and destinations.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, …
    • 37. Zigwell Inc. is AutoPower’s largest US distributor of UPS generators in five Midwestern states. Network ModelsA Capacitated Transshipment ModelZigwell has 10 BigGen’s at site 1These generators must be delivered to construction sites in two cities denoted and 343 BigGen’s are required at site and 7 are required at site 34Network Models
    • 38. 1+102543-3-7This is a network diagram or network flow diagram. Each arrow is called an arc or branch. Each site is termed a node.SupplyDemandNetwork Models
    • 39. cij the costs (per unit) of traversing the routesuij the capacities along the routesCosts 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.Because 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 Models
    • 40. 1+102543-3-7c12c23c24c25c34c43c53u12u23u24u25u34u43u53Network Models
    • 41. LP Formulation of the ModelNetwork ModelsA Capacitated Transshipment ModelThe goal is to find a shipment plan that satisfies the demands at minimum cost, subject to the capacity constraints.The capacitated transshipment model is basically identical to the transportation model except that:1. Any plant or warehouse can ship to any other plant or warehouse2. There can be upper and/or lower bounds (capacities) on each shipment (branch)Network Models
    • 42. The decision variables are:xij = total number of BigGen’s sent on arc (i, j) = flow from node i to node jThe model becomes:Min c12x12 + c23x23 + c24x24 + c25x25 + c34x34 + c43x43 + c53x53 + c54x54s.t.+x12 = 10-x12 + x23 + x24 + x25 = 0-x23 – x43 – x53 + x34 = -3 -x24 + x43 – x34 – x54 = -7 -x25 + x53 + x54 = 0 0 < xij < uij all arcs (i, j) in the network
    • 43. Properties of the Model1. xij is associated with each of the 8 arcs in the network. Therefore, there are 8 corresponding variables: x12, x23, x24, x25, x34, x43, x53, and x54 The objective is to minimize total cost.2. There is one material flow balance equation associated with each node in the network. For example:Total flow out of node is 10 units1Total flow out of node minus the total flow into node is zero (i.e., total flow out must equal total flow into node ).222Total flow out of node must be 3 units less than the total flow into node .33
    • 44. Intermediate nodes that are neither supply points nor demand points are often termed transshipment nodes.3. The positive right-hand sides correspond to nodes that are net suppliers (origins). The sum of all right-hand-side terms is zero (i.e., total supply in the network equals total demand).The zero right-hand sides correspond to nodes that have neither supply nor demand.The negative right-hand sides correspond to nodes that are net destinations.
    • 45. In general, flow balance for a given node, j, is:Total flow out of node j – total flow into node j = supply at node jNegative supply is a requirement. Nodes with negative supply are called destinations, sinks, or demand points.Nodes with positive supply are called origins, sources, or supply points.Nodes with zero supply are called transshipment points.4. A small model can be optimized with Solver.
    • 46. Integer Optimal SolutionsNetwork ModelsA Capacitated Transshipment ModelThe integer property of the network model can be stated thus:If all the RHS terms and arc capacities, uij, are integers in the capacitated transshipment model, there will always be an integer-valued optimal solution to this model.Network Models
    • 47. The structure of this model makes it possible to apply special solution methods and software that optimize the model much more quickly than the more general simplex method used by Solver.Efficient Solution ProceduresNetwork ModelsA Capacitated Transshipment ModelThis makes it possible to optimize very large scale network models quickly and cheaply.Network Models
    • 48. The shortest-route model refers to a network for which each arc (i,j) has an associated number, cij, which is interpreted as the distance (or cost, or time) from node i to node j.Network ModelsA Shortest-Route ModelA route or path between two nodes is any sequence of arcs connecting the two nodes.The objective is to find the shortest (or least-cost or least-time) routes from a specific node to each of the other nodes in the network.Network Models
    • 49. In this example, Aaron Drunner makes frequent wine deliveries to 7 different sites:874H12347651611213323Note that the arcs are undirected (flow is permitted in either direction).Distance between nodes.Home Base
    • 50. The goal is to minimize overall costs by making sure that any future delivery to any given site is made along the shortest route to that site.The goal is to minimize overall costs by finding the shortest route from node H to any of the other 7 nodes. Note that in this model, the task is to find an optimal route, not optimal xij’s.Network Models
    • 51. In this example, Michael Carr is responsible for obtaining a high speed printing press for his newspaper company. Network ModelsAn Equipment Replacement ModelIn a given year he must choose between purchasing:New Printing PressOld Printing Presshigh annual acquisition costlow initial maintenance costno annual acquisition costhigh initial maintenance costNetwork Models
    • 52. Assume a 4-year time horizon. Let:cij denote the cost of buying new equipment at the beginning of year i, i = 1, 2, 3, 4 and maintaining it to the beginning of year j, j = 2, 3, 4, 5Three alternative feasible policies are:1. Buying new equipment at the beginning of each year. Total (acquisition + maintenance) cost = c12 + c23 + c34 + c452. Buy new equipment only at the beginning of year 1 and maintain it through all successive years. Total (buying + maintenance) cost = c15
    • 53. 3. Buy new equipment at the beginning of years 1 and 4. Total cost = c14 + c45The solution to this model is obtained by finding the shortest (i.e., minimum cost) route from node 1 to node 5 of the network.Each node on the shortest route denotes a replacement, that is, a year at which new equipment should be bought.
    • 54. Here is the network model for this problem.Assume the following costs:$1,600,000 purchase cost$500,000 maintenance cost in purchase year$1,000,000, $1,500,000, and $2,200,000 for each additional year the equipment is kept12345c12c23c34c45c13c14c15c24c25c35
    • 55. In the maximal-flow model, there is a single source node (the input node) and a single sink node (the output node).Network ModelsA Maximal Flow ModelThe goal is to find the maximum amount of total flow that can be routed through a physical network (from source to sink) in a unit of time.The amount of flow per unit time on each arc is limited by capacity restrictions.The only requirement is that for each node (other than the source or the sink):flow out of the node = flow into the nodeNetwork Models
    • 56. The UDPC (Urban Development Planning Commission) is an ad hoc special interest study group.An Application of Maximal-Flow: The Urban Development Planning CommissionNetwork ModelsA Maximal Flow ModelThe group’s current responsibility is to coordinate the construction of the new subway system with the state’s highway maintenance department.Because the new subway system is being built near the city’s beltway, the eastbound traffic on the beltway must be detoured.Network Models
    • 57. The proposed network of alternative routes and the different speed limits and traffic patterns (producing different flow capacities) are given below:154326406003402060016002Detour BeginsDetour EndsIndicates a capacity of 6000 vehicles per hour in the direction of the arrow.Indicates 0 capacity in the direction of the arrow.
    • 58. Translating the Excel solution to the original network diagram gives the following traffic pattern:154326442266288