工件的安裝與排序問題

1、工件的安裝與排序問題王曉楠，崔超，陳濤（中國(guó)礦業(yè)大學(xué)，徐州 221008）摘要：本文首先深入分析了組合優(yōu)化的特點(diǎn)，然后針對(duì)本題中設(shè)備對(duì)工件排血安裝時(shí)的重量約束和體積約束的特點(diǎn)，就題目中提出幾個(gè)問題分別設(shè)計(jì)了不同的算法，通過不同的算法的優(yōu)劣的比較，不僅較好的解決了工件的排序安裝問題，還得出了問題中算法設(shè)計(jì)的一些根據(jù)。在問題1中，我們引入了貪心策略和自適應(yīng)方法對(duì)搜索算法進(jìn)行改進(jìn)，大大減小了搜索的規(guī)模得到了一種效率和性能都不錯(cuò)的搜索算法，另外還針對(duì)數(shù)據(jù)的特點(diǎn)給出了一種操作簡(jiǎn)便的簡(jiǎn)化算法，通過兩種算法的比較得出了一些有用的算法設(shè)計(jì)結(jié)論。在問題1的算法設(shè)計(jì)過程中我們還適當(dāng)?shù)囊肓艘恍├碚撟C明，使算法更加

2、有說服力，最終通過MATLAB軟件得出了令人滿意的結(jié)果，有力的證明了算法的可行性。在問題2中將問題1的算法進(jìn)行綜合，然后分別從不同的出發(fā)點(diǎn)提出了兩種算法，一種是適用性較強(qiáng)但不易實(shí)現(xiàn)的解析算法，另一種針對(duì)數(shù)據(jù)特點(diǎn)的較簡(jiǎn)便的針對(duì)性算法，并比較了兩種算法各自的適應(yīng)性，簡(jiǎn)便的求出了第二組數(shù)據(jù)的排序結(jié)果，并得出第一組數(shù)據(jù)無解的結(jié)論。問題3根據(jù)前面的結(jié)論，如果只考慮重量，分析了兩種相臨扇區(qū)總重量差最大的情況，通過數(shù)學(xué)分析得出工件調(diào)整幅度，如果還要考慮體積因素，通過對(duì)工件的貪心選擇，不斷修正工件重量和體積，篩選出滿足條件的工件組合 。我們?cè)谡撐牡淖詈筮€給出了模型的評(píng)價(jià)和推廣。一 問題重述某設(shè)備由24個(gè)工件組

3、成，安裝時(shí)需要按工藝要求重新排序。設(shè)備的24個(gè)工件均勻分布在等分成六個(gè)扇形區(qū)域的一圓盤的邊緣上，放在每個(gè)扇形區(qū)域的4個(gè)工件總重量與相鄰區(qū)域的4個(gè)工件總重量之差不允許超過一定值（如4g）。工件的排序不僅要對(duì)重量差有一定的要求，還要滿足體積的要求，即兩相鄰工件的體積差應(yīng)盡量大，使得相鄰工件體積差不小于一定值（如3）；當(dāng)工件確實(shí)不滿足上述要求時(shí)，允許更換少量工件。問題1按重量排序算法；問題2按重量和體積排序算法；問題3當(dāng)工件不滿足要求時(shí)，指出所更換工件及新工件的重量和體積值范圍，并輸出排序結(jié)果。請(qǐng)按下面兩組工件數(shù)據(jù)（重量單位：g ，體積單位：），進(jìn)行實(shí)時(shí)計(jì)算：序號(hào)重量體積序號(hào)重量體積1348101.

4、51358.510323521022357.5103334710533551034349105.54351103.55347.51065355.510363471046357102733094734196832998834296.59329100.5934095.510327.598.51034497113299811342.595.112331.59912343.596.513348.5104.513357.5102.5143471051435510315346.5107.515353.5103.516348104.516356.5103.517347.510417356103.518348

5、104.518352.5104193339719342.59820330972034496.521332.59921339.59822331.59822341.59623331.596.523341962433294.52434597二 問題分析本題要求給出一種算法對(duì)24個(gè)工件按重量和體積的約束條件進(jìn)行組合和排序， 并安裝到設(shè)備圓周的六個(gè)等分扇區(qū)上，每個(gè)扇區(qū)放置四個(gè)工件。相鄰扇區(qū)的工件的重量之差不允許超過一定值，而相鄰工件之間的體積差也要滿足不小于一定值的約束。表面上看似乎算法只要算法能給出一組排序滿足要求即可，不需要進(jìn)行最優(yōu)化，但是通過深入分析可知，由于數(shù)據(jù)可能并不理想，滿足要求的可行解的集

