運籌學與供應鏈管理-第5講.ppt

第五讲 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 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).,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 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:,Demand,Supply,Assembly 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 2000,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 motor 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 Destination 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: We could have used an “=“ instead of “ since supply and demand are balanced for this model.,Transportation Model,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 Model,Two general types of constraints.,Variations 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 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 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:,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 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,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 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,If 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,Assignment Model,In 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 assign,Salespeople to sales territories,Computers to networks,Consultants to clients,Service representatives to service calls,Commercial artists to advertising copy,The important constraint is that each person or machine be assigned to one and only one task.,We will use the AutoPower example to illustrate Assignment problems.,AutoPower Europes Auditing Problem,AutoPowers 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, Germany,Liege, Belgium,Nancy, France,Tilburg, the Netherlands,Assignment Model,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 plants dominant language.,Keeping these issues in mind, first estimate the (opportunity) cost to AutoPower of sending each vice-president to each plant.,Assignment Model,The following table lists the assignment costs in $000s for every vice-president/plant combination.,Assignment Model,Consider the following assignment:,Assignment Model,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 Enumeration,This 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,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,For this model, let xij = number of V.Ps of type i assigned to plant j where i = F, M, O, P j = 1, 2, 3, 4,The LP Formulation and Solution,Notice 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,As a result, the optimal assignment is:,Total Cost ($000s) = 10 + 10 + 15 + 13 = 48,Assignment Model,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 Model,In 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,Case 1: Supply Exceeds 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:,Assignment Model,To formulate this model, simply drop the constraint that required a V.P. at plant 4 and solve it.,Assignment Model,Unequal Supply and Demand:,Case 2: Demand Exceeds Supply,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:,Assignment Model,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).,Assignment Model,In the solution, the dummy V.P. would be assigned to a plant. In reality, this plant would not be audited.,Assignment Model,Unequal Supply and Demand:,In this Assignment model, the response from each assignment is a profit rather than a cost.,Maximization Models,For 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,Here is the profit matrix for this model.,Assignment Model,The Assignment Model,Certain assignments in the model may be unacceptable for various reasons.,Situations with Unacceptable Assignments,In 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,Network Models,Transportation 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, ,Zigwell Inc. is AutoPowers largest US distributor of UPS generators in five Midwestern states.,Network Models,A Capacitated Transshipment Model,Network Models,This is a network diagram or network flow diagram.,Each arrow is called an arc or branch. Each site is termed a node.,Network Models,cij the costs (per unit) of traversing the routes,uij the capacities along the routes,Costs 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,Network Models,LP Formulation of the Model,Network Models,A Capacitated Transshipment Model,The 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 warehouse,2. There can be upper and/or lower bounds (capacities) on each shipment (branch),Network Models,The decision variables are:,xij = total number of BigGens sent on arc (i, j) = flow from node i to node j,The model becomes:,Min c12x12 + c23x23 + c24x24 + c25x25 + c34x34 + c43x43 + c53x53 + c54x54,s.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,Properties of the Model,1. 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:,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.,In general, flow balance for a given node, j, is:,Total flow out of node j total flow into node j = supply at node j,Negative 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.,Integer Optimal Solutions,Network Models,A Capacitated Transshipment Model,The 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,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 Procedures,Network Models,A Capacitated Transshipment Model,This makes it possible to optimize very large scale network models quickly and cheaply.,Network Models,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 Models,A Shortest-Route Model,A 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,In this example, Aaron Drunner makes frequent wine deliveries to 7 different sites:,Note that the arcs are undirected (flow is permitted in either direction).,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 xijs.,Network Models,In this example, Michael Carr is responsible for obtaining a high speed printing press for his newspaper company.,Network Models,An Equipment Replacement Model,In a given year he must choose between purchasing:,New Printing Press,Old Printing Press,high annual acquisition cost,low initial maintenance cost,no annual acquisition cost,high initial maintenance cost,Network Models,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, 5,Three alternative feasible policies are:,1. Buying new equipment at the beginning of each year.,Total (acquisition + maintenance) cost = c12 + c23 + c34 + c45,2. Buy new equipment only at the beginning of year 1 and maintain it through all successive years.,Total (buying + maintenance) cost = c15,3. Buy ne