




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、Chapter 7 - Network Flow Models,1,Chapter 7 Network Flow Models,Introduction to Management Science 8th Edition by Bernard W. Taylor III,Chapter 7 - Network Flow Models,2,Chapter Topics,The Minimum Cost Network Flow Problem The Shortest Route Problem The Minimal Spanning Tree Problem The Maximal Flow
2、 Problem,Chapter 7 - Network Flow Models,3,Overview,A network 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 un
3、derstanding. A large number of real-life systems can be modeled as networks which are relatively easy to conceive and construct.,Chapter 7 - Network Flow Models,4,Network diagrams consist of nodes and branches. Nodes (circles), represent junction points, or locations. Branches (lines, Arcs), connect
4、 nodes and represent flow. Paths, a set of branches connecting two nodes,Network Components (1 of 3),Chapter 7 - Network Flow Models,5,Figure 7.1 Network of Railroad Routes,Four nodes, four branches in figure. “Atlanta”, node 1, termed origin, any of others destination. Branches identified by beginn
5、ing and ending node numbers. Value assigned to each branch (distance, time, cost, etc.).,Network Components (2 of 3),Chapter 7 - Network Flow Models,6,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) Destina
6、tion node (Sink node) Supply node: flow in flow out Transshipment node: flow in = flow out,Chapter 7 - Network Flow Models,7,Problem: Determine the shortest routes from the origin to all destinations.,Figure 7.2 Shipping Routes from Los Angeles,The Shortest Route Problem Definition and Example Probl
7、em Data (1 of 2),Chapter 7 - Network Flow Models,8,Figure 7.3 Network of Shipping Routes,The Shortest Route Problem Definition and Example Problem Data (2 of 2),Chapter 7 - Network Flow Models,9,Figure 7.4 Network with Node 1 in the Permanent Set,The Shortest Route Problem Solution Approach (1 of 8)
8、,Determine the initial shortest route from the origin (node 1) to the closest node (3).,Chapter 7 - Network Flow Models,10,Figure 7.5 Network with Nodes 1 and 3 in the Permanent Set,The Shortest Route Problem Solution Approach (2 of 8),Determine all nodes directly connected to the permanent set.,Cha
9、pter 7 - Network Flow Models,11,Figure 7.6 Network with Nodes 1, 2, and 3 in the Permanent Set,Redefine the permanent set.,The Shortest Route Problem Solution Approach (3 of 8),Chapter 7 - Network Flow Models,12,Figure 7.7 Network with Nodes 1, 2, 3, and 4 in the Permanent Set,The Shortest Route Pro
10、blem Solution Approach (4 of 8),Continue,Chapter 7 - Network Flow Models,13,The Shortest Route Problem Solution Approach (5 of 8),Figure 7.8 Network with Nodes 1, 2, 3, 4, and 6 in the Permanent Set,Continue,Chapter 7 - Network Flow Models,14,The Shortest Route Problem Solution Approach (6 of 8),Fig
11、ure 7.9 Network with Nodes 1, 2, 3, 4, 5, and 6 in the Permanent Set,Continue,Chapter 7 - Network Flow Models,15,The Shortest Route Problem Solution Approach (7 of 8),Figure 7.10 Network with Optimal Routes from Los Angeles to All Destinations,Optimal Solution,Chapter 7 - Network Flow Models,16,Tabl
12、e 7.1 Shortest Travel Time from Origin to Each Destination,The Shortest Route Problem Solution Approach (8 of 8),Solution Summary,Chapter 7 - Network Flow Models,17,The Shortest Route Problem Solution Method Summary,Select the node with the shortest direct route from the origin. Establish a permanen
13、t 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 set nodes. Repeat steps 3 and 4 until all nodes have jo
14、ined the permanent set.,Chapter 7 - Network Flow Models,18,The Shortest Route Problem Computer Solution with QM for Windows (1 of 2),Exhibit 7.1,Chapter 7 - Network Flow Models,19,The Shortest Route Problem Computer Solution with QM for Windows (2 of 2),Exhibit 7.2,Chapter 7 - Network Flow Models,20
15、,Formulation 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 + 14x67 subject to: x12 + x13 + x14= 1 x12 - x24 -
16、 x25 = 0 x13 - 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 Problem Computer Solution with Excel (1 of 4),Chapter 7 - Network Flow Models,21,Exhibit 7.3,The Shortest Route Problem Computer Solution wit
17、h Excel (2 of 4),Chapter 7 - Network Flow Models,22,Exhibit 7.4,The Shortest Route Problem Computer Solution with Excel (3 of 4),Chapter 7 - Network Flow Models,23,Exhibit 7.5,The Shortest Route Problem Computer Solution with Excel (4 of 4),Chapter 7 - Network Flow Models,24,Figure 7.11 Network of P
18、ossible Cable TV Paths,The Minimal Spanning Tree Problem Definition and Example Problem Data,Problem: Connect all nodes in a network so that the total branch lengths are minimized.,Chapter 7 - Network Flow Models,25,The Minimal Spanning Tree Problem Solution Approach (1 of 6),Figure 7.12 Spanning Tr
19、ee with Nodes 1 and 3,Start with any node in the network and select the closest node to join the spanning tree.,Chapter 7 - Network Flow Models,26,The Minimal Spanning Tree Problem Solution Approach (2 of 6),Figure 7.13 Spanning Tree with Nodes 1, 3, and 4,Select the closest node not presently in th
20、e spanning area.,Chapter 7 - Network Flow Models,27,The Minimal Spanning Tree Problem Solution Approach (3 of 6),Figure 7.14 Spanning Tree with Nodes 1, 2, 3, and 4,Continue,Chapter 7 - Network Flow Models,28,The Minimal Spanning Tree Problem Solution Approach (4 of 6),Figure 7.15 Spanning Tree with
21、 Nodes 1, 2, 3, 4, and 5,Continue,Chapter 7 - Network Flow Models,29,The Minimal Spanning Tree Problem Solution Approach (5 of 6),Figure 7.16 Spanning Tree with Nodes 1, 2, 3, 4, 5, and 7,Continue,Chapter 7 - Network Flow Models,30,The Minimal Spanning Tree Problem Solution Approach (6 of 6),Figure
22、7.17 Minimal Spanning Tree for Cable TV Network,Optimal Solution,Chapter 7 - Network Flow Models,31,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
23、node not presently in the spanning tree. Repeat step 3 until all nodes have joined the spanning tree.,Chapter 7 - Network Flow Models,32,The Minimal Spanning Tree Problem Computer Solution with QM for Windows,Exhibit 7.6,Chapter 7 - Network Flow Models,33,Figure 7.18 Network of Railway System,The Ma
24、ximal Flow Problem Definition and Example Problem Data,Problem: Maximize the amount of flow of items from an origin to a destination.,Chapter 7 - Network Flow Models,34,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 t
25、he network from origin to destination and ship as much as possible.,Chapter 7 - Network Flow Models,35,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
26、maximum flow along the paths until flow is no longer possible.,Chapter 7 - Network Flow Models,36,Figure 7.21 Maximal Flow for Path 1-3-6,The Maximal Flow Problem Solution Approach (3 of 5),Continue,Chapter 7 - Network Flow Models,37,Figure 7.22 Maximal Flow for Path 1-3-4-6,The Maximal Flow Problem
27、 Solution Approach (4 of 5),Continue,Chapter 7 - Network Flow Models,38,Figure 7.23 Maximal Flow for Railway Network,The Maximal Flow Problem Solution Approach (5 of 5),Optimal Solution,Chapter 7 - Network Flow Models,39,The Maximal Flow Problem Solution Method Summary,Arbitrarily select any path in
28、 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 more paths with available f
29、low capacity.,Chapter 7 - Network Flow Models,40,The Maximal Flow Problem Computer Solution with QM for Windows,Exhibit 7.7,Chapter 7 - Network Flow Models,41,iij = flow along branch i-j and integer Maximize Z = x61 subject to: x61 - x12 - x13 - x14 = 0 x12 - x24 - x25 = 0 x12 - x34 - x36 = 0 x14 +
30、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 0,The Maximal Flow Problem Computer Solution with Excel (1 of 4),Chapter 7 - Network Flow Models,42,The Maximal Flow Problem Computer Solution with Excel (2 of 4),Exhibit 7.8,C
31、hapter 7 - Network Flow Models,43,The Maximal Flow Problem Computer Solution with Excel (3 of 4),Exhibit 7.9,Chapter 7 - Network Flow Models,44,The Maximal Flow Problem Computer Solution with Excel (4 of 4),Exhibit 7.10,Chapter 7 - Network Flow Models,45,The Maximal Flow Problem Example Problem Statement and Data (1 of 2),Determine the shortest route from Atlanta (node 1) to each of the other five nodes (branches show travel time between nodes). Assume branches show distance (instead of t
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 北京市装修工程奖惩合同
- 固定木桩采购合同范本
- 圆形货架采购合同范本
- 车位转让高价合同范本
- 福建个人租赁合同范本
- 肉羊屠宰收购合同范本
- 挖管道劳务合同范本
- 病句搭配不当30题及答案
- 2025合同法深度解析:合同终止的法定情形与协商解除
- 2025授权生产合同授权生产协议产品生产合同范本
- 2025陕西核工业工程勘察院有限公司招聘(21人)笔试参考题库附带答案详解
- 2025年山东、湖北部分重点中学高中毕业班第二次模拟考试数学试题含解析
- 8.2 诚信经营 依法纳税课件-高中政治统编版选择性必修二法律与生活
- 2025年超高功率大吨位电弧炉项目发展计划
- DB32T 5076-2025 奶牛规模化养殖设施设备配置技术规范
- 2024年四川省高等职业教育单独考试招生文化素质考试中职英语试卷
- 人教A版必修第二册高一(下)数学6.3.2-6.3.3平面向量正交分解及坐标表示【课件】
- 高速公路修补合同协议
- 航空业劳动力安全保障措施
- 《OCR技术及其应用》课件
- 2025年内科主治医师考试消化内科
评论
0/150
提交评论