6、合可能很大，但也可能很小甚至并不存在，因此要提高算法的適應(yīng)性就必須對(duì)排序的結(jié)果進(jìn)行目標(biāo)優(yōu)化，使結(jié)果盡可能滿足要求，而不是簡(jiǎn)單的給出一組可行解，這樣我們就可以通過最優(yōu)或極優(yōu)可行解來驗(yàn)證是否可以找到可行方案。因此問題可變?yōu)槿缦碌膬?yōu)化問題：其中為一組排序方案，為所有可能排序的集合。由于每個(gè)位置上的工件只能從給定的24個(gè)工件中選，因此這是一種典型的組合優(yōu)化問題。問題1只要求考慮重量約束下的排序，是單目標(biāo)組合優(yōu)化問題。我們將目標(biāo)函數(shù)定義為相鄰扇區(qū)重量之差的最大值，尋找使該值最小的排序方案。目前對(duì)于組合優(yōu)化問題的解決方案主要有兩種策略，一是對(duì)搜索算法進(jìn)行改進(jìn)，以減少搜索的時(shí)間復(fù)雜度，如禁忌搜索算法；另一種

7、是利用遺傳算法、模擬退火算法等概率算法計(jì)算最優(yōu)解。本問題所有可能的排序共有種，我們選擇第一種方法，引入貪心策略通過搜索近似最優(yōu)解以大降低搜索的復(fù)雜度，然后在保證算法結(jié)果不會(huì)惡化的前提下逐漸簡(jiǎn)化算法，提高算法的效率。問題2既要求滿足重量約束又要求滿足體積約束，是多目標(biāo)優(yōu)化問題，由于重量與體積之間相互并不一定有太大關(guān)聯(lián)，因此若數(shù)據(jù)不理想而兩者又要同時(shí)滿足可能是非常困難的。我們的解決辦法從滿足體積約束的排序方案中進(jìn)行選擇，找出最滿足重量要求的可行方案，即把對(duì)體積的要求作為一項(xiàng)約束條件，按重量目標(biāo)優(yōu)化。當(dāng)然也可以把重量作為約束條件，按體積目標(biāo)優(yōu)化，但是由于體積的優(yōu)化牽扯到了NP-C問題，我們采用前一種

8、解決方案。問題3是在不滿足前兩個(gè)問題的情況下對(duì)個(gè)別工件進(jìn)行調(diào)整，當(dāng)工件不滿足要求時(shí)，允許更換少量的數(shù)據(jù)。根據(jù)前面解決問題的算法可以得出兩種修改策略：一是按重量排序；二是按重量和體積排序。針對(duì)問題一：根據(jù)問題一證明，使平均值是在不斷自我修整的，后面扇區(qū)的工件總重量最大可能接近前面扇區(qū)的總重量，但由于本設(shè)備的形狀是一個(gè)圓盤，第六個(gè)扇區(qū)與第一個(gè)扇區(qū)相臨，此時(shí)第六個(gè)扇區(qū)總重量和第一個(gè)扇區(qū)總質(zhì)量之差是累計(jì)誤差最大的。三 模型的基本假設(shè)1. 圓盤被均勻分成六個(gè)扇形區(qū)域，每個(gè)區(qū)域是固定劃分的，工件是按照一定順序安裝到各個(gè)位置上去的。2. 問題1中各扇區(qū)內(nèi)工件的可以隨便排列，只要工件相同都算是同一排列。四 符

9、號(hào)說明： 扇區(qū)的工件總重量： 扇區(qū)的工件平均重量： 所有工件的平均重量： 扇區(qū)和扇區(qū)的工件總重量之差，其中扇區(qū)和扇區(qū)相鄰： 相鄰區(qū)域工件總重量之差允許的最大值： 位置處的工件體積： 位置與位置處的體積之差，位置與位置相鄰： 相鄰位置處的工件體積之差所允許的最小值： 工件的全排序集： 一組排序方案： 工件總集： 算法第步操作后的剩余可選工件集：剩余可選工件集中工件的平均重量： 工件五 模型的建立和求解問題1：模型的建立：1) 理論說明：首先建立組合優(yōu)化的模型，前面的分析中已經(jīng)說明，我們采用的目標(biāo)函數(shù)為相鄰扇區(qū)重量之差的最大值，尋找一組排序方案使這個(gè)值最小，即 （1）其中：，為第個(gè)扇區(qū)的所有可能的

