725 空气滤清器连接板冲孔、冲槽、落料复合模设计(有cad图+文献翻译)
725 空气滤清器连接板冲孔、冲槽、落料复合模设计(有cad图+文献翻译),725,空气滤清器连接板冲孔、冲槽、落料复合模设计(有cad图+文献翻译),空气滤清器,连接,冲孔,复合,设计,cad,文献,翻译
2011届毕业设计 材 料 系 、 部: 机械工程系 学生姓名: 刘林飞 指导教师: 和道 职 称: 讲师 专 业: 材料成型及控制工程 班 级: 材料成型0704 学 号: 212070406 2011 年 6 月湖南工学院毕业设计(论文)工作中期检查表题目空气滤清器连接板冲孔、冲槽、落料复合模设计学生姓名刘林飞班级学号070426专业材料成型及控制工程指导教师填写学生开题情况学生调研及查阅文献情况毕业设计(论文)原计划有无调整学生是否按计划执行工作进度学生是否能独立完成工作任务学生的英文翻译情况学生每周接受指导的次数及时间毕业设计(论文)过程检查记录情况学生的工作态度在相应选项划“”认真一般较差尚存在的问题及采取的措施:指导教师签字: 年 月 日系部意见: 负责人签字:年 月 日湖南工学院2011届毕业设计(论文)指导教师审阅表 系:机械工程系 专业:材料成型及控制工程 学生姓名刘林飞学 号212070426班 级成型0704专 业材料成型及控制工程指导教师姓名和道课题名称空气滤清器连接板冲孔、冲槽、落料复合模设计评语:(包括以下方面,学习态度、工作量完成情况、材料的完整性和规范性;检索和利用文献能力、计算机应用能力;学术水平或设计水平、综合运用知识能力和创新能力;)是否同意参加答辩:是 否指导教师评定成绩分值:指导教师签字: 年 月 日湖南工学院毕业设计(论文)评阅教师评阅表题目空气滤清器连接板冲孔、冲槽、落料复合模设计学生姓名刘林飞班级学号070426专业材料成型及控制工程评阅教师姓名职称工作单位评分内容具 体 要 求总分评分开题情况调研论证能独立查阅文献资料及从事其他形式的调研,能较好地理解课题任务并提出实施方案,有分析整理各类信息并从中获取新知识的能力。10外文翻译摘要及外文资料翻译准确,文字流畅,符合规定内容及字数要求。10设计质量论证、分析、设计、计算、结构、建模、实验正确合理。35创新工作中有创新意识,有重大改进或独特见解,有一定实用价值。10撰写质量结构严谨,文字通顺,用语符合技术规范,图表清楚,书写格式规范,符合规定字数要求。15综合能力能综合运用所学知识和技能发现与解决实际问题。20总评分评阅教师评阅意见评阅成绩总评分20%评阅教师签名日期湖南工学院毕业设计(论文)答辩资格审查表题 目空气滤清器连接板冲孔、冲槽、落料复合模设计学生姓名刘林飞学 号212070426专 业材料成型及控制工程指导教师和道内容综述(对毕业设计或论文的研究步骤和方法、主要内容及创新之处进行综述,提出答辩申请): 申请人签名: 日期:资 格 审 查 项 目是否01工作量是否达到所规定要求02文档资料是否齐全(任务书、开题报告、外文资料翻译、定稿论文及其相关附件资料等)03是否完成任务书规定的任务04完成的成果是否达到验收要求05是否剽窃他人成果或者直接照抄他人设计(论文)指导教师签名: 毕业设计(论文)答辩资格审查小组意见:符合答辩资格,同意答辩 不符合答辩资格,不同意答辩审查小组成员签名: 年 月 日注:此表中内容综述由学生填写,资格审查项目由指导教师填写。湖南工学院2011届毕业设计(论文)答辩及最终成绩评定表 系:机械工程系 专业:材料成型及控制工程学生姓名刘林飞学号212070426班级成型0704答辩日期课题名称空气滤清器连接板冲孔、冲槽、落料复合模设计指导教师成 绩 评 定分值评 定小计 课题介绍思路清晰,语言表达准确,概念清楚,论点正确,实验方法科学,分析归纳合理,结论严谨,设计(论文)有应用价值。30答辩表现思维敏捷,回答问题有理论根据,基本概念清楚,主要问题回答准确大、深入,知识面宽。必答题40自由提问30合 计100答 辩 评 分分值:答辩小组长签名:答辩成绩a: 40指导教师评分分值:指导教师评定成绩b: 40评阅教师评分分值:评阅教师评定成绩c: 20最终评定成绩: 分数: 等级:答辩委员会主任签名: 年 月 日说明:最终评定成绩a+b+c,三个成绩的百分比由各系自己确定,但应控制在给定标准的10左右。零件号材料T10A毛坯重量编制机械加工工艺过程综合卡片零件名称冲孔凸模生产类型毛坯种类指导工序工序名称工序说明机床夹具刀具量具切削深度mm进给量mm/r主轴转速r/min切削速度m/min时间定额min5下料根据零件图尺寸,下料F20360mm10车外圆面车右端面,粗车外圆柱面尺寸:F10.6324,F14.4318,F1735,调头车外圆F638CA6140三爪卡盘外圆车刀游标卡尺4.70.8150031.415检验20热处理按技术要求热处理至HRC586225精车精车F10.15mm至尺寸,并车出斜度309CA6140三爪卡盘外圆车刀游标卡尺0.170.8150016.630磨外圆面磨F14至尺寸外圆磨床三爪卡盘砂轮游标卡尺0.20.00560027.135钳工去除工艺柄40检验湖南工学院毕业设计(论文)开题报告 题目空气滤清器连接板冲孔、冲槽、落料复合模设计学生姓名刘林飞班级学号212070426 专业材料成型及控制工程一、课题的目的和意义:冲压加工作为一个行业,在国民经济的加工行业中占有重要地位。根据统计,冲压件在各个行业中均占有相当大的比重,尤其在汽车、电机、仪表、军工、家电等方面所占比重更大。采用冲压模具生产零部件,具有生产效益高,质量好,成本低,节约能源和原料等一系列优点,它以成为当代工业生产中的重要手段和工艺发展方向。模具工业已被我国正式确定为基础产业,并在“十五”中列为重点扶持产业。从1997年开始,我国模具工业产值超过了机床工业产值。因此模具对国民经济和社会发展起着举足轻重的作用。对于冲压生产而言,单工位模具结构单一,生产效率低,而且钣金零件不能过于复杂,否则就需要多副单工位模具才能实现。如果采用级进模进行生产,就可以改变这些缺点。标志冲模技术先进水平的精密多工位级进模,具有生产周期短、用操作人员少、精度高、寿命长和生产效率高等特点,是我国重点发展的精密冲模。本次毕业设计,指导老师给我安排的是空气滤清器连接板冲孔、冲槽、落料复合模设计。通过对零件进行工艺分析,我们可以了解到零件材料为加工性能较好的45号钢,零件的主要加工工序主要有:落料、冲孔、冲槽等。通过结合大学所学的专业知识,参考文献资料,以及指导老师指导,我初步理清了本次设计的基本思路,掌握了有关毕业设计的基本方法。二、文献综述1、中国冲压模具的发展现状中国冲压模具的发展现状改革开放带了我国的经济进入高速发展的时期,模具的市场的需求量也进一步的增加。模具行业也一直以15%左右的增速再发展。因此带来的模具工业企业的所有制成分的巨大变化,一些国有专业模具厂也如雨后春笋般的建立起来,同时也带来了以集体、独资、私营和合资等形式的快速发展。赋有“模具之乡”的浙江宁波和黄岩地区是现今我国规模最大的两个地方;广东地区也渐渐掀起了开建模具厂的浪潮;其中科龙、康佳等集团纷纷建立了自己的模具制造中心;中外合资或是外商独资形式的模具企业现也有几千家。近年许多模具企业加大了用于技术进步的投资力度,将技术进步视为企业发展的重要动力。一些国内模具企业已普及了二维CAD,并陆续开始使用UG、Pro/Engineer、I-DEAS、Euclid-IS等国际通用软件,个别厂家还引进了Moldflow、C-Flow、DYNAFORM、Optris和MAGMASOFT等CAE软件,并成功应用于冲压模的设计中。以汽车覆盖件模具为代表的大型冲压模具的制造技术已取得很大进步,东风汽车公司模具厂、一汽模具中心等模具厂家已能生产部分轿车覆盖件模具。此外,许多研究机构和大专院校开展模具技术的研究和开发。经过多年的努力,在模具CAD/CAE/CAM技术方面取得了显著进步;在提高模具质量和缩短模具设计制造周期等方面做出了贡献。例如,吉林大学汽车覆盖件成型技术所独立研制的汽车覆盖件冲压成型分析KMAS软件,华中理工大学模具技术国家重点实验室开发的注塑模、汽车覆盖件模具和级进模CAD/CAE/CAM软件,上海交通大学模具CAD国家工程研究中心开发的冷冲模和精冲研究中心开发的冷冲模和精冲模CAD软件等在国内模具行业拥有不少的用户。虽然中国模具工业在过去十多年中取得了令人瞩目的发展,但许多方面与工业发达国家相比仍有较大的差距。例如,精密加工设备在模具加工设备中的比重比较低;CAD/CAE/CAM技术的普及率不高;许多先进的模具技术应用不够广泛等等,致使相当一部分大型、精密、复杂和长寿命模具依赖进口。2、中国冲压模具的发展方向模具技术的发展应该为适应模具产品“交货期短”、“精度高”、“质量好”、“价格低”的要求服务。达到这一要求急需发展如下几项:(1)全面推广CAD/CAM/CAE技术模具CAD/CAM/CAE技术是模具设计制造的发展方向。随着微机软件的发展和进步,普及CAD/CAM/CAE技术的条件已基本成熟,各企业将加大CAD/CAM技术培训和技术服务的力度;进一步扩大CAE技术的应用范围。计算机和网络的发展正使CAD/CAM/CAE技术跨地区、跨企业、跨院所地在整个行业中推广成为可能,实现技术资源的重新整合,使虚拟制造成为可能。(2)高速铣削加工国外近年来发展的高速铣削加工,大幅度提高了加工效率,并可获得极高的表面光洁度。另外,还可加工高硬度模块,还具有温升低、热变形小等优点。高速铣削加工技术的发展,对汽车、家电行业中大型型腔模具制造注入了新的活力。目前它已向更高的敏捷化、智能化、集成化方向发展。(3)模具扫描及数字化系统高速扫描机和模具扫描系统提供了从模型或实物扫描到加工出期望的模型所需的诸多功能,大大缩短了模具的在研制制造周期。有些快速扫描系统,可快速安装在已有的数控铣床及加工中心上,实现快速数据采集、自动生成各种不同数控系统的加工程序、不同格式的CAD数据,用于模具制造业的“逆向工程”。模具扫描系统已在汽车、摩托车、家电等行业得到成功应用,相信在“十五”期间将发挥更大的作用。 (4)电火花铣削加工电火花铣削加工技术也称为电火花创成加工技术,这是一种替代传统的用成型电极加工型腔的新技术,它是有高速旋转的简单的管状电极作三维或二维轮廓加工(像数控铣一样),因此不再需要制造复杂的成型电极,这显然是电火花成形加工领域的重大发展。国外已有使用这种技术的机床在模具加工中应用。预计这一技术将得到发展。(5)提高模具标准化程度我国模具标准化程度正在不断提高,估计目前我国模具标准件使用覆盖率已达到30%左右。国外发达国家一般为80%左右。(6)优质材料及先进表面处理技术选用优质钢材和应用相应的表面处理技术来提高模具的寿命就显得十分必要。模具热处理和表面处理是否能充分发挥模具钢材料性能的关键环节。模具热处理的发展方向是采用真空热处理。模具表面处理除完善应发展工艺先进的气相沉积(TiN、TiC等)、等离子喷涂等技术。 (7)模具研磨抛光将自动化、智能化模具表面的质量对模具使用寿命、制件外观质量等方面均有较大的影响,研究自动化、智能化的研磨与抛光方法替代现有手工操作,以提高模具表面质量是重要的发展趋势。 (8)模具自动加工系统的发展这是我国长远发展的目标。模具自动加工系统应有多台机床合理组合;配有随行定位夹具或定位盘;有完整的机具、刀具数控库;有完整的数控柔性同步系统;有质量监测控制系统。我国冲压模具与发达国家企业之间的差距不小,因此要发挥整体优势和综合竞争力,要加强统筹协调、完善合作机制,创造性地工作。也需要加大对模具相关专业人才的综合素质培训投入。2、设计内容与步骤(1)冲压零件的工艺性分析:材料的冲压性能分析、结构形状工艺性分析、尺寸的工艺性分析、精度的工艺性分析等。(2)冲压工艺的总体方案的分析和确定:单工序模方案、复合模方案、级进模方案的对比,最终确定的方案;(3)基于所确定的总体方案,进行排样设计:拟定工位数、各工位的冲压性质和冲压顺序,绘制板料的排样图;(4)基于总体方案和排样方案,进行工艺计算,如:凸凹模尺寸及偏差、间隙、变形力、压力中心、卸料力等计算;(5)模具关键结构的方案设计:凸凹模结构形式、导向、导料、定位、卸料等;(6)模具总体结构设计与确定:基于上述内容,设计并确定模具总体结构,描述模具的工作原理和工艺动作,并绘制二维装配图和相应的三维图;(7)选择合理的冲压设备(考虑设备吨位与变形力的吻合、冲裁封闭高度与设备装模高度的吻合、模具的平面尺寸与设备工作台面尺寸的吻合等);(8)进行模具零件的详细设计:确定模具中的标准件(联结零件:螺钉、销钉、弹性元件等)的型号和数量,对模具中的非标准件进行详细的结构尺寸设计,绘制相应的二维零件图;(9)编制模具中主要零件的制造工艺方案和加工方法;(10)撰写设计说明书;(11)所有设计文档、资料的整理、收尾、答辩。3、绘图任务(1) 模具总装配图(2) 模具零件图(3) 模具总成三维图(可选)(4) 模具主要零件三维图(可选)四、设计过程进度计划(1)第五周:完成以上设计内容中的“1-2”(2)第六周:完成以上设计内容的“3-5”(3)第七八周:完成以上设计内容的“6-7”(4)第九十周:完成以上设计内容的“8”(5)第十一、十二周:完成以上设计内容中的“9”(6)第十三、十四周:完成以上设计内容中的“10”(6)第十五周:完成以上设计内容中的“11”指导教师批阅意见 指导教师(签名): 年 月 日注:可另附A4纸湖南工学院毕业设计(论文)工作中期检查表题目空气滤清器连接板冲孔、冲槽、落料复合模设计学生姓名刘林飞班级学号070426专业材料成型及控制工程指导教师填写学生开题情况学生调研及查阅文献情况毕业设计(论文)原计划有无调整学生是否按计划执行工作进度学生是否能独立完成工作任务学生的英文翻译情况学生每周接受指导的次数及时间毕业设计(论文)过程检查记录情况学生的工作态度在相应选项划“”认真一般较差尚存在的问题及采取的措施:指导教师签字: 年 月 日系部意见: 负责人签字:年 月 日湖南工学院2011 届毕业设计(论文)课题任务书系: 机械工程系 专业: 材料成型及控制工程指导教师和道学生姓名刘林飞课题名称空气滤清器连接板冲孔、冲槽、落料复合模设计内容及任务设计图纸模具总装图一张全部模具零件图纸(其中至少有一张电脑绘图)所有图纸折合成0号图不得少于3张。设计说明书1、资料数据充分,并标明数据出处。2、计算过程详细、完全。3、公式的字母含义应标明,有时还应标注公式的出处。4、内容条理清楚,按步骤书写。5、说明书要求用计算机打印。6、设计说明书按要求格式独立撰写,不少于12000字。自选一个重要模具零件编制加工工艺路线,进行相关的计算,并编制加工工艺卡和工序卡。翻译一篇本专业外文文献(10000个以上印刷符号),并附译文。拟达到的要求或技术指标1、保证规定的生产率和高质量的冲压件的同时,力求成本低、模具寿命长。2、设计的冷冲模必须保证操作安全、方便。3、冲模零件必须具有良好的工艺性,即制造装配容易、便于管理。4、便于搬运、安装、紧固到冲床上并且方便、可靠。5、保证模具强度前提下,注意外形美观,各部分比例协调。进度安排起止日期工作内容备注2周(2.283.11)毕业调研2周(3.143.25)集中实习10周(3.286.3)毕业设计1周(6.66.10)毕业答辩主要参考资料、冷冲压工艺及模具设计刘心治主编重庆大学出版社、冲压工艺及模具设计万战胜主编 铁道出版社、冲模设计 吉林人民出版社、实用冲压技术 机工出版社、冷冲压及塑料成型工艺与模具设计资料 机工出版社、模具设计与制造简明手册 冯炳尧等编 上海出版社7、冲压工艺模具设计实用技术郑家贤编机械工业出版社8、实用板金冲压工艺图集梁炳文主编机械工业出版社9、几何量公差与检测甘永立主编上海科学技术出版社10、机械制造专业英语章跃主编机械工业出版社教研室意见年 月 日系主管领导意见年 月 日离散应用数学离散应用数学98(1999) 121-130最小化模式下料问题科林麦克迪尔米德统计部门,牛津大学,南公园路一号,牛津大学OX1 3TG,英国收稿于1997年10月21日,接受于1999年2月8日摘 要在切割存量模式最小化问题,我们希望,以满足尽可能少巨型卷轴卷轴切割各种客户的需求,并进一步减少使用不同的切削模式的数量。我们专注于特殊情况,其中任何两个客户卷轴到一个巨型合适,但没有三事:这个案件的兴趣,部分是因为它是最简单的情况是不平凡的,部分是因为它在实践中可能会出现当一个尝试一个解决方案,以改善迭代。我们发现,该模式最小化问题是强NP难的,即使在这种特殊情况下,当inding最低废液的基本问题是微不足道的。我们的分析主要论点集中在均衡的子集,并提出了涉及亚均衡的启发式搜索方法的方法。 1999 Elsevier科学BV公司保留所有权利。关键词:下料,切割模式;分区; NP难;动态规划1 简介有些材料如纸,可制造性巨无霸卷,这是后来成为更窄辊切,以满足客户的需求。为了减少浪费,应选择切割方式,以尽可能少的使用客机(见4,7,8)。因此,下料问题已基本输入一个正整数j,不同的正整数r1的,., Rn和D1的,.,正整数的DN,以及需要的任务是,以尽可能客机的宽度j的数为满足客户的卷筒宽度里迪需求对每个i = 1 ,.,,全这是其中的经典OR问题之一。它包含了强烈的NP -完全问题三分区:因此即使巨幅大小J外面有一层氮、多项式满足每个客户的卷轴大小国际扶轮扶轮J / 4 J / 2 -看6,p。224。因此我们不能指望在合理时间内总是能找到最优解等问题的。每一次不同的客户卷轴模式是被削减,在切割机的刀需要重新设置。甲由Cn中Goulimis并在第29届欧洲与产业调查研究组1996年3月有关如何找到办法来解决上述料问题,这进一步减少了用于切割不同模式的数量问题 - 见1,2,9 。一般情况下这当然是变得越来越难。为了探讨扩展问题雪上加霜,我们在这里考虑一个特殊的案件中,尽量减少对客机(减少废物),数量基本问题是微不足道的。最小化格局:输入:D1的正整数;的DN。任务:在切割存量问题,即要求I型迪卷轴是,任何两个卷轴到一个巨型做它,但没有三,工业最低废液,进一步减少了使用不同模式的数量。这种特殊的情况是非常有限的部分原因是因为它似乎是最简单的情况是完全不平凡的,部分是因为它可能会在实践中产生的,当一个一个解决方案试图改善迭代的兴趣。例如,如果对目前使用的一些模式集合同意的大型卷轴和difer小卷轴而已,它在任何两个小卷轴左边的大型卷轴的宽度,那么当我们试图重新分配小我们面临的正是这种卷轴的特殊情况16。我们调查模式是否最小化问题还很难在这个特殊的情况,并简要考虑办法找到好的解决办法。很明显,所需要的客机数量最少的是我的di / 2,圆了总需求的一半,它是微不足道的一个相应的最低工业废液。但是,它是多么容易跻身工业废物最小的解决方案,一个能最大限度地降低使用的模式的数量,?对于这个问题的变体在没有三个客户卷轴它变成珍宝,但也有一些对可能不是,它是在1表明,问题是强NP -难问题。下面的定理加强这种不利的结果。定理1:这个问题最小化模式是强NP -难问题。对上述问题的理解关键是一个平衡的一个子集的概念。给定一个家庭d =(d1,dn)的非负整数,表示x(d)的在任何解决方案中使用最少的废物模式的最小数量。还有,另一个平衡的非空的子集 1,n ,如果它能够被分割成两个集合A和B,tA di = 5ieB di。因此,如果 di = 0然后单独设置i是平衡的。让v(d)是最大的数字的平衡子集两两相互无关的。引理1:如果J2i di是偶数,然后x(d)= n - v(d)。如果i di 是奇数,令x(d) = i(d),其中d1从D获得通过增加一个额外的统筹的DN +1 = 1。我们将在下一节中证明这个引理。当与一个模式最小化所面临的问题,我们领导的定理1和引理1以上考虑启发式方法inding亚群平衡的好包装。不幸的是NP -完全甚至是测试,如果一个家庭中的正整数格a1,.,an有一个平衡的一个子集。这就是问题称为弱分区是大卫约翰逊的NP完全列10,其中四分之三的NP完全独立的证据被引用,最早在13。 我们希望工业亚群的平衡好包装,但我们知道这是很难工业最佳包装,的确是很难平衡的工业任何一个子集。自然启发式的方法是反复寻找和删除一个平衡的一个子集,最好是小的。其中寻求一个平衡的一个子集的方法是使用diferencing,这里我们再次取代其diference绝对值两个数字 - 参见5,12,15,17。这种方法目前正在调查中最小的格局16中。另一种方法是使用一个还算快速算法,保证工业均衡的子集或子集的最小平衡:我们会看到,我们可以使用一个简单的动态规划方法来测试,如果有一个平衡的子集,均衡和IND一个最小的子集如果有一个,在伪多项式时间。最小的模式启发式方法更普遍的情况下在降低库存的问题被认为是1,2,9,11。 该论文的其余部分计划如下。在下一节中,我们建立的模式之间的平衡亚群的数量和包装的关系。接下来,我们证明我们的主要结果,这个问题最小化模式是强NP -难问题。在此之后,我们认为briely如何寻找平衡的子集,并inally我们做一些总结性发言。2 模式,学位和平衡套在这一节中,我们将证明引理1,其中涉及的图案编号,包亚群平衡英格斯。最小化的问题可以改写格局在图上。一个模式,涉及卷轴I型和J型卷筒之间将对应顶点顶点vi和vj的边缘。我们将让我们的图,包含在任何顶点循环但不包含多个边缘。给定一个图G =(V,E)对集V = v1,.,v2的顶点,连同非负整数重量的边缘E,我们的家庭W时,顶点加权第六度过度的重量与我们六边事件的总和与任何循环,计数两次。给定一个向量d =(d1. dn)的正整数,我们呼吁d如果每个顶点Vi有两人加权程度地代表公克WA网络。考虑以下问题。学位:输入:积极intergers d1.甚至与dn。任务:工业用尽可能少的边缘一个代表网络。给定一个d组=(d1. dn)的正整数,甚至与我二,有一个度之间的解决方案和模式MINIMI SATION这些自然的对应,特别是最小的边数前者的可能等于 (d)项。引理1:假设di是偶数。设G w是任何代表工作,并考虑为G的K个节点集K表的组成部分。这当然必须有至少k - 1条边,如果它有这个数目,因此是对K树,那么三分之二的顶点着色表明,K是平衡的。因此,在G的边数至少有n减去若干套组成部分的平衡。因此(D)Jsn - 的v(d)。为了证明反向不等式,考虑任何V1.Vn(Ki:i I),其中一个最不均衡。我们将证明,有代表怨恨网络G,W使得图G有组件(Gi:I i)如已设立文基顶点,这些组件是这样,如果文是平衡的,然后是一树基如果没有则Gi是一加一树循环。这将完成该引理的证明。考虑平衡集K,其中分区A U S使得YieA= igBdi国际能源署。我们必须表明,有对T边缘E对K和非负权重,我们一树T,使得对于每一个节点v K时,对事件边的权重之和等于的dv(其中双回路数)。我们使用 K|表感应。如果A或B是空的,结果是微不足道的,因为我们必须为每个V光那假设A和B都是非空的dv = 0。选择任何一个和b阿B和不失一般性假设大分贝。减少大的分贝。现在K表 B的是平衡的,我们可以感应工业适当的加权树。然后加入与体重分贝边缘抗体。最后,考虑一个集K这是不均衡的,但就是这样,相应的要求和是偶数。如上所述,我们可以随时更换了使用成本的一个边缘的diference两个要求。因此,我们能满足所有,但一用边缘形成一个对K树需求,然后添加一个循环结束的组成部分。3 最小化模式是强NP -难在本节中,我们证明定理1,这个问题最小化模式是强NP -难问题。总结三(或舒尔三)是三,这样的两个之和等于第三个不同的整数集合。下面的问题可以得到更充分的描述,总结成独特的整数分区的三倍作为。总结三元输入:S1.S3n不同的正整数。问:能否输入三元分割成总结?这个问题类似于数值匹配与目标款项,加里和Johnson 6,第224,但额外的(令人惊讶的麻烦),条件是涉及的人数必须是不同的。引理2:问题总结三元是强NP -完全的。本节的大部分将用于证明上述引理,但首先,让我们看到,它会产生定理1。证明定理1(假设引理2):我们给一个总结,学位strightforward三倍,多项式时间减少。考虑一个总结三元上述实例。以 =作为学位实例(2s1 .2s3n)。由于硅是不同的正整数,也有规模不小于3套平衡。因此,(dHence由引理1,第十章x(d) 2n与x(d)为2n =当且仅如果s1 .s3n可分为总结三倍现在考虑的问题总结三倍,这显然是在NP。我们将证明它是强NP -通过给从NP -完全问题限制X3C减少完成,下述,总结每个三元组在O(n3)的。限制X3C:输入:一组第三季度的X元素和一个三元组集合C在十,这样每个X的 元素完全相同3三元载。问:可以划分为三元X是在C?引理3: 限制X3C问题是NP完全的。证明 据了解,这个问题是NP完全问题,如果每个元素被限制在最多3三倍,而不是正好3 - 见加里和Johnson 6,第221。这是很容易对注册整洁的实例X,使每个元素恰好是3的三倍。很明显,我们能坚持,每个元素在2或3的三倍。我们可以在分区中的元素正好两个三元组分为三个区块的大小。对于每个块x,Y,Z,添加新的元素三个x,y,z及x,y,z,x,y,z,x1, y,z,x1,y,z。调用新的实例X,C的。显然,每个X的元素是完全相同三三元在C;和X可以被划分在C到三倍,如果有仅当X可以被划分为三元在C。引理2: 考虑一个实例X,C的限制X3C,其中| X = = CI=3q。季度全令Y = X x 1 ,., 7。我们将建设一个扩大在Y D的收集,包含三元使得X可分为三元在C分区,当且仅当y可划分为D中三元,接着我们将构造一个实例(秒(y)的:你们的Y总结三倍,其中每个尺寸S(y)的异O(n2),),这样的总结恰恰三倍对应的三元组在D形成一个二分图G =(C,X,E)的顶点C部及X和顶点窄隙室和X GX的相邻(即边发射GE)的正是由于当x 吨G中的每个顶点度是三,我们可以在多项式时间内找到一个合适的3边染色:E - 1,2,3。现在,我们每个元素x GX的分割成三份(x,1),(x,2)和(x,3)。鉴于一特里普尔T = x,y,z气相色谱,令T是三重T= (x,KTx),(y,(Ty),(z,(Tz)观察,在三T的分子具有不同的第一坐标(X),以及独特的第二个坐标(必须是1,2,3),而C=(T:TG)分区集X x 1,2,3。接着,每个X光霞,让Fx的是集合组成的四个三元(x,1),(x,4),(x,5),(x,3),(x,4), (x,5),(x,2),(x,6),(x,7)和(x,3),(x,6),(x,7)。设D是由碳的收集与所有的X 十,因此D包含在集合在一起Fx的三元| | +4 | x |= 5n的三倍。如果某些子集合的D是Y的分区,然后对每个x G X的时候,恰恰的要素之一(x,1),(x,2),(x,3)不包括由三元组在D东经外汇,因此必须由在D东经企业所得税三倍以下方便,这包括X可以被划分在C到三倍,当且仅当y划分可分为三元在D这样就完成了施工红外警戒的一部分。下一步,我们将看到如何分配尺寸S(y)对每个元素y戈瑞以便在Y元素的总结三元正是在D的三元组,我们将使用一个界定差不多的K -明智的独立随机变量的家庭小样本空间。设1 = 3 log2 n+10,令t = 2n1,令k = 91,让8 = 2。有Q的一个子集0,1,大小2(1 + 0(1)K的:如果一个点的合作=(ro1 .,cot)是随机挑选的统一Q,则,., cot)的是8距离的K -明智的独立,见3。今后这类一套Q可以(明确)在多项式时间建成北界。给定一个点合作宾馆,对每个i = 1 ,., 2n个,让$ = $(co)是非负,teger二进制扩展coy。当一个点co=(co1,., cot)的采收有限公司。从Q随机均匀,然后S1.,.S2n是随机变量,以价值观在0,1 ,., N - 1个,其中N = 2Z,它们具有以下属性。对于任何集成电路与IC1 .2n 与0| 11 69,和任何集合0,1 ,., N - 我们:I I)G E) - |E| /NI/| 61 / 2:现在,我们可以定义元素的大小为我们总结三元原审(年)。为清楚起见,我们将写的(X,1),而不是秒(X,1)等。给定一个采样点的合作宾馆,对每个i = 1 ,., n我们设S(xi,1)= 2S2i - 1(co)+ 2N个和S(xi,2)= 2S2i(m)+ 2N。设x G X,假设使(x,3)是在三T Cwhere T公司还包含(X,1)和(x ,2)。然后我们设S(x,3)=s(x,1)+ s(x,2)( 4N)。这个定义的(x,i)为每个X G X和iG1,2,3。现在,对于每个x G X的,设S(x,4)=(s(x,1)+s(x,3)/ 2s(x,5)=(- S的(x,1)+ S(x),1)/ 2s(x,6)=(d(x,2)+s(x,3)/ 2和S(x,7)=(- S(x,2) +s(x,3)/ 2。现在我们已经定义了一个正整数的大小为每个Y戈瑞的(y)和D中的每个三是始终总结。让BCQ公司是坏的情形,或者因为你们的价值之(y)的失败是不同的,或一些较D组其他三是总结。我们将表明,P(B)“1。它会跟有一个采样点的合作 Q b,和我们能找到这样一个由穷举搜索多项式时间点。这将完成该引理的证明。为了证明P(B)“1,它足以让我们假设随机变量的S1,S2n正是9明智的每个独立的均匀分布于0,1,N - 1,然后,以证明P(B)“1 / 2。观察,从s的定义(y)的,为每个Y有一个向量a(y)的e - 1,0,1,2 2n个,大小为支持最多3,使得s(y)的,保险业监督(y)的;是一个常数(即不依赖于合作)。让y1和y2是Y的不同元素,让a=a(y1)a(y2)。这是很容易看到,a是一个非零整数大小为支持最多6个载体,并有一个常数c使得s(y1)=s(y2)的当且仅当易=角但是,这最后事件的概率至多为1 /全因此,概率为你们的价值之(y)的并不都是最明显的是在 2N6同样,对于我们可能会说不需要的三倍。让日y1,y2和y3 的是不同的元素,形成一个不考虑在D事件的s(y1)+s(y2)=s(y3)。设a =a(y1)+a(y2)=s(y3)。然后,一个有规模的支持最多9,并有一个常数c使得s(y1)+s(y2)=s(y3)当且仅当易=角我们断言向量a是非零。然后,它将按照三倍的概率并不一定是在D总结至多()3 6 ;,因此P(B)6(72i0nfn)“1 / 2,根据需要。它仍然只是建立上述索赔。对于每一个元素y =(x i)e ,让n1(y)= x和7i2(y)= i,记Yia(y)i的由c(y)。假设a = 0时:我们必须获得矛盾。请注意:第一,如果7i2(y)= 3,那么r(y)= 4。因此,既不氮气,也不7i2(y2)的可以等于3,因为我们不是让Yiai“4 - ff(y3) 0。现在假设氮气(y2)的 1,2,这是ff(y1)= 2。那么C(Y2)的必须是1或2。我们认为这两种情况。(一) 首先假设的c(y2)= 1。然后,cr(y3)= 3。现在a(y1的只有一个非零统筹2,a(y2)的有-1,1,1和a(y3)有1,1,1。然后的n1(y1)= n1(y2)= n1 (y2)和特里普尔T =(y1 y2 y3)isinD,矛盾。(二) 现在假设r(y2)= 2。然后,r(y2)= 4。现在a(y1有一个2,(y2)的有1个2和a(y3)有2,2。同样的三重性T D,一个矛盾。现在我们已经表明,n2(y1)的e 1,2,3,同样y2。因此,这两个n2(y1)和7i2(y2)在4,5,6,7。因此ff(y1)和cr(y2)的are1or3,cr(y2)is2或4。首先假设ff(y1)= C(y2)= 1,所以C(y3)= 2。然后两个a(y1)和a(y2)的有非零统筹-1 1 1和a(y3)有2。但接下来a(y1)和a(y2)的必须具有相同的支持。接下去的n1(y1)= n1(y2),这是不可能的。不失一般性,我们现在可以假设ff(y1)= 1和“r(y2)= 3。然后,r(y1)= 4,和a(y1)的有非零协调-1,1,1,a(y1)有1,1,1,和a(y3)有2,2。然后,我们再一次工业a(y1)和a(y2)的必须具有相同的支持,等的n1(y1)= n1(y2)= 1(y3)。但现在,三T是在D,一对矛盾。4 寻找平衡的子集这是一个NP完全测试,如果一个家庭中格A1 ,., 可持续的竞争整数的POS机一有一个平衡的一个子集,但我们仍然可能希望为亚群平衡的格局中搜索到最小某些启发式方法。在本节中,我们看到,一个简单的基于动态规划的方法就能解决的伪多项式时间等问题。红外警戒看到我们如何测试,如果有一个平衡的一个子集,如果这样工业之一(另外两个最小相应的总和)在O( 5 iai)的步骤。之后,我们将看到如何找到一个平衡的最小的子集,在O(n2J iai)的步骤。这不是明显的,这些算法将在一个最小化的启发式方法具有更好的模式。让s0=5 0 / 2。对于每个S = 0,1 ,., S0的,而且每个j = 0,1 ,., n,设集f(s,j)为T。如果有一个相应和S子集,让集f(s,j)的平等F,否则。则f(0,j)的每个j = T为= 0,1 ,., n,且集F(S,0)=每次的F = 1 ,., S0的。我们可以计算所有的值集f(0,j)在反过来,在O(1)每个值的步骤,如下所示。为s = 1 ,.,对于j = 1 .n s0f(s,j) f(s,j - 1)V f(s - aj,j - 1)。(如果s 0,我们解释集f(s,j)a s F)如果在上述复发,这是从来没有的情况是,在右边两个术语是T,那么就没有平衡的一个子集。但假设这种情况确实存在,而且我们第一次见面是在s0和j0。那么有两种不同的亚群的相应和 A和B(一j0和一个不包含)。此外A和B必须是不相交的,由s0的极小。很明显,我们可以发现这样集合A和B很快,他们的联盟是需要平衡的设置。现在假设我们希望工业一个最小的平衡,如果有一子。我们描述动态规划的需要O(n2J iai)的步骤为基础的方法。和以前一样,让s0= iai / 2。对于每个s = 0,1 ,.,s0的,而且每个J型,K和K = 0,1 ,., 6 ,让集f(s,j,k)为T,如果有一个大小最多K表的一个子集与对应和s,让集f(s,j,k),否则等于F。然后再次发生f(s,j,k)=f(s,j - 1,k)V f(s - flj,j - 1,k - 1)再加上适当的边界条件,使我们能够确定的所有值在O集f(s,j,k)O(1) 每个值的步骤。对于每个S = 1,s0的是让作为一个子集最小尺寸1,n的相应和S如果有这样的一个子集,让为as= 0,如果不是;,让旅馆是第二小的尺寸一个子集1 . n s如果至少有两个这样的子集,让bs= 0,如果没有。我们已经看到,我们可以计算出所有值集f(s,j,k)inO(n2s0)步骤。从这些值集f(s,j,k),我们可以计算出在相同的约束,因为所有的价值和BS,内容如下。要计算的,注意,如果f = 0的(s,N组,n)= F和如果没有则因为是最小的k,使得集f(s,n,k)=T现在假设as= 0,考虑如何计算学士学位。请注意,如果集f(s,j,k)= T接着我们可以找到一个子集1,j大小至多k与相应和S透过回溯复发。我们也可以说,如果有多个这样的子集检查,如果再发生在右侧,如果过了相应的集f(s,n,n)(我们知道的是T)这两个术语吨有一个独特的解决方案,然后bs= 0。否则,bs是最K,使得相应的f(s,n,k)有一个以上的解决方案。如果bs当时的不可能有平衡的一个子集0。假设现在至少有一个非零值学士学位,并设T是一个值之比达到最小为+ BS上旅馆所有的S = 0。让我们在与Bt是每个T和相应的金额,这样独特的套装| AT= | 转Bt =胜。 (我们可以找到这样集快。)以下的索赔将完成我们的证明。索赔:该套在与Bt是不相交的,并在u =转Bt CT是最小的平衡设置证明索赔:假设在满足不同的集合和Bt。记的在 Bt基因的总和美国那么这也是转Bt和在。但现在金+不at+bt= | Ct|。5 结束语我们已经看到,即使是在削减库存问题非常有限的情况下,它是强NP -难,尽量减少使用不同模式的数量,因此,我们不能期望能够解决伪多项式时间等问题,即使。关键的概念,是一个平衡的子集,我们被带往亚群平衡的考虑包装启发式,从而考虑寻求这种子集NP难问题。6 如需进一步阅读以下参考,也是读者所关心的:14。致 谢我非常感谢其他参与在红外警戒中讨论的研究组成员。参考文献1 C. Aldridge, J. Chapman, R. Gower, R. Leese, C. McDiarmid, M. Shepherd, H. Tuenter, H. Wilson, A.Zinober, Pattern Reduction in Paper Cutting, Report of the 29th European Study Group with Industry,University of Oxford, March 1996.2 J.M. Allwood, C.N. Goulimis, Reducing the number of patterns in the 1-dimensional cutting stockproblem, Internal Report of Control Section, Electrical Engineering Department, Imperial College, 1988.3 N. Alon, O. Goldreich, J. Hastad, R. Peralta, Simple constructions of almost k-wise independent randomvariables, Random Structures and Algorithms 3 (1992) 289-304.4 V. Chvatal, Linear Programming, Freeman, San Francisco, 1983, pp. 195-212.5 E.G. Coffman, G.S. Lueker, Probabilistic Analysis of Packing and Partitioning Algorithms, Wiley, New York, 1991.6 M.R. Garey, D.S. Johnson, Computers and Intractability, Freeman, San Francisco, 1979.7 P.C. Gilmore, R.E. Gomory, A linear programming approach to the cutting-stock problem, Oper. Res.9 (1961) 849-859.8 P.C. Gilmore, R.E. Gomory, A linear programming approach to the cutting-stock probelem - Part II,Oper. Res. 11 (1963) 863-888.9 C.N. Goulimis, Optimal solutions for the cutting stock problem, European J. Oper. Res. 44 (1990)197-208.10 D. Johnson, The NP-completeness column: an ongoing guide, J. Algorithms 3 (1982) 182-195.11 R.E. Johnston, Rounding algorithms for cutting stock problems, J. Asian-Pacific Oper. Res. Soc. 3(1986) 166-171.12 N. Karmarkar, R.M. Karp, The differencing method of set partitioning, Technical Report UCB/CSD82/113, Computer Science Division (EECS), University of California, Berkeley, 1982. 13 A. Shamir, On the cryptocomplexity of knapsack systems, Proc. 11th Ann. ACM Symp. on Theory ofComputing, 1979, pp. 118-129.14 P.E. Sweeney, E.R. Paternoster, Cutting and packing problems: a categorized, application-orientatedresearch bibliography, J. Oper. Res. Soc. 43 (1992) 691-706. 15 L-H. Tsai, The modiied diferencing method for the set partitioning problem with cardinality conditions,Discrete Appl. Math. 63 (1995) 175-180.16 H. Tuenter, Personal communication, 1996.17 B. Yakir, The diferencing algorithm LDM for partitioning: a proof of a conjecture of Karmarkar andKarp, Math. Oper. Res. 21 (1996) 85-99.16
收藏