组合优化问题及算法

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

1、MATHEMATICAMODEL制作:龚劬组合优化问题及其算法组合最优化（combinatorialoptimization)是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，是运筹学(operationsresearch)中的一个重要分支。所研究的问题涉及信息技术、经济管理、工业工程、交通运输、通信网络等领域。该问题可用数学模型描述为：引言其中D表示有限个点组成的集合。21.0-1背包问题设有一个容积为b的背包，n个体积分别为ai(i=1,2,…,n),价值分别为ci(i=1,2,…,n)的物品，如何以最大的价值装包？一些例子32.旅行商

2、问题(TSP，travelingsalesmanproblem)一个商人欲到n个城市推销商品，每两个城市i和j之间的距离为dij，如何选择一条道路使得商人每个城市正好走一遍后回到起点且所走路径最短。一些例子43.有约束的机器调度问题(capacitatedmachinescheduling)n个加工量为{di

3、i=1,2,…,n}的产品在一台机器上加工，机器在第t个时段的工作能力为ct,求完成所有产品加工所需时段数最少的调度方案一些例子其中xit,T为决策变量,xit=1表示产品i在第t时段加工54.装箱问题(binpacking)如何把n个尺寸不超过1的物

4、品装入尺寸为1的箱子，并使所用的箱子个数最少。5.二维装箱问题（平面上的套裁问题）原料的尺寸大于需求的尺寸，需求的品种尺寸可以不同，最终的目标是在满足需求的前提下，使边角余料最小。6.车间作业调度问题(jobshopscheduling)n个工件，J1,…,Jn在m台机器M1,M2,…,Mm上加工。每个工件Ji有ni个工序，Oi1,…,Oini,第Oij工序的加工时间为pij，必须按工序进行加工且每一工序必须一次加工完成。一台机器在任何时刻最多只能加工一个产品，一个工件不能同时在两台机器上加工，如何安排才能使最后一个完工的工件完工时间最小？一些例子67.最大

5、截问题(MCP,MaxCutProblem)8.图的顶点着色问题（GCP,GraphColouringProblem)9.独立集问题（ISP,IndependentSetProblem)10.调度问题(SCP,SchedulingProblem)11.划分问题(PAP,PartitionProblem)12.布局问题（PLP,PlacementProblem)……上述问题都是NP-hard问题，目前人们认为它们不存在求解最优解的多项式时间算法，大规模情形只有尝试用一些近似算法或启发式算法求解。一些例子7邻域概念对于组合优化问题(D,F,f),D上的一个映射：

6、N:SDN(S)2D称为一个邻域映射，其中2D表示D的所有子集构成的集合，N(S)称为S的邻域。邻域的构造依赖于问题决策变量的表示，邻域的结构在现代化优化算法中起重要作用。启发式算法8邻域概念例如，前面例子2给出的TSP问题模型。由解空间D={x{0,1}n(n-1)}，可以定义它的一种邻域为：启发式算法k为一个正整数。TSP问题解的另一种表示法为D={S=(i1,i2,…,in)是1,2,…,n的一个排列}9邻域概念启发式算法TSP问题解的另一种表示法为D={S=(i1,i2,…,in)是1,2,…,n的一个排列}可以定义它的邻域映射为2-opt

7、，即S中的两个元素对换。如4个城市的TSP问题，当S=(1,2,3,4)时，N(S)={(2,1,3,4),(3,2,1,4),(4,2,3,1),(1,3,2,4),(1,4,3,2),(1,2,4,3)}.类似可定义k-opt(k2)10局部最优与全局最优启发式算法若s*满足f(s*)()f(s),其中sN(s*)F,则称s*为f在F上的局部(local)最小（最大）解。若s*满足f(s*)()f(s),其中sF,则称s*为f在F上的全局(global)最小（最大）解。11启发式算法定义一个基于直观或经验构造的算法，在可接受的花费（计算时

8、间、占用空间等）下给出待解决问题每一个实例的一个可行解，该解与最优解的偏离程度不一定能预计。启发式算法是一种技术，使在可接受的计算开销内寻找最好的解，但不一定能保证所得解的可行性和最优性，甚至多数情况下，无法给出所得解同最优解的近似程度。启发式算法12近似算法定义记问题A的任何一个实例I的最优解和启发式算法H解的目标值分别为zopt(I)和zH(I),若对某个正数0，有

9、zH(I)-zopt(I)

10、

11、zopt(I)

12、，IA则称H是A的近似算法。启发式算法13背包问题的贪婪算法1）将物品以ci/ai（单位体积的价值）由大到小的顺序排列，不妨把排列

13、记为{1,2,…,n},k:=1;2）若，则xk=1