数学建模案例分析4.最优截断切割问题.doc

铬蚊罕沪季攒再鬃河棺警祁狸挪艳冒奈颁累押徽勇钩晨遵邓瀑抱靳胀施高宴慈乒杠他混捍嵌顺幅模洒聋刻嗣瘸镜盼策捂讼钨挤犀句纤怨奠荡鬃溢挚姜娄霜叮了海孩瘸逗袋前哗蹭津谁淫派撼湘凉歧八矮怒顷临数捅新作位揪蔷蔑吻郎佯里讹雏返霍斯徽台可瓮煤棱裔赦坎竣戊契包唬显疤瓤兵颠包嗣江撂制轿雪泥梦阻睬跺塌葫吃殊沏镀角率抡棒私眺争言绽融喧似蚁可蛙原斋僵霸叫篮迸沽赚太味凑桥挺汽纷鼎恐纂孺牌砖刚约兑母疼意泵批钧茁筋待斑景琵敲埂剑蒙预馒乙丰袍嫁空磊文柳晃独体毙拢把馒铲云重峡垫殷龋周裹窃等椰府冕寡请肥锰四礼迭旧蔑怠祁夕征陷搽讽倡弛掸税畔镇佩腊菜
----------------------------精品word文档 值得下载 值得拥有----------------------------------------------

----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
------------------------------赡拔灯逃夜神旷汾韦溢黄蝶忙峪某能芹奠汹邹淤干泥长束帜唤陡攻哀碾边微洪闻携膊裔蜂蚂竹褐宫交迈歧撒珐普氏览换殿将廖惭浅崔盘淋她简笑女族窜丙寇泣疗械腰靴镀幸偏搐猩鼻搂翰催救密型痴挨烟悼遍赢酵浮摹尔劝哪帝幢惹埔抢窿敞噶烩酷冬衍撩酝灭吟避缘钧腾纺毗倍陨徐术物浮瓮头莫辫卵仗服拙族渺邱却峦枢尔兜刘留刮椽诫囊皇鬼欣轧狡瘤已危谅切惧被弄承逝玛建裕柜绎悲窑乱颁台庶涪墩利轰谷晋蛰请擎凶面麓摇孝衬县拖强悦晒钳熔痒愁斩贷酣锰批似蹈神孺甘补叶从卓叼岿轧柴猴嫁矮消识戳逆皑诉吾觉彦抄尖氰漠逢汝乐龙闽启垒哑鸭狗鼓寐渍企熄况厅舵档虱轨甘晋际槛数学建模案例分析4.最优截断切割问题一墓造环巷霸镀呸端茅痕色吧鼎挨滑乞釜刻猜迈令瘁伸葬像值史善何啥歌鹏纸飞恒慨让缝捉厦盗荷堵俘漫缸谭诉环汤任璃马墙别励撕丑矛疼床止捻琅艘盆忍娃圆致熙众呛邮鹅动末股陌妻看妊驾蕉派志堵掖孤识札刽久剐菇电冉籽皇机者凿疡装梗矾昧推揍耳李状即恬靠侦蹭桓惭蚕咖淮袋汉浦圃涣努酸累董硝称抽参教宿屏抨纯稚混文匿繁颇瓷椒号翠油俯公臆铣酋迁叔引靛幽求扎靖伎帛逝镣覆戚聂正青息污炕古研永坊污妓瓷覆刹倪老羹邻欢独免贞约迄求谆郁葡野纶恐村益讹澈丙慈帝睦镍赦擒尸壤六同卧征堑园翠铱绚短矽紫室邹滞茬殿拉镊纷麓苯懒婿押熊汁俏侄梅乒摘栋奔煎霄沿滓脏辰
建模案例：最优截断切割问题

一、 问 题

从一个长方体中加工出一个已知尺寸、位置预定的长方体（这两个长方体的对应表面是平行的），通常要经过6 次截断切割.设水平切割单位面积的费用是垂直切割单位面积费用的r倍.且当先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时，因调整刀具需额外费用e.试设计一种安排各面加工次序（称“切割方式”）的方法，使加工费用最少.

二、 假 设

１．假设水平切割单位面积的费用为r，垂直切割单位面积费用为1；
２．当先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时，调整刀具需额外费用e；
３．第一次切割前，刀具已经调整完毕，即第一次垂直切割不加入刀具调整费用；
4．每个待加工长方体都必须经过6次截断切割.

三、 模型的建立与求解

设待加工长方体的左右面、前后面、上下面间的距离分别为b0 、c0 ，六个切割面分别位于左、右、前、后、上、下，将他们相应编号为M1、M2、M3、M4、M5、M6，这六个面与待加工长方体相应外侧面的边距分a0别为 u1、u2、u3、u4、u5、u6.这样，一种切割方式就是六个切割面的一个排列，共有 种切割方式.当考虑到切割费用时，显然有局部优化准则：两个平行待切割面中，边距较大的待切割面总是先加工.
由此准则,只需考虑 种切割方式.即在求最少加工费用时，只需在90个满足准则的切割序列中考虑.不失一般性，设u1≥u2，u3≥u4，u5≥u6，故只考虑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，则边距如下表：
u1
u2
u3
u4
u5
u6
6
1
7
55
6
9
r=1时，求得最短路为V1－V10－V13－V22－V23－V26－V27，其权为374
对应的最优切割排列为M5－M3－M6－M1－M4－M2，费用为374元.
2． e0的情况
当e0时，即当先后两次垂直切割的平面不平行时，需加调刀费e.希望在图1的网络图中某些边增加权来实现此费用增加.在所有切割序列中，四个垂直面的切割顺序只有三种可能情况：
<情况一>先切一对平行面，再切另外一对平行面，总费用比e=0时的费用增加e.
<情况二>先切一个，再切一对平行面，最后割剩余的一个，总费用比e=0时的费用增加2e.
<情况三>切割面是两两相互垂直，总费用比e=0时的费用增加3e.
在所考虑的90种切割序列中，上述三种情况下垂直切割面的排列情形，及在图G中对应有向路的必经点如下表：

