数学建模工件的加工次序问题学习教案.pptx

《数学建模工件的加工次序问题学习教案.pptx》由会员分享，可在线阅读，更多相关《数学建模工件的加工次序问题学习教案.pptx（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数学建模工件的加工次序数学建模工件的加工次序(cx)问题问题第一页，共26页。摘要摘要(zhiyo)n n本文探讨的问题是如何安排工件的加工顺序以使得各工件的完工时间之和最短、机床花费的总时间最小、加工工件的总补偿费用最少。求解这一问题主要用到了图论和线性规划的数学方法。在第一问与第三问中，本文先将题中所给出的数据、条件转换为图，在此基础上表示出目标函数及约束条件，利用非线性规划求得最优解。第二问中，文本利用了图论中哈密顿链原理，将完成工件加工的问题转化为有向图中点的遍历，所建立的模型可遍历哈密顿链中的全部(qunb)点且得到最短路径。第1页/共26页第二页，共26页。n n最终求解模

2、型，结果如下：n n(1)加工(ji gng)顺序为4109711538612141213时，各工件的完工时间和最小，为2588。n n(2)加工(ji gng)顺序为4711109538621141213时，机床花费的总时间最小，为114。n n(3)加工(ji gng)顺序为4711105938612141213时，总补偿费最小，为。n n(4)对u进行讨论，可分为以下几种情况:u92、92=u108、108=u174、174=u199、199=u209、209=u219、219=u269、269=u309、309=u=345,并进而用lingo可求出答案n n(5)把一般情况下上述各问题

3、的解法进行的一些讨论。第2页/共26页第三页，共26页。问题重述问题重述(zhn sh)与分析与分析n n现有现有1414件工件等待在一台机床上加工件工件等待在一台机床上加工(ji gng)(ji gng)，某些工件，某些工件的加工的加工(ji gng)(ji gng)必须安排在另一些工件加工必须安排在另一些工件加工(ji gng)(ji gng)完工完工以后才能开始，第以后才能开始，第j j号工件的加工号工件的加工(ji gng)(ji gng)时间时间tj tj及先期必须及先期必须完工的工件号完工的工件号i i由下表给出。由下表给出。工件号j1234567891011121314tj202

4、8251642123210242040243616前期 工件号i3,45,7,85,9-10,113,8,943,5,74-4,76,7,145,121,2,6第3页/共26页第四页，共26页。1）若给出一个加工工序，则确定了每个工件的完工时间（包括等待与加工两个阶段）。试设计一个满足条件的加工顺序，使各工件的完工时间之和最小。2）若第j号工件紧接着第i号工件完工后开工，机床需要花费的准备时间是：3）假定工件的完工时间（包括等待与加工两个阶段）超过一确定时限u时，则需支付一定的补偿费用，其数值等于超过时间与费用率之积，各工件的补偿费用率i如下：u=100，tij=0，安排一个加工顺序，使总补偿

5、最小。(4)试对(3)中的u进行讨论。(5)能否对一般(ybn)情况下上述各问题的解法进行一些讨论。j1234567891011121314i121015161011108541010812第4页/共26页第五页，共26页。问题问题(wnt)分析分析n n这五个问题都是要求一种最优加工次序，使得工件这五个问题都是要求一种最优加工次序，使得工件完工时间和、机床花费时间、总补偿费分别达到最完工时间和、机床花费时间、总补偿费分别达到最小。由于题中安排了各工件的前期工件，所以解题小。由于题中安排了各工件的前期工件，所以解题时可以先利用图论的知识将加工工件之间的先后关时可以先利用图论的知识将加工工件之间

6、的先后关系表示出来。由于第系表示出来。由于第j j号工件完工时间和补偿费与其号工件完工时间和补偿费与其前置加工工件完工时间的累加密切相关，所以单纯前置加工工件完工时间的累加密切相关，所以单纯用图论解决完工时间和补偿费的最优化是很复杂的，用图论解决完工时间和补偿费的最优化是很复杂的，但是可以在有向图的基础上将目标函数但是可以在有向图的基础上将目标函数(hnsh)(hnsh)、约束条件巧妙表示出来，再结合非线性规划解出最约束条件巧妙表示出来，再结合非线性规划解出最优解。在第二问中，求得的是机床花费总时间的最优解。在第二问中，求得的是机床花费总时间的最小值问题，实质就是要解决机床的总准备时间最短小值

