工件排序的均匀差值和检验标号算法.doc

《工件排序的均匀差值和检验标号算法.doc》由会员分享，可在线阅读，更多相关《工件排序的均匀差值和检验标号算法.doc（12页珍藏版）》请在三一文库上搜索。

1、工件排序的均匀差值和检验标号算法邓 鑫，侯志白，张子阳（徐州空军学院，徐州 221000）摘要：本文以目标规划基本理论为基础，借鉴整数规划中的0-1规划的特征，实现了工件摆放位置与工件重量，体积的联系，建立重量排序模型，以及重量与体积双重目标下的排序模型，运用lingo进行求解。但作者不局限于lingo求出的可行解，而是大胆创新，针对题目数据的特点，提出依据大小顺序每6个工件分段的思想，首先采用均匀差值算法找到了重量排序的满意解；其次，在满意解的基础上，运用检验标号，不仅满足了体积要求，而且直观明了，当工件不满足要求时，能够具体找出需要更换的工件所处的位置以及重量和体积值的范围。填补了ling

2、o只能求解不能反映临界状态，不能进行灵敏度分析的空白一.问题的重述某设备由24个工件组成，安装时需要按工艺要求重新排序。设备的24个工件均匀分布在等分成六个扇形区域的一圆盘的边缘上，放在每个扇形区域的4个工件总重量与相邻区域的4个工件总重量之差不允许超过一定值（如4g）。工件的排序不仅要对重量差有一定的要求，还要满足体积的要求，即两相邻工件的体积差应尽量大，使得相邻工件体积差不小于一定值（如3）；当工件确实不满足上述要求时，允许更换少量工件。问题1按重量排序算法；问题2按重量和体积排序算法；问题3当工件不满足要求时，指出所更换工件及新工件的重量和体积值范围，并输出排序结果。二问题的分析工件安装

3、时，按工艺要求重新排序，排序要满足重量要求，如果各区域之间的重量差M越小，运行就越稳定，寿命就越长；还要符合体积要求,假如相邻工件的体积差Q越大，那么在安装时区分度就越大，结构简单，安装方便。综合考虑这两个指标时。同时处理两个目标比较困难，而且如果去求多个目标的最优解还会导致一些相互矛盾的结果，那么运用目标规划的理论，根据实际情况去确定模型，采用实际数据去求解，将重量要求设为高级目标，体积要求设为低级目标，借鉴分层序列法，在高级目标达到满意解的基础上，求低级目标的满意解。这种方法突出强调了高级目标的重要性，当高级目标要求较高时，造成满意解的数目较少，此时再去求低级目标的满意解，可能会导致无解。

4、三基本假设1. 各个工件之间体积之差并非全部超过一定值Q；2. 将圆盘划分为24个位置，每个工件对应圆盘上的一个位置，则相邻的4个位置划分为一个扇形区域；3. 圆盘有一定的强度，不会因为重量过分集中于一个区域导致轴等部件损坏，使得排序无法进行；4. 圆盘上的工件排序以顺时针为标准进行排序。四符号说明 每个扇形区域的4个工件总重量与相邻的4个工件总重量之差不允许超过的一定值； 相邻工件体积差不小于的一定值；表示圆盘等分成的区域，；表示第i个工件的重量；表示第i个工件的体积； 表示第i个位置工件的重量，J为该工件的序号； 表示第i个位置工件的体积； 表示； 表示第i个位置的工件； 表示第i个工件被

5、安排在圆盘的第j个位置，0或1； 满足相邻区域总重量和的差值不超过一定值M的满意解的集合； 表示正偏差变量，； 表示负的偏差变量，； 表示优先因子，规定远大于。五模型的建立与求解5.1 问题一 重量排序算法5.1.1问题分析设备的24个工件均匀分布在等分成6个扇形区域的一个圆盘的边缘，所以可以将圆盘划分为24个位置，每个工件对应圆盘上的一个位置，就表示第i个工件被放在第j个位置，而相邻的4个位置就构成了一个扇形区域。那么以6个扇形区域为列，24个工件的重量为24行，组成了一个24*6的矩阵：因为在这个扇形区域中的4个工件的总重量与相邻区域中的4个工件的总重量不允许超过一定值M，所以问题的模型为

