MCM88 問題—B.兩輛鐵路平板車的裝貨問題

1、MCM88 問題B.兩輛鐵路平板車的裝貨問題由七種規(guī)格的包裝箱要裝到兩輛鐵路平板車上去。包裝箱的寬和高時一樣的，但厚度（t，以厘米計(jì)）及重量（，以公斤計(jì)）是不同的。下表給出了每種包裝箱的厚度、重量以及數(shù)量。每輛平板車有10.2米的地方可用來裝包裝箱（像面包片那樣），載重為40噸。由于當(dāng)?shù)刎涍\(yùn)得限制，對C5，C6，C7類的包裝箱的總數(shù)有一個特別的限制：這類箱子所占的空間（厚度）不能超過302.7厘米。試把包裝箱（見下表）裝到平板車上去使得浪費(fèi)的空間最小。 C1 C2 C3 C4 C5 C6 C7t(厘米) 48.7 52.0 61.3 72.0 48.7 52.0 64.0W(公斤) 2000

2、3000 1000 500 4000 2000 1000件數(shù) 8 7 9 6 6 4 8本題是由佐治亞理工學(xué)院的J.Bartholdi提供的。這是出現(xiàn)在福特汽車公司的一個尚未解覺的問題的修正與簡化。J.Bartholdi還寫了一片評論性文章The Outstanding Railroad Flatcar Papers，The UMAPJournal，v.9(1988)，no.4，399403。 平板列車車廂的優(yōu)化裝載摘要：在已知尺寸和載重量的約束下，如何在兩輛平板列車車廂(以下簡稱車廂)上裝載幾種特定的板條箱,使得剩余空間最??？針對“目的地卡車運(yùn)輸約束”（以下簡稱“卡車約束” ）的兩種可能解釋

3、，我們找到了相應(yīng)的最小剩余空間。它們被證明都是最優(yōu)的。我們利用計(jì)算機(jī)給出了所有取的最小剩余空間相應(yīng)裝載方式。然后討論了程序?qū)侠硗茝V后問題的計(jì)算復(fù)雜度問題，并得到：上述計(jì)算方法不能應(yīng)用到具有大量參數(shù)的問題，因?yàn)樗荖P問題。最后建議使用遺傳算法去解決它。一、簡介 首先，我們把問題重新闡訴一遍：在尺寸大小和載重量的約束下，在兩節(jié)車廂上裝載各種規(guī)格的板條箱。每中班條箱有其特定的厚度和重量，但其寬和高是統(tǒng)一的。向量和分別表示有各種板條箱的數(shù)量（單位個）、重量（單位噸）和厚度（單位cm）構(gòu)成的向量真值見表1。 和分別表示平板車的實(shí)際載重量，即的第I個元素N表示在第j號車廂上的第I種板條箱的數(shù)量，它們滿

4、足入下約束：表1 1i7時ni，ti和wi（即，和分量）值板條箱號（個）ni (cm) ti (噸) wi1 2 3 4 5 6 78 7 9 6 6 4 848.7 50.2 61.3 72.0 48.7 52.0 64.02 3 1 0.5 4 2 1C1：每種板條箱的裝載量不會超過其可用量， N Nn 1 i 7C2：每節(jié)車廂上的箱子的厚度不超過1020cm， 1020，j=1，2C3：每節(jié)車廂上的箱子重量不超過40噸，40， j=1，2。C4：“卡車約束”，即第5，6，7種板條箱的總厚度不超過302.7cm。因?yàn)槲覀儾恢来思s束是針對第一節(jié)車廂還是兩節(jié)車廂的總和，所以我們對每種理解都作

5、了 解答。定義向量使得=0， 1 i4， =ti， 5i7則或者（1） +302.7或者（2） 302.7, j=1.2 那么秋糧車廂的具有最少剩余空間的載貨量就等價于求（+）取得極大值使對應(yīng)的和。二、最優(yōu)解針對以上兩種情況，我們給出并證明了剩余空間最小的最優(yōu)解。全部最優(yōu)解將在下節(jié)給出。定理1 設(shè)N是由滿足C1C2 和（1）的無序?qū)?，為元素?gòu)成的集合，則存在，N使得其總和使用空間為2039.4cm，這是所能裝載的最大數(shù)量（即只有0.6cm的剩余量）。證明 考慮=（4，7，4，3，0，0，0），=（4，0，5，3，3，3，0），我們很容易證得它們構(gòu)成的集合屬于N。即：一，+=（8，7，9，6，3

