组合优化及算法课件.ppt

《组合优化及算法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、组合优化CombinatorialOptimization组合优化是运筹学的后继课程，同时也是运筹学的一个重要独立分支，是一类重要的优化问题最优化(数学规划)连续优化(数学规划)：数学规划（线性规划、非线性规划）、非光滑优化、全局优化、锥优化等离散优化：网络优化、组合优化、整数规划等不确定规划：随机规划、模糊规划等所谓组合(最)优化(CombinatorialOptimization)又称离散优化（DiscreteOptimization），它是通过数学方法去寻找离散事件的最优编排、分组、次序或筛选等.这类问题可用数学模型描述为：优化问题三要素:(Min,f,F)或(Max,f,F)其中

2、D表示有限个点组成的集合(定义域),f为目标函数,F={x

3、xD,g(x)0}为可行域组合优化–定义组合优化–例例0-1背包问题(knapsackproblem)给定n个容积分别为ai，价值分别为ci的物品.设有一个容积为b的背包，如何以最大的价值装包？用数学规划模型表示为：D={0,1}n例装箱问题(BinPacking)以尺寸为1的箱子装进给定的n个尺寸不超过1的物品，如何使所用的箱子个数最少?组合优化–例整数线性规划(IntegerLinearProgramming)(IP).我们假设线性整数规划的参数（约束矩阵和右端项系数）都是整数(或有理数).许多组合优化问题可以用整数规划

4、模型表示,但有时不如直接用自然语言描述简洁组合优化问题–定义定义：组合优化问题是一个极小化问题，或者是一个极大化问题，它由下述三部分组成：（1）实例集合；（2）对每一个实例I，有一个有穷的可行解集合S(I).（3）目标函数，对每一个实例I和每一个可行解，赋以一个有理数.如果是极小化（极大化）问题，则实例I的最优解为这样一个可行解，它使得对于所有，它都有算法–定义定义：算法是指一步步求解问题的通用程序，它是解决问题的程序步骤的一个清晰描述.定型算法，即算法从前一步到后一步的运行是由当时状态唯一确定的.如果存在一个算法，他它对问题任意一个给定实例，在有限步之后，一定能得到该实例的答案，那么我

5、们称算法能解决该问题.近似算法、最优算法近似算法：对于一个优化问题，如果给定任意一个实例I,算法A总能找到一个可行解，那么这个算法称为该问题的近似算法.最优算法：如果进一步，如果这个可行解的目标值总等于最优解值，则称A为最优算法.典型组合优化问题背包问题装箱问题平行机排序问题图与网络优化问题最小支撑树、最短路、最大流、最小费用流、最大基数匹配问题指派问题旅行售货商问题斯坦纳最小树问题本课程的主要目的讲授这些问题的数学描述和相应算法.背包问题给定n个容积分别为ai，价值分别为ci的物品.设有一个容积为b的背包，如何以最大的价值装包？平行机排序问题M个完全相同的机器，n个相互独立的工件，加工

6、时间互不相同，每个工件只需在任一台机器上不中断建工一次，如果安排加工方案，才能使预定的加工时间最短？计算复杂性的概念多项式时间算法对于组合优化问题，我们关心的一般不是最优解的存在性和唯一性，而是如何找到有效的算法求得一个最优解.那么如何衡量算法的优劣、有效与无效呢？完全枚举法可以求得最优解,但枚举时间有时不可能接受ATSP:(n-1)!枚举(TOUR,周游或环游)设计算机每秒进行100亿次枚举,需30!/10e+10>2.65e+22(秒)即2.65e+22/(365*24*60*60)>8.4e+13(年)计算复杂性的概念多项式时间算法构造算法的目的是能够解决问题（或至少是问题某个子类

7、）的所有实例而不单单是某一个实例问题（Problem）是需要回答的一般性提问，通常含有若干个满足一定条件的参数.问题通过下面的描述给定：（1）描述所有参数的特性，（2）描述答案所满足的条件.问题中的参数赋予了具体值的例子称为实例(instance).衡量一个算法的好坏通常是用算法中的加、减、乘、除和比较等基本运算的总次数（计算时间）C（I）同实例I在计算机计算时的二进制输入数据(输入规模/长度d（I）)的大小关系来度量.计算模型C(I)=f(d(I)):该函数关系称为算法的计算复杂性（度）计算复杂性的概念多项式时间算法例构造算法将n个自然数从小到大排列起来算法输入自然数a(1),a(2

8、),…,a(n).for(i=1;ia(j)){k=a(i);a(i)=a(j);a(j)=k;}即该算法的计算复杂性（度）为O(n2)基本运算的总次数(最坏情形）：2n(n-1)=O(n2)计算复杂性的概念定义1.4假设问题和解决该问题的一个算法已经给定，若存在g(x)为多项式函数且对该问题任意的一个实例I，使得计算时间成立，则称该算法为解决该问题的多项式(时间)