1、工件的安裝與排序問題的模型陳雪平，于慶，楊念(徐州師范大學，徐州221000)摘要：本文以實際工件的安裝為背景，討論了工件的排序問題。通過認真 分析工件安裝時的工藝要求，針對相鄰扇區重量和的差不大于一定值的限制條 件，考慮各扇區重量和的值波動范圍較小和較大的兩種情況，分別建立了模型。 模型一主要使各扇區重量和穩定于均值，建立規劃模型，并借助C語言編程實現求解；模型二則直接比較相鄰扇區重量和的差值， 使之最大值盡可能小，來滿 足工件安裝的重量要求。而同時考慮重量和體積時，我們采用先按重量粗分，再 按體積細分來排序。通過對模型的求解，我們得到了合理的排序結果。現列出第 一組工件序號的排序結果如下表

2、：(方括號內為此扇區工件的重量和；圓括號內為此工件的體積 )扇區1扇區2扇區3扇區4扇區5扇區6問題20 12 17 111 23 14 188 21 3 410 19 13 29 24 6 137 22 5 16-一-13591357.51356.51355.513571357問題2 (102)14(105)6(104)12(99)1(101.5)5(106)-二二19(97)21(99)24(94.5)3(105)22(98)23 ( 96.5)15 (107.5)4(105.5)13 (104.5)8(98)17(104)18 (104.5)10 (98.5)11(98)9(100.5)

3、16(104.5)20(97)7(94)13591357.51356.51355.513571357當無法通過內部調試來滿足要求時，我們詳細討論了更換新工件的各種情 況，并提出了具體的解決方案，給出了更換新工件重量和體積的范圍。如： 當被更換工件的重量為g時，新工件的重量g'的范圍：max g(i) - g(k) - .g(j)亠 g _g' _ min g (i)亠二 g (k ) ; ： - g (j )亠 g 當被更換工件的體積為v(j)時，新工件的體積V(j)的范圍：v (j) _max v(i)亠 8, v ( k )亠 3 或 v (j): min v(i) 3,v

4、(k) 8本文所建立的數學模型，能有效地解決工件的安裝與排序問題。最后文章對 模型做出了評價與推廣，對實際應用具有一定的指導意義一、問題的重述工廠在安裝某設備的工件時，需要按工藝的要求對工件進行重新排序。本 題中，將24個工件放在等分成6個扇形區域的一圓盤的邊緣上，每個扇形區域 內都要放上4個工件。針對工件的重量和體積有不同的排序原則，提出了以下3個問題：問題一：只考慮工件的重量時，保證每個扇形區域內的4個工件總重量與相鄰區域內的4個工件總重量之差不超過一定值(如：4g );問題二：同時考慮工件的重量與體積時，除了要保證每個扇形區域內的4個工件總重量與相鄰區域內的 4個工件總重量之差不超過一定

5、值（如：4g ）外, 為充分利用圓盤空間，還提出了體積的要求，即要滿足兩個相鄰工件的體積差盡 量大，使得兩個相鄰工件的體積差不小于一定值（如：3cm3）；問題三：當這組工件確實不滿足重量或體積要求時，允許更換少量工件，指出所更換工件，及新工件的重量和體積值范圍，并輸出排序結果。問題要求我們做的工作如下：1、建立一個合理的模型和相應的算法，將 24個工件均勻的放在6個扇形 區域內，使得每個扇形區域的4個工件總重量與相鄰區域內的4個工件 總重量之差不超過一定值（如：4g），并輸出排序結果。2、 建立一個能夠同時滿足重量和體積要求的模型和相應的算法，將24個 工件，有序地排放在圓盤的邊緣上，輸出排序

6、結果。3、在模型的建立和求解中，考慮不滿足重量和體積要求的情況， 提出更換 的方法和范圍。4、實時計算，按給定的兩組工件數據求解出排序結果。如不滿足要求，則進行更換，指出更換的工件及新工件的重量和體積范圍。二、問題的分析1、問題一的分析：首先，明確24個工件均勻分布的含義，即工件在每個扇形區域的個數要相等， 不能多于或少于4,并且各個扇形區域內工件的質量和要在某一的范圍內，不能 出現過重或過輕的情況。其次，由以上的均勻分布可得：每個工件必須在且只能在其中的一個扇形區 域內，這樣，我們就很容易想到0-1規劃的指派問題模型。2、問題二的分析：由于問題二要滿足的條件不僅是重量上的，而且還要滿足體積上

