工件的安装与排序问题
工件的安装与排序问题
摘要：主要研究工件的排序问题，从两方面进行考虑，一是考虑重量，二是考
虑体积。在工件满足这两个条件时，不需要更换工件，否则需要更换。通过不同的算法，我们确定如何安装和排序的问题。问题1运用了0-1整数规划模型，通过求解得到各个扇形区的工件。问题2同时考虑了重量和体积的问题，使模型更复杂化了。问题3利用了灵敏度分析，能够很快地解答出重量和体积的取值范围。
一、 问题的重述
某设备由24个工件组成，安装时需要按工艺要求重新排序。
Ⅰ．设备的24个工件均匀分布在等分成六个扇形区域的一圆盘的边缘上，放在每个扇形区域的4个工件总重量与相邻区域的4个工件总重量之差不允许超过一定值（如4g ）。
Ⅱ．工件的排序不仅要对重量差有一定的要求，还要满足体积的要求，即两相邻工件的体积差应尽量大，使得相邻工件体积差不小于一定值（如3 ）； Ⅲ．当工件确实不满足上述要求时，允许更换少量工件。 问题1．按重量排序算法；
问题2．按重量和体积排序算法；
问题3．当工件不满足要求时，指出所更换工件及新工件的重量和体积值范围，并输出排序结果。
请按下面两组工件数据（重量单位：g ，体积单位： ），进行实时计算：
二、 问题分析
本题要求给出一种算法对24个工件按重量和体积的约束条件进行组合和排序， 并安装到设备圆周的六个等分扇区上，每个扇区放置四个工件。相邻扇区的工件的重量之差不允许超过一定值，而相邻工件之间的体积差也要满足不小于一定值的约束。
1、问题一的分析： 首先，明确24个工件均匀分布的含义，即工件在每个扇形区域的个数要相等，只能有4个工件在每个扇形区，并且各个扇形区域内工件的质量和要在某一的范围内（4），不能出现过重或过轻的情况。
其次，由以上的均匀分布可得：每个工件必须在且只能在其中的一个扇形区域内，这样，我们就很容易想到0-1规划的指派问题模型。从而利用lingo 软件优化模型，得到结果。 2、问题二的分析：
由于问题二要满足的条件不仅是重量上的，而且还要满足体积上的，所以要同时考虑重量和体积。体积的要求是相邻两个工件之间比较（
3、问题三的分析：
综合考虑重量和体积时，分为以下3种：
⎧当相邻工件的体积满足要求时, 重量不能满足要求⎪
⎨当相邻工件的重量满足要求时, 体积不能满足要求
⎪重量和体积都不满足要求 ⎩
三、 问题的假设与符号说明
（一）、问题的假设：
1．圆盘被均匀分成六个扇形区域，每个区域是固定划分的，工件是按照一定顺序安装到各个位置上去的。
2．给出的两组工件的重量与体积没有关联，互不影响。
3．当只考虑重量因素时，我们假设圆盘足够大，每个扇形区域内的工件重量无论多大，均能放在扇形区域内，不会影响其他区域的重量。 （二）、符号说明：
X(i,j) 第i 个工件是否放在第j 个扇形区内 W(i) 第i 个工件的重量 V(i) 第i 个工件的体积
S(j) 第j 个区4个工件的总重量 m 重量差值 n 体积差值
四、 模型的建立和求解
1．问题1：把24个工件均匀分布在6个扇形区，要求相邻区域的质量达到最小，即每个扇形区内的4个工件总重量与6个扇形区工件重量的均值之差小于一个值m ，让m 最小。 目标函数： Min=m;
首先引入0-1变量：
⎧1, 第i 个工件放在第j 个扇区上 x ij =⎨
0, 第i 个工件不放在第j 个扇区上⎩
约束条件：
显然，由于问题要求每一个工件都要放到圆盘上去，故有
∑x
j =1
6
ij
=1
又，每个扇形区域都要分到4个工件，故有
∑x
i =1
24
ij
=4
每个扇形区4个工件的重量之和与6个扇形区工件重量的均值之差小于一个值m 。
∑x
i =1
24
ij
*wi -339*4
详细代码请看附录，现将实例中提供的两组数据运行结果如下： （第一组数据结果）
第一扇区：1,11,18,24 （其重量和为：1357） 第二扇区：9,13,14,21（其重量和为：1357） 第三扇区：5,15,19,20 （其重量和为：1357） 第四扇区：3,6,12,22 （其重量和为：1357） 第五扇区：2,4,8,10 （其重量和为：1357.5） 第六扇区：7,16,17,23 （其重量和为：1357）
（第二组数据结果）
第一扇区：2,6,7,9 （其重量和为：1395.5） 第二扇区：14,15,19,20 （其重量和为：1395） 第三扇区：1,12,18,23（其重量和为：1395.5） 第四扇区：4,10,17,24 （其重量和为：1396） 第五扇区：3,8,16,22 （其重量和为：1395） 第六扇区：5,11,13,21（其重量和为：1395）
问题1的改进：通过对数据的分析，让它从小到大进行排序，先把前三个最大的数和倒三小的数组合成三组，依次下去让它每四个数据组合在一块，形成六个扇
第二组得到：
2. 问题2：通过问题的要求，知道重量和体积的约束从而进行建立模型。主要思想是把体积作为目标条件，而约束条件是重量不允许超过一定值，相邻的两个工件体积差值达到最大n 。 目标函数：max=n; 约束条件： 首先引入0-1变量：
⎧1, 第i 个工件放在第j 个扇区上
x ij =⎨
⎩0, 第i 个工件不放在第j 个扇区上
v i+1- vi |>=n (i从1到23取值)
|v 24- v1|>=n
|
∑x
j =1
6
ij
=1
∑x
i =1
24
ij
=4
Mj+1- Mj
M 6--M 1
注：j 已经分为了24个区
分工件的体积不满足要求，得进行更换工件，第一组数据需要更换10,12；3,16；23,24；1,9。第二组数据需要更换2,5；3,16；23,24。
3. 问题3：工件不满足要求，则要更换工件来使得工件的重量和体积都得到条件约束。由问题2可得只需在问题二的基础上改变一些工件的体积使它们的差值大于3，第一组数据需要更换10,12；3,16；23,24；1,9。第二组数据需要更换2,5；3,16；23,24。
五、模型的评价和推广
本文针对题目提出的不同要求，我们分别给出了按重量和体积排序的不
同的模型和算法，对于问题一，我们建立了以各扇区对重量均值作差后取绝对值最小为目标函数的模型，再用限制条件 加以控制，得出了在各扇区重量波动范围较小下的排序，但由于数据的取值是离散的，而且各扇区的重量取值是不独立的，同时也存在波动范围较大情况下合理的排序，我们还做了一个适合一般情况的模型，具体思路如下：
首先，将24个工件按重量从小到大依次排序，若相等则归为一类，设
共有m 类，第i 类的单个重量为w i ，共有p i 件，放入第j 个扇区的第i 类工件的件数为 x ij ，i =1,2,…m , , j =1,2,…,6, 有：
min z = max { |∑x ij . w i -∑x i (j +1) . w i |, |∑x i 6. w i -∑x i 1. w i | }
i =1,2,...,5m
i =1
i =1
i =1
i =1
m
m
m
m
使得 ∑x ij =4，j =1,2,…,6;
i =1
∑∑x ij =24;
i =1j =1
m 6
x ij =0,1,…, p i .
对于该模型，我们考虑了网络搜索法来求解，另外，当
max {|∑x . w -∑x
ij
i
m m
i (j +1)
i =1,2,...,5i =1i =1
. w i |, |∑x i 6. w i -∑x i 1. w i | } ≤ε 时，我们就
i =1
i =1
m m
可以找到一组可行解，当min z =
m
m
max { |∑x . w -∑x
ij
i
m m
i (j +1)
. w i |,
i =1,2,...,5i =1i =1
|∑x i 6. w i -∑x i 1. w i | } >ε 时，我们就无法找到一种排序来满足条件，此
i =1
i =1
时必须更换新工件。
定理：针对重量，对任意一组数据，必须更换新工件的充要条件：
min z = max { |∑x ij . w i -∑x i (j +1) . w i |, |∑x i 6. w i -∑x i 1. w i | } >ε
i =1,2,...,5
i =1
i =1
i =1
i =1
m
m
m
m
定理：针对体积，对任意一组数据，必须更换新工件的充要条件：
m ax z =min {|∑x ij . v i -∑x i (j +1) . v i |，|∑x i (24). v i -∑x i 1. v i |}
i =1,2,...,23
i =1
i =1
i =1
i =1
m
m
m
m
对于问题二，我们找到了一种比较有效的方法对所提供数据进行了排
序，得到了模型的算法图。 对于问题三，我们对各种可能出现的情况进行了详细的分类讨论，可操作性还是比较强的，通过更换是可以达到条件要求的。此时，我们在理论上已建立了整个排序过程的完整体系，利用了C 语言编程对模型进行的求解，所得到的结果都通过了验证，体现了我们算法的合理性和结果的正确性。有的模型的算法较难实现，故有一定的缺陷。
参考文献：（略）
附录：问题一的程序：
model : sets :
shanqu/1..6/:s; gongjian/1..24/:w;
link(gongjian,shanqu):x; endsets data :
w=348 352 347 349 347.5 347 330 329 329 327.5 329 331.5 348.5 347 346.5 348 347.5 348 333 330 332.5 331.5 331.5 332; enddata ! 目标函数; min =m;
! 每个扇区的4个工件重量之和与各区重量均值之差小于m; @for(shanqu(j):
@abs(@sum(link(i,j):x(i,j)*w(i)-339*4))
@sum(gongjian(i):x(i,j))=4;); ! 每个工件只能放在一个扇区; @for(gongjian(i):
@sum(shanqu(j):x(i,j))=1;); @for(link(i,j):@bin(x));
@for(shanqu(j):@sum(gongjian(i):w(i)*x(i,j))=s(j)); end
部分运行结果：
S( 1) 1357.000 S( 2) 1357.000
S( 3) 1357.000 S( 4) 1357.000 S( 5) 1357.500 S( 6) 1357.000 X( 1, 1) 1.000000
X( 1, 2) 0.000000 X( 1, 3) 0.000000 X( 1, 4) 0.000000 X( 1, 5) 0.000000 X( 1, 6) 0.000000 X( 2, 1) 0.000000 X( 2, 2) 0.000000 X( 2, 3) 0.000000 X( 2, 4) 0.000000 X( 2, 5) 1.000000 X( 2, 6) 0.000000
X( 3, 2) 0.000000 X( 3, 3) 0.000000 X( 3, 4) 1.000000 X( 3, 5) 0.000000 X( 3, 6) 0.000000 X( 4, 1) 0.000000 X( 4, 2) 0.000000 X( 4, 3) 0.000000 X( 4, 4) 0.000000 X( 4, 5) 1.000000 X( 4, 6) 0.000000 X( 5, 1) 0.000000 X( 5, 2) 0.000000 X( 5, 3) 1.000000 X( 5, 4) 0.000000 X( 5, 5) 0.000000 X( 5, 6) 0.000000 X( 6, 1) 0.000000 X( 6, 2) 0.000000 X( 6, 3) 0.000000 X( 6, 4) 1.000000 X( 6, 5) 0.000000 X( 6, 6) 0.000000 X( 7, 1) 0.000000 X( 7, 2) 0.000000 X( 7, 3) 0.000000 X( 7, 4) 0.000000 X( 7, 5) 0.000000 X( 7, 6) 1.000000 X( 8, 1) 0.000000 X( 8, 2) 0.000000 X( 8, 3) 0.000000 X( 8, 4) 0.000000 X( 8, 5) 1.000000 X( 8, 6) 0.000000 X( 9, 1) 0.000000 X( 9, 2) 1.000000 X( 9, 3) 0.000000 X( 9, 4) 0.000000 X( 9, 5) 0.000000 X( 9, 6) 0.000000 X( 10, 1) 0.000000 X( 10, 2) 0.000000
X( 10, 4) 0.000000 X( 10, 5) 1.000000 X( 10, 6) 0.000000
X( 11, 1) 1.000000 X( 11, 2) 0.000000 X( 11, 3) 0.000000 X( 11, 4) 0.000000 X( 11, 5) 0.000000 X( 11, 6) 0.000000 X( 12, 1) 0.000000 X( 12, 2) 0.000000 X( 12, 3) 0.000000 X( 12, 4) 1.000000 X( 12, 5) 0.000000 X( 12, 6) 0.000000 X( 13, 1) 0.000000 X( 13, 2) 1.000000 X( 13, 3) 0.000000 X( 13, 4) 0.000000 X( 13, 5) 0.000000 X( 13, 6) 0.000000 X( 14, 1) 0.000000 X( 14, 2) 1.000000 X( 14, 3) 0.000000 X( 14, 4) 0.000000 X( 14, 5) 0.000000 X( 14, 6) 0.000000 X( 15, 1) 0.000000 X( 15, 2) 0.000000 X( 15, 3) 1.000000 X( 15, 4) 0.000000 X( 15, 5) 0.000000 X( 15, 6) 0.000000 X( 16, 1) 0.000000 X( 16, 2) 0.000000 X( 16, 3) 0.000000 X( 16, 4) 0.000000 X( 16, 5) 0.000000 X( 16, 6) 1.000000 X( 17, 1) 0.000000 X( 17, 2) 0.000000 X( 17, 3) 0.000000
X( 17, 5) 0.000000
X( 17, 6) 1.000000
X( 18, 1) 1.000000
X( 18, 2) 0.000000
X( 18, 3) 0.000000
X( 18, 4) 0.000000
X( 18, 5) 0.000000
X( 18, 6) 0.000000
X( 19, 1) 0.000000
X( 19, 2) 0.000000
X( 19, 3) 1.000000
X( 19, 4) 0.000000
X( 19, 5) 0.000000
X( 19, 6) 0.000000
X( 20, 1) 0.000000
X( 20, 2) 0.000000
X( 20, 3) 1.000000
X( 20, 4) 0.000000
X( 20, 5) 0.000000
X( 20, 6) 0.000000
X( 21, 1) 0.000000
X( 21, 2) 1.000000
X( 21, 3) 0.000000
X( 21, 4) 0.000000
X( 21, 5) 0.000000
X( 21, 6) 0.000000
X( 22, 1) 0.000000
X( 22, 2) 0.000000
X( 22, 3) 0.000000
X( 22, 4) 1.000000
X( 22, 5) 0.000000
X( 22, 6) 0.000000
X( 23, 1) 0.000000
X( 23, 2) 0.000000
X( 23, 3) 0.000000
X( 23, 4) 0.000000
X( 23, 5) 0.000000
X( 23, 6) 1.000000
X( 24, 1) 1.000000
X( 24, 2) 0.000000
X( 24, 3) 0.000000
X( 24, 4) 0.000000
X( 24, 5) 0.000000
问题二的程序：
model :
sets :
gongjian/1..24/:w,v;
gongqu/1..24/;
shanqu/1..6/:m;
link(gongjian,shanqu):x;
endsets
data :
w=348 352 347 349 347.5 347 330 329 329 327.5 329 331.5 348.5 347 346.5 348 347.5 348 333 330 332.5 331.5 331.5 332;
v=101.5 102 105 105.5 106 104 94 98 100.5 98.5 98 99 104.5 105 107.5 104.5 104 104.5 97 97 99 98 96.5 94.5;
enddata
max =n;
@for(gongjian(i)|i#le#23:@abs(v(i+1)-v(i))>n);
@abs(v(24)-v(1))>n;
@for(shanqu(j):@sum(gongjian(i):x(i,j))=4);
@for(gongjian(i):@sum(shanqu(j):x(i,j))=1);
@for(shanqu(j):@sum(gongjian(i):w(i)*x(i,j))=m(j));
@for(shanqu(j)|j#le#5:@abs(m(j+1)-m(j))
@abs(m(6)-m(1))
@for(link:@bin(x));
end
部分运行结果：
M( 1) 1358.500 0.000000
M( 2) 1356.500 0.000000
M( 3) 1354.000 0.000000
M( 4) 1357.500 0.000000
M( 5) 1358.500 0.000000
X( 1, 1) 0.000000 0.000000 X( 1, 2) 0.000000 0.000000 X( 1, 3) 0.000000 0.000000 X( 1, 4) 0.000000 0.000000 X( 1, 5) 0.000000 0.000000 X( 1, 6) 1.000000 0.000000 X( 2, 1) 1.000000 0.000000 X( 2, 2) 0.000000 0.000000 X( 2, 3) 0.000000 0.000000 X( 2, 4) 0.000000 0.000000 X( 2, 5) 0.000000 0.000000 X( 2, 6) 0.000000 0.000000 X( 3, 1) 0.000000 0.000000 X( 3, 2) 0.000000 0.000000 X( 3, 3) 0.000000 0.000000 X( 3, 4) 0.000000 0.000000 X( 3, 5) 1.000000 0.000000 X( 3, 6) 0.000000 0.000000 X( 4, 1) 0.000000 0.000000 X( 4, 2) 0.000000 0.000000 X( 4, 3) 0.000000 0.000000 X( 4, 4) 1.000000 0.000000 X( 4, 5) 0.000000 0.000000 X( 4, 6) 0.000000 0.000000 X( 5, 1) 1.000000 0.000000 X( 5, 2) 0.000000 0.000000 X( 5, 3) 0.000000 0.000000 X( 5, 4) 0.000000 0.000000 X( 5, 5) 0.000000 0.000000 X( 5, 6) 0.000000 0.000000 X( 6, 1) 0.000000 0.000000 X( 6, 2) 1.000000 0.000000 X( 6, 3) 0.000000 0.000000 X( 6, 4) 0.000000 0.000000 X( 6, 5) 0.000000 0.000000 X( 6, 6) 0.000000 0.000000 X( 7, 1) 0.000000 0.000000 X( 7, 2) 1.000000 0.000000 X( 7, 3) 0.000000 0.000000 X( 7, 4) 0.000000 0.000000 X( 7, 5) 0.000000 0.000000 X( 7, 6) 0.000000 0.000000 X( 8, 1) 0.000000 0.000000
X( 8, 3) 0.000000 0.000000 X( 8, 4) 1.000000 0.000000 X( 8, 5) 0.000000 0.000000 X( 8, 6) 0.000000 0.000000 X( 9, 1) 0.000000 0.000000 X( 9, 2) 0.000000 0.000000 X( 9, 3) 0.000000 0.000000 X( 9, 4) 0.000000 0.000000 X( 9, 5) 0.000000 0.000000 X( 9, 6) 1.000000 0.000000 X( 10, 1) 1.000000 0.000000 X( 10, 2) 0.000000 0.000000 X( 10, 3) 0.000000 0.000000 X( 10, 4) 0.000000 0.000000 X( 10, 5) 0.000000 0.000000 X( 10, 6) 0.000000 0.000000 X( 11, 1) 0.000000 0.000000 X( 11, 2) 0.000000 0.000000 X( 11, 3) 1.000000 0.000000 X( 11, 4) 0.000000 0.000000 X( 11, 5) 0.000000 0.000000 X( 11, 6) 0.000000 0.000000 X( 12, 1) 1.000000 0.000000 X( 12, 2) 0.000000 0.000000 X( 12, 3) 0.000000 0.000000 X( 12, 4) 0.000000 0.000000 X( 12, 5) 0.000000 0.000000 X( 12, 6) 0.000000 0.000000 X( 13, 1) 0.000000 0.000000 X( 13, 2) 0.000000 0.000000 X( 13, 3) 1.000000 0.000000 X( 13, 4) 0.000000 0.000000 X( 13, 5) 0.000000 0.000000 X( 13, 6) 0.000000 0.000000 X( 14, 1) 0.000000 0.000000 X( 14, 2) 0.000000 0.000000 X( 14, 3) 0.000000 0.000000 X( 14, 4) 1.000000 0.000000 X( 14, 5) 0.000000 0.000000 X( 14, 6) 0.000000 0.000000 X( 15, 1) 0.000000 0.000000 X( 15, 2) 0.000000 0.000000 X( 15, 3) 1.000000 0.000000
X( 15, 5) 0.000000 0.000000 X( 15, 6) 0.000000 0.000000 X( 16, 1) 0.000000 0.000000 X( 16, 2) 0.000000 0.000000 X( 16, 3) 0.000000 0.000000 X( 16, 4) 0.000000 0.000000 X( 16, 5) 1.000000 0.000000 X( 16, 6) 0.000000 0.000000 X( 17, 1) 0.000000 0.000000 X( 17, 2) 0.000000 0.000000 X( 17, 3) 0.000000 0.000000 X( 17, 4) 0.000000 0.000000 X( 17, 5) 0.000000 0.000000 X( 17, 6) 1.000000 0.000000 X( 18, 1) 0.000000 0.000000 X( 18, 2) 1.000000 0.000000 X( 18, 3) 0.000000 0.000000 X( 18, 4) 0.000000 0.000000 X( 18, 5) 0.000000 0.000000 X( 18, 6) 0.000000 0.000000 X( 19, 1) 0.000000 0.000000 X( 19, 2) 0.000000 0.000000 X( 19, 3) 0.000000 0.000000 X( 19, 4) 0.000000 0.000000 X( 19, 5) 0.000000 0.000000 X( 19, 6) 1.000000 0.000000 X( 20, 1) 0.000000 0.000000 X( 20, 2) 0.000000 0.000000 X( 20, 3) 1.000000 0.000000 X( 20, 4) 0.000000 0.000000 X( 20, 5) 0.000000 0.000000 X( 20, 6) 0.000000 0.000000 X( 21, 1) 0.000000 0.000000 X( 21, 2) 0.000000 0.000000 X( 21, 3) 0.000000 0.000000 X( 21, 4) 1.000000 0.000000 X( 21, 5) 0.000000 0.000000 X( 21, 6) 0.000000 0.000000 X( 22, 1) 0.000000 0.000000 X( 22, 2) 1.000000 0.000000 X( 22, 3) 0.000000 0.000000 X( 22, 4) 0.000000 0.000000 X( 22, 5) 0.000000 0.000000
X( 23, 1) 0.000000 0.000000 X( 23, 2) 0.000000 0.000000 X( 23, 3) 0.000000 0.000000 X( 23, 4) 0.000000 0.000000 X( 23, 5) 1.000000 0.000000 X( 23, 6) 0.000000 0.000000 X( 24, 1) 0.000000 0.000000 X( 24, 2) 0.000000 0.000000 X( 24, 3) 0.000000 0.000000 X( 24, 4) 0.000000 0.000000 X( 24, 5) 1.000000 0.000000 X( 24, 6) 0.000000 0.000000