10、工件組合的質(zhì)量。若使用完全搜索算法，則總共需要搜索個(gè)結(jié)果，這顯然代價(jià)太高昂了，所以有必要對(duì)搜索算法進(jìn)行改進(jìn)。目標(biāo)函數(shù)要求相鄰扇區(qū)的工件總重量之差的最大值盡可能小，由于工件擺放在設(shè)備的圓周上，易知沿某一固定方向（如順時(shí)針）相鄰扇區(qū)的工件總重量差不能一直遞增或遞減，而應(yīng)保持有增有減的趨勢(shì)才可能滿足題目要求的重量約束條件，因此對(duì)這一目標(biāo)進(jìn)行優(yōu)化得到的各扇區(qū)的工件總重量相對(duì)而言一定比較接近且一定在所有工件重量的平均值附近，針對(duì)目標(biāo)函數(shù)的這一要求，我們可以對(duì)目標(biāo)函數(shù)進(jìn)行轉(zhuǎn)化，將目標(biāo)函數(shù)轉(zhuǎn)換為： （2）通過分析可知目標(biāo)函數(shù)（2）的要求比目標(biāo)函數(shù)（1）的要求要強(qiáng)，即滿足目標(biāo)函數(shù)（2）一定能滿足目標(biāo)函數(shù)（1）

11、，也就是說目標(biāo)函數(shù)（2）對(duì)目標(biāo)函數(shù)（1）具有充分性。當(dāng)然這里只是從直觀的角度去分析的，下面將給出理論上的嚴(yán)格說明。我們對(duì)24個(gè)工件進(jìn)行排序，假設(shè)找到一組排序，設(shè)每個(gè)扇形區(qū)域的總重量分別為、，為了使每個(gè)扇形區(qū)域的工件總重量與相鄰區(qū)域的工件總重量之差盡可能的小，使其滿足不超過一個(gè)定值（如4），這就要求、盡量的相等，既接近算術(shù)平均值4。如果我們從24個(gè)工件中找到這組排序，使每個(gè)扇區(qū)的重量分別為、即最接近算術(shù)平均值4的一組排序，而它們當(dāng)中卻有兩個(gè)相鄰扇形區(qū)域的總重量超過一定值（如4），即不滿足重量條件，則可得出：這24個(gè)工件無論怎么排序都不能滿足每個(gè)扇形區(qū)域的四個(gè)工件總重量與相鄰區(qū)域的四個(gè)工件總重量之

12、差不允許超過一定值（4）這個(gè)條件。下面來證明我們的結(jié)論：結(jié)論一：如果從24個(gè)工件中找到一種排序，使每個(gè)扇區(qū)4個(gè)工件的總重量、盡量相等，即等于所有工件重量的算術(shù)平均值4，則每個(gè)扇形區(qū)域的工件總重量與相鄰區(qū)域的工件總重量之差的和最小，同時(shí)也使相鄰兩個(gè)扇形區(qū)域的總重量之差的最大值最小，即這種排序?yàn)樽顑?yōu)排序。證明：假設(shè)存在另外一種排序，在六個(gè)扇形區(qū)域重量的排序?yàn)?、，其?則相鄰扇形區(qū)域的重量差為：我們知道對(duì)于不等式，當(dāng)時(shí)取等號(hào)，故：當(dāng)時(shí)，取最小值。同理、也能取最小值。由于、離散取值，由條件可知每個(gè)扇區(qū)的總重量近似相等，即、，此時(shí)、；又由于，所以此時(shí)這樣就證明了此排序使每個(gè)扇形區(qū)域的工件總重量與相鄰區(qū)域

13、的工件總重量之差的和最小，同時(shí)也使相鄰兩個(gè)扇形區(qū)域的總重量之差的最大值最小，即這種排序?yàn)樽顑?yōu)排序。結(jié)論二：如果找到一種排序，使每個(gè)扇形區(qū)域的四個(gè)工件的總重量盡量相等，即接近于4，而這種排序不滿足重量的約束要求，即不能使所有相鄰扇形區(qū)域的重量差小于一定的值（4），則得出結(jié)論：這24個(gè)工件無論怎么樣排序，都不能滿足重量要求。根據(jù)結(jié)論一，我們得到了這種排序即每個(gè)扇區(qū)四個(gè)工件總重量盡量等于4是最優(yōu)排序，使相鄰兩個(gè)扇形區(qū)域的總重量之差的最大值最小，如果這種最優(yōu)排序都不滿足要求，則其它的排序一定不滿足要求。2) 算法設(shè)計(jì)：如何找到這種排序，使每個(gè)扇形區(qū)域的四個(gè)工件總重量盡量相等，即等于4。此類問題是典型的