7、的，所以要 同時考慮重量和體積。體積的要求是相鄰兩個工件之間比較，而重量的要求是相 鄰扇區之間的比較，所以將重量的要求優先考慮，進而再去考慮體積的要求。3、問題三的分析：明確不滿足的情況有兩大種：（1）只考慮重量時，不滿足重量的要求（2）綜合考慮重量和體積時，分為以下 3種：當相鄰工件的體積滿足要求時，重量不能滿足要求 當相鄰工件的重量滿足要求時，體積不能滿足要求 重量和體積都不滿足要求三、模型的假設與符號的說明（一）模型的假設1所給的24個工件的重量在某范圍內，相差不大，不會出現很重或很輕的 工件。2、當只考慮重量因素時，我們假設圓盤足夠大，每個扇形區域內的工件重 量無論多大，均能放在扇形區

8、域內，不會影響其他區域的重量。3、存在重量相同但體積不同的同種工件和體積相同但重量不同的同種工件 供我們更換。(二)符號的說明Xij當Xj =0時表示第i個工件不放在第j個扇形區域內當咎=1時表示第i個工件放在第j個扇形區域內w第i個工件的重量Vi第i個工件的體積M24個工件的總重量z相鄰扇區質量和之差的要求范圍S相鄰工件體積之差的要求范圍-1X工件的重量向量X = (wnw2,., w24)7Y工件的體積向量Y = (弋,.,v24)Tn4工件的次序向量n = (1,2,.,24)rnn的重排向量四、模型的建立和求解問題一按重量排序算法的數學模型1、分析我們將同重量的工件區分開，那么共有 2

9、4種不同的工件。針對問題一只考 慮重量差的要求可建立一個0-1規劃模型。首先引入0 -1變量：Xj 二1, 第i個工件放在第j個扇區上0,第i個工件不放在第j個扇區上扇區工件重量123456W-X|1X12*3X14XI5X166送 X1j =1jW2X21X22X23X24X25X266瓦 X2j =1j4wiXi1Xi 2X3Xi4X5Xi66為Xij=1j4W24X(24)1X(24)2X(24)3X(24)4X(24)5X(24)66為 X(24) j =1j24 乞Xi1 i呂=424乞Xi2=424為Xi3=424乞Xi4y=424£ Xi5=424乞Xi6id：=4顯然

10、，由于問題要求每一個工件都要放到圓盤上去，故有6Xij =1j 4又，每個扇形區域都要分到4個工件，故有24' Xij =4i 二目標函數為:24m i nf =|送 XjWii A7i（其中,624M =二二xj wi)id j d24化簡得min f =|£ x1Mi24=rXjWi d1624lx 網24=r /i =124i 41|Xij -gw6(其中，v Xj=1)j J24i 6二、區 一 % ) |Wi 46 j _1現在，我們令1 X“ = lx“|ijij6又，Xj =o或1,故1Xij = |Xj -|.06則，目標函數化為：24m i nf =、 Xj

11、 wi 4針對問題的排序原則：保證每個扇形區域的4個工件的總重量與相鄰區域的4個工件總重量1-；時，所求的解滿足條件；21-；時，所求的解不滿足條件。2函數 和0-1規劃的隱 枚舉法2之差的絕對值不超過一定值g >0（如：名=4g），這樣，當目標函數:1min f 一一 ；時，便滿足要求22、建模24min f 八 Xjj w ，口6為 Xij =1廣 jm24s.t.丨 Z xij =4Nj =0 或 124當目標函數min f = v Xij wi#24當目標函數min f =、 Xij w i3、求解：該模型可以通過 Matlab中的linprog()實現求解，針對本題算法的特殊情

12、況，我們還采用了 C語言編程來實現求解。 此算法的主要思路如下： 輸入24個數據（工件的重量）； 將其從小到大進行排序； 按照算法將其分成6組，并計算出各組的重量和； 將各組重量和按從小到大排序 ； 將最大的一組置于任一扇形區域，然后比較第一大和第二大的重量，若 差大于限制條件:，則需更換，若滿足，則置于其相鄰的位置上； 比較第一大與第三大的重量，若差大于限制條件:，則需更換，若滿足,貝U置于其另一相鄰的位置上，依次類推，得出排序結果。詳細代碼請看附錄，現將實例中提供的兩組數據運行結果如下:第一扇區：20 12 17 1第二扇區：11 23 14 18第三扇區：8 21 3 4第四扇區：10

13、19 15 2第五扇區：9 24 6 13第六扇區：7 22 5 16（第一組數據結果）（其重量和為：1359）（其重量和為：1357.5）（其重量和為：1356.5）（其重量和為：1355.5）（其重量和為：1357）（其重量和為：1357）第一扇區：8 11 5 17第二扇區：23 12 3 6第三扇區：9 20 18 13第四扇區：21 24 4 1第五扇區：7 10 15 2第六扇區：22 19 14 16（第二組數據結果）（其重量和為：1394）（其重量和為：1394）（其重量和為：1396）（其重量和為：1396.5）（其重量和為：1395.5）（其重量和為：1396）問題二按重量

