《数学建模优秀论文最优截断切割问题.doc》由会员分享，可在线阅读，更多相关《数学建模优秀论文最优截断切割问题.doc（12页珍藏版）》请在三一文库上搜索。
1、B题 截断切割组号：88截断切割摘要本文讨论的问题是实际生产加工中的截断切割问题，研究了采用何种切割顺序能使得材料切割所用费用最省。根据题中条件，待加工材料和成品均为长方体，且不同的加工顺序使得材料切割费用不同，我们考虑了将三维直角坐标系与有向图相结合的方式构造模型。本文构造的有向图是三维形式的，有向图的顶点坐标（x，y，z）分别代表侧面（左右面）、正面（前后面）、水平面（上下面）的切割次数，其中x，y，z都在0.1.2中取值。有向弧代表一个从弧的始点至弧终点的切割步骤，弧权值代表弧所代表的加工步骤所需加工费。那么切割问题就转化为了求解一个带权有向图的最短路径问题。通过编写数学软件，运用lin
2、gou软件求得了最短路径。最终我们解出了最优切割法：（1）当r=1，e=0时，最短切割路径为：5，3，1，6，4，2；5，3，6，1，4，2（2）当r=1.5，e=0时，最短切割路径为：3，1，5，4，6，2；3，5，1，4，6，2（3）当r=8，e=0时，最短切割路径为：3，1，4，5，2，6（4）当r=1.5，e=2时，最短切割路径为：3，1，5，4，6，2；3，5，1，4，6，2（1）（2）（3）（4）情况的最少费用分别为：374，437.5，540.5，443.5。（数字1,2,3,4,5,6分别代表切割左右前后上下面）当然，本文是假设切割是在一定的切割原则，即在两个平行待切割面中，边
3、距较大的待切割面总是先加工这一原则下进行的，这是符合基本的切割作业常识的，也符合截断切割的同类换序定理（在截断切割方式中交换其内相邻同类切割的切割次序，总切割面积不因切割面积的交换而改变；若交换间隔一异类切割的的同类切割的切割次序，则割弃长较大的同类切割面先切割者，其总切割面积较小）。再者，由题意，成品与待切割品的相邻平行面的距离已经给定。那么也可以通过调整相邻平行面的距离而使得切割花费达到更省，这是本题可以改进的一个方向。关键词：截断切割 最优切割次序 一、问题重述在某些工业部门（如贵重石材加工等）采用截断切割的加工方式。这里“截断切割”是指将物体沿某个切割平面分成两部分。从一个长方体中加工
4、出一个已知尺寸、位置预定的长方体（这两个长方体的对应表面是平行的），通常要经过6 次截断切割.设水平切割单位面积的费用是垂直切割单位面积费用的r倍。且当先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时，因调整刀具需额外费用e。现今要设计一种安排各面加工次序（称“切割方式”）的方法，使加工费用最少。从排列组合的角度考虑，切割方法应有种，当然这其中也会有一些方法是等价的，现在我们规定两个平行待切割面中，边距较大的待切割面总是先加工。每一次切割由于会使得相邻面的相应边长减小，所以会影响到下一次切割时所需的切割费用。水平面与竖直面的单位面积加工费用又不相同。所以安排加工面次序的问题就应该
5、转化为多阶段动态问题，而图解法又是解决这一问题的良策。二、模型假设与符号说明（一） 模型假设a. 待加工长方体与成品长方体对应表面平行。b. 工作台是水平的，而且加工工件与水平台的接触面是事先指定好的，不允许改变。c. 假设水平切割单位面积的费用为r，垂直切割单位面积费用为1；d. 第一次切割前，刀具已经调整完毕，即第一次垂直切割不加入刀具调整费用；e. 每个待加工长方体都必须经过6次截断切割.f. 假设在切割时，遵守这样的准则：两个平行待切割面中，边距较大的待切割面总是先加工。（二） 符号说明,分别表示待加工长方体的长、宽、高。,分别表示成品长方体的长、宽、高。,分别表示待加工长方体与成品长
6、方体。有向图顶点是，坐标为（,），,分别代表侧面（左右面）、正面（前后面）、水平面（上下面）的切割次数。其中,都在0.1.2中取值。,分别表示在时，长方体左右、前后、上下面的距离。有向弧（,）代表一个从至的切割步骤，弧的权值代表弧所代表的加工步骤需要的加工费。 三、建立模型、考虑不同切割方式的总数设待加工长方体的左右面、前后面、上下面间的距离分别为、。六个切割面分别位于左、右、前、后、上、下，将它们相应编号为、，这六个面与待加工长方体相应外侧面的边距分别为、。这样，一种切割方式就是六个切割面的一个排列，共有种切割方式。当考虑到切割费用时，显然有局部优化准则：两个平行待切割面中，边距较大的待切割
7、面总是先加工。由此准则,只需考虑种切割方式。即在求最少加工费用时，只需在90个满足准则的切割序列中考虑。不失一般性，设、，故只考虑在前、在前、在前的切割方式。、根据不同情况建立数学模型1、e=0的情况为简单起见,先考虑e=0的情况。构造如图所示的一个有向赋权网络图G(V,E)。为了表示切割过程的有向性，在网络图上加上坐标轴x，y，z。G(V,E)图G(V,E)的含义为：(1)、空间网络图中每个结点（,）表示被切割石材所处的一个状态。顶点坐标，分别代表石材在左右、前后、上下方向上已被切割的刀数。顶点(0,0,0)表示石材的最初待加工状态，顶点(2,2,2)表示石材加工完成后的状态。(2)、G的弧
8、（,）表示石材被切割的一个过程，若长方体能从状态经一次切割变为状态，即当且仅当时，（,）到(,)有弧(,)，相应弧上的权(,)即为这一切割过程的费用。对于任意相邻状态的点之间的弧的权值公式如下：其中，、分别代表在状态时，长方体的左右面、上下面、前后面之间的距离。(3)、根据局部优化准则知第一刀有三种选择，即第一刀应切、中的某个面，在图中分别对应的弧为(,)，(,)，(,)，图G中从到的任意一条有向道路代表一种切割方式。从到共有90条有向道路，对应着所考虑的90种切割方式。到的最短路即为最少加工费用，该有向道路即对应所求的最优切割方式。2、e0的情况当e0时，即当先后两次垂直切割的平面不平行时，
9、需加调刀费e。希望在上面的网络图中某些边增加权来实现此费用增加。在所有切割序列中，四个垂直面的切割顺序只有三种可能情况（不管它们之间是否穿插水平切割）：先切一对平行面，再切另外一对平行面，总费用比e=0时的费用增加e。先切一个，再切一对平行面，最后割剩余的一个，总费用比e=0时的费用增加2e。切割面是两两相互垂直，总费用比e=0时的费用增加3e。在所考虑的90种切割序列中，上述三种情况下垂直切割面的排列情形，及在图G中对应有向路的必经点如下表（z=0,1,2）：垂直切割面排列情形有向路必经点情况一（一）-(1,0,z),(2,0,z),(2,1,z)情况一（二）-(0,1,z),(0,2,z)
10、,(1,2,z)情况二（一）-(0,1,z),(1,1,z),(2,1,z)情况二（二）-(1,0,z),(1,1,z),(1,2,z)情况三（一）-(1,0,z),(1,1,z),(2,1,z)情况三（二）-(0,1,z),(1,1,z),(1,2,z)我们希望通过在上面的网络图中的某些边上增加权来进行调刀费用增加的计算，但由于网络图中的某些边是多种切割序列所公用的。对于某一种切割序列，需要在此边上增加权e，但对于另外一种切割序列，就有可能不需要在此边上增加权e，这样我们就不能直接利用上面的网络图进行边加权这种方法来求出最短路径。由上表可以看出，三种情况的情形（一）有公共点集(2,1,z)|
11、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的情况如下图中所示。再来判断是否满足调整垂直刀具为二次
12、、一次时的情况，我们发现所增加的权满足另外两类切割序列。综合上述分析，我们将原网络图G分解为两个网络图1和2，并在指定边上的权增加e，然后分别求出图和中从到的最短路，最短路的权分别为：d1,d2.则得出整体的最少费用为：，相应的图求出的最优切割序列即为其对应的最短路径。图图、对“每次选择一个加工费用最少的待切割面进行切割”这个准则的好坏进行评价评价的标准：最佳切割方式可以不唯一，可是最佳加工费用应等于按照之前的模型求解出的最少加工费用。即：若准则精选出的不同切割方式有很多，而相应的加工费却不全相同，则其不具备优化准则的基本属性。同样，即使精选出的切割方式唯一，但加工费却非真正意义上的最小，则准
13、则也无最优性可言。根据实例中的数据，在局部最优准则的前提下，假定时，求出的最佳加工费用为374元，这与用上面的模型求解出的结果相同。假定时，求出的最佳加工费用为490元，这个与用上面的模型求解出的结果443.5不相同，并且比上面的结果大。因此，“每次选择一个加工费用最少的待切割面进行切割”不能作为最佳优化准则使用，但当时可以采用这个准则，而当时不能采用这个准则。四、模型求解结果由题目所给的数据可以得出、的值：6175.569A、r=1,e=0时弧1,21,41,102,32,52,113,63,124,5权值275.5190145275.576585743.5142.5弧4,74,135,65
14、,85,146,96,157,87,16权值19075142.576305722.53820弧8,98,179,1810,1110,1310,1911,1211,1411,20权值38861451001451454058弧12,1512,2113,1413,1613,2214,1514,1714,2315,18权值3043.5751007575403030弧15,2416,1716,2517,1817,2618,2719,2019,2220,21权值22.520202086584058弧20,2321,2422,2322,2523,2423,2624,2725,2626,27权值1612304
15、030161288费用最少为374元。B、r=1.5，e=0时弧1,21,41,102,32,52,113,63,124,5权值275.5190217.5275.576875765.25142.5弧4,74,135,65,85,146,96,157,87,16权值190112.5142.576455733.753830弧8,98,179,1810,1110,1310,1911,1211,1411,20权值38129145100217.51454087弧12,1512,2113,1413,1613,2214,1514,1714,2315,18权值3065.2575100112.575404530
16、弧15,2416,1716,2517,1817,2618,2719,2019,2220,21权值33.75203020129584058弧20,2321,2422,2322,2523,2423,2624,2725,2626,27权值1612304030161288费用最少为437.5元。C、r=8，e=0时弧1,21,41,102,32,52,113,63,124,5权值275.51901160275.57646457248142.5弧4,74,135,65,85,146,96,157,87,16权值190600142.5762405718038160弧8,98,179,1810,1110,1
17、310,1911,1211,1411,20权值386448145100116014540464弧12,1512,2113,1413,1613,2214,1514,1714,2315,18权值30348751006007540230弧15,2416,1716,2517,1817,2618,2719,2019,2220,21权值18020160206448584058弧20,2321,2422,2322,2523,2423,2624,2725,2626,27权值1612304030161288费用最少为540.5元。D、r=1.5，2e15参数组最佳截断方案（1、2、3、4、5、6分别为、）加工费
18、re10531642；5361423741.50315462；351462437.580314526540.51.52315462；351462443.51.52.5315462；351462；3541624451.53354162445.51.53.53541624461.54354162446.51.54.53541624471.55354162447.51.55.53541624481.56354162448.51.56.53541624491.57354162449.51.57.53541624501.58354162450.51.58.53541624511.59354162451.
19、51.59.53541624521.510354162452.51.510.53541624531.511354162453.51.511.53541624541.512354162454.51.512.53541624551.513354162455.51.513.53541624561.514354162456.51.514.53541624571.515354162457.5五、灵敏度分析由模型计算结果得出，当e=0时，r的改变会引起最佳截断方案的变化。不难看出，当r=1时，每次截取时都选用边距最大的面进行切割。当r越大时，截取水平面的步骤趋向于往后进行。且由D表中数据可知，当r保持一定
20、，随着e的增大，最佳截面方案不受影响，但是均是采用了先切一对平行面，再切另外一对平行面，总费用比e=0时的费用增加e。由数学模型得出的最佳方案与实践运用是相同的。六、参考文献1 朱德通，最优化模型与实验，上海：同济大学出版社，2003年。2 刁在筠 刘桂真 宿洁 马建华，运筹学（第三版），北京：高等教育出版社，2008年。3 谢金星 薛毅，优化建模与LINDO/LINGO软件，北京：清华大学出版社，2007年。4 梁幼鸣，最优截断切割，http:/ 1,4 1,102,3 2,5 2,113,6 3,124,5 4,7 4,135,6 5,8 5,146,9 6,157,8 7,168,9 8
21、,179,1810,11 10,13 10,1911,12 11,14 11,2012,15 12,2113,14 13,16 13,2214,15 14,17 14,2315,18 15,2416,17 16,2517,18 17,2618,2719,20 19,2220,21 20,2321,2422,23 22,2523,24 23,2624,2725,2626,27/:D;ENDSETSDATA:D=275.5 190 145275.5 76 5857 43.5142.5 190 75142.5 76 3057 22.538 2038 86145 100 145145 40 5830
22、43.575 100 7575 40 3030 22.520 2020 8658 4058 161230 4030 161288;ENDDATAF(SIZE(CITIES)=0;FOR(CITIES(i)|i#LT#SIZE(CITIES):F(i)=MIN(ROADS(i,j):D(i,j)+F(j);ENDr=1.5，e=2SETS:CITIES/1.27/:F;ROADS(CITIES,CITIES)/1,2 1,4 1,102,5 2,114,5 4,7 4,135,8 5,147,8 7,168,9 8,179,1810,11 10,13 10,1911,14 11,2013,14
23、13,16 13,2214,17 14,2316,17 16,2517,18 17,2618,2719,20 19,2220,2322,23 22,2523,2625,2626,27/:D;ENDSETSDATA:D=275.5 190 217.576 87144.5 190 112.578 4538 3040 129145 100 217.540 8777 100 112.542 4520 3022 12958 401632 40181210;ENDDATAF(SIZE(CITIES)=0;FOR(CITIES(i)|i#LT#SIZE(CITIES):F(i)=MIN(ROADS(i,j):D(i,j)+F(j);END