管理科学07流通网络模型

《管理科学07流通网络模型》由会员分享，可在线阅读，更多相关《管理科学07流通网络模型（50页珍藏版）》请在装配图网上搜索。

1、Chapter 7Network Flow ModelsIntroduction to Management Science8th EditionbyBernard W.Taylor III1Chapter 7-Network Flow ModelsChapter TopicsThe Minimum Cost Network Flow ProblemThe Shortest Route ProblemThe Minimal Spanning Tree ProblemThe Maximal Flow Problem2Chapter 7-Network Flow ModelsOverviewA n

2、etwork is an arrangement of paths connected at various points through which one or more items move from one point to another.The network is drawn as a diagram providing a picture of the system thus enabling visual interpretation and enhanced understanding.A large number of real-life systems can be m

3、odeled as networks which are relatively easy to conceive and construct.3Chapter 7-Network Flow ModelsNetwork diagrams consist of nodes and branches.Nodes(circles),represent junction points,or locations.Branches(lines,Arcs),connect nodes and represent flow.Paths,a set of branches connecting two nodes

4、Network Components(1 of 3)4Chapter 7-Network Flow ModelsFigure 7.1Network of Railroad RoutesFour nodes,four branches in figure.“Atlanta”,node 1,termed origin,any of others destination.Branches identified by beginning and ending node numbers.Value assigned to each branch(distance,time,cost,etc.).Netw

5、ork Components(2 of 3)5Chapter 7-Network Flow ModelsNetwork Concepts(3/3)Flow:the quantity routing through a branchCapacity:the max flow on a branch per unit timeSource node(Origin node)Destination node(Sink node)Supply node:flow in flow outTransshipment node:flow in=flow out6Chapter 7-Network Flow

6、ModelsProblem:Determine the shortest routes from the origin to all destinations.Figure 7.2Shipping Routes from Los AngelesThe Shortest Route ProblemDefinition and Example Problem Data(1 of 2)7Chapter 7-Network Flow ModelsFigure 7.3Network of Shipping RoutesThe Shortest Route ProblemDefinition and Ex

7、ample Problem Data(2 of 2)8Chapter 7-Network Flow ModelsFigure 7.4Network with Node 1 in the Permanent SetThe Shortest Route ProblemSolution Approach(1 of 8)Determine the initial shortest route from the origin(node 1)to the closest node(3).9Chapter 7-Network Flow ModelsFigure 7.5Network with Nodes 1

8、 and 3 in the Permanent SetThe Shortest Route ProblemSolution Approach(2 of 8)Determine all nodes directly connected to the permanent set.10Chapter 7-Network Flow ModelsFigure 7.6Network with Nodes 1,2,and 3 in the Permanent SetRedefine the permanent set.The Shortest Route ProblemSolution Approach(3

9、 of 8)11Chapter 7-Network Flow ModelsFigure 7.7Network with Nodes 1,2,3,and 4 in the Permanent SetThe Shortest Route ProblemSolution Approach(4 of 8)Continue12Chapter 7-Network Flow ModelsThe Shortest Route ProblemSolution Approach(5 of 8)Figure 7.8Network with Nodes 1,2,3,4,and 6 in the Permanent S

10、etContinue13Chapter 7-Network Flow ModelsThe Shortest Route ProblemSolution Approach(6 of 8)Figure 7.9Network with Nodes 1,2,3,4,5,and 6 in the Permanent SetContinue14Chapter 7-Network Flow ModelsThe Shortest Route ProblemSolution Approach(7 of 8)Figure 7.10Network with Optimal Routes from Los Angel

11、es to All DestinationsOptimal Solution15Chapter 7-Network Flow ModelsTable 7.1Shortest Travel Time from Origin to Each DestinationThe Shortest Route ProblemSolution Approach(8 of 8)Solution Summary16Chapter 7-Network Flow ModelsThe Shortest Route ProblemSolution Method SummarySelect the node with th