6、： (1)运用Lingo软件可以对模型1进行求解，得到的是一个可行解的集合R(M)，当M的取值越大时，集合R(M)中的可行解的数目就越多，相反则越少。5.1.2 算法讨论1问题用Lingo求解模型时，当一定值M较大时，虽然可行解较多，但许多可行解处于临界状态，以这样的解为基础无法实现相邻工件体积差不小于一定值Q的要求，而当一定值M较小时，求解模型所需要的时间很长，如果增加工件数目，模型将无法用Lingo求解。2思路 显然各区域中工件的总重量越接近一个平均值，相邻区域之间的总重量和的差就会越小，如果这个差小于一定值M，那么这样的一个均匀分组构成的排序就成为一个可行解。3算法实现STEP1 将24

7、个工件从小到大进行排序；STEP2 以重量从轻到重的的顺序，每6个工件分一段，分成四段，每段中的 工件的重量值在一个区间内，后一段的区间内的值大于前一段的区间内的值；STEP3 将最后一段中的6个工件放入6个区域内，以第4个区域中的工件重量值为中位数，求出其它区域中的工件的重量值与中位数的差值；STEP4 将前一段中的最轻的工件放入差值最大的区域中，将重量次轻的工件放入差值其次大的区域中。依此原则，将该段中6个工件放入6个区域中；STEP5 比较各区域中工件重量与第4区域中的工件重量的差值，重复STEP4，直到4 段中的工件均已放入6个区域中；STEP6 观察法进行手工调整。4举例说明（1）

8、对于第一组工件数据进行从小到大排序，如下图：序号108911720重量327.5329329329330330体积98.598100.5989497序号122223242119重量331.5331.5331.5332332.5333体积999896.594.59997序号153614517重量346.5347347347347.5347.5体积107.5105104105106104序号116181342重量348348348348.5349352体积101.5104.5104.5104.5105.5102（2） 将标中最后一段中的工件放入6个区域中，并计算差值：123456序号重量差值序号重

9、量差值序号重量差值序号重量差值序号重量差值序号重量差值235244349113348.50.518348016348013480（3） 按差值原则将第3段中的6个工件放入6个区域中：12345623524434911334850518348016348013480153465-0.533470634701434705347.50.517347.50.53.510.500.50.5（4） 按差值原则将第2段，第1段中的工件放入6个区域中，得到如下图所示的初始解：123456序号重量差值序号重量差值序号重量差值序号重量差值序号重量差值序号重量差值235244349113348.50.5134801

10、6348018348015346.5-0.533470634701434705347.50.517347.50.512331.5-0.522331.5-0.523331.5-0.524332021332.50.519333110327.5-2.58329-1733002033009329-111329-11357.51356.51357135713571357.5（5） 观察发现第一个区域与第二个区域的总重量差为1，而第三个区域与第四个区域的重量差为0，所以将第二个区域与第三个区域互换位置，同时可以将第三区域中的17号工件与3号工件互换，结果如下表所示123456序号重量差值序号重量差值序号重

11、量差值序号重量差值序号重量差值序号重量差值2352413348.50.5434911348016348018348015346.5-0.56347017347.50.51434705347.50.53347012331.5-0.523331.5-0.522331.5-0.524332021332.50.519333110327.5-2.5733008329-12033009329-111329-11357.513571357135713571357 0.500000.55评价：该算法明显优于用Lingo求解模型，观察工件重量与体积的关系，伴随着重量的增大，体积的数值大体集中在两个区间内。划分成

