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

数学建模 浙江大学数学系 谈之奕 tanzy@ 运筹与统计 组合优化 组合优化 数学建模 ? 通常把从有限个可行解中找出使 某个目标函数达到最优的解的优 化问题称为组合优化 （Combinatorial Optimization） ? 组合优化与组合学（Combinatorics） 同为研究离散对象的数学分支，但两 者侧重不同。后者着重研究满足特定 性质对象的存在性，计数，构造等问 题，前者要求在众多可行解中按一定 标准选出最优解 Journal of Combinatorial Optimization Discrete Optimization 2 背包问题 数学建模 ? 背包问题（Knapsack Problem） ? 一背包客准备参加自助游，想要 携带的物品很多，但随身背包的 容量有限，因此希望通过综合考 虑，使放入背包中的物品对旅行 的帮助最大 n ? 设物品数为 ，由于每个物品可 以选择放入或不放入，因此可行 解数目不超过 2n 个 3 3 旅行售货商问题 数学建模 ? 旅行售货商问题（Traveling Salesman Problem， TSP） ? 一推销商想在若干个城市中推销自己的产品。计划从 某个城市出发，经过每个城市恰好一次，最后回到出 发的城市。假设城市之间距离已知，推销商应如何选 择环游路线，使他走的路程最短 1 ? 2 n ? 每一条环游路线对应于 的一个排列。不同的排 (n ? 1) ! 列数目共有 个 4 环游美国的TSP 数学建模 美国48个 州首府的 TSP环游 （上图的 环游顺序 与1954年 论文相 美国49个城市的最优TSP环游 Dantzig, G., Fulkerson, R., Johnson, S., Solution of a Large-Scale Traveling-Salesman Problem, Journal of the Operations Research Society of America, 2, 393-410 同，但不 再是最优 的，下图 为最优环 游） 5 VLSI设计中的TSP 数学建模 ? 441个焊点的印刷电路板 Applegate, D. L., Bixby, R. E., Chvátal V., Cook, W., Espinoza D. G., Goycoolea, M., Helsgaun, K., Certification of an optimal TSP tour through 85,900 cities, Operations Research Letters, 37, 11-15, 2009. 6 指派问题 数学建模 ? 指派问题（Assignment Problem） n n ? 设有 项任务需分配给 位员工，每人完成其 i j cij 中一项，员工 完成任务 所需时间为 ，如 何分配可使完成所有任务所用总时间最少 ? 不同的分配方案共有 种 n! 7 枚举 数学建模 ? 组合优化问题通常 不能通过枚举所有 可行解并加以比较 来求解，其原因是 可行解的数目可能 是一很大的数，以 致于当前或相当长 的一段时间内人力 或计算机不能承受 20 ?1 按一千克小麦含 25000粒计算， 棋盘上的小麦总 计约为7400亿 吨，按目前的平 均产量计算，是 全世界一千多年 生产的全部小麦 63 2 ? ? 9223372036 9.22 10 ? 18 854775808 舍罕王 PK 西萨·班·达依尔 8 函数量阶 数学建模 10 20 40 100 函数 lgn 1秒 1.30秒 1.60秒 2秒 n 4.34秒 8.69秒 17.37秒 43.4秒 5 n 12小时 16天 514天 138年 n 2 n! 444秒 18.2天 5.27天 151世纪 世纪 3 ? 8世纪 1.1?1038 .3 103 ? 8世纪 1.1?1038 1 ? .7 10 20 世纪 1 ? 148 .2 101 ? 148 世纪 n n 138年 1 ? 1.4?10190 .4 10 1 ? 16 世纪 54 世纪 世纪 .6 10 9 函数量阶 数学建模 快100倍 快10000倍 快1000000倍 现在的计算机 lgn N N 2 N 4 N 6 n N 100N 10000N 1000000N 5 n N 2.51N 6.31N 15.85N n 2 N N 6.64 N ?13.28 N ?19.93 ? 10 Top500 数学建模 gigaFLOPS= teraFLOPS= 10 9 10 12 时间 公司 计算机 浮点数运算次数 提高倍数 1993.6(首届)