7、问题，实质就是要解决机床的总准备时间最短的问题。该问题可转化为最短路径问题，但是同时的问题。该问题可转化为最短路径问题，但是同时要考虑到各加工工件的前期工件。这就需要构造一要考虑到各加工工件的前期工件。这就需要构造一个好的有向图，再遍历点并求得最短路径。个好的有向图，再遍历点并求得最短路径。第5页/共26页第六页，共26页。模型模型(mxng)假设假设n n(1)(1)假设相邻工件之间的加工是紧挨着进行的，即假设相邻工件之间的加工是紧挨着进行的，即除了准备时间外，不浪费任何时间。除了准备时间外，不浪费任何时间。n n(2)(2)假设机床在加工工件的过程中运转正常。假设机床在加工工件的过程中运转

8、正常。n n(3)(3)假设不会发生意外情况（机器假设不会发生意外情况（机器(j q)(j q)坏掉、加工坏掉、加工的工件不能正常使用等。）的工件不能正常使用等。）第6页/共26页第七页，共26页。符号符号(fho)说明说明n n 第i号工件在加工流程中的加工序号n n 各工件完工时间之和n n 机床花费的总时间n n 加工时的总补偿费n n 表示从节点i(表示加工工件i)到节点j(表示加工工件j)的准备时间。n n 是0-1变量，表示是否选取直接从加工第i号工件接替到加工第j号工件这一顺序n n ，表示选取了从加工i号工件到加工j号工件的顺序n n ，表示不选取从加工i号工件到加工j号工件的

9、顺序n nn n 表示第 个工件的完工时间超过了确定时限(shxin)u j=1,2.14 n n 表示第 个工件的完工时间没有超过了确定时限(shxin)u j=1,2.14 第7页/共26页第八页，共26页。模型建立模型建立(jinl)与求解与求解n n1、总完工时间最优模型n n问题1中要求(yoqi)根据各个工件的加工时间，以及其前期工件的要求(yoqi)，建立以总的完工时间最少为目标的目标函数。在加工时间一定的情况下，对其进行合理的排序，使目标函数达到最小值。第8页/共26页第九页，共26页。n n(1)(1)模型建立模型建立n n总的完工时间包括各工件的等待时间之和与各工件的加工时

10、间总的完工时间包括各工件的等待时间之和与各工件的加工时间之和。由于各工件的加工时间之和是一定之和。由于各工件的加工时间之和是一定(ydng)(ydng)的，所以完工的，所以完工时间最优问题等价于各工件等待时间总和的最优化问题。时间最优问题等价于各工件等待时间总和的最优化问题。n n设第设第 个工件的加工次序为个工件的加工次序为 ，总的完工时间为，总的完工时间为 。n n每个工件都被其后置加工工件所等待，因此，总的工件等待时每个工件都被其后置加工工件所等待，因此，总的工件等待时间即每个工件被等待的时间总和。间即每个工件被等待的时间总和。n n第第 个工件被等待的时间为个工件被等待的时间为 ，则所

11、有工件被等待的时间，则所有工件被等待的时间为为 n n所有工件的加工时间为所有工件的加工时间为n n因此总的完工时间之和为：因此总的完工时间之和为：第9页/共26页第十页，共26页。n n(2)约束条件分析n n设 是 的前期工件(gngjin)，则第 个工件(gngjin)的加工次序应早于第 个工件(gngjin)的加工次序，所以 n n由题目当中的表可得约束条件为：n n n n n n n n n n n n n n n n 均为正整数，i=1,2,314。第10页/共26页第十一页，共26页。n n(3)相关图形n n由题目(tm)中的表可作图如下：11 9 4 7 5 3 10图1第

12、11页/共26页第十二页，共26页。n n(4)模型求解n n这是一个最优化问题，由于变量和约束条件都很多，人工求解有一定困难，因此可以(ky)借助lingo软件，求解得到最佳加工顺序和最少总完工时间。n n在lingo软件中求解的部分代码：n nMIN=5175-20*y1-28*y2-25*y3-16*y4-42*y5-12*y6-32*y7-10*y8-24*y9-20*y10-40*y11-24*y12-36*y13-16*y14=0;（目标函数的表示）。n n由lingo计算得使得总完工时间最短的最佳加工次序为：n n ，n n此时总完工时间为2588。1 8 3 14 13 2 6