12、的4段必然使其中的2段在一个区间内，另两段在另一个区间内，这样在一个圆盘上划分的区域中，工件体积的数值两两分布在不同的区间内，为满足体积要求创造了良好的前提条件。5.2 问题二 重量和体积排序算法5.2.1问题分析工件的排序不仅要对重量差有一定的要求，还要满足体积的要求，即相邻工件的体积差应尽量大，使得相邻工件的体积差不小于一定值Q。因为模型二的高级目标是满足相邻区域的重量差不超过一定值M，所以在求解相邻工件的体积差不小于一定值Q的低级目标时，可以考虑在模型一中得到的高级目标的可行解的集合R(M)中寻找低级目标的解。如果满足低级目标的解不满足高级目标，就意味着低级目标的达到破坏了高级目标的保持

13、，违反了目标规划的原则。根据题意，建立模型：MIN=+ (i=1,2,3,4,5，6) (j=1,2,24)(j=1,2,3,4,5) (2) (j=1,2,23)或1（i=1,2,3,4,5,6;j=1,2,24），,.运用Lingo模型可以对模型2进行求解，将M设为4，N设为3，可以求得一个可行解。5.2.2算法分析 1.问题 运用Lingo软件去求解模型，发现运行时间较长。经过前面的分析,在满足高级目标的满意解中寻找低级目标的满意解，当目标较多时，必然导致“维数灾难”，无法用软件求解，2.思路 不妨以模型一的方法求解出来的可行解为基础，将寻找满足低级目标的解的求解过程，用程序框图演示出来

14、：取R(M)中的一个可行解在六个区域中分别求分在同一区域中的相邻工件之间的体积差改变区域内四个工件的排序两区域之间的工件进行调整，重量差不超过定值M的条件下改变体积排序结果体积差大于定值体积差小于定值体积差大于定值体积差小于定值连接各区域形成初始方案体积差大于定值体积差小于定值灵敏度分析 调换工件3.算法实现当进行调整时，首先进行区域排序使得一个区域中的体积较大的工件与另一个区域的体积较小的工件相邻，对排序结果进行观察，此时既有区域内的工件调整不满足体积要求，又有区域与区域之间的相邻工件不满足体积要求，依照如下步骤对一组相邻工件进行调整：STEP0: 对各区域工件的体积进行排序，为了使各区域中

15、相邻工件的体积差最大，将模型一求得的可行解中每一区域处在2，3段的工件进行交换，STEP1；STEP1: 比较相邻位置上工件的体积得到体积偏差 （i=1,223）， （即），取，若，STEP2；否，STEP7；STEP2: 若，选取第i个工件。是，STEP3；否，STEP5。STEP3: 引入检验标号，考虑将第i个位置上的工件与第j个位置上的工件互换。表示因为第j个位置上工件变化而引起的重量差的变化，表示因为第i个位置上工件变化而引起的重量差的变化。若，或，都不大于3，则STEP4；否，STEP1(都大于3，且小于4)。STEP4: 取第i+1个位置上的工件，引入检验标号，考虑第i+1个位置上

16、的工件与第j个位置上的工件互换。表示因为第j个位置上工件变化而引起的重量差的变化，表示因为第i个位置上的工件变化而引起的重量差的变化。若，或，都不大于3，则STEP8；否，STEP1。STEP5: 若，选取第j个工件与第1个工件交换，引检验号，为，为。若，或，都不大于3，则STEP6；否，STEP1。STEP6: 选取第24个位置的工件与第j个交换。若，选取第j个工件与第1个工件交换，引检验号，为，为。若，若，或，都不大于3，则STEP8；否，STEP1。STEP7: 停止排序，输出结果。STEP8: 停止排序，输出的两个工件的位置。根据前后与的体积，对进行灵敏度分析，求出的调解范围。 下面根

17、据算法，就第一组工件在问题一的可行解的基础上对问题二进行求解： 将问题一的可行分配方案在考虑体积偏差的情况下进行制表，如下表所示：1 352 25 349 49 348.5 1313 348 1817 348 1621 348 131027.5105.57.5104.510104.55.5104.54.5101.52 331.5 12 6 331.5 2210 330 2014 332 2418 332.5 2122 333 19-6.599-898-897-11.594.5-599-7973 346.5 157 347.5 511 347 1415 347 319 347 623 347.5