14、組合優(yōu)化問題。為了解決這一問題，我們可以對(duì)完全搜索算法進(jìn)行改進(jìn)，通過在搜索算法中引入貪心策略，將較大的搜索空間分為幾個(gè)小的搜索空間，可以大大減小搜索規(guī)模而搜索的結(jié)果不會(huì)惡化，即至少仍可以得到一組近似最優(yōu)解甚至是全局最優(yōu)解。算法一：引入貪心策略的搜索算法算法步驟：Step1：初始化。求出24個(gè)工件的平均值，給出初始可選工件集合。Step2：從可選的工件集中選出四個(gè)工件，選取原則為工件組合的重量平均值最接近于。Step3：從初始可選工件集中去掉已選擇的4個(gè)工件，得到剩余可選工件集，之后有兩種操作方法：一種方案是用代替重復(fù)進(jìn)行Step2，直至工件選完全部安裝到設(shè)備上，標(biāo)準(zhǔn)重量平均值始終用，我們稱之為

15、固定平均值法；另一方案是求出剩余可選工件集中工件的平均重量，用、代替和，重復(fù)進(jìn)行Step2，直到工件選完全部安裝到設(shè)備上算法結(jié)束，標(biāo)準(zhǔn)重量平均值用剩余可選工件集的平均重量，這種稱為自適應(yīng)平均值法。引入貪心策略后，搜索算法的規(guī)模為，主要由前兩項(xiàng)決定，同完全搜索算法的規(guī)模相比計(jì)算式中的各部分由相乘變?yōu)橄嗉樱?guī)模大為降低，這使得計(jì)算機(jī)求解變得不僅可行而且十分簡(jiǎn)便快捷。至于結(jié)果是否合理我們將在模型求解中討論。這里之所以采用貪心策略，是考慮到由于工件數(shù)較多，工件可能的組合數(shù)會(huì)更多，我們將第1步操作之前和第2步操作之前的所有可選工件組合的重量平均值制成下面的兩幅圖，以便于同所有工件重量平均值進(jìn)行直觀的比較

16、：圖1.算法第1步選擇扇區(qū)1的工件組合圖2.算法第2步選擇扇區(qū)1的工件組合由圖可知有相當(dāng)一部分工件組合的平均重量在平均值附近，這樣第步操作選出的工件組合的重量均值就可以非常接近于剩余可選工件集中工件的重量平均值，因此將它們選出后對(duì)剩余的工件集合的重量平均值產(chǎn)生的影響就是微乎其微的，這樣步操作的候選組合中仍然可以找到盡可能接近于總體平均值的組合，因此算法就很有可能是可行的。我們知道只有具有“貪心選擇性質(zhì)”的問題用貪心算法才能求得全局最優(yōu)解，否則只能得到局部最優(yōu)解3。下面我們對(duì)問題的貪心選擇性質(zhì)和局部最優(yōu)進(jìn)行說明。i. 貪心選擇性質(zhì)：根據(jù)前面的證明，我們可以得到結(jié)論：如果使圓盤上的工件組合滿足重量

17、條件，應(yīng)該使得各個(gè)扇形區(qū)域上的工件重量之和盡可能相等，這樣如果從扇區(qū)一開始，那么為當(dāng)前最接近4的，即可以滿足在第一個(gè)扇區(qū)，是可能的最優(yōu)解。ii. 局部最優(yōu)解：如果前面的k-1個(gè)扇形區(qū)域上的工件已經(jīng)尋找出來，那么第k個(gè)扇形區(qū)域上的工件重量只要滿足和第k-1個(gè)的重量差最小。因?yàn)椋涸谶@里，只是把該問題化成一個(gè)子問題，在該問題里面，也是尋求最優(yōu)組合，使之滿足相鄰的扇區(qū)工件重量差最小的條件。這樣，就把k之后圓盤的各個(gè)扇區(qū)化成一個(gè)類似與原來24個(gè)工件排列的問題。這樣，該問題滿足局部最優(yōu)解。算法二：算法一的簡(jiǎn)化算法主要思想如下：通過對(duì)題目給出的數(shù)據(jù)進(jìn)行分析，可得如下兩幅圖：圖3.第一組數(shù)據(jù)的重量和體積分布圖

18、4.第二組數(shù)據(jù)的重量和體積分布通過對(duì)兩幅圖片的分析可知，兩組數(shù)據(jù)中工件按重量和體積明顯分等為兩類，這很可能跟設(shè)備的實(shí)際工作情況有關(guān)，也就是說此設(shè)備的工作環(huán)境中工件的重量和體積是有一定要求的，因此我們可以根據(jù)具體的數(shù)據(jù)和實(shí)際情況來設(shè)計(jì)出一種針對(duì)性的算法，根據(jù)具體的數(shù)據(jù)可以將算法大大簡(jiǎn)化。由于工件按重量明顯分為兩組，且同組工件之間重量接近，因此要使每個(gè)扇區(qū)的平均重量最接近總平均重量必須兩組各取兩個(gè)，否則就會(huì)因搭配問題使大大偏離，從而難以完成目標(biāo)的優(yōu)化，根據(jù)這一思路，我們可以得到如下過程的算法：首先將所有工件的重量按大小排序；選出重量最大的和最小的工件，按一定的旋轉(zhuǎn)方向放在一個(gè)扇區(qū)中的兩個(gè)相鄰的位置

