工件安裝與排序問(wèn)題模型

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

2、：(方括號(hào)內(nèi)為此扇區(qū)工件的重量和；圓括號(hào)內(nèi)為此工件的體積 )扇區(qū)1扇區(qū)2扇區(qū)3扇區(qū)4扇區(qū)5扇區(qū)6問(wèn)題20 12 17 111 23 14 188 21 3 410 19 13 29 24 6 137 22 5 16-一-13591357.51356.51355.513571357問(wèn)題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當(dāng)無(wú)法通過(guò)內(nèi)部調(diào)試來(lái)滿(mǎn)足要求時(shí)，我們?cè)敿?xì)討論了更換新工件的各種情 況，并提出了具體的解決方案，給出了更換新工件重量和體積的范圍。如： 當(dāng)被更換工件的重量為g時(shí)，新工件的重量g'的范圍：max g(i) - g(k) - .g(j)亠 g _g' _ min g (i)亠二 g (k ) ; ： - g (j )亠 g 當(dāng)被更換工件的體積為v(j)時(shí)，新工件的體積V(j)的范圍：v (j) _max v(i)亠 8, v ( k )亠 3 或 v (j): min v(i) 3,v

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

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

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

7、的，所以要 同時(shí)考慮重量和體積。體積的要求是相鄰兩個(gè)工件之間比較，而重量的要求是相 鄰扇區(qū)之間的比較，所以將重量的要求優(yōu)先考慮，進(jìn)而再去考慮體積的要求。3、問(wèn)題三的分析：明確不滿(mǎn)足的情況有兩大種：（1）只考慮重量時(shí)，不滿(mǎn)足重量的要求（2）綜合考慮重量和體積時(shí)，分為以下 3種：當(dāng)相鄰工件的體積滿(mǎn)足要求時(shí)，重量不能滿(mǎn)足要求 當(dāng)相鄰工件的重量滿(mǎn)足要求時(shí)，體積不能滿(mǎn)足要求 重量和體積都不滿(mǎn)足要求三、模型的假設(shè)與符號(hào)的說(shuō)明（一）模型的假設(shè)1所給的24個(gè)工件的重量在某范圍內(nèi)，相差不大，不會(huì)出現(xiàn)很重或很輕的 工件。2、當(dāng)只考慮重量因素時(shí)，我們假設(shè)圓盤(pán)足夠大，每個(gè)扇形區(qū)域內(nèi)的工件重 量無(wú)論多大，均能放在扇形區(qū)

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

9、4種不同的工件。針對(duì)問(wèn)題一只考 慮重量差的要求可建立一個(gè)0-1規(guī)劃模型。首先引入0 -1變量：Xj 二1, 第i個(gè)工件放在第j個(gè)扇區(qū)上0,第i個(gè)工件不放在第j個(gè)扇區(qū)上扇區(qū)工件重量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、，由于問(wèn)題要求每一個(gè)工件都要放到圓盤(pán)上去，故有6Xij =1j 4又，每個(gè)扇形區(qū)域都要分到4個(gè)工件，故有24' Xij =4i 二目標(biāo)函數(shù)為:24m i nf =|送 XjWii A7i（其中,624M =二二xj wi)id j d24化簡(jiǎn)得min f =|£ x1Mi24=rXjWi d1624lx 網(wǎng)24=r /i =124i 41|Xij -gw6(其中，v Xj=1)j J24i 6二、區(qū) 一 % ) |Wi 46 j _1現(xiàn)在，我們令1 X“ = lx“|ijij6又，Xj =o或1,故1Xij = |Xj -|.06則，目標(biāo)函數(shù)化為：24m i nf =、 Xj

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

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

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