18、 179107.58106111058.510561044.51044 327.5 108 329 812 330 716 331.5 2320 329 1124 329 9-798.5-6.598-10.594-896.5-3.598-1.5100.50.50000-0.5 i j对表格的说明： i为圆盘上的第i个位置； 为第i个位置工件的重量，j为该工件的序号； 为第i个位置工件的体积； 表示。 调整方法： 在图表中寻找，若则分配方案既满足重量偏差又满足以及体积偏差；如果，则依照算法进行调整。对图表进行分析，得到，下面对和的分配方案进行调整：1.对的分配调整通过寻找可以得到如下位置的工件：

19、 ， ， ， ，. 其中满足体积偏差条件的工件有：，。 在满足体积偏差的条件下使得相邻区域质量偏差最小的是：，。 2.对的分配调整 在表格中寻求，但找不到满足重量检验向量的工件，故不可调整。 3.对和 进行调整后，寻求得到，则得到问题二的可行分配方案。如下表所示：1 352 25 349 49 348.5 1313 348 1817 348 1621 348 131027.5105.57.5104.510104.55.5104.54.5101.52 331.5 12 6 331.5 2210 330 2014 332 2418 332.5 2122 333 19-6.599-898-897-1

20、1.594.5-599-7973 346.5 157 347.5 511 347 1415 347 319 347 623 347.5 179107.58106111058.510561044.51044 327.5 108 329 812 330 716 331.5 2320 329 1124 329 9-798.5-4100.5-10.594-896.5-3.598-4980.50000-0.5总结：对于第一组工件，问题二可以通过分配方案的调整来满足体积和重量偏差的要求，不需要更换工件5.3 问题三 当工件不满足要求时，关于临界状态的灵敏度分析 由问题一和问题二的算法，可以得到：当工件不满

21、足要求时，算出返回不合条件的工件位置，根据分配矩阵可以得到工件的序号.体积和重量。 就问题二而言，设不满足的工件位置为体积为，根据，对进行灵敏度分析，使得，且或对进行灵敏度分析，使得，且 因为工件在圆盘上排列，第一位置与第二位置的工件相邻也要满足体积偏差大于等于3，如果算法返回不满足，则对进行灵敏度分析且或对进行灵敏度分析同上。 通过对不合条件的两工件进行灵敏度分析，可以得到两工件的各自体积的调整范围，以上是对一对不合条件的工件进行的调整，对于多个工件的情况，调整方法同上。 以上是在满足重量偏差的条件下进行的灵敏度分析，如果将高级目标设为满足体积差的条件还可在优先满足体积差的条件下进行不合重量

22、偏差条件的灵敏度分析。5.4对于第二组数据的求解 运用模型一二的算法求解第二组数据，如下表123456序号重量差值序号重量差值序号重量差值序号重量差值序号重量差值序号重量差值1358.51.513357.50.52357.50.56357016356.5-0.517356-14351-418352.5-2.515353.5-1.5335501435505355.50.5243452.5203441.5103441.511342.5012343.5119342.50734108342121339.5-1.52334109340-122341.50.51395.513961394.51395.51

23、3951395 将第一区域与第二区域对调，使得相邻区域间重量差达到较小； 将每个区域内二，三段的工件对换位置，不同区域间以体积较大的工件与体积较小的工件相邻的原则进行排序，最终形成的排序既满足重量差要求，又满足体积差要求，如下表所示：123序号重量体积序号重量体积序号重量体积13357.5102.51.58.51032357.510318352.51044351103.515353.5103.52034496.524345971034497834296.573419621339.59813961395.51394.5456序号重量体积序号重量体积序号重量体积635710216356.5103.517356103.511342.595.112343.596.519342.5983355103143551035355.51032334196934095.522341.5961395.513961394.5六建议、评价（略） 七参考文献（略）