6、，3，0）=（8，7，9，6，6，4，8）。二，=35.540， =33.540。三，=10201020， =1019.41020。四， +=302.1302.7也就是說：，N，（+）=2039.4 設(shè)N，（+）2039.4，則我們可以證明（+）=2039.4。首先證明 M+M=ni, i1，2，3，4。反設(shè)存在1，2，3，4使得M+Mn，則（M+M）=（M+M）ti +( M+M)ti （M+M）ti +302.7 (由（1）) （niti）+302.7ti (由反設(shè))204048.7也就是說將至少有48.7cm的剩余空間，顯然矛盾，故有M+ M=ni, i1，2，3，4 然后由上訴結(jié)論只需

7、證(3) 3( M+M)ti302.7不成立便可得結(jié)論：，是最優(yōu)解。 記M= M+M，i5，6，7反設(shè)（3）成立，則由7t5=340.9得M57，然后分別考慮： M5=0。由t6 , t7是整數(shù)知Miti是整數(shù)，因此它不能屬于（302.1，302.7），（3）不成立。 M5=1。由Miti(302.1，302.7)，得M6t6+M7t7=254因?yàn)?t7=256254所以M74,通過驗(yàn)證M7=0，1，2，3四種情況知（3）不成立。 M5=2。同前可得M6t6+M7t7=205，此時它無正整數(shù)解。（3）亦不成立。 M5=3。此時M5t5=146.1，故同M5=0情形 （3）亦不成立。不過當(dāng)（3）

8、中“”換成“”則至少有一解M6=3, M7=0。事實(shí)上，是包含在這一情形中的一個解。 M5=4。則Miti為一整數(shù)加0.8不可能屬于（302.1，302.7）。 M5=5。M6t6+M7t7=59，不可能成立。 M5=6。亦無解。這樣我們就證明了（3）無解，那2039.4是（+）所能取得的最大值。定理1是在卡車約束（1）情況下得最優(yōu)解，它顯然是在約束2下的可行解，所以我們有可能用更少的剩余空間來裝滿車廂。事實(shí)上，在這種情況下正好裝滿。 定理2 存在，滿足C1C3和（2）使得它正好裝滿兩節(jié)車廂。 證明 設(shè)=（6，2，6，0，0，0，4），=（0，5，2，5，2，1，2），則可驗(yàn)證它們滿足C1C2

9、和（2）： 一，+=（6，7，8，5，2，1，6）（8，7，9，6，6，4，8），= 二，=1020。 三，=2840，=31.540 四 =-256302.7，=277.4302.7，故（2）成立（當(dāng)然不滿足（1）。 以上驗(yàn)證表明定理2成立。三、最優(yōu)和近似最優(yōu)的算法。這一節(jié)將給出每種卡車約束下的計(jì)算程序。首先我們把兩節(jié)車廂合并成一個大車廂（叫合并車廂），那么合并車廂有20.4m長,80噸載重量。這是它約束（1）下最多只能裝5，6，7類板條箱302.7cm，而在約束（2）下只能裝上述箱子605.4cm。每當(dāng)程序?qū)喜④噹业揭唤谱顑?yōu)解，它就試圖在兩節(jié)車廂中把它重新分配已達(dá)到平衡（這一過程叫平

10、衡）。因?yàn)閮闪熊囅涞娜魏慰尚薪獾慕M合都是合并車廂的可行解，所以合并車廂的最優(yōu)解若能被平衡，則它一定是最優(yōu)解。事實(shí)說明，總有合并車廂的最優(yōu)解能被平衡。也就是說這是以有效的計(jì)算方法。 程序放在附錄二中。它由求解合并車廂的所有可行解的檢索，打印出用戶所要求的（近似）最優(yōu)解，然后再把它進(jìn)行平衡。附錄一給出的兩個運(yùn)行實(shí)例，得到合并車廂在（1）下的唯一最優(yōu)解（剩余空間為0.6cm），它有60種平衡。它在約束（2）下算出合并車廂有10個最優(yōu)解，而其中只有6個可被唯一平衡。 算法的優(yōu)缺點(diǎn)：通過給程序提供適當(dāng)?shù)膮?shù)，我們能夠列出所有剩余空間比某一給定值小而又不小于極小值的（近似）最優(yōu)解（例如在約束（1）下，總共

11、有1282中裝載方法使得剩余空間小于10cm）。當(dāng)然對實(shí)際操作來說，還可以粗糙一些。理論上正好裝滿車廂的最優(yōu)解，實(shí)際操作很可行不通，這就是說對具體操作還需要些“手法”。程序的另一優(yōu)點(diǎn)是它易于被改造用于相關(guān)問題的解答。例如，若某種板條箱的厚度測度不精確，則只要改動程序中的兩個向量即可。甚至像加上另一卡車約束條件這樣大的變動，計(jì)算機(jī)程序也能在少量改動下進(jìn)行計(jì)算。同時它還可以把優(yōu)化準(zhǔn)則改變，例如是重量和厚度的某一加權(quán)值等等。例如，定理二成立的六種滿載都具有最大載重量。具體見附錄一。程序的缺點(diǎn)是：它對較大數(shù)據(jù)的問題有點(diǎn)兒不合世紀(jì)。因?yàn)樗举|(zhì)上是一種窮舉法，運(yùn)行速度太慢，這種不成熟的算法只適合那些相對簡

