transportationandnetworkmodels(英文版)-資料下載頁

　　

【正文】 always be an integervalued optimal solution to this model. 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 work models quickly and cheaply. The shortestroute model refers to a work 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 ShortestRoute 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 leastcost or leasttime) routes from a specific node to each of the other nodes in the work. In this example, Aaron Drunner makes frequent wine deliveries to 7 different sites: 8 7 4 H 1 2 3 4 7 6 5 1 6 1 1 2 1 3 3 2 3 Note that the arcs are undirected (flow is permitted in either direction). Distance between nodes. Home Base 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 In this example, Michael Carr is responsible for obtaining a high speed printing press for his newspaper pany. 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 Assume a 4year 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 new equipment at the beginning of years 1 and 4. Total cost = c14 + c45 The solution to this model is obtained by finding the shortest (., minimum cost) route from node 1 to node 5 of the work. Each node on the shortest route denotes a replacement, that is, a year at which new equipment should be bought. Here is the work 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 kept 1 2 3 4 5 c12 c23 c34 c45 c13 c14 c15 c24 c25 c35 In the maximalflow model, there is a single source node (the input node) and a single sink node (the output node). Network Models A Maximal Flow Model The goal is to find the maximum amount of total flow that can be routed through a physical work (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 node The UDPC (Urban Development Planning Commission) is an ad hoc special interest study group. An Application of MaximalFlow: The Urban Development Planning Commission Network Models A Maximal Flow Model The 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. The proposed work of alternative routes and the different speed limits and traffic patterns (producing different flow capacities) are given below: 1 5 4 3 2 6 4 0 6 0 0 3 4 0 2 0 6 0 0 1 6 0 0 2 Detour Begins Detour Ends Indicates a capacity of 6000 vehicles per hour in the direction of the arrow. Indicates 0 capacity in the direction of the arrow. Translating the Excel solution to the original work diagram gives the following traffic pattern: 1 5 4 3 2 6 4 4 2 2 6 6 2 8 8 演講完畢，謝謝觀看！