12、e shortest direct route from the origin.Establish a permanent set with the origin node and the node that was selected in step 1.Determine all nodes directly connected to the permanent set nodes.Select the node with the shortest route(branch)from the group of nodes directly connected to the permanent

13、 set nodes.Repeat steps 3 and 4 until all nodes have joined the permanent set.17Chapter 7-Network Flow ModelsThe Shortest Route ProblemComputer Solution with QM for Windows(1 of 2)Exhibit 7.118Chapter 7-Network Flow ModelsThe Shortest Route ProblemComputer Solution with QM for Windows(2 of 2)Exhibit

14、 7.219Chapter 7-Network Flow ModelsFormulation as a 0-1 integer linear programming problem.xij=0 if branch i-j is not selected as part of the shortest route and 1 if it is selected.Minimize Z=16x12+9x13+35x14+12x24+25x25+15x34+22x36+14x45+17x46+19x47+8x57+14x67subject to:x12+x13+x14=1x12-x24-x25=0 x

15、13-x34-x36=0 x14+x24+x34-x45-x46-x47=0 x25+x45-x57=0 x36+x46-x67=0 x47+x57+x67=1 xij=0 or 1 The Shortest Route ProblemComputer Solution with Excel(1 of 4)20Chapter 7-Network Flow ModelsExhibit 7.3The Shortest Route ProblemComputer Solution with Excel(2 of 4)21Chapter 7-Network Flow ModelsExhibit 7.4

16、The Shortest Route ProblemComputer Solution with Excel(3 of 4)22Chapter 7-Network Flow ModelsExhibit 7.5The Shortest Route ProblemComputer Solution with Excel(4 of 4)23Chapter 7-Network Flow ModelsFigure 7.11Network of Possible Cable TV PathsThe Minimal Spanning Tree ProblemDefinition and Example Pr

17、oblem DataProblem:Connect all nodes in a network so that the total branch lengths are minimized.24Chapter 7-Network Flow ModelsThe Minimal Spanning Tree ProblemSolution Approach(1 of 6)Figure 7.12Spanning Tree with Nodes 1 and 3Start with any node in the network and select the closest node to join t

18、he spanning tree.25Chapter 7-Network Flow ModelsThe Minimal Spanning Tree ProblemSolution Approach(2 of 6)Figure 7.13Spanning Tree with Nodes 1,3,and 4Select the closest node not presently in the spanning area.26Chapter 7-Network Flow ModelsThe Minimal Spanning Tree ProblemSolution Approach(3 of 6)F

19、igure 7.14Spanning Tree with Nodes 1,2,3,and 4Continue27Chapter 7-Network Flow ModelsThe Minimal Spanning Tree ProblemSolution Approach(4 of 6)Figure 7.15Spanning Tree with Nodes 1,2,3,4,and 5Continue28Chapter 7-Network Flow ModelsThe Minimal Spanning Tree ProblemSolution Approach(5 of 6)Figure 7.16

20、Spanning Tree with Nodes 1,2,3,4,5,and 7Continue29Chapter 7-Network Flow ModelsThe Minimal Spanning Tree ProblemSolution Approach(6 of 6)Figure 7.17Minimal Spanning Tree for Cable TV NetworkOptimal Solution30Chapter 7-Network Flow ModelsThe Minimal Spanning Tree ProblemSolution Method SummarySelect

21、any starting node(conventionally,node 1).Select the node closest to the starting node to join the spanning tree.Select the closest node not presently in the spanning tree.Repeat step 3 until all nodes have joined the spanning tree.31Chapter 7-Network Flow ModelsThe Minimal Spanning Tree ProblemCompu

22、ter Solution with QM for WindowsExhibit 7.632Chapter 7-Network Flow ModelsFigure 7.18Network of Railway SystemThe Maximal Flow ProblemDefinition and Example Problem DataProblem:Maximize the amount of flow of items from an origin to a destination.33Chapter 7-Network Flow ModelsFigure 7.19Maximal Flow

