数学建模优秀论文最优截断切割问题

数学建模优秀论文最优截断切割问题内容摘要：

在所考虑的 90 种切割序列中，上述三种情况下垂直切割面的排列 情形，及在图 G 中对应有向路的必经点如下表（ z=0,1,2）： 垂直切割面排列情形 有向路必经点 情况一（一） 1M 2M 3M 4M (1,0,z),(2,0,z),(2,1,z) 情况一（二） 3M 4M 1M 2M (0,1,z),(0,2,z),(1,2,z) 情况二（一） 3M 1M 2M 4M (0,1,z),(1,1,z),(2,1,z) 情况二（二） 1M 3M 4M 2M (1,0,z),(1,1,z),(1,2,z) 情况三（一） 1M 3M 2M 4M (1,0,z),(1,1,z),(2,1,z) 情况三（二） 3M 1M 4M 2M (0,1,z),(1,1,z),(1,2,z) 我们希望通过在上面的网络图中的某些边上增加权来进行调刀费用增加的计算，但由于网络图中的某些边是多种切割序列所公用的。 对于某一种切割序列，需要在此边上增加权 e，但对于另外一种切割序列，就有可能不需要在此边上增加权 e，这样我 们就不能直接利用上面的网络图进行边加权这种方法来求出最短路径。 由上表可以看出，三种情况的情形（一）有公共点集 {(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} 6 及与之相关联的入弧，就形成两个新的网络图，如图Ｈ 1 和Ｈ 2。 这两个网络图具有 互补性。 对于一个问题来说，最短路线必存在于它们中的某一个中。 由于调整垂直刀具为 3次时，总费用需增加 3e，故我们先安排这种情况的权增加值e，每次转刀时，给其待切弧上的权增加 e。 增加 e的情况如下图中所示。 再来判断是否满足调整垂直刀具为二次、一次时的情况，我们发现所增加的权满足另外两类切割序列。 综合上述分析，我们将原网络图 G分解为两个网络图Ｈ 1和Ｈ 2，并在指定边上的权增加 e，然后分别求出图 1H 和 2H 中从 1V 到 27V 的最短路，最短路的权分别为： d1,得出整体的最少费用为： 12min( , )d d d ，相应的图求出的最优切割序列即为其对应的最短路径。 图 1H 7 图 2H Ⅲ、对“每次选择一个加工费用最少的待切割面进行切割”这个准则的好坏进行评价 评价的标准： 最佳切割方式可以不唯一，可 是最佳加工费用应等于按照之前的模型求解出的最少加工费用。 即：若准则精选出的不同切割方式有很多，而相应的加工费却不全相同，则其不具备优化准则的基本属性。 同样，即使精选出的切割方式唯一，但加工费却非真正意义上的最小，则准则也无最优性可言。 根据实例中的数据，在局部最优准则的前提下，假定 0, 1er时，求出的最佳加工费用为 374 元，这与用上面的模型求解出的结果相同。 假定 2, 时，求出的最佳加工费用为 490 元，这个与用上面的模 型求解出的结果 不相同，并且比上面的结果大。 因此，“ 每次选择一个加工费用最少的待切割面进行切割 ”不能作为最佳优化准则使用，但当 0e 时可以采用这个准则，而当 0e 时不能采用这个准则。 四、 模型求解 结果 由题目所给的数据可以得出 1u 、 2u 、 3u 、 4u 、 5u 、 6u 的值： 1u 2u 3u 4u 5u 6u 6 1 7 6 9 8 A、 r=1,e=0 时 弧 1,2 1,4 1,10 2,3 2,5 2,11 3,6 3,12 4,5 权值 190 145 76 58 57 弧 4,7 4,13 5,6 5,8 5,14 6,9 6,15 7,8 7,16 权值 190 75 76 30 57 38 20 弧 8,9 8,17 9,18 10,11 10,13 10,19 11,12 11。