13、 12图2第12页/共26页第十三页，共26页。n n2、机床花费总时间最优模型n n(1)模型建立(jinl)机床花费总时间包括机床的总准备时间和总的工件加工时间。总的工件加工时间是一定的，因此解决机床花费总时间最短问题等价于机床准备总时间的最优化问题。本模型将此问题转化为图论中的遍历哈密顿链问题。构造图如下 n n 11 9 4 7 5 3 10图3第13页/共26页第十四页，共26页。n n图中的顶点(dngdin)表示加工工件号，实线表示规定的加工先后顺序，如有向实线 表示加工顺序应该是先加工了4号工件才能加工9号工件。有向虚线表示可以相邻加工的两个工件号，如虚线 表示可以先加工5号工

14、件，再紧接着加工9号工件；表示可以先加工9号工件，再紧接着加工5号工件。有向弧的权用 表示从节点i(表示加工工件i)到节点j(表示加工工件j)的准备时间。n n 是0-1变量，表示是否选取加工第i号工件后紧接着加工第j号工件这一路径。n n ，表示选取了从加工i号工件到加工j号工件的顺序n n ，表示不选取从加工i号工件到加工j号工件的顺序18314132612图4第14页/共26页第十五页，共26页。n n现要求求得一种加工顺序，使得机床的总等待时间最短。转换为图论问题即是寻找一条最短路径，并满足如下要求：n n 该路径经过所有节点一次且仅一次，且无环，因此路径数目要比节点数目少1；n n

15、该路径经过工件(gngjin)i所代表的节点时，必须已经经过工件(gngjin)i的所有前置节点。n n根据图1，与图2，3号工件(gngjin)必定是排在第7个序号上，13号工件(gngjin)必定排在最后一个加工序号上，同理，12号工件(gngjin)必定是倒数第二个被加工，14号工件(gngjin)必定是倒数第三个被加工。因此问题简化为找到图3、图4这两部分的最优加工顺序。建立模型为：n nMin n ns.t.n n 第15页/共26页第十六页，共26页。n n(2)模型求解n n本模型用求解：n n对图一求解n n求解结果(ji gu)为：471110953 所需机床花费总时间为45

16、。n n对图二求解n n求解结果(ji gu)为：38621141213 所需机床花费总时间为69。第16页/共26页第十七页，共26页。n n3、总补偿费最少模型n n本问题主要研究如何给出一个加工顺序使得总补偿费最小。n n(1)目标(mbio)函数分析n n变量说明:表示第 个工件的完工时间（包括等待与加工两个阶段）j=1,214n n u表示确定时限，题目中给的值为100n n 表示第 j个工件的完工时间超过了确定时限 u n n 表示第j 个工件的完工时间没有超过了确定时限 u j=1,214n n 表示第 j个工件的补偿费率n n根据题目要求，只有超过了确定时限的工件才需要支付补偿

17、费用，由此可以得到目标(mbio)函数为：n nMin （）第17页/共26页第十八页，共26页。n n(2)约束条件分析n n根据题目给出的表中可以得知各工件之间的关系（），由此也可以得到各工件完工时间之间的关系（）。由分析知道工件3的完工时间为199，工件14的完工时间为285，工件12的完工时间为309，工件13的完工时间为345，因此工件3以后完工的工件的完工时间都会超过确定时限 u，则 （为工件3以后完工的工件号，包括工件3）；而不管安排怎样的加工顺序工件4的完工时间都不会超过 u，则 ；对于工件5，它加工之前工件4、7、11、10必须完工，因此工件5的完工时间至少为108，也超过了

18、确定时限 u，则 ；对于工件7，它最多排在工件4、9、10的后面，因此它的完工时间最多为92，不超过 u，则 ；对于工件9、10、11，它们(t men)可能超过也可能不超过确定时限，这只能根据加工的顺序来得到 的值。n n工件的完工时间 与工件的加工顺序 之间的关系为（），由问题一可知。第18页/共26页第十九页，共26页。n n(3)(3)总补偿费最少模型的建立总补偿费最少模型的建立n n基于上面基于上面(shng mi(shng mi n)n)的分析，以（）为目标函数，以（）、的分析，以（）为目标函数，以（）、（）、（）、（）为约束条件建立模型（）、（）、（）为约束条件建立模型Min第1

