组合优化及算法.ppt

组合优化 Combinatorial Optimization 组合优化是运筹学的后继课程，同时也是运筹学的一个重要独立分支，是一类重要的优化问题 组合优化问题 – 定义 定义：组合优化问题 是一个极小化问题，或者是一个极大化问题，它由下述三部分组成： （1）实例集合； （2）对每一个实例I，有一个有穷的可行解集合S(I). （3）目标函数 ，对每一个实例I和每一个可行解 ，赋以一个有理数 .如果 是极小化（极大化）问题，则实例I 的最优解为这样一个可行解 ，它使得对于所有 ，它都有 算法 – 定义 定义：算法是指一步步求解问题的通用程序，它是解决问题的程序步骤的一个清晰描述. 近似算法、最优算法 近似算法：对于一个优化问题，如果给定任意一个实例I,算法A总能找到一个可行解，那么这个算法称为该问题的近似算法. 典型组合优化问题 背包问题 装箱问题 平行机排序问题 图与网络优化问题 最小支撑树、最短路、最大流、最小费用流、最大基数匹配问题 指派问题 旅行售货商问题 斯坦纳最小树问题 背包问题 给定n个容积分别为ai，价值分别为ci的物品.设有一个容积为b的背包，如何以最大的价值装包？ 平行机排序问题 M个完全相同的机器，n个相互独立的工件，加工时间互不相同，每个工件只需在任一台机器上不中断建工一次，如果安排加工方案，才能使预定的加工时间最短？ * 最优化(数学规划) 连续优化(数学规划)： 数学规划（线性规划、非线性规划）、非光滑优化、全局优化、锥优化等 离散优化：网络优化、组合优化、整数规划等 不确定规划：随机规划、模糊规划等 所谓组合(最)优化(Combinatorial Optimization)又称离散优化（Discrete Optimization），它是通过数学方法去寻找离散事件的最优编排、分组、次序或筛选等. 这类问题可用数学模型描述为： 优化问题三要素: (Min,f,F)或(Max,f,F) 其中D表示有限个点组成的集合(定义域) , f为目标函数,F={x|x?D, g(x)?0}为可行域 组合优化 – 定义 组合优化 – 例 例 0-1背包问题(knapsack problem) 给定n个容积分别为ai，价值分别为ci的物品.设有一个容积为b的背包，如何以最大的价值装包？用数学规划模型表示为： D= {0,1}n 例 装箱问题(Bin Packing) 以尺寸为1的箱子装进给定的n个尺寸不超过1的物品，如何使所用的箱子个数最少? 组合优化 – 例 整数线性规划(Integer Linear Programming) (IP) . 我们假设线性整数规划的参数（约束矩阵和右端项系数）都是整数(或有理数). 许多组合优化问题可以用整数规划模型表示,但有时不如直接用自然语言描述简洁 定型算法，即算法从前一步到后一步的运行是由当时状态唯一确定的. 如果存在一个算法，他它对问题任意一个给定实例，在有限步之后，一定能得到该实例的答案，那么我们称算法能解决该问题. 最优算法：如果进一步，如果这个可行解的目标值 总等于最优解值，则称A为最优算法. 本课程的主要目的讲授这些问题的数学描述和相应算法. 计算复杂性的概念 多项式时间算法 对于组合优化问题，我们关心的一般不是最优解的存在性和唯一性，而是如何找到有效的算法求得一个最优解. 那么如何衡量算法的优劣、有效与无效呢？ 完全枚举法可以求得最优解,但枚举时间有时不可能接受 ATSP: (n-1)!枚举(TOUR,周游或环游) 设计算机每秒进行100亿次枚举,需 30! / 10e+10 2.65e+22 (秒) 即 2.65e+22 / (365*24*60*60) 8.4e+13 (年) 计算复杂性的概念 多项式时间算法 构造算法的目的是能够解决问题（或至少是问题某个子类）的所有实例而不单单是某一个实例 问题（Problem）是需要回答的一般性提问，通常含有若干个满足一定条件的参数. 问题通过下面的描述给定：（1）描述所有参数的特性，（2）描述答案所满足的条件. 问题中的参数赋予了具体值的例子称为实例(instance). 衡量一个算法的好坏通常是用算法中的加、减、乘、除和比较等基本运算的总次数（计算时间）C（I）同实例I在计算机计算时的二进制输入数据(输入规模/长度d（I）)的大小关系来度量. ?计算模型 C(I) = f(d(I)) : 该函数关系称为算