15运筹学——运输问题的图上作业法和CPP问题.pptVIP

《运筹学》第十四讲 教案要点 文 件 名：071OR14.PPT； 授课时间：2007年11月29日 授课班级：元培学院自动化、信计05级用 授课内容：运输问题的图上作业法，CPP问题 自编讲义：《线性规划理论及其应用》《图上作业法》 难 点：初始解、判优、调优,CPP的奇点配对 重 点：图解的规定，初始解的生成，判优准则，调优方法；CPP问题与Euler图的关系,奇点配对方法,逐圈检查思想。 下节预习：教材：教材第十五章对策论。 运筹学 元培学院信计、自动化05级 2007.11.29. 图上作业法 中国科学家提出的解运输问题的图上作业法[万哲先等]； 中国邮递员 [Chinese Postman Problem]问题。 运输问题图上作业法 流量、靠右画、流向图; 对流、避免对流； 查圈，注意圈的个数； 流向图中每个圈的内圈长、外圈长、全圈长和半圈长，正则圈； 判优准则和调整方法。 运输问题图上作业法 查供销是否平衡？ 找初始可行解[流向图]； 靠右走； 内外圈长均不超过半圈长的叫正则圈； 调整方法。 找初始可行解 避对流，靠右走； 优否？调整。 三圈逐圈查； 检查圈Ⅰ 内圈长？ 圈Ⅰ初调后 内圈仍过半； 圈Ⅰ再调后 内圈0不过半； 检查圈Ⅱ 外圈过半； 圈Ⅱ初调后 外圈仍过半； 圈Ⅱ再调后 外圈仍过半； 圈Ⅱ三调后 外圈不过半； 回查圈Ⅰ 外圈过半； 圈Ⅰ四调后 外圈仍过半； 圈Ⅰ五调后 外圈不过半； 调整圈Ⅲ 外圈过半； 调整圈Ⅲ后 运输问题的图上作业法 如无圈，则没有对流的运输方案就是最优解。 有圈的时候，先每个圈里删去最长的一条边破圈，找初始可行解，每个流量靠右记。 最优解要求：每个圈的内外圈长都不超过半圈长[这种圈叫正则圈]。 如有一个圈的外(内)圈长超过半圈长,找出最小的一个外(内)圈流量,内(外)圈反向流此流量,消去对流,得新可行解再检验。 找初始可行解 先破圈， CPP问题 中国邮递员问题 无奇点可一笔画，有Euler圈叫Euler图； 有一对奇点可一笔画,有Euler 链,不返回。 CPP问题 无奇点可一笔画； 有奇点,“消除”奇点:奇点是成对的，寻找一对，用附加边连接，“消除”这一对,逐对消除，即是一个方案。我们要找出最佳配对的方案。 “奇偶点作业法”。 CPP问题 找奇点 CPP问题 逐圈查 CPP问题 奇点就近配对 补充作业 求左面的运输问题的最优解。 * 邯 252 丰 津 石 德 239 8 -5 2 5 6 郑 徐 济 青 -3 -5 -3 -5 349 317 393 118 180 165 266 120 邯 252 丰 津 石 德 239 8 -5 2 5 6 郑 徐 济 青 -3 -5 -3 -5 349 317 393 118 180 165 266 120 5 11 11 8 3 11 13 5 5 丰台起，顺时针； 邯 252 丰 津 石 德 239 8 -5 2 5 6 郑 徐 济 青 -3 -5 -3 -5 349 317 393 118 180 165 266 120 8 3 11 13 5 5 Ⅰ Ⅱ Ⅲ 5 11 11 邯 252 丰 津 石 德 239 8 -5 2 5 6 郑 徐 济 青 -3 -5 -3 -5 349 317 393 118 180 165 266 120 8 3 11 13 5 5 Ⅰ 5 11 11 内圈最小流量为5，外圈反向流5，消去对流。 5 6 6 内圈长过半； 内圈长539 邯 252 丰 津 石 德 239 8 -5 2 5 6 郑 徐 济 青 -3 -5 -3 -5 349 317 393 118 180 165 266 120 8 3 11 13 5 5 Ⅰ 5 6 6 内圈最小流量为6，外圈反向流6，消去对流。 11 6 内圈长？ 内圈长419 邯 252 丰 津 石 德 239 8 -5 2 5 6 郑 徐 济 青 -3 -5 -3 -5 349 317 393 118 180 165 266 120 8 3 11 13 5 5 Ⅰ 11 6 外圈也不过半，圈Ⅰ暂告一段落，查圈Ⅱ。 Ⅱ 外圈长？ 外圈长386 邯 252 丰 津 石 德 239 8 -5 2 5 6 郑 徐 济 青 -3 -5 -3 -5 349 317 393 118 180 165 266 120 8 3 11 13 5 5 Ⅱ 11 6 外圈最小流量___， 外圈长？ 3 2 10 8 5 外圈长1201 3 内 __圈反向流3，消去对流。 邯 252 丰 津 石 德 239 8 -5 2 5 6 郑 徐 济 青 -3 -5 -3 -5 349 317 393 118 180 165 266 120 5 3 8 10 2 5 Ⅱ 11 6