案例+平板車的裝載問題

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

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

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

≤1.此時得到的最優(yōu)解若是整數(shù),則它就是ILP的最優(yōu)解;否則,我們在此解附近來找到一個可行解,即整數(shù)解.項目123456投資(億元)526468收益0.50.40.60.50.91收益率0.10.20.10.1250.150.125可以看出,投資優(yōu)先次序是:2,5,4(6),1(3).因此我們很容易得到兩個最優(yōu)解:本例比較簡單,我們不用軟件可直接求解LP.為此,我們算出每個項目的投資收益率,即單位投資的收益.列表:12為此,我們必須進一步處理,先看第一個最優(yōu)解易算出它們的年收益都是P=3.0.由于我們放寬了xi的取值范圍,上述最優(yōu)收益超過了實際的最優(yōu)收益,因為上述兩組最優(yōu)解都包含了非0,1的值,它是不滿足約束條件,實際上不是可行解.13取介于0,1之間的實數(shù)值,根據(jù)優(yōu)先選取收益率高的原則,又可以取得兩組最優(yōu)解:x3=0時的最優(yōu)解為(2/5,1,0,1,1,1),收益為3.0;x3=1時的一最優(yōu)解為(0,1,1,0,1,1)(原則二:在同等收益的解中,優(yōu)先取使得不滿足約束的解分量盡量少,因此(0,1,1,1,1,0.5)舍去),收益為2.9,此解已經(jīng)滿足變量取值為0,1的約束,因此是原問題的一個可行解.它的年收益可以作為原問題最優(yōu)解的一個候選者,即年收益少于2.9的解肯定不會是最優(yōu)解,這就是定界.而對應于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,我們進一步增加約束x1=0或x1=1來考察,即將變量取0,1的值的約束改為x3=0,x1=0或x3=0,x1=1來求解.對于約束x3=0,x1=0,滿足投資總額不超過22的解為(0,1,0,1,1,1),對應的年收益為2.8,雖然它是原問題的一個可行解,但是由于其年收益不到2.9,不可能為最優(yōu)解.對于約束x3=0,x1=1,有兩組最優(yōu)解(1,1,0,1,1,5/8)和(1,1,0,1/4,1,1),對應的年收益都是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的約束,此時求得的最優(yōu)解分別為我們再一一考察它們.過程我們用圖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ǔ)上,對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評注:分支定界法本質(zhì)上就是窮舉法.不過它是一種改進的窮舉法.它在算法實現(xiàn)上有很大的靈活性,往往取決于對問題的處理方式,分