12、單的問題。它的弱點(diǎn)還將在下一節(jié)詳細(xì)闡述。四、方法評估和問題推廣前兩節(jié)的計(jì)算和證明完全依賴于這一特定問題。如前所述，當(dāng)箱子個數(shù)增多時，算法因速度太慢而不可用，自然要問有沒有一種通用的算法來克服上述困難呢？回答是否定的。因?yàn)樗囊话銌栴}是NP復(fù)雜的。我們建議使用遺傳算法近似解決這一問題。我們說問題P是屬于NP簇的，是指它不能被人以確定的多項(xiàng)式步內(nèi)的Turing計(jì)算法所解決。Garey and Johnson 1979.(一種非正式的定義為：除非有神明幫助，否則一個NP問題不能在多項(xiàng)式步內(nèi)用確定的Turing即算法被解決)。有時稱NP問題是NP復(fù)雜的。任一NP問題的多項(xiàng)式時間確定Turing算法的存

13、在性意味所有NP問題都由上述算法。S.A.cook在1971年證明了NP問題的存在性cook 1971。定理3 車廂裝載是NP復(fù)雜問題。其中車廂裝載問題定義如下：給定箱子集合N，定義重量厚度，給定四個正整數(shù)k,W,T和T,問是否存在k個不相交的子集使得對i1,k下式成立：，？（注意，w(n),t(n)不必是整數(shù)，但由于誤差的原因，我們總會用一些有理數(shù)去近似它們，故總會歸結(jié)為整數(shù)問題。前兩式子表示重量，厚度的限制，最后一式表示設(shè)法要達(dá)到的厚度）。證明 先證車廂裝載是NP問題。如果奇跡給我們提供了k個不相交的子集Si,我們能夠很快驗(yàn)證Si是不是一個解。說明它是一個NP問題只需說明在k=1,并忽略掉

14、限制2是它是一個NP問題，此時它變?yōu)镵NAPSACK問題：給定有限集N, ,對正整數(shù)W,T是否使得 且？KNAPSACK是NP問題Karp 1972，故有車廂裝載問題有多項(xiàng)式算法 KNAPSACK有多項(xiàng)式算法，故車廂裝載問題比KNAPSACK更難更復(fù)雜。而KNAPSACK是NP復(fù)雜問題，故車廂裝載是NP問題。 我們注意到，定理1的證明完全依附于附加的卡車約束。盡管在這里附加條件簡化了原問題，但對一般問題卻增加了復(fù)雜度。任何能夠在具有限制條件下多項(xiàng)式時間能夠解決的問題，必能在去掉限制后求解。所以附加條件不能改變其NP問題的本質(zhì)。 還應(yīng)注意：我們的算法分兩步，即合成車廂的近似優(yōu)化求解法和上述解在各

15、車廂種的平衡，而這種平衡是一個PARTITION(分割)問題它也是NP的, Karp 1972：給定有限集A及A上一實(shí)函數(shù)S(a),問是否存在一子集A使得 = ?看起來把一個NP問題分成兩個NP問題沒什么改進(jìn)。但事實(shí)上對于小規(guī)模的問題是較為有效的。因?yàn)镵NAPSACK問題比車廂裝載問題要簡單的多。而分割問題也相對容易些。如果給我們一個更加一般的例子，我們就不會像計(jì)算問題給出的例子那樣輕而一舉地解決。對于一般問題，像裝載滿足約束C1C3和(1)或(2)的車廂那樣，它構(gòu)成一個Z中的凸集L，其中n是一大數(shù)。使得剩余空間達(dá)到最少的優(yōu)化裝載方案，一定靠近L的邊界。我們可用下法來找這樣的裝載：先隨集給以可

16、行解，然后同過加載直到邊界，然后通過隨機(jī)加減載重量沿邊界搜索，通過迭代，我們便可以找到一種接近最優(yōu)的方案。五、結(jié)論在對卡車約束的兩種合理解釋下，我們解決了所給的問題。并證明0.6cm和0cm的剩余空間分別是兩種情況下的最優(yōu)解。當(dāng)然，它們都是針對給定問題的。另外我們還給出一計(jì)算機(jī)程序，它可以處理具有誤差的數(shù)據(jù)。最后我們證明了在嚴(yán)格意義下的一般問題是NP問題，沒有通用的多項(xiàng)式算法去求解。 參考資料Cook,S.A.1971.The complexity of theozem-proving procedures.In proceedings of the 3ed Annual ACM Symposium on Theory of computing,151158. New York:Association for computing Machinery.Garey,M.R.,and D.S.Johndon.1979.Computers