管理科学流通网络模型.ppt

Chapter 7 - Network Flow Models Network Concepts (3/3) Flow: the quantity routing through a branch Capacity: the max flow on a branch per unit time Source node (Origin node) Destination node (Sink node) Supply node: flow in flow out Demand node: flow in flow out Transshipment node: flow in = flow out The Minimal Spanning Tree Problem Solution Method Summary Select 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. The Minimal Spanning Tree Problem Computer Solution with QM for Windows Exhibit 7.6 Figure 7.18 Network of Railway System The Maximal Flow Problem Definition and Example Problem Data Problem: Maximize the amount of flow of items from an origin to a destination. Figure 7.19 Maximal Flow for Path 1-2-5-6 The Maximal Flow Problem Solution Approach (1 of 5) Arbitrarily choose any path through the network from origin to destination and ship as much as possible. Figure 7.20 Maximal Flow for Path 1-4-6 The Maximal Flow Problem Solution Approach (2 of 5) Re-compute branch flow in both directions and then select other feasible paths arbitrarily and determine maximum flow along the paths until flow is no longer possible. Figure 7.21 Maximal Flow for Path 1-3-6 The Maximal Flow Problem Solution Approach (3 of 5) Continue Figure 7.22 Maximal Flow for Path 1-3-4-6 The Maximal Flow Problem Solution Approach (4 of 5) Continue Figure 7.23 Maximal Flow for Railway Network The Maximal Flow Problem Solution Approach (5 of 5) Optimal Solution The Maximal Flow Problem Solution Method Summary Arbitrarily 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, and 3 until there are no mor