19、上；選出剩余工件中重量最大和最小的工件，按相同的旋轉(zhuǎn)方向放在接下來的位置上；重復(fù)操作，直到所有的工件被選完，算法結(jié)束。3) 模型求解： 根據(jù)題目所給數(shù)據(jù)和我們給出的算法，我們通過MATLAB軟件編程得到各組數(shù)據(jù)的排序結(jié)果：表一：用固定平均值法求得第一組數(shù)據(jù)的排序結(jié)果區(qū)域扇形區(qū)域1扇形區(qū)域2扇形區(qū)域3工件位置123456789101112工件序號(hào)13724251020481217每個(gè)區(qū)域的重量/135713571357區(qū)域扇形區(qū)域4扇形區(qū)域5扇形區(qū)域6工件位置131415161718192021222324工件序號(hào)6913211114161915182223每個(gè)區(qū)域的重量/p>

20、7.5最大重量差：0.5表二：用自適應(yīng)法求得第一組數(shù)據(jù)的排序結(jié)果區(qū)域扇形區(qū)域1扇形區(qū)域2扇形區(qū)域3工件位置123456789101112工件序號(hào)13724251020481217每個(gè)區(qū)域的重量/135713571357區(qū)域扇形區(qū)域4扇形區(qū)域5扇形區(qū)域6工件位置131415161718192021222324工件序號(hào)6913211114161915182223每個(gè)區(qū)域的重量/135713571357.5 最大重量差：0.5由上面的結(jié)果可見，引入貪心策略后，搜索的結(jié)果仍然很好，最大的重量差為0.5，而且用固定平均值法與用自適應(yīng)平均值法所得結(jié)果相同。在本題中，0.5是最小重量差，而第一組數(shù)據(jù)中所有工

21、件重量的平均值為339.271，任何一個(gè)扇區(qū)內(nèi)工件組合的平均值都不等于這個(gè)值，所以最終的全局最優(yōu)排序一定不可能滿足各扇區(qū)工件總重量都相等，所以這里求得的就是全局最優(yōu)解，可見算法一具有優(yōu)良的性能。表三：用固定平均值法求得第二組數(shù)據(jù)：區(qū)域扇形區(qū)域1扇形區(qū)域2扇形區(qū)域3工件位置123456789101112工件序號(hào)1292135710461124每個(gè)區(qū)域的重量/1395.51395.51395.5區(qū)域扇形區(qū)域4扇形區(qū)域5扇形區(qū)域6工件位置131415161718192021222324工件序號(hào)81213181416192215172023每個(gè)區(qū)域的重量/1395.51395.51394.5最大重量差

22、：1.0表四：用自適應(yīng)法求得第二組數(shù)據(jù)的排序結(jié)果：區(qū)域扇形區(qū)域1扇形區(qū)域2扇形區(qū)域3工件位置123456789101112工件序號(hào)129213571046824每個(gè)區(qū)域的重量/1395.51395.51395區(qū)域扇形區(qū)域4扇形區(qū)域5扇形區(qū)域6工件位置131415161718192021222324工件序號(hào)111215171314222316181920每個(gè)區(qū)域的重量/1395.513951395.5最大重量差：0.5對(duì)比第二組數(shù)據(jù)的這兩組結(jié)果可以發(fā)現(xiàn)自適應(yīng)平均值法與固定平均值法略有不同，且自適應(yīng)平均值法的排序結(jié)果優(yōu)于固定平均值法。這不難理解，因?yàn)楣潭ㄆ骄捣ㄒ恢笔褂迷瓉淼乃泄ぜ亓科骄?，?/p>

23、扇區(qū)內(nèi)的工件組合重量平均值不可能精確等于所有工件重量平均值，這樣之前的操作中所產(chǎn)生的誤差會(huì)在后來的操作中積累下來，所以固定平均值法的排序結(jié)果中重量差最大值總是出現(xiàn)在最后一項(xiàng)。而對(duì)于自適應(yīng)平均值法，由于每次操作時(shí)所使用的平均值總是當(dāng)前剩余可選工件集的重量平均值，它能實(shí)時(shí)反映系統(tǒng)當(dāng)前的狀態(tài)，并能及時(shí)作出調(diào)整，避免了重量差的積累，因此效果由于固定平均值法。表五：用算法二求得的第一組數(shù)據(jù)的排序結(jié)果：區(qū)域扇形區(qū)域1扇形區(qū)域2扇形區(qū)域3工件位置123456789101112工件序號(hào)210481391111671820每個(gè)區(qū)域的重量/1357.51354.51356區(qū)域扇形區(qū)域4扇形區(qū)域5扇形區(qū)域6工件位置