14、和體積排序的算法數(shù)學(xué)模型1 、數(shù)學(xué)表述： 首先引入：工件的重量向量：X =（ w-i,w>, .,w24）工件的體積向量：丫 =（ v1,v2, .,v24）工件的次序向量：n =（1,2，n）使之滿(mǎ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 .解得目標(biāo)函數(shù)：'S(X, Y,n )= n（ 其中，向量:各分量是次序向量 n各分量的重排）2

15、、流程表示3、求解我們?nèi)匀徊捎肅語(yǔ)言編程，詳細(xì)代碼請(qǐng)看附錄，現(xiàn)將實(shí)例中提供的兩組 數(shù)據(jù)運(yùn)行結(jié)果如下：（第一組數(shù)據(jù)結(jié)果）24個(gè)工件序號(hào)為（首尾相接）：2 19 15 10 14 21 4 11 6 24 13 9 12 3 8 16 1 22 17 20 5 23 18 7（第二組數(shù)據(jù)結(jié)果）24個(gè)工件序號(hào)為（首尾相接）：11 6 22 13 7 1 9 2 23 3 8 5 12 14 20 4 10 15 21 16 19 17 24 18問(wèn)題三的回答：（一）只考慮重量時(shí)，不滿(mǎn)足條件：設(shè)第i扇區(qū)和第j扇區(qū)之間的重量和不滿(mǎn)足條件（i與j扇區(qū)相鄰，j 與k扇區(qū)相鄰，其重量分別為g(i),g(j),

16、g(k)，只需更換其中一個(gè)扇區(qū)中某一工件。不妨設(shè)更換第j個(gè)扇區(qū)中的一個(gè)工件，記該工件的重量為g,這樣，更換后 第j扇區(qū)的重量和為g'(j)，則g'(j)需滿(mǎn)足：|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設(shè)新工件的重量為g'=+ g，所以新工件的重量范圍為：maxg(i) - ；,g(k) - ； g(j) g 豈 g'乞 ming(i)；. g(k) g(j) g(三)同時(shí)考慮重量和體積時(shí) 當(dāng)體積滿(mǎn)足要求，重量不滿(mǎn)足要求時(shí)，在更換時(shí)，我們只需按上 述(一)的方法只更換工件的重量而保持其體積不變。 當(dāng)重量滿(mǎn)足要求，體積不滿(mǎn)足要求時(shí)，我們可以按照上述(一)的思想方法進(jìn)行更換，具體更換方法如下：我們假設(shè)第i個(gè)工件和第j個(gè)工件之間的體積不滿(mǎn)足條件(i與j工件相鄰，j與k工件相鄰，其體積分別為v(i) ,v( j), v(k)，只需更換i，j中某一工件。不

18、妨更換第j個(gè)工件這樣，更換后第j個(gè)工件的體積為v(j)，則v(j)需滿(mǎn)足:|v'(j) -v(k)|_ 5解得：廠(chǎng) 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 當(dāng)重量和體積都不滿(mǎn)足要求時(shí)，我們可以分步更換：先不考慮體積，只考慮重量，則可以按上述 (一)的方法將其重量更換 為滿(mǎn)足重量要求的情形。然后再按照(二)-的方法將其體積更換為滿(mǎn)足體 積要求的情形。若先不考慮重量，只考

19、慮體積，(二)-的方法將其體積更換為滿(mǎn)足 體積要求的情形。然后再按照(二)-的方法將其重量更換為滿(mǎn)足重量要求 的情形。五、模型的評(píng)價(jià)和推廣本文針對(duì)題目提出的不同要求，我們分別給出了按重量和體積排序的不 同的模型和算法，對(duì)于問(wèn)題一，我們建立了以各扇區(qū)對(duì)重量均值作差后取絕 對(duì)值最小為目標(biāo)函數(shù)的模型，再用限制條件 ；加以控制，得出了在各扇區(qū)重 量波動(dòng)范圍較小下的排序，但由于數(shù)據(jù)的取值是離散的，而且各扇區(qū)的重量 取值是不獨(dú)立的，同時(shí)也存在波動(dòng)范圍較大情況下合理的排序， 我們還做了 一個(gè)適合一般情況的模型，具體思路如下：首先，將24個(gè)工件按重量從小到大依次排序，若相等則歸為一類(lèi)，設(shè)共有m類(lèi)，第i類(lèi)的單個(gè)重量為Wj ,共有p件，放入第j個(gè)扇區(qū)的第i類(lèi)工件的件數(shù)為 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