运筹学网络最优化问题PPT学习教案

1、会计学1 运筹学网络最优化问题运筹学网络最优化问题 第1页/共70页 第2页/共70页 点 连 线 （ 边 或 弧 ） 基 本 概 念 权 （ 赋 权 图 ） 网 络 图 最 小 费 用 流 问 题 最 大 流 问 题 网 络 最 优 化 问 题主 要 类 型最 短 路 问 题 最 小 支 撑 树 问 题 货 郎 担 问 题 和 中 国 邮 路 问 题 节 点 （ 供 应 点 、 转 运 点 、 需 求 点 ） 净 流 量 建 模 和 求 解 数 学 模 型 电 子 表 格 模 型 第3页/共70页 第4页/共70页 第5页/共70页 v1v3v5 v2v4v6 87 36 5 4 8 5 2

2、 1 对于该网络图，可以提出许多极值问题对于该网络图，可以提出许多极值问题 第6页/共70页 第7页/共70页 （6 6）邮递员从邮局）邮递员从邮局vi出发要经过出发要经过每每 一条边一条边将邮件送到用户手中，最后将邮件送到用户手中，最后 回到邮局回到邮局vi，如何安排路线使总路，如何安排路线使总路 程最短。这属于程最短。这属于中国邮递员问题中国邮递员问题。 第8页/共70页 第9页/共70页 和和指派问题指派问题，以及在下，以及在下 面将要提到的两种重要类型：面将要提到的两种重要类型：最最 大流问题大流问题和和最短路问题最短路问题。 第10页/共70页 （5050，400400 ） （505

3、0，200200 ） （5050，400400 ） （5050，300300 ） F1F1 F2F2 DCDC W2W2 W1W1 8080 7070 6060 9090 （无限制，（无限制，700700） （无限制，（无限制，900900） 第11页/共70页 第12页/共70页 第13页/共70页 第14页/共70页 第15页/共70页 1111 2222 Min z = 700300200 400900400 FWFDCDCW FDCFWDCW fff fff 第16页/共70页 1111 2222 111 222 1212 111 222 1 Min z = 700300200 400

4、900400 = 80 + = 70 () 0 s.t. = 60 90 , FWFDCDCW FDCFWDCW FWFDC FDCFW DCWDCWFDCFDC FWDCW DCWFW FDC fff fff ff ff ffff ff ff f 212 11112222 , , 50 ,0 FDCDCWDCW FWFDCDCWFDCFWDCW fff ffffff 第17页/共70页 第18页/共70页 第19页/共70页 第20页/共70页 总距离最短。总距离最短。 第21页/共70页 第22页/共70页 第23页/共70页 7070 8080 6060 4040 3030 5050 4

5、040 7070 5050 vsvs v1v1 v2v2 v3v3 v5v5 v4v4 vtvt 第24页/共70页 123 141 24252 353 41424 52535 Max F= = 0 ( ) 0 0 s.t ( ) 0 ( ) 0 0 vsvvsvvsv vvvsv vvvvvsv vvvsv vvtvvvv vvtvvvv ijij fff ff fff ff fff fff fc 第25页/共70页 第26页/共70页 第27页/共70页 7070 8080 4040 1010 2020 3030 5050 4040 6060 3030 4040 4040 7070 505

6、0 2020 6060 v1v1 v2v2 v3v3 v5v5 v4v4 vtvt p1p1 pspsptpt p2p2 vsvs 第28页/共70页 11123 1411 24252 353 44141424 52535 12 Max F= ( )0 ( ) 0 0 ( )( )0 s.t. ( )0 ( psppsvvsvvsvvsv vvvsvpsv vvvvvsv vvvsv vptvvtpvvvvv vvtvvvv ppp fffff fff fff ff fffff fff ff 141 2 212 )0 ( )0 0 vpsp pptpvtpp ijij f fff fc 第29

