组合优化问题及算法.ppt_第1页
组合优化问题及算法.ppt_第2页
组合优化问题及算法.ppt_第3页
组合优化问题及算法.ppt_第4页
组合优化问题及算法.ppt_第5页
已阅读5页，还剩29页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、、MATHEMATICA MODEL、制作：功勋、组合优化问题及其算法、-2-、组合优化是通过数学方法的研究寻找离散事件的最佳组织、研究的问题，信息技术、 可以使用数学模型将此问题描述为引言。 其中，d表示由有限个点组成的集合。-3-、1. 0-1背包问题设置一个容积为b的背包，n个体积分别为ai (I=1，2，2，n )，价值分别为ci (I=1，2，n )。 一些例子，-4-，2 .旅行者问题(TSP，traveling salesman problem )一个商人想向n个城市销售商品，在两个城市I和j之间的距离是dij，商人的各城市选择路线，使其恰好走到起点，一些例子3 .受约束的机器调

2、度问题n个加工量di|I=1，2， n的产品在一台机器上加工，机器在第一个时间段的xit=1表示产品I在第t个时间段加工，- 6 5 .二维装箱问题(平面上的成套问题)原料的尺寸大于需求的尺寸，需求的品种尺寸可以不同，最终的目标是在满足需求的基础上，最小化角的垫材。 6 .工厂作业安排问题(job shop scheduling) n个工件，J1，Jn用m台机械M1，M2，Mm加工。 每个工件Ji都有ni工序，Oi1、Oini、第Oij工序的加工时间为pij，必须按工序加工，按工序加工。 一台机器随时最多只能加工一个产品，一个工件不能同时用两台机器加工，如何安排最后完成的工件的完成时间最小？

3、几个例子，-7-，7 .最大截距问题(MCP，Max Cut Problem) 8.图的顶点着色问题(GCP，Graph Colouring Problem) 9.独立集问题(。 排程问题11 .分区问题12 .布局问题11 .布局问题上述问题都是NP-hard问题。一些实例-8-、邻近度概念被称为组合优化问题(d、f、f )、d上的一种映射： N:SD N(S)2D被称为邻近度映射，2D表示d的所有子集配置的集合，并且邻近度结构N(S )取决于问题决定性变量的表示启发式算法，-9-，邻域概念，例如上例2中所示的TSP问题模型。 根据求解空间d=x 0，1 n (n1)，邻近区域可以定义为：启

4、发式算法，k可以定义为正整数。 TSP问题解的另一个表现是，如D=S=(i1，i2，in )为1，2，n的一个数组，-10-，邻近概念，启发式算法，TSP问题解的另一个表现是d=s的4个城市的TSP问题那样，s=(1，2，3，4 ) 如果s*满足f(s*)()f(s )，其中sF，则s*被称为f上的全局(全局)最小(最大)解。、-12-、启发式算法、-13-、启发式算法、-14-、背包问题的贪婪算法1 )将物品按照ci/ai (每单位体积的价值)从大到小的顺序排列，并将排列记作1、2、n也可以2 )，如果是，则将x 否则xk=0，k:=k 1。 在k=n 1时停止。 否则，旋转2). (x1，x2，xn )是贪婪算法得到的解，单位体积的价值越大，越优先是贪婪算法的原则。 启发式算法、-

人人文库> 全部分类> 行业资料 > 信息产业

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论