24、131415161718192021222324工件序號(hào)512172232362414211519每個(gè)區(qū)域的重量/13581357.51359最大重量差：3表六：用算法二求得的第二組數(shù)據(jù)的排序結(jié)果區(qū)域扇形區(qū)域1扇形區(qū)域2扇形區(qū)域3工件位置123456789101112工件序號(hào)121291376231622178每個(gè)區(qū)域的重量/1395.51396.51396區(qū)域扇形區(qū)域4扇形區(qū)域5扇形區(qū)域6工件位置131415161718192021222324工件序號(hào)511319141215101820424每個(gè)區(qū)域的重量/1395.513961392.5最大重量差：3.5 可見，算法二的結(jié)果也是滿足要求的

25、，但這種簡(jiǎn)化算法的性能不如算法一，因?yàn)樗]有確切的目標(biāo)數(shù)來約束它，它只是針對(duì)具體的數(shù)據(jù)而設(shè)計(jì)的，因而算法比較簡(jiǎn)單且易操作，但它的缺點(diǎn)就是只適應(yīng)于某一類特點(diǎn)的數(shù)據(jù)，不易推廣。問題2：模型的建立：算法一：綜合法本問題要求給出一個(gè)同時(shí)滿足重量和體積約束條件的算法，但是由于在本題中重量與體積之間并沒有直接的聯(lián)系，因此難以找到一種統(tǒng)一的進(jìn)行優(yōu)化的規(guī)則，若分別進(jìn)行優(yōu)化則一方面會(huì)導(dǎo)致算法的復(fù)雜度過大（對(duì)兩個(gè)大的解空間進(jìn)行搜索），另一方面遵循重量約束的組合目標(biāo)優(yōu)化的可行解與遵循體積約束的組合目標(biāo)優(yōu)化的可行解之間并不一定相容，也就是說兩個(gè)解集不一定有交集。即使有交集，要實(shí)現(xiàn)這一運(yùn)算也是要花費(fèi)高昂的代價(jià)的。不過

26、在優(yōu)化求解之前，我們?nèi)匀豢梢酝ㄟ^兩個(gè)約束條件的單獨(dú)組合優(yōu)化來驗(yàn)證僅考慮一個(gè)約束條件時(shí)的可行解是否存在從而可能簡(jiǎn)化處理過程。這樣我們得到算法一的過程如下：過程一（可行性驗(yàn)證）：驗(yàn)證單一約束條件下可行解是否存在，即滿足重量之差不大于給定值的可行解是否存在，滿足體積之差不小于給定值的可行解是否存在。若找不到滿足約束條件的可行解，則算法結(jié)束，返回不能滿足要求的信息。過程二（可行解尋找）：將對(duì)體積的約束條件嵌入到問題1的算法一中去，作為搜索過程中的一項(xiàng)約束條件，即在搜索過程中工件組合必須滿足體積的要求，若進(jìn)入了不滿足體積要求的空間則退到上一層循環(huán)中去以退出不滿足要求的空間。在過程一中，由于不僅要對(duì)重量約

27、束進(jìn)行可行性驗(yàn)證，還要對(duì)體積約束進(jìn)行可行性驗(yàn)證。而問題1中只給出了重量排序算法，沒有給出體積排序算法，因此在這里有必要給出滿足體積約束條件的排序的簡(jiǎn)單說明。體積約束下的工件排序：由于體積條件為相鄰位置之差不小于給定值，這一點(diǎn)不同于問題一的重量排序算法，因此不能再像問題1中的進(jìn)行目標(biāo)轉(zhuǎn)化并引入貪心策略，但是體積條件是相鄰工件之間的約束，根據(jù)這一點(diǎn)我們可以構(gòu)造一個(gè)體積差矩陣，矩陣中的每個(gè)元素。根據(jù)題目所給的最小體積差，我們可以將體積差矩陣轉(zhuǎn)化為一個(gè)0-1矩陣，轉(zhuǎn)換規(guī)則為：若，則，表示工件與可以放在相鄰的位置上；否則，表示工件與不能放在相鄰的位置上。我們的目標(biāo)就是尋找一組可行的排列是體積要求得到滿足