7、页/共70页 第30页/共70页 第31页/共70页 工程工程工期工期需要劳动力（人）需要劳动力（人） A.A.地下通道地下通道5 57 7月月100100 B.B.人行天桥人行天桥6 67 7月月8080 C.C.新建道路新建道路5 58 8月月200200 D.D.道路维修道路维修 8 8月月8080 第32页/共70页 第33页/共70页 S S 6 6 7 7 5 5 B6B6 A5A5 8 8 C5C5 A6A6 C6C6 A7A7 D8D8 C8C8 B7B7 C7C7 B B C C A A D D T T 120120 80808080 100100 8080 200200 8

8、080 注意：增加一个起点注意：增加一个起点 和一个终点，其和一个终点，其容量容量 是是供应量供应量和和需求量需求量 第34页/共70页 月份月份投入劳动力投入劳动力项目项目A A项目项目B B项目项目C C项目项目D D 5 510010020208080 6 612012040408080 7 712012080804040 8 812012040408080 合计合计46046010010080802002008080 第35页/共70页 第36页/共70页 最小？最小？ 第37页/共70页 (3,2)(3,2) (6,3)(6,3) (2,8)(2,8) (1,3)(1,3) (4,4

9、)(4,4)(2,3)(2,3) (5,7)(5,7) (2,4)(2,4) （2,52,5） (3,4)(3,4) (6,6)(6,6) v1v1v7v7v6v6 v5v5 v4v4 v3v3 v2v2 第38页/共70页 电子表格模型电子表格模型P166P166 求得的最小费用为求得的最小费用为145145 第39页/共70页 通过网络到目的地的总距离最短通过网络到目的地的总距离最短。 第40页/共70页 v1v1 v2v2 v3v3 v4v4 v5v5 v6v6 v7v7 2 2 9 9 6 6 8 83.53.5 1 14 4 5 5 2.52.53 3 第41页/共70页 负）负）P

10、169P169 1213232434 3545465767 Min z = 29681 343.52.55 xxxxx xxxxx 第42页/共70页 第43页/共70页 第44页/共70页 年限年限1 12 23 34 4 购置费（万元）购置费（万元）2.52.5 2.62.6 2.82.8 3.13.1 维修与运行费（万元）维修与运行费（万元）1 11.51.52 24 4 第45页/共70页 第46页/共70页 1 13 35 52 24 4 3.53.53.63.63.83.84.14.1 1111 5 5 7 7 5.35.3 5.15.1 7.17.1 第47页/共70页 第48页

11、/共70页 使用年数使用年数1 12 23 34 4 处理价（万元）处理价（万元） 2 2 1.61.6 1.31.3 1.11.1 第49页/共70页 第50页/共70页 第51页/共70页 第52页/共70页 第53页/共70页 第54页/共70页 方法完成方法完成网络设计网络设计，使得边的总成，使得边的总成 本最小。本最小。这种问题称为最小支撑树这种问题称为最小支撑树 问题。问题。 第55页/共70页 第56页/共70页 4 4 2 2 5 5 4 41 1 4 4 3 37 7 1 1 5 5 7 7 2 2 A A B B D D C CE E F F G G 第57页/共70页 第

12、58页/共70页 第59页/共70页 A A B BC CD D E EF F 4 4 2 .2 . 2 2 3 3 1 .1 . 5 5 1 .1 . 6 61.1. 8 8 2 .2 . 6 6 2 .2 . 8 8 2 .2 . 8 84 .4 . 2 2 第60页/共70页 第61页/共70页 第62页/共70页 第63页/共70页 第64页/共70页 第65页/共70页 v1v1 v2v2 v3v3v4v4 v9v9v6v6 v5v5 v8v8v7v7 5 5 5 5 2 24 4 4 4 4 4 4 4 3 3 4 4 3 3 9 9 6 6 在图中有在图中有4 4个奇个奇 点点v2v2、v4v4、v6v6 、v8v8，采用，采用“