案例+平板車的裝載問題

兩輛鐵路平板車的裝載問題(88年MCM之B題)1要把七種規(guī)格的包裝箱裝到兩輛鐵路平板車上,包裝箱的寬和高都是相同的,但厚度(t,以厘米計(jì))及重量(w,以噸計(jì))卻不同.下表給出了它們的厚度、重量及數(shù)量每輛平板車有10.2米的地方可以用來裝箱(像面包片那樣),載重為40噸.由于當(dāng)?shù)刎涍\(yùn)的限制,對(duì)C5,C6,C7三類包裝箱的總數(shù)有如下特殊約束:它們所占的空間(厚度)不得超過302.7厘米.試把這些包裝箱裝到平板車上,而浪費(fèi)的空間最小.21問題分析題中所有包裝箱共重89噸,總厚度達(dá)到2749.5cm,而兩輛平板車只能載2×40=80噸,2040cm,因此不能全裝下,究竟在兩輛車上裝哪些種各多少個(gè)箱子才合適,必須有評(píng)價(jià)的標(biāo)準(zhǔn).這標(biāo)準(zhǔn)是遵守題中說明的重量、厚度方面的約束條件,并且體現(xiàn)出盡可能多裝.由題意,只考慮像面包片重疊那樣的裝法,把問題簡(jiǎn)化為:兩輛車上裝箱總厚度之和盡可能大,這是一個(gè)典型的規(guī)劃問題.32模型構(gòu)建4兩輛平板車裝箱總厚度之和此問題的數(shù)學(xué)模型為:這是整數(shù)線性規(guī)劃模型5我們運(yùn)用LINDO軟件求解,可以得到該問題的一個(gè)最優(yōu)解為最優(yōu)值為2039.4.從運(yùn)行的結(jié)果報(bào)告來看,LINDO求解時(shí)用到了分支定界法.一些技巧與改進(jìn)1.由于兩輛平板車的對(duì)稱性,我們只要對(duì)某個(gè)6變量進(jìn)行限制,例如x13≤4,這樣計(jì)算量就減少了.2.從最優(yōu)解我們發(fā)現(xiàn),前四種貨物箱全部裝載完.事實(shí)上,如果我們仔細(xì)計(jì)算早就可以發(fā)現(xiàn):在限定所載后三種貨物箱的厚度和不超過302.7cm時(shí),裝載前四種貨物箱的厚度大于或等于2040-302.7=1737.3,而前四種貨物箱的總厚度正好為1737.3cm,且總重量為49t.由于后三種貨物箱總厚度不超過302.7cm的最大值我們很容易發(fā)現(xiàn)為302.1cm,就是C5三箱,C6三箱,C7不裝(因?yàn)樗鼈兊暮穸确謩e為48.7,52,64,換動(dòng)任何一個(gè)都將改動(dòng)超過0.6cm.)而此時(shí)總重為67t.手工就可以派出一個(gè)最優(yōu)解.基于這些分析后,我們很容易通過7編程算出所有的最優(yōu)解(前四種箱數(shù)約束事實(shí)上可以用等式,第五,六種各三個(gè),第七種為零).我們今后會(huì)看到,即使我們利用計(jì)算機(jī)處理一些問題,進(jìn)行必要的數(shù)學(xué)處理和具體問題的分析對(duì)我們解決問題往往很有幫助.特別是參加數(shù)學(xué)建模競(jìng)賽時(shí)更是如此.探索題：如果你多運(yùn)行幾次,觀察結(jié)果有什么不同?8問題二投資效益問題及分支定界法1.問題的提出

項(xiàng)目123456投資(億元)526468收益(億元)0.50.40.60.50.91一個(gè)公司有22億元資金可用來投資,現(xiàn)有六個(gè)項(xiàng)目可供選擇,各項(xiàng)目投資額和預(yù)計(jì)受益如下表:應(yīng)選那幾個(gè)項(xiàng)目投資收益最大?92.模型的建立引入表征是否對(duì)的i個(gè)項(xiàng)目投資的變量xi:因此投資總額為因而預(yù)見的年收入為從而模型(ILP)為103.模型的求解方法1.窮舉法.由于現(xiàn)在只有6個(gè)項(xiàng)目,每個(gè)項(xiàng)目都有投資和不投資兩種可能的選擇,因此共有64種投資方案.我們可以將這64個(gè)方案一一驗(yàn)證是否可行,并對(duì)可行的方案計(jì)算收益,進(jìn)行比較,選出最優(yōu)方案.此方法簡(jiǎn)便易行.但是,計(jì)算量較大,而且隨著可選項(xiàng)目的增多,不太具有推廣性.11方法2.

分支定界法.分支定界法的思想是:先求解LP:即放寬變量的取值范圍,改成0≤xi