14、和體積排序的算法數學模型1 、數學表述： 首先引入：工件的重量向量：X =（ w-i,w>, .,w24）工件的體積向量：丫 =（ v1,v2, .,v24）工件的次序向量：n =（1,2，n）使之滿足條件：4n4n"4I . I 二 w _、 Wi | 一 4 ,（n=1,2,3,4,5,6）;i Nn -3i "n 十41xWi -i 二24'Wi |i =21< 4 .n . 1-v 11-3 ,(i=1,2,23);1V1 - V24 |-3 .解得目標函數：'S(X, Y,n )= n（ 其中，向量:各分量是次序向量 n各分量的重排）2

15、、流程表示3、求解我們仍然采用C語言編程，詳細代碼請看附錄，現將實例中提供的兩組 數據運行結果如下：（第一組數據結果）24個工件序號為（首尾相接）：2 19 15 10 14 21 4 11 6 24 13 9 12 3 8 16 1 22 17 20 5 23 18 7（第二組數據結果）24個工件序號為（首尾相接）：11 6 22 13 7 1 9 2 23 3 8 5 12 14 20 4 10 15 21 16 19 17 24 18問題三的回答：（一）只考慮重量時，不滿足條件：設第i扇區和第j扇區之間的重量和不滿足條件（i與j扇區相鄰，j 與k扇區相鄰，其重量分別為g(i),g(j),

16、g(k)，只需更換其中一個扇區中某一工件。不妨設更換第j個扇區中的一個工件，記該工件的重量為g,這樣，更換后 第j扇區的重量和為g'(j)，則g'(j)需滿足：|g'(j) -g(i)I 蘭豈YJg'(j) g(k)1 < 名解得：g(i-s<g(j) < g(i) +gYj g(k)呂蘭g'(j)蘭g(k)即：maxg(i) - ；，g(k) - ；豈 g'(j)豈 ming(i) ；.g(k) ；?令 J = g'(j) -g(j)貝U的范圍：m axg i() ； g, k (-)； -g j 住)乞 mgi n

17、(； g k (； ) g j設新工件的重量為g'=+ g，所以新工件的重量范圍為：maxg(i) - ；,g(k) - ； g(j) g 豈 g'乞 ming(i)；. g(k) g(j) g(三)同時考慮重量和體積時 當體積滿足要求，重量不滿足要求時，在更換時，我們只需按上 述(一)的方法只更換工件的重量而保持其體積不變。 當重量滿足要求，體積不滿足要求時，我們可以按照上述(一)的思想方法進行更換，具體更換方法如下：我們假設第i個工件和第j個工件之間的體積不滿足條件(i與j工件相鄰，j與k工件相鄰，其體積分別為v(i) ,v( j), v(k)，只需更換i，j中某一工件。不

18、妨更換第j個工件這樣，更換后第j個工件的體積為v(j)，則v(j)需滿足:|v'(j) -v(k)|_ 5解得：廠 v(j)蘭 v(i) + 5 或 v(j) <v(i) - 5- v(j) A v(k) + 5 或 v(j) < v(k) - 5即：v'( j) _ maxv(i) 5v(k) 5或v (j)乞 minv(i) - 5 v(k) - 5 當重量和體積都不滿足要求時，我們可以分步更換：先不考慮體積，只考慮重量，則可以按上述 (一)的方法將其重量更換 為滿足重量要求的情形。然后再按照(二)-的方法將其體積更換為滿足體 積要求的情形。若先不考慮重量，只考

19、慮體積，(二)-的方法將其體積更換為滿足 體積要求的情形。然后再按照(二)-的方法將其重量更換為滿足重量要求 的情形。五、模型的評價和推廣本文針對題目提出的不同要求，我們分別給出了按重量和體積排序的不 同的模型和算法，對于問題一，我們建立了以各扇區對重量均值作差后取絕 對值最小為目標函數的模型，再用限制條件 ；加以控制，得出了在各扇區重 量波動范圍較小下的排序，但由于數據的取值是離散的，而且各扇區的重量 取值是不獨立的，同時也存在波動范圍較大情況下合理的排序， 我們還做了 一個適合一般情況的模型，具體思路如下：首先，將24個工件按重量從小到大依次排序，若相等則歸為一類，設共有m類，第i類的單個重量為Wj ,共有p件，放入第j個扇區的第i類工件的件數為 Xj，i =1,2,m, , j=1,2,6,有：y Xi6.w -、xWi | i4i=1minz二 maX I ' Xj.Wj_'i).w|i 4刑，5 i 4i 4 m使得、Xj =4, j =1,2,6;i 4m 6送送Xj =24；i 4 j 4Xj