工件加工顺序.doc

B题 机床加工 摘 要 本文讨论了如何排列工件加工顺序分别使工件加工时间总和最小、机床加工总时间最小和加工工件总补偿费用最小这三个问题。 运用线性规划的方法解决了工件加工时间总和最小的问题，建立了模型，结合多个约束条件，使用lingo软件做线性规划得出工件加工顺序为，加工时间最小和为2588。 运用哈米尔顿图原理解决了机床加工总时间最小的问题，使用lingo软件做非线性规划得出加工顺序为 机床最小总加工时间为459。 运用线性规划原理解决了加工工件总补偿费用最小问题，建立了模型，结合约束条件，使用lingo软件做线性规划处理得出工件加工顺序为最小补偿费14242。 文章运用穷举法分别检验建立的三个模型及算出的数据，得出了结论是模型是正确的，数据十分精准。 关键字：线性规划 哈密尔顿图 一、问题重述 现有14件工件等待在一台机床上加工，某些工件的加工必须安排在另一些工件完工以后才能开始。第工件的加工时间及先期完工的工件号用下表给出： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 20 28 25 16 42 12 32 10 24 20 40 24 36 16 前期工号 3,4 5,7,8 5,9 - 10, 11 3,8,9 4 3,5,7 4 - 4,7 6,7,14 5,12 1,2,6  （）给出一个加工顺序，确定了每个工件的完工时间（包括等待与加工两个阶段）。 试设计一个满足条件的加工顺序，使各个工件的完工时间之和达到最小。 ? ? （2）假若第号工件紧接着第号工件后开工，机床需要花费的准备时间试设计一个满足条件的加工顺序，使机床花费的总时间最小。 ? ? ?（3）假定工件的完工时间（包括等待与加工两个阶段）超过一确定时限,则需支付一定的补偿费用，其数值等于超过时间与费率乘积（各个工件补偿率, 见下表）。  1 2 3 4 5 6 7 8 9 10 11 12 13 14 　 12 10 15　 16 10 11 10 8 5 4 10 10 8 12 试在=100，=0，安排一个加工顺序，使的总补偿费用最小。 号工件加工顺序编号； 为各个工件的完工时间之和； 为机床需要花费的总时间； 为补偿费； 为第号工件的完工时间； 其中以上 模型假设 机床在加工工件时不会出现问题。 每个工件可以反复使用。 加工各个工件之间的时间是连续的。 模型的建立与求解 问题一： 根据题意可以设各个工件的完工时间之和为 约束条件为： ， 利用可以得出最佳的方案和结果为： 的最优解为： 问题二： 根据题意要求我们可以绘得如下机床准备时间的有向图： 图 1 图 2 从图中可以看出此图为半哈密尔顿图，起点为，终点为，可以将首尾相接，得到H-圈。根据以上图可以画出邻接矩阵如下表： 表 1 25 2 4 10 14 3 0 8 12 0 4 12 0 12 0 8 10 12 7 8 0 4 11 0 4 6 9 11 0 13 14 16 0 2 4 14 17 19 0 2 18 20 21 0 0 4 15 16 20 0 通过编程得到可以得到满足条件的加工顺序，即： 机床花费的最小准备时间为：114 加工14个工件的总时间为 花费总时间为： 问题三： 目标函数 约束条件： ， 得到： 最小补偿费为： 14242 模型检验 由题意可得一个包括10个工件的不等式 其中没有、、、，可以得到、、、的条件为 分析不等式得，、可放在这条链中的某些节点中，经过排列组合共有19种排法，先对进行排序 见下表 表 2 排列序号 排列的方法 加工这7个工件的完工时间之