应用运筹学第五章

《应用运筹学第五章》由会员分享，可在线阅读，更多相关《应用运筹学第五章（72页珍藏版）》请在金锄头文库上搜索。

1、应用运筹学应用运筹学应用运筹学科学与研究类通识课程科学与研究类通识课程浙江大学数学系谈之奕应用运筹学第五章组合优化 （Combinatorial Optimization）应用运筹学2组合优化 通常把从有限个可行解中找出使某个目标 函数达到最优的解的优化问题称为通常把从有限个可行解中找出使某个目标 函数达到最优的解的优化问题称为组合优 化组合优 化（Combinatorial Optimization)。 象象Lagrange 乘子法那样在实数空间内取值 的优化问题称为乘子法那样在实数空间内取值 的优化问题称为连续优化连续优化（Continuous Optimization），与之相对应的就称

2、为），与之相对应的就称为离散 优化离散 优化（Discrete Optimization）。）。应用运筹学3组合优化 组合优化与组合优化与组合学组合学（ Combinatorics）同为研究离 散对象的数学分支，但两者 侧重不同。后者着重研究满 足特定性质对象的存在性， 计数，构造等问题，前者要 求在众多可行解中按一定标 准选出最优解。）同为研究离 散对象的数学分支，但两者 侧重不同。后者着重研究满 足特定性质对象的存在性， 计数，构造等问题，前者要 求在众多可行解中按一定标 准选出最优解。Discrete OptimizationJournal of Combinatorial Optimi

3、zation应用运筹学4背包问题 一背包客准备参加自 助游，想要携带的物 品很多，但随身背包 的容量有限，因此希 望通过综合考虑，使 放入背包中的物品对 旅行的帮助最大一背包客准备参加自 助游，想要携带的物 品很多，但随身背包 的容量有限，因此希 望通过综合考虑，使 放入背包中的物品对 旅行的帮助最大背包、手表、帐篷、电筒、 头灯、手杖、瑞士军刀 、贴 身衣、火炉、凉鞋、防晒油背包、手表、帐篷、电筒、 头灯、手杖、瑞士军刀 、贴 身衣、火炉、凉鞋、防晒油应用运筹学5背包问题 设需要考虑的物品共有种，第 种物品的价值 为，大小为，背包容量为设需要考虑的物品共有种，第 种物品的价值 为，大小为，背

4、包容量为 背包问题背包问题（knapsack）要求选择，使得在的前提下，使尽可能的大）要求选择，使得在的前提下，使尽可能的大 由于每个物品只有放入和不放入两种可能，因此 可行解数目不超过个由于每个物品只有放入和不放入两种可能，因此 可行解数目不超过个nj, 2 , 1nICCwIjj Ijjpn2jpjw应用运筹学旅行售货商问题 一推销商想在若干个城市中推销自己的产 品。计划从某个城市出发，经过每个城市 恰好一次，最后回到出发的城市。假设城 市之间距离已知，推销商应如何选择环游 路线，使他走的路程最短。该问题称为一推销商想在若干个城市中推销自己的产 品。计划从某个城市出发，经过每个城市 恰好一