19、9页/共26页第二十页，共26页。n n(4)模型的求解n n经过化简后，目标函数中只剩 下 n n n n几个未知变量，根据lingo软件可以得出结果。总补偿费最小的加工顺序为，总补偿费为。n n 根据题目给出的表中可以得知各工件之间的关系（），由此也可以得到各工件完工时间之间的关系（）。由分析(fnx)知道工件3的完工时间为199，工件14的完工时间为285，工件12的完工时间为309，工件13的完工时间为345，因此工件3以后完工的工件的完工时间都会超过确定时限u，则 （为工件3以后完工的工件号，包括工件3）；而不管安排怎样的加工顺序工件4的完工时间都不会超过 u，则 ；对于工件5，它加

20、工之前工件4、7、11、10必须完工，因此工件5的完工时间至少为108，也超过了确定时限 u，则 ；对于工件7，它最多排在工件4、9、10的后面，因此它的完工时间最多为92，不超过，则；对于工件9、10、11，它们可能超过也可能不超过确定时限，这只能根据加工的顺序来得到 的值。第20页/共26页第二十一页，共26页。n n4.对(3)中的u进行讨论。n n对u进行讨论，可以分为以下几种情况n n当u92时，所有工件加工时间都超过了时限(shxin)，所有（j=1,2,3,5.）.由式（），（.3）和mj的值。n n当92=u108，此情况与u=100相同，答案为总补偿费最小的加工顺序为 n n

21、总补偿费为。n n当108=u174n n 其他约束条件相同n n当174=U199n n 其他约束条件相同第21页/共26页第二十二页，共26页。n n当199=U209n n当209=u219n n 其他约束条件同(1.2)(1.3)n n当219=u269n n 其他约束条件同(1.2)(1.3)n n当269=u309n n 其他约束条件同(1.2)(1.3)n n当309=u345n n 其他约束条件同(1.2)(1.3)n n当345=u,所有工件加工时间皆没有超过时限u，此时(c sh)原问题相当于问题二第22页/共26页第二十三页，共26页。n n5.对一般情况下上述各问题的解

22、法进行的一些讨论n n 对于前两个问题总的完工时间包括各工件的等待时间之和与各工件的加工(ji gng)时间之和。由于各工件的加工(ji gng)时间之和是一定的，所以完工时间最优问题等价于各工件等待时间总和的最优化问题。n n设第 i个工件的加工(ji gng)次序为 ，总的完工时间为 。n n每个工件都被其后置加工(ji gng)工件所等待，因此，总的工件等待时间即每个工件被等待的时间总和。n n第 i个工件被等待的时间为 ，则所有工件被等待的时间为 n n所有工件的加工(ji gng)时间为 为确定的数n n因此总的完工时间之和为:n n 第23页/共26页第二十四页，共26页。n n（

23、3）中变量说明:表示第 个工件的完工时间（包括等待与加工两个阶段）j=1,2nn n u表示确定时限 n n 表示第 个工件的完工时间超过了确定时限 un nj=1,2n n n 表示第 个工件的完工时间没有超过了确定时限 u j=1,2n n n 表示第 个工件的补偿费率n n根据题目要求，只有超过了确定时限的工件才需要支付(zhf)补偿费用，由此可以得到目标函数为：n n （）n n可根据给出的时间与费率表的出如同（）的约束条件，得出如同（），（）的约束条件。建立了本问题的最优模型第24页/共26页第二十五页，共26页。模型模型(mxng)评价评价n n优点：n n1、模型结构简单，可读性强,容易操作。n n2、模型采用先进算法，利用最优模型，经验证正确率较高，具有很好的通用性和推广性。n n3、模型的建立过程科学严谨，采用专业的计算软件，可信度较高。n n4、原创性很强，文章中的大部分模型都是自行推导(tudo)建立的；n n5、建立的模型能与实际紧密联系，结合实际情况对问题进行求解，使得模型具有很好的通用性和推广性；n nn n缺点：n n1、在问题5的求解过程中，工件加工时限是人为确定的，缺少理论依据。n n2、论文总体把握不是太好，论文格局安排还有待改进。第25页/共26页第二十六页，共26页。