28、。不難發(fā)現(xiàn)若把作為一個(gè)鄰接矩陣，則可以表示成一個(gè)無向圖，圖的每個(gè)頂點(diǎn)表示一個(gè)工件，兩頂點(diǎn)之間有邊則說明這兩個(gè)頂點(diǎn)表示的工件可以放在相鄰的位置上，無邊則表示兩個(gè)工件不能放在相鄰的位置上。這樣進(jìn)行體積排序?qū)嵸|(zhì)上就轉(zhuǎn)化為尋找這個(gè)圖中的哈密頓回路問題。由于科學(xué)早已有了結(jié)論，即判定任意一個(gè)圖是否是哈密頓圖的問題是一類NP-完全問題，更何況要在較短時(shí)間內(nèi)輸出所有的哈密頓回路,所以這一問題的解決是相當(dāng)困難的。盡管已經(jīng)存在一些尋求一個(gè)圖的哈密頓回路的方法，如分支算法和約束算法等。但所有這些算法都不是很有效的，其時(shí)間復(fù)雜度幾乎是不可接受的。因此我們只能通過圖論中的一些必要條件證明某個(gè)圖不是哈密頓圖，以省掉后面不

29、必要的分析。算法二：針對(duì)性算法算法一雖然是希望盡量通過解析的方法來達(dá)到組合優(yōu)化的目的，但是無疑算法實(shí)現(xiàn)的難度太大了，且算法的效率也不是很好。因此有必要從具體的數(shù)據(jù)入手來尋找更有效、更易于實(shí)現(xiàn)的算法。仔細(xì)分析數(shù)據(jù)不難發(fā)現(xiàn)兩組數(shù)據(jù)有一些共同點(diǎn)，但也有一些區(qū)別，數(shù)據(jù)中有著比較大的規(guī)律。因此最好的辦法應(yīng)該是從具體的數(shù)據(jù)入手，分析數(shù)據(jù)的特點(diǎn)，然后設(shè)計(jì)算法進(jìn)行優(yōu)化排序，兩組數(shù)據(jù)的共同之處就是工件無論是按重量還是按體積都可以明顯的劃分為兩組，一類是大重量、大體積，另一類是小重量、小體積（當(dāng)然這里的大小只是相對(duì)而言，并不是說兩組工件的重量和體積真的相差很大）。而不同之處在于：第一組數(shù)據(jù)兩組之間體積差別并不明顯

30、，這一點(diǎn)不利于體積的優(yōu)化排序，但重量差別明顯，且同組工件重量差不大，分布均勻；第二組數(shù)據(jù)則相反，兩組工件之間體積差別明顯，且同組的工件體積差不大，但同組工件的重量不如第一組數(shù)據(jù)分布的那么集中，但問題1的算法同樣適用。針對(duì)兩組數(shù)據(jù)各自的特點(diǎn)，我們應(yīng)該采取不同的處理過程。對(duì)第一組數(shù)據(jù)，由于重量分布集中且組間差別明顯而體積差別不明顯，且組內(nèi)工件體積之差就可以達(dá)到本題的要求，所以對(duì)體積約束條件來說，顯然組間工件的約束相對(duì)要強(qiáng)一點(diǎn)，而組內(nèi)工件的約束相對(duì)于第二組數(shù)據(jù)要弱一點(diǎn)，總的來說兩組工件的體積分布更接近一些，因此仍然需要使用算法一，先進(jìn)行體積排序可行性的驗(yàn)證。若驗(yàn)證體積排序可行，再根據(jù)各組組內(nèi)工件重量

31、分布比較接近（重量至多差5.5），組間工件的重量差較大（至少為15）的特點(diǎn)，要滿足重量的約束條件，則必須保證個(gè)扇區(qū)內(nèi)的工件組合為“兩大兩小”的形式，即兩個(gè)大重量工件加兩個(gè)小重量工件，這樣才可能滿足重量約束條件，據(jù)此約束條件得以轉(zhuǎn)化為較簡(jiǎn)單的形式。在此前提下，再次利用貪心策略，選擇與當(dāng)前工件滿足體積差要求但體積差最小的工件安裝在當(dāng)前工件旁邊。第二組數(shù)據(jù)的算法的描述如下：Step1：體積約束排序可行性驗(yàn)證。Step2：根據(jù)貪心策略進(jìn)行搜索，選擇當(dāng)前工件滿足體積差要求但體積差最小的工件。Step3：驗(yàn)證是否滿足重量約束條件，即一個(gè)扇區(qū)內(nèi)“兩大兩小”的形式，若不滿足，將此工件排除在外，重復(fù)Step2；