≤1.此時(shí)得到的最優(yōu)解若是整數(shù),則它就是ILP的最優(yōu)解;否則,我們?cè)诖私飧浇鼇碚业揭粋€(gè)可行解,即整數(shù)解.項(xiàng)目123456投資(億元)526468收益0.50.40.60.50.91收益率0.10.20.10.1250.150.125可以看出,投資優(yōu)先次序是:2,5,4(6),1(3).因此我們很容易得到兩個(gè)最優(yōu)解:本例比較簡(jiǎn)單,我們不用軟件可直接求解LP.為此,我們算出每個(gè)項(xiàng)目的投資收益率,即單位投資的收益.列表:12為此,我們必須進(jìn)一步處理,先看第一個(gè)最優(yōu)解易算出它們的年收益都是P=3.0.由于我們放寬了xi的取值范圍,上述最優(yōu)收益超過了實(shí)際的最優(yōu)收益,因?yàn)樯鲜鰞山M最優(yōu)解都包含了非0,1的值,它是不滿足約束條件,實(shí)際上不是可行解.13取介于0,1之間的實(shí)數(shù)值,根據(jù)優(yōu)先選取收益率高的原則,又可以取得兩組最優(yōu)解:x3=0時(shí)的最優(yōu)解為(2/5,1,0,1,1,1),收益為3.0;x3=1時(shí)的一最優(yōu)解為(0,1,1,0,1,1)(原則二:在同等收益的解中,優(yōu)先取使得不滿足約束的解分量盡量少,因此(0,1,1,1,1,0.5)舍去),收益為2.9,此解已經(jīng)滿足變量取值為0,1的約束,因此是原問題的一個(gè)可行解.它的年收益可以作為原問題最優(yōu)解的一個(gè)候選者,即年收益少于2.9的解肯定不會(huì)是最優(yōu)解,這就是定界.而對(duì)應(yīng)于x3=0的最優(yōu)解恰為我們第一步得到且至今還為處理的解.這一步圖解如下:14圖1(0,1,1/3,1,1,1),3.0

(2/5,1,0,1,1,1),3.0(0,1,1,0,1,1),2.9由于x3=0的解中x1=2/5,我們進(jìn)一步增加約束x1=0或x1=1來考察,即將變量取0,1的值的約束改為x3=0,x1=0或x3=0,x1=1來求解.對(duì)于約束x3=0,x1=0,滿足投資總額不超過22的解為(0,1,0,1,1,1),對(duì)應(yīng)的年收益為2.8,雖然它是原問題的一個(gè)可行解,但是由于其年收益不到2.9,不可能為最優(yōu)解.對(duì)于約束x3=0,x1=1,有兩組最優(yōu)解(1,1,0,1,1,5/8)和(1,1,0,1/4,1,1),對(duì)應(yīng)的年收益都是2.925,

15圖2(0,1,1/3,1,1,1),3.0

(2/5,1,0,1,1,1),3.0(0,1,1,0,1,1),2.9

(0,1,0,1,1,1)2.8(1,1,0,1/4,1,1)2.925或×(1,1,0,1,1,5/8)2.925再在(1,1,0,1/4,1,1)的基礎(chǔ)上分別增加x4=0和x4=1的約束,此時(shí)求得的最優(yōu)解分別為我們?cè)僖灰豢疾焖鼈?過程我們用圖2表示:定界16年收益為2.925,前者雖為可行解,但是年收益不足2.9,因此舍去,后者即為上一步未曾處理的解.圖解為(0,1,1/3,1,1,1),3.0(2/5,1,0,1,1,1),3.0(0,1,1,0,1,1),2.9

(0,1,0,1,1,1)2.8(1,1,0,1/4,1,1)2.925×(1,1,0,0,1,1)2.8(1,1,0,1,1,5/8)2.925×繼續(xù)在(1,1,0,1,1,5/8)的基礎(chǔ)上,對(duì)x6增加約束:(1,1,0,0,1,1),年收益為2.8,以及(1,1,0,1,1,5/8),17

(0,1,1/3,1,1,1),3.0

(2/5,1,0,1,1,1),3.0(0,1,1,0,1,1),2.9

(0,1,0,1,1,1)2.8(1,1,0,1/4,1,1)2.925×(1,1,0,0,1,1)2.8×(1,1,0,1,1,5/8)2.925(1,1,0,1,1,0)2.3(1,1,0,1,1/2,1)2.85

××

結(jié)論:(0,1,1,0,1,1)為最優(yōu)解,最大收益為2.9億元.18評(píng)注:分支定界法本質(zhì)上就是窮舉法.不過它是一種改進(jìn)的窮舉法.它在算法實(shí)現(xiàn)上有很大的靈活性,往往取決于對(duì)問題的處理方式,分