最优截断切割问题.doc

《数学建模与数学实验(第3版)》配套PPT课件

收藏

资源目录
跳过导航链接。
数学建模与数学实验第3版配套PPT课件.zip
压缩包内文档预览:
预览图 预览图 预览图 预览图 预览图
编号:211097769    类型:共享资源    大小:8.74MB    格式:ZIP    上传时间:2022-05-05 上传人:考**** IP属地:山西
30
积分
关 键 词:
数学建模与数学实验(第3版) 数学 建模 实验 配套 PPT 课件
资源描述:
《数学建模与数学实验(第3版)》配套PPT课件,数学建模与数学实验(第3版),数学,建模,实验,配套,PPT,课件
内容简介:
建模案例:最优截断切割问题一、 问 题从一个长方体中加工出一个已知尺寸、位置预定的长方体(这两个长方体的对应表面是平行的),通常要经过6 次截断切割.设水平切割单位面积的费用是垂直切割单位面积费用的r倍.且当先后两次垂直切割的平面(不管它们之间是否穿插水平切割)不平行时,因调整刀具需额外费用e.试设计一种安排各面加工次序(称“切割方式”)的方法,使加工费用最少.二、 假 设假设水平切割单位面积的费用为r,垂直切割单位面积费用为1;当先后两次垂直切割的平面(不管它们之间是否穿插水平切割)不平行时,调整刀具需额外费用e;第一次切割前,刀具已经调整完毕,即第一次垂直切割不加入刀具调整费用;4每个待加工长方体都必须经过6次截断切割.三、 模型的建立与求解 设待加工长方体的左右面、前后面、上下面间的距离分别为b0 、c0 ,六个切割面分别位于左、右、前、后、上、下,将他们相应编号为M1、M2、M3、M4、M5、M6,这六个面与待加工长方体相应外侧面的边距分a0别为 u1、u2、u3、u4、u5、u6.这样,一种切割方式就是六个切割面的一个排列,共有 种切割方式.当考虑到切割费用时,显然有局部优化准则:两个平行待切割面中,边距较大的待切割面总是先加工. 由此准则,只需考虑 种切割方式.即在求最少加工费用时,只需在90个满足准则的切割序列中考虑.不失一般性,设u1u2,u3u4,u5u6,故只考虑M1在M2前、M3在M4前、M5在M6前的切割方式.1. e=0 的情况 图1 G(V,E) 为简单起见,先考虑e=0 的情况.构造如图的一个有向赋权网络图G(V,E).为了表示切割过程的有向性,在网络图上加上坐标轴 x,y,z,图G(V,E)的含义为: (1)空间网络图中每个结点Vi(xi,yi,zi)表示被切割石材所处的一个状态.顶点坐标xi、yi、zi分别代表石材在左右、前后、上下方向上已被切割的刀数.例如:V24(2,1,2) 表示石材在左右方向上已被切割两刀,前后方向上已被切一刀,上下方向上已被切两刀,即面M1、M2、M3、M5、M6均已被切割.顶点V1(0,0,0) 表示石材的最初待加工状态,顶点V27(2,2,2)表示石材加工完成后的状态. (2)G的弧(Vi,Vj)表示石材被切割的一个过程,若长方体能从状态Vi经一次切割变为状态Vj,即当且仅当xi+yi+zi+1=xj+yj+zj时,Vi(xi,yi,zi)到Vj(xj,yj,zj)有弧(Vi,Vj),相应弧上的权W(Vi,Vj)即为这一切割过程的费用. W(Vi,Vj)=(xj-xi)(bici)+(yj-yi)(aici)+(zj-zi)(aibi)r 其中,ai、bi、ci分别代表在状态Vi时,长方体的左右面、上下面、前后面之间的距离. 例如,状态V5(1,1,0),a5 = a0-u1,b5 = b0-u3,c5 = c0;状态V6(2,1,0) W(V5,V6) (b0-u3)c0 (3)根据准则知第一刀有三种选择, 即第一刀应切M1、M3、M5中的某个面,在图中分别对应的弧为( V1,V2),(V1,V4),(V1,V10). 图G中从V1到V27的任意一条有向道路代表一种切割方式.从V1到V27共有90条有向道路,对应着所考虑的90种切割方式.V1到V27的最短路即为最少加工费用,该有向道路即对应所求的最优切割方式. 实例:待加工长方体和成品长方体的长、宽、高分别为10、145、19和3、2、4,两者左侧面、正面、底面之间的距离分别为6、7、9,则边距如下表: u1u2u3u4u5u66175569r=1时,求得最短路为V1V10V13V22V23V26V27,其权为374 对应的最优切割排列为M5M3M6M1M4M2,费用为374元. 2 e0的情况 当e0时,即当先后两次垂直切割的平面不平行时,需加调刀费e.希望在图1的网络图中某些边增加权来实现此费用增加.在所有切割序列中,四个垂直面的切割顺序只有三种可能情况: 先切一对平行面,再切另外一对平行面,总费用比e=0时的费用增加e. 先切一个,再切一对平行面,最后割剩余的一个,总费用比e=0时的费用增加2e. 切割面是两两相互垂直,总费用比e=0时的费用增加3e. 在所考虑的90种切割序列中,上述三种情况下垂直切割面的排列情形,及在图G中对应有向路的必经点如下表:垂直切割面排列情形有向路必经点情况一 (一)M1M2M3M4(1,0,z),(2,0,z),(2,1,z)情况一 (二)M3M4M1M2(0,1,z),(0,2,z),(1,2,z)情况二 (一)M3M1M2M4(0,1,z),(1,1,z),(2,1,z)情况二 (二)M1M3M4M2(1,0,z),(1,1,z),(1,2,z)情况三 (一)M1M3M2M4(1,0,z),(1,1,z),(2,1,z)情况三 (二)M3M1M4M2(0,1,z),(1,1,z),(1,2,z) z=0,1,2 我们希望通过在图1的网络图中的某些边上增加权, 来进行调刀费用增加的计算,但由于网络图中的某些边是多种切割序列所公用的.对于某一种切割序列,需要在此边上增加权e,但对于另外一种切割序列, 就有可能不需要在此边上增加权e,这样我们就不能直接利用图1的网络图进行边加权来求最短路径. 由上表可以看出,三种情况的情形(一)有公共点集(2,1,z)|z=0,1,2,情形(二)有公共点集(1,2,z)|z=0,1,2.且情形(一)的有向路决不通过情形(二)的公共点集,情形(二)的有向路也不通过情形(一)的公共点集.所以可判断出这两部分是独立的、互补的.如果我们在图G中分别去掉点集(1,2,z)|z=0,1,2和(2,1,z)|z=0,1,2及与之相关联的入弧,就形成两个新的网络图,如图1和2.这两个网络图具有互补性.对于一个问题来说,最短路线必存在于它们中的某一个中. 由于调整垂直刀具为3次时,总费用需增加3e, 故我们先安排这种情况的权增加值e,每次转刀时,给其待切弧上的权增加e.增加e的情况如图2中所示.再来判断是否满足调整垂直刀具为二次、一次时的情况,我们发现所增加的权满足另外两类切割序列.综合上述分析,我们将原网络图G分解为两个网络图1和2,并在指定边上的权增加e,然后分别求出图1和2中从V1到V27的最短路,最短路的权分别为:d1,d2.则得出整体的最
温馨提示:
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
提示  人人文库网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文
本文标题:《数学建模与数学实验(第3版)》配套PPT课件
链接地址:https://www.renrendoc.com/paper/211097769.html

官方联系方式

2:不支持迅雷下载,请使用浏览器下载   
3:不支持QQ浏览器下载,请用其他浏览器   
4:下载后的文档和图纸-无水印   
5:文档经过压缩,下载后原文更清晰   
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

网站客服QQ:2881952447     

copyright@ 2020-2025  renrendoc.com 人人文库版权所有   联系电话:400-852-1180

备案号:蜀ICP备2022000484号-2       经营许可证: 川B2-20220663       公网安备川公网安备: 51019002004831号

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知人人文库网,我们立即给予删除!