数学建模《运筹与统计组合优化》

数学建模 浙江大学数学系谈之奕 tanzy@ 运筹与统计 组合优化 组合优化 • 通常把从有限个可行解中找出使 某个目标函数达到最优的解的优 化问题称为组合优化 （Combinatorial OptimizationCombinatorial Optimization） • 组合优化与组合学（CombinatoricsCombinatorics） 同为研究离散对象的数学分支，但两 者侧重不同。后者着重研究满足特定 性质对象的存在性，计数，构造等问 题，前者要求在众多可行解中按一定 Journal ofJournal of CombinatorialCombinatorial 标准选出最优解 OptimizationOptimization 数学建模 DiscreteDiscrete OptimizationOptimization 2 背包问题 • 背包问题（Knapsack Problem） • 一背包客准备参加自助游，想要 携带的物品很多，但随身背包的 容量有限，因此希望通过综合考 虑，使放入背包中的物品对旅行 的帮助最大 n • 设物品数为，由于每个物品可 以选择放入或不放入，因此可行 解数目不超过2 n个 数学建模 3 3 旅行售货商问题 • 旅行售货商问题（Traveling Salesman ProblemTraveling Salesman Problem， TSPTSP） • 数学建模 一推销商想在若干个城市中推销自己的产品。计划从 某个城市出发，经过每个城市恰好一次，最后回到出 发的城市。假设城市之间距离已知，推销商应如何选 择环游路线，使他走的路程最短 1 • 每一条环游路线对应于 (n 1)!列 数目共有个 2n 的一个排列。不同的排 环游美国的 TSP 数学建模 国 48 48个美 州首府的 T TSP SP环游 （上图的 环游顺序 与 19541954年 论文相 同，但不 再是最优 的，下图 为最优环 游） 美国 49 49个城市的最优 TSPTSP环游 Dantzig, G., Fulkerson, R., Johnson, S.,Dantzig, G., Fulkerson, R., Johnson, S., Solution of a Large-Scale Traveling-SalesmanSolution of a Large-Scale Traveling-Salesman Problem,Problem, Journal of the Operations ResearchJournal of the Operations Research Society of AmericaSociety of America, 2, 393-410, 2, 393-410 5 VLSI设计中的 TSP • 441441个焊点的印刷电路板 数学建模 Applegate, D. L., Bixby, R. E., ChváApplegate, D. L., Bixby, R. E., Chvátal V., Cook, W., Espinoza D. G., Goycoolea, M.,tal V., Cook, W., Espinoza D. G., Goycoolea, M., Helsgaun, K., Certification of an optimal TSP tour through 85,900 cities,Helsgaun, K., Certification of an optimal TSP tour through 85,900 cities,OperationsOperations R Research Lettersesearch Letters, 37, 11-15, 2009., 37, 11-15, 2009. 6 指派问题 • 指派问题（Assignment Problem） 数学建模 nn • 设有 项任务需分配给位员工，每人完成其 i j c ij 中一 项，员工 完成任务 所需时间为，如 何分配可使完成所有任务所用总时间最少 • 不同的分配方案共有种 n! 枚举 • 63 数学建模 201 按一千克小麦含 25000 粒计算， 棋盘上的小麦总 计约为 7400 亿 吨，按目前的平 均产量计算，是 全世界一千多年 生产的全部小麦 组合优化问题通常 不能通过枚举所有 可行解并加以比较 来求解，其原因是 可行解的数目可能 是一很大的数，以 致于当前或相当长 的一段时间内人力 或计算机不能承受 9223372036 2 9.22 10 854775808 舍罕王 PKPK 西萨·班·达依尔 18 8 函数量阶 数 10 1020 2040 40100100函 数学建模 lgn 1 1秒1.301.30秒1.601.60秒 17.3717.37秒 514514天 2 2秒 43.443.4秒 138138年 1 .7 10 n n 2 5 4.344.34秒 8.698.69秒 1 12 2小时 16 16天 444444秒5 5.27.27天 151151世纪 18.218.2天 世 纪 n n! 20 世纪 1 148 .2 101 148 n n 9 1 138 38年 3 8 世纪 1.11038 .3 103 8 世纪 1.11038 .4 10 16 1 世纪 54 .6 10 世纪 世纪 10190 世纪 11.4 函数量阶 在的计算机 快 100100倍快 1000010000倍 数学建模 快 10000001000000倍 现 lgn n n 2 5 N N N N 2 100N 2.51N N4N 6 1000000N 15.85N N19.93 10000N 6.31N 13.28 n N N6.64N Top500 http://www.top500.orghttp://www.top500.org 数学建模 g gigaFLOPS=igaFLOPS= teraFLOPS=teraFLOPS= 10 9 10 12 时间公司计算机浮点数运算次数 提高倍数 1993.6(1993.6(首届) )TMCTMCCM5CM559.70GFlops59.70GFlops 1998.6(11 1998.6(11届) )IntelIntelASCI-RedASCI-Red1338.00GFlops1338.00GFlops22.422.4 2003.6(21 2003.6(21届) )NECNECNEC VectorNEC Vector 35860.00GFlops35860.00GFlops600.7600.7 2008.6(31 2008.6(31届) )IBMIBMBladeCenterBladeCenter1026.0TFlops1026.0TFlops1718617186 2 2010.11(36010.11(36届) ) 国防科大天河一号2566.0TFlops2566.0TFlops4298142981 2012.12(402012.12(40届) )CrayCrayTitanTitan17590.0T