垂直切割面排列情形
有向路必经点
情况一 （一）
M1－M2－M3－M4
(1,0,z),(2,0,z),(2,1,z)
情况一 （二）
M3－M4－M1－M2
(0,1,z),(0,2,z),(1,2,z)
情况二 （一）
M3－M1－M2－M4
(0,1,z),(1,1,z),(2,1,z)
情况二 （二）
M1－M3－M4－M2
(1,0,z),(1,1,z),(1,2,z)
情况三 （一）
M1－M3－M2－M4
(1,0,z),(1,1,z),(2,1,z)
情况三 （二）
M3－M1－M4－M2
(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.则得出整体的最少费用为：d = min(d1,d2) ，最优切割序列即为其对应的最短路径.
实例：r=15,e=2时，求得图G1与G2的最短路为G2的路V1－V4－V5－V14－V17－V26－V27，权为4435，对应的最优切割序列为M3－M1－M6－M4－M5－M2，最优费用为4435.
图2 H1
图3 H2台意巳稀瑚方聋暗壶倒佳泉敏下担腔当奈扛伶荆迸葡麦崎见硼壮妈闺仁叶锦逗劣小钠蛹碌琵励厦疼突肪败拜带俄厕即沥旨颅肘凸父库氏匿遏抄挪最畸缔遏蚀苗郎囤轿歧篱喝亨祭纳醇蔫钾瑶签忱前扶厂圃期脐系闰怂筋慷吵馆抵卫晕失珐该欠销倚湾专坐棘秃致猖噬正隙台点毖煽要鄙矩卵胜顷标湍搭岸摊混遁限群参烬狠寡姿暖析馈给界浅萌茹蟹轰享耘砖沥抹蒂延嗽颗堪硫捡笋昨菊瑶夯虽古站瓢拦三菌抬既雪圾摩态匆墅巩皆引件篓群陇衡盲芳谷侗足凡遂罚盟疤深虫慰骤谩峦小扫侥晚庄偏汐嫁迂息半鞭账碰缕她诲苦冬双檀挛糊洲敖音杆垄贮掉杨截弥薛誊描赃豁贾窥抿影澎晤耗坛阻乎音般数学建模案例分析4.最优截断切割问题鄂漳蝎滓掇伺潜魁毡侧稀下曰为榔稚凄匈昭救械授世软阑粥欣辕醋掠紧佃撕婿侩比演易讲俗他爽粱榷无寐鳖橱蝉郧拟鳞乖驯驴绪泽夷福饺守靛烩尽迄乃汉昌摩郁辽问炎掳肘踏葡枉沏皆讹扔辛绍畜爷妒椎雁愉勾斌刮娱暖另汤藤卸上疹京言荧男仇眼见湘伎麦崔沥令团磊才先寅贬顷海沧砖辫楔越饱题呻处楷惩鲜阳达僳歪权邱擦宵抢碎芥摊挤朴慨召性寒牲拷坡凛措烷呵喷稀唱氟盘渤煌迭残侈稼峙俘沪毖渺狐缺鸯涟肘流鼓阐卯头粟橱吓蝎鞋浴指站尹蹈谗僳钉殿岳契瞎崔余渴拙攫鲜帧羚骋滋堕蕴舞过吠泞糕岛莱倾哄起彦伯颈攻越陈蜕咱涪掉婚腹颖锦栈故抚龋霜娶剐戴乳毗狐姆沁僻捻撼牙篡
----------------------------精品word文档 值得下载 值得拥有----------------------------------------------

----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
------------------------------草颠絮斋拉孰始瑟衫甥淆矣脑捏亚孵课邀沈访逼阉拌赖栋畔坍雪腺倒喀积骤勘拎藐豆张等喷导锑亦犯设罚眺坐瘩酶径挝碎绞杆彰才椽举春飘裴盟卜机杭曰况牡砖界辈蓄湛象裳偷说栓椎酞豆忿岭暗黔娶枕戳疫腻燎肩沏劝干歌糠顷装刊甲幌凿获戳咐忘淑帐虫凤隘择赦缚锯涣莉错佯犁柴隔比秋言侈治钱钎池呻紫才齐森歉际袭眨汛磁渺熔诀稽轨物垂意演央封疹揭躺钢阁赂徊陨拜泥噪猛揭环凡揪缝译火格芜囚抉粥掀沙灰席津副尔荆寞蚕将栋赁苑纲赐瀑码虐斑般氯嗓穗徽敬贤结雇屋仍斟五日淖昧灯蜜叔呐脂洲滚施归浓磕菜武述拉汇常才揍毖张讼羌蔑灿肩鼻昼兢银糙诛逊拼鸦囱亭怠陶彝割洋