案例二：1997B截断切割问题赛题分析.ppt

某些工业部门（如贵重石材加工等）采用截断切割的加工方式。这里“截断切割”是指将物体沿某个切割平面分成两部分。从一个长方体中加工出一个已知尺寸、位置预定的长方体（这两个长方体的对应表面是平行的），通常要经过6次截断切割。水平切割单位面积的费用是垂直切割单位面积费用的r 倍，且当先后两次垂直切割的平面(不管它们之间是否穿插水平切割)不平行时，因调整刀具需额外费用e。 试为这些部门设计一种安排各面加工次序（称“切割方式”）的方法，使加工费用最少。（由工艺要求，与水平工作台接触的长方体底面是事先指定的）,案例2：截断切割 （1997年B题）,详细要求如下： 1）需考虑的不同切割方式的总数。 2）给出上述问题的数学模型和求解方法。 3）试对某部门用的如下准则作出评价：每次选择一个加工费用最少的待切割面进行切割。 4）对于e = 0的情形有无简明的优化准则。 5）用以下实例验证你的方法：待加工长方体和成品长方体的长、宽、高分别为10、14.5、19和3、2、4，二者左侧面、正面、底面之间的距离分别为6、7、9（单位均为厘米）。垂直切割费用为每平方厘米1元，r和e的数据有以下4组： a. r =1, e = 0; b. r =1.5, e =0; c. r =8, e =0; d. r =1.5; 2 = e = 15. 对最后一组数据应给出所有最优解，并进行讨论。,你会想到它是属于哪一类问题？,读完题目之后,你可能会认为是题目很简单，但是 计算总费用时却因“加工次序”而止步,这么多问题要求解，你是否弄清楚了？,你会去翻阅什么建模辅导书？,？,只有6个面，你是否会尝试穷举法？,某些工业部门（如贵重石材加工等）采用截断切割的加工方式。这里“截断切割”是指将物体沿某个切割平面分成两部分。从一个长方体中加工出一个已知尺寸、位置预定的长方体（这两个长方体的对应表面是平行的），通常要经过6次截断切割。水平切割单位面积的费用是垂直切割单位面积费用的r 倍，且当先后两次垂直切割的平面(不管它们之间是否穿插水平切割)不平行时，因调整刀具需额外费用e。 试为这些部门设计一种安排各面加工次序（称“切割方式”）的方法，使加工费用最少。（由工艺要求，与水平工作台接触的长方体底面是事先指定的）,案例2：截断切割 （1997年B题）,反复读题,？,详细要求如下： 1）需考虑的不同切割方式的总数。 2）给出上述问题的数学模型和求解方法。 3）试对某部门用的如下准则作出评价：每次选择一个加工费用最少的待切割面进行切割。 4）对于e = 0的情形有无简明的优化准则。 5）用以下实例验证你的方法：待加工长方体和成品长方体的长、宽、高分别为10、14.5、19和3、2、4，二者左侧面、正面、底面之间的距离分别为6、7、9（单位均为厘米）。垂直切割费用为每平方厘米1元，r和e的数据有以下4组： a. r =1, e = 0; b. r =1.5, e =0; c. r =8, e =0; d. r =1.5; 2 = e = 15. 对最后一组数据应给出所有最优解，并进行讨论。,注意要求，建模一定要严格按照要求进行,总的切割方式为多少个？,“加工费用最少”表明本问题是一个典型的最优化问题，目标是使得总加工费用最少，而要做的决策则是确定各面加工次序（“切割方式”）。 切割方式的决策主要与待加工长方体和成品长方体的长、宽、高有关，另外还与换刀具费用e及水平切割单位面积的费用与垂直切割单位面积费用的r 倍数有关。（影响决策的因素） 总加工费用包括各面加工费用及换刀具费用。,1、审题分析,一、模型准备,方法：可在图书馆、网上查阅、向专家询问、通过实物切割试验来得到资料，并最好用笔做好记录。,不过，此问题暂时不需要搜集数据，重点寻找与之最接近的数学模型资料。,Next：建模，关键是理清不同加工次序下的总加工费如何计算,一、模型准备,2、收集资料,3、问题重述（略）,1）、(a1，a2, b1, b2, c1, c2) ：待加工长方体和成品长方体两者的左侧面（右侧面、正面、背面、底面、顶面）之间的距离，也称为切去长度，单位：cm。 2）、 决策变量为x=x1x2x3x4x5x6：表示一种切割方式，为切割的一个排列，共有6!种排列，xi可以取1，2，3，4，5，6。 3）、fi ：第i次切割xi的切割费用（不含换刀费用）。 4）、f(x)：切割方式x的总加工费用，它是切割费用与换刀具费用的总和。,基本假设及符号说明,二、模型假设,此问题在模型假设与符号说明之后，最好给出图形便于直观理解，这同时也为解题提供方便。,可将确定最佳切割方式的问题归结为如下最优化模型：,注意：这个模型不能用一般的最优化方法进行求解，因为f(x)是形式较复杂的非线性函数。,模型一：一般切割模型,三、模型建立,通过对问题的分析，我们可以将原问题抽象为一个01整数规划模型。由于每个面只切割1次，第i次切割只能切割1个面，从而可以确定模型的约束条件。,定义变量 ：如果 表示第i次切割第j个面，如果 表示第i次不切割第j个面，其中i=1,2,6,j=1,2,6。,模型二： 01整数规划模型,三、模型建立,定义变量 ：如果 表示第i次切割第j个面，如果 表示第i次不切割第j个面，其中i=1,2,6,j=1,2,6。,注意：需要重新定义决策变量,（1）重新分析题目,所以，得到01整数规划模型如下：,模型二： 01整数规划模型,三、模型建立,（2）建立模型,这里用x代表全体决策变量,模型求解可用Matlab软件（穷举法）略。,注意到目标函数是个非线性函数，所以这是一个非线性的01整数规划。,三、模型建立,四、模型求解,总的说来，由于非线性规划问题在计算上常是困难的，理论上的讨论也不能像线性规划那样给出简洁的结果形式和全面透彻的结论. 这点又限制了非线性规划的应用，所以，在数学建模时，要进行认真的分析，对实际问题进行合理的假设、简化，首先考虑用线性规划模型，若线性近似误差较大时，则考虑用非线性规划。,首先考虑到一共需要切割6次。按照排列知识，不同方案应该有 种。 其次，注意如果两次相继的加工是切割一对相互平行的平面，那么交换其顺序对整个切割费用将不产生任何影响。 这种相互平行的平面一共有3对。其中的1对在加工顺序中相邻的情况共5!种，有某2对相邻的共4!种，3对都相邻的有3!种。 根据组合学中的容斥原理便可得到结果： (种),1、重新分析,一、模型准备,虽然解决了切割方式的个数，但是为穷举带来了麻烦,五、模型分析与改进,模型一、二都没给出总加工费的就是办法，需要修正模型,2、重新寻找更好的建模方式、方法,五、模型分析与改进,此问题涉及次序问题，可以考虑用排序论的相关理论进行讨论求解。 此问题的求解定会参考长方体的切割图形，所以可以考虑用图论的相关理论进行讨论求解。,另外，关于问题4、5的简单分析,4题.“每次选择加工费最小的待切割面进行切割”是否可作为优化准则使用？只需按此准则选择切割方式, 然后考察各方式是否有相同的加工费, 并且该加工费是否为最小即可说明。(是否为最小原则上需要比较了720个加工费后才能达成).理由是: 最佳切割方式虽然可能不唯一, 但最佳加工费用应是唯一不变的值.,计算结果：依准则选出的不同切割方案多达15种，且还表明了此切割标准一般不可作为优化准则使用.,2）每次选择加工费最小的待切割面进行切割”虽不可作为优化准则使用, 但只要其精选出的15种不同切割方式的最小加工费并未漏掉最优切割方式所对应的、真正的最小加工费, 那么由某部门提出的该“准则”仍有可借其快速辅助优化的重要价值