5、次，最后回到出发的城市。假设城 市之间距离已知，推销商应如何选择环游 路线，使他走的路程最短。该问题称为旅 行售货商问题旅 行售货商问题（Traveling Salesman Problem，TSP）应用运筹学旅行售货商问题 每一条环游路线对应于的一个置 换。不同的置换数目共有个。注意 到和对应的两条环 游路线总长度相同，因此不同的每一条环游路线对应于的一个置 换。不同的置换数目共有个。注意 到和对应的两条环 游路线总长度相同，因此不同的 TSP 环游 路线共有条环游 路线共有条n 2 1 )!1( n ) 2 1 (n) 1 2 1- (nn)!1(21n应用运筹学旅行售货商问题阿姆斯特丹阿

6、姆斯特丹 685 925 1180 960 1755 1235 1180 柏林柏林 1160 1105 340 1530 585 630 日内瓦日内瓦325 950 880 1575 1025 米兰米兰870 575 1495 830 布拉格布拉格1290 625 290 罗马罗马1915 1130 华沙华沙795 维也纳维也纳 最优路程：最优路程：5140罗马维也纳布拉格华沙 柏林阿姆斯特丹日内瓦米兰罗马维也纳布拉格华沙 柏林阿姆斯特丹日内瓦米兰应用运筹学VLSI设计中的TSP PMA343应用运筹学枚举 组合优化问题通常不能通过枚举所有可能的解加 以比较来求解，其原因是可行解的数目可能是一

7、 很大的数，以致于当前或相当长的一段时间内人 力或计算机不能承受组合优化问题通常不能通过枚举所有可能的解加 以比较来求解，其原因是可行解的数目可能是一 很大的数，以致于当前或相当长的一段时间内人 力或计算机不能承受 也有一些问题，如最小生成树，可以不通过枚举 找到最优解，从而使求解时间大幅下降。而对有 些问题，如也有一些问题，如最小生成树，可以不通过枚举 找到最优解，从而使求解时间大幅下降。而对有 些问题，如TSP，目前还没有找到这样的方法，目前还没有找到这样的方法 组合优化研究的一个重要方面是区分哪些问题是 容易求解，哪些问题是难求解的组合优化研究的一个重要方面是区分哪些问题是 容易求解，哪

8、些问题是难求解的应用运筹学枚举18631022. 985477580892233720362 120舍罕王舍罕王 PK 西萨班达依尔西萨班达依尔如果一升小麦按150000粒计算， 总计约为130万亿升小麦，按目前 的平均产量计算，是全世界生产 两千年的全部小麦如果一升小麦按150000粒计算， 总计约为130万亿升小麦，按目前 的平均产量计算，是全世界生产 两千年的全部小麦应用运筹学世纪世纪世纪世纪世纪世纪138年世纪世纪世纪 年世纪世纪世纪18.2天世纪天世纪151世纪世纪5.27天天444秒秒138年年514天天16天天12小时小时43.4秒秒17.37秒秒8.69秒秒4.34秒秒2秒秒1

9、.60秒秒1.30秒秒1秒秒100402010函数函数 nln n 5nn2 !n nn20107 . 18103 . 338101 . 1 54106 . 1函数量阶148102 . 116104 . 1190104 . 1应用运筹学快快1000000倍快倍快10000倍快倍快100倍现在的计算机倍现在的计算机nlg n5nn2N2NNNN4N6NN10000N100N1000000N51. 2N31. 6N85.15 64. 6N28.13N93.19N函数量阶应用运筹学http:/www.top500.org/42981.5725660000天河一号国防 科大天河一号国防 科大2010.

10、11(36届届)600.7358600NEC VectorNEC2003.6(21届届)22.413380ASCI-RedIntel1998.6(11届届)597CM5TMC1993.6(首届首届)提高 倍数提高 倍数浮点数运 算次数（ 亿次浮点数运 算次数（ 亿次/秒）秒）计算机公司时间计算机公司时间应用运筹学计算复杂性 计算复杂性计算复杂性（computational complexity）理论在组合优化学科 中的应用之一是将问题按难度分类 ，从而为进一步研究指明方向。）理论在组合优化学科 中的应用之一是将问题按难度分类 ，从而为进一步研究指明方向。 计算复杂性理论建立在一种名为计算复杂性

11、理论建立在一种名为图 灵机图 灵机（ Turing machine）的理论计 算模型之上。该模型由）的理论计 算模型之上。该模型由A. Turing于于 1936年提出，它能模拟目前所有的 合理计算模型。年提出，它能模拟目前所有的 合理计算模型。Alan Turing英国计算机学家英国计算机学家 (1912-1954)应用运筹学图灵机B11B111BB1BB111B11BBB应用运筹学ACM Turing Award ACMs most prestigious technical award is accompanied by a prize of $100,000. The contribu

12、tions should be of lasting and major technical importance to the computer field. 自自1966年创立至今，共有年创立至今，共有51名科学 家获此殊荣名科学 家获此殊荣Association for Computing Machinery应用运筹学ACM Turing AwardEdsger Wybe Dijkstra (1972)Donald Ervin Knuth (1974)Stephen A. Cook (1982)Richard M. Karp (1985)Andrew Chi- Chih Yao (姚期智

13、姚期智, 2000) 应用运筹学时间复杂性 用算法执行过程中所需的加、减、乘、比较等基 本运算次数表示算法所用的时间。用算法执行过程中所需的加、减、乘、比较等基 本运算次数表示算法所用的时间。 将在计算机中表示实例所需字节数称为实例的将在计算机中表示实例所需字节数称为实例的规 模规 模（size） 。存储整数一般需个字节。） 。存储整数一般需个字节。 算法的算法的时间复杂性时间复杂性（time complexity）是关于实 例规模的一个函数，它表示用该算法求解 所有规模为的实例中所需基本运算次数最多的 那个实例的基本运算次数。）是关于实 例规模的一个函数，它表示用该算法求解 所有规模为的实例

14、中所需基本运算次数最多的 那个实例的基本运算次数。n)(nf nkk2log应用运筹学时间复杂性 若一算法的时间复杂性，这 里为一多项式，则称它为若一算法的时间复杂性，这 里为一多项式，则称它为多项式时间 算法多项式时间 算法。不能这样限制时间复杂性函数的算 法称为。不能这样限制时间复杂性函数的算 法称为指数时间算法指数时间算法。 结合关于函数增长速度的比较，和算法的 实际运行效果，把多项式时间算法称为结合关于函数增长速度的比较，和算法的 实际运行效果，把多项式时间算法称为有 效算法有 效算法，指数时间算法称为，指数时间算法称为无效算法无效算法。)()(npOnf )(p应用运筹学P 类 若一

15、问题已找到多项式时间算法 ，称这样的问题属于若一问题已找到多项式时间算法 ，称这样的问题属于多项式时间 可解问题类多项式时间 可解问题类（polynomial solvable problem class），记为），记为 P。证明 一问题属于。证明 一问题属于P 类只需设计出求解 该问题的多项式时间算法。类只需设计出求解 该问题的多项式时间算法。 最小生成树即为最小生成树即为P 类中的问题； 判断一个整数是否为质数也属于类中的问题； 判断一个整数是否为质数也属于P 类。类。应用运筹学NP 类 所谓所谓非确定性算法非确定性算法在多项式时间内求解某问题， 是指它能在多项式时间内求解某问题， 是指它

16、能 猜想猜想出该实例的一个可行解，其规模不超过输入规模 的多项式函数；出该实例的一个可行解，其规模不超过输入规模 的多项式函数； 在输入规模的多项式时间内验证猜想是否正确。在输入规模的多项式时间内验证猜想是否正确。 非确定性算法多项式时间可解问题类非确定性算法多项式时间可解问题类（ nondeterministic polynomial solvable problem class），记为NP 类。），记为NP 类。应用运筹学P=NP 猜想 非确定性算法在现实生活中 并不存在，只是为研究而定 义的一种理论算法。非确定性算法在现实生活中 并不存在，只是为研究而定 义的一种理论算法。 P 类中的问题是多项式时间 可求解问题，而NP 类中的