32、若滿足，將選出的工件按裝在當(dāng)前工件的旁邊位置，并作為新的當(dāng)前工件，重復(fù)Step2。當(dāng)工件安裝完畢后算法結(jié)束。而對(duì)于第二組數(shù)據(jù)，體積分布較為集中，組間體積差較大，由圖4可知，體積接近的工件組內(nèi)工件體積差不超過3，因此可以證明排序時(shí)必須兩組工件交替安裝，即當(dāng)前位置安裝了一個(gè)大體積的工件時(shí)，下一個(gè)則必然是小體積的工件。而由問題1算法一可知，通過貪心策略得到的非常接近于平均值的工件組合一定是2個(gè)大重量工件加2個(gè)小重量的工件，根據(jù)圖4的對(duì)應(yīng)關(guān)系，也就是2個(gè)大體積的工件加2個(gè)小體積的工件，這樣就可以直接利用問題1的結(jié)果，在一個(gè)扇區(qū)排序使大小工件交錯(cuò)安裝，同時(shí)保證扇區(qū)交界處的工件也滿足這一要求即可。因此針對(duì)

33、這一類數(shù)據(jù)就可以直接利用問題1的結(jié)果的進(jìn)行重排序。第二組數(shù)據(jù)的排序算法如下：Step1：利用問題1的算法一選出滿足重量約束條件的工件組合。Step2：第一步的結(jié)果進(jìn)行重排序，原則是：組合關(guān)系不能改變，大小體積的工件交替安裝在設(shè)備的圓周上。易知，排序組合可以有很多，而我們只要給出滿足要求的一組就可以。顯然這種方法只適合于兩組工件重量差別較大的情況，若重量相差不多，則Step1得到的結(jié)果可能不是“兩大兩小”的組合，此時(shí)這一算法就不再適用了。這時(shí)應(yīng)該增加約束條件，使Step1結(jié)果滿足“兩大兩小”的組合方式，才能繼續(xù)使用，這樣實(shí)際上又回到了算法一，只是由于工件體積分布的規(guī)律性不需要體積約束的驗(yàn)證了。模

34、型的求解：先求第二組數(shù)據(jù)的排序結(jié)果。根據(jù)問題1的自適應(yīng)平均值排序算法的結(jié)果，利用算法二得到如下排序結(jié)果：區(qū)域扇形區(qū)域1扇形區(qū)域2扇形區(qū)域3位置123456789101112序號(hào)192213751048624體積/10395.5103981039610397103.596.510297區(qū)域扇形區(qū)域4扇形區(qū)域5扇形區(qū)域6位置131415161718192021222324序號(hào)151117121322142316191820體積/103.595.1103.596.5102.59610396103.59810496.5可見，體積間隔和重量間隔均滿足要求。對(duì)第一組數(shù)據(jù)，我們首先進(jìn)行了體積約束的驗(yàn)證。首先

35、給出一個(gè)判斷哈密頓圖的充分條件：狄拉克Dirac定理1：設(shè)是含個(gè)頂點(diǎn)的簡(jiǎn)單無向圖，其頂點(diǎn)的最小度用表示。若，則是哈密頓圖。我們用MATLAB軟件求出了各工件之間體積差的鄰接矩陣，然后得出了所有頂點(diǎn)的度為：故，而，所以，因而這是哈密頓圖，存在哈密頓回路，即工件滿足體積條件。第二步，利用貪心策略搜索，根據(jù)問題三，我們可以看到序號(hào)10的工件有這較大的偏差，根據(jù)貪心選擇性質(zhì)，對(duì)十號(hào)重量修改為332，這樣同時(shí)滿足以上結(jié)論。問題三：當(dāng)工件不滿足要求時(shí)，允許更換少量的數(shù)據(jù)。根據(jù)前面解決問題的算法可以得出兩種修改策略：一是按重量排序；二是按重量和體積排序。針對(duì)問題一：根據(jù)問題一證明，使平均值是在不斷自我修整的，后面扇區(qū)的工件總重量最大可能接近前面扇區(qū)的總重量，但由于本設(shè)備的形狀是一個(gè)圓盤，第六個(gè)扇區(qū)與第一個(gè)扇區(qū)相臨，此時(shí)第六個(gè)扇區(qū)總重量和第一個(gè)扇區(qū)總質(zhì)量之差是累計(jì)誤差最大的。因此，如果存在不滿足的工件，最有可能在第六個(gè)扇區(qū)選擇工件是出現(xiàn)，這樣根據(jù)算法可以選擇出來最有四個(gè)工件，可以對(duì)該四個(gè)工件中某個(gè)工件做適當(dāng)?shù)恼{(diào)整，以達(dá)到滿足條件的工件出現(xiàn)。