23、 for Path 1-2-5-6The Maximal Flow ProblemSolution Approach(1 of 5)Arbitrarily choose any path through the network from origin to destination and ship as much as possible.34Chapter 7-Network Flow ModelsFigure 7.20Maximal Flow for Path 1-4-6The Maximal Flow ProblemSolution Approach(2 of 5)Re-compute b

24、ranch flow in both directions and then select other feasible paths arbitrarily and determine maximum flow along the paths until flow is no longer possible.35Chapter 7-Network Flow ModelsFigure 7.21Maximal Flow for Path 1-3-6The Maximal Flow ProblemSolution Approach(3 of 5)Continue36Chapter 7-Network

25、 Flow ModelsFigure 7.22Maximal Flow for Path 1-3-4-6The Maximal Flow ProblemSolution Approach(4 of 5)Continue37Chapter 7-Network Flow ModelsFigure 7.23Maximal Flow for Railway NetworkThe Maximal Flow ProblemSolution Approach(5 of 5)Optimal Solution38Chapter 7-Network Flow ModelsThe Maximal Flow Prob

26、lemSolution Method SummaryArbitrarily select any path in the network from origin to destination.Adjust the capacities at each node by subtracting the maximal flow for the path selected in step 1.Add the maximal flow along the path to the flow in the opposite direction at each node.Repeat steps 1,2,a

27、nd 3 until there are no more paths with available flow capacity.39Chapter 7-Network Flow ModelsThe Maximal Flow ProblemComputer Solution with QM for WindowsExhibit 7.740Chapter 7-Network Flow Modelsiij=flow along branch i-j and integerMaximize Z=x61subject to:x61-x12-x13-x14=0 x12-x24-x25=0 x12-x34-

28、x36=0 x14+x24+x25-x46=0 x25-x56=0 x36+x46+x56-x61=0 x12 6 x24 3 x34 2 x13 7 x25 8 x36 6 x14 4 x46 5x56 4 x61 17 xij 0The Maximal Flow ProblemComputer Solution with Excel(1 of 4)41Chapter 7-Network Flow ModelsThe Maximal Flow ProblemComputer Solution with Excel(2 of 4)Exhibit 7.842Chapter 7-Network F

29、low ModelsThe Maximal Flow ProblemComputer Solution with Excel(3 of 4)Exhibit 7.943Chapter 7-Network Flow ModelsThe Maximal Flow ProblemComputer Solution with Excel(4 of 4)Exhibit 7.1044Chapter 7-Network Flow ModelsThe Maximal Flow ProblemExample Problem Statement and Data(1 of 2)Determine the short

30、est route from Atlanta(node 1)to each of the other five nodes(branches show travel time between nodes).Assume branches show distance(instead of travel time)between nodes,develop a minimal spanning tree.45Chapter 7-Network Flow ModelsThe Maximal Flow ProblemExample Problem Statement and Data(2 of 2)4

31、6Chapter 7-Network Flow ModelsStep 1(part A):Determine the Shortest Route Solution1.Permanent Set Branch Time1 1-25 1-35 1-4 72.1,2 1-35 1-47 2-5113.1,2,3 1-47 2-511 3-474.1,2,3,4 4-510 4-695.1,2,3,4,6 4-510 6-5136.1,2,3,4,5,6The Maximal Flow ProblemExample Problem,Shortest Route Solution(1 of 2)47C

32、hapter 7-Network Flow ModelsThe Maximal Flow ProblemExample Problem,Shortest Route Solution(2 of 2)48Chapter 7-Network Flow ModelsThe Maximal Flow ProblemExample Problem,Minimal Spanning Tree(1 of 2)The closest unconnected node to node 1 is node 2.The closest to 1 and 2 is node 3.The closest to 1,2,and 3 is node 4.The closest to 1,2,3,and 4 is node 6.The closest to 1,2,3,4 and 6 is 5.The shortest total distance is 17 miles.49Chapter 7-Network Flow ModelsThe Maximal Flow ProblemExample Problem,Minimal Spanning Tree(2 of 2)50Chapter 7-Network Flow Models