兩輛鐵路平板車的裝貨問題的討論

1、兩輛鐵路平板車裝貨問題的討論摘要本文鑒于對(duì)題中" C5,C6,C7類的包裝箱的總數(shù)的特別的限制：這類箱子所占的空間（厚度）不能超過302.7cm"的不同理解，分對(duì)一輛車上C5,C6,C7類的包裝箱的總數(shù)限制和兩輛車上的總數(shù)限制兩種情況討論，分別得出了各自情況下的滿足題意的最優(yōu)方案。對(duì)一輛車上C5,C6,C7類的包裝箱的總數(shù)限制情況，為整數(shù)線性規(guī)劃問題，建立模型一，并用LINGO求的最優(yōu)解（僅為多組解中一組），用枚舉法得出了6組（見表一），最優(yōu)解為兩輛車?yán)速M(fèi)總空間為0cm。并用VB驗(yàn)證模型一的建立以及分析思路的正確性。對(duì)兩輛車上C5,C6,C7類的包裝箱的總數(shù)限制情況，仍為整

2、數(shù)線性規(guī)劃問題，建立模型二，并用LINGO求的最優(yōu)解（僅為多組解中一組），兩輛車?yán)速M(fèi)的總空間為0.6cm。同時(shí)我們發(fā)現(xiàn)規(guī)律：所有最優(yōu)解必須滿足前四種包裝箱厚度達(dá)到最大（即全部用上），后三種包裝箱的厚度在滿足約束條件下達(dá)到最大。對(duì)于后三種包裝箱占用空間達(dá)到最大的問題，我們通過建立模型三，并應(yīng)用LINGO求得新約束條件 c5 =3,c6=3, c7=0，兩輛車的總厚度為2039.4cm，總重量為67噸。由此，可得到簡(jiǎn)化的A車上裝貨情況，即模型四，滿足約束條件之后把剩余部分裝到B車上，B車也滿足題目要求，用VB求得30組最優(yōu)解（見表二），大大提高了計(jì)算速度，克服了枚舉法的效率低下。關(guān)鍵詞：整數(shù)線性規(guī)

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

4、2.0 64.0w(kg) 2000 3000 1000 500 4000 2000 1000件數(shù) 8 7 9 6 6 4 8二、 問題分析通過讀題我們不難得出此題屬于整數(shù)型線性規(guī)劃問題，由題目中給出的條件,我們可以算出貨物的總重量為89噸，而兩輛車的載重量為80噸，所以必然不能將貨物全部裝載完，也就是說必然會(huì)有貨物剩余。我們假設(shè)平板車上只能放一排包裝箱，且包裝箱之間間隙忽略不計(jì)。對(duì)于題目中所說的對(duì)C5,C6,C7類包裝箱的總數(shù)的特別限制我們有兩種理解：一種是對(duì)于每輛車而言，車上C5,C6,C7類包裝箱的總空間不超過302.7cm，另一種是對(duì)于兩輛車而言，C5,C6,C7類包裝箱的總空間不超過

5、302.7cm。由此，我們打算分別對(duì)這兩種情況建立模型，并利用LINGO解出該整數(shù)型線性規(guī)劃的最優(yōu)解。考慮到變量較多以及變量權(quán)值的特殊性，我們猜想對(duì)每種情況都可能存在多組最優(yōu)解。我們準(zhǔn)備先利用lingo軟件解出一組最優(yōu)解作為基礎(chǔ)解，再根據(jù)t1=t5、t2=t6的關(guān)系，枚舉討論得出其余最優(yōu)解。對(duì)于第一種假設(shè)手工假設(shè)的方法完全適用，對(duì)于第二種假設(shè)我們發(fā)現(xiàn)用這種方法有很大的局限性，于是我們換一種思維先確定兩輛車的總數(shù)，再具體分配到每輛小車，以此來縮小題中變量的約束條件范圍，再利用VB等高級(jí)語言編程找出滿足條件的所有最優(yōu)解。三、 模型假設(shè)一、 每輛平板車上只能裝載一排的包裝箱，不存在并排或者疊加等情況

6、二、 包裝箱之間的間隙可忽略不計(jì)三、 不考慮方案不同僅僅是AB車車次相互交換的情況四、 不考慮一輛車上同一種包裝箱組合方案的不同排列五、 在重量符合要求的情況下，不考慮兩車重量差別大小對(duì)最優(yōu)解的影響 四、 符號(hào)系統(tǒng)假設(shè)兩輛車分別為A車和B車，：分別表示C1C7的厚度（厘米）：分別表示C1C7的重量（噸）：分別表示C1C7在A車中裝的件數(shù)：分別表示C1C7在B車中裝的件數(shù) （見模型三）(i=1,2,36,7)五、 模型建立 基于對(duì)題目中C5、C6、C7類包裝箱總數(shù)的限制的不同理解，我們將從以下兩種情況建立模型并求解一、 先考慮第一種情況，即本題中對(duì)C5、C6、C7類的包裝箱總數(shù)的限制為同一輛鐵路

7、平板車上這類箱子所占的厚度不能超過302.7cm，則由題意可建立模型一：s.t用LINGO計(jì)算出一組基礎(chǔ)解：C1C2C3C4C5C6C7twC5C7X6260004102028256Y0525212102031.5277.4對(duì)上述基礎(chǔ)解進(jìn)行變換:從條件中我們觀察到t1=t5=48.7, t2=t6=52.0, 所以容易得到一個(gè)結(jié)論：C1與C5, C2與C6之間可以相互調(diào)換，只要保證總數(shù)不變，則同一輛車上箱子所占的總空間也不變，此時(shí)只要滿足C5,C6,C7總空間限制和重量限制的條件，就是也是滿足此模型的一組最優(yōu)解。觀察基礎(chǔ)解可以分析得出：1.對(duì)A車： C1與C5、C2與C6不能有數(shù)量上的變化因?yàn)?/p>

8、X5,X6均為0, 所以不能從C1->C5, C2->C6 方向調(diào)換，而這樣會(huì)造成C5,C6,C7總空間的增加，即使空間增加最小的一個(gè)單位：256+48.7=304.7 已經(jīng)超過302.7的限制，所以對(duì)于X解已經(jīng)不能變換。2.對(duì)B車：C5->C1一單位C1C2C3C4C5C6C7twC5C7X6260004102028256Y1525112102028.5228.7C5->C1兩單位 C1C2C3C4C5C6C7twC5C7X6260004102028256Y2525012102027.5180C2->C6一單位 不可以！因?yàn)镃5C7超出302.7！C6->

9、C2一單位 不可以！因?yàn)镃2已經(jīng)達(dá)到最多7件！C5->C1一單位 , C2->C6一單位C1C2C3C4C5C6C7twC5C7X6260004102028256Y1425122102028.5280.7C5->C1兩單位,C2->C6一單位C1C2C3C4C5C6C7twC5C7X6260004102028256Y2425022102026.5232C5->C1兩單位 ,C2->C6兩單位C1C2C3C4C5C6C7twC5C7X6260004102028256Y2325032102025.5284浪費(fèi)空間T=2040-1020x2=0cm , 我們將上述

10、方法總結(jié)如下：由于t1=t5、t2=t6，C5->C1一單位引起重量減少2噸、同時(shí)C5C7的總空間減少48.7cm；C2->C6一單位引起重量減少1噸、同時(shí)C5C7的總空間增加52.0cm。所以這種變換只會(huì)讓重量變小，只需考慮它對(duì)C5C7總空間的影響：設(shè)C5->C1 x個(gè)單位，C2->C6 y個(gè)單位，則有解得當(dāng)(x，y)=（0，0）、(1，0)、(2，0)、(1，1)、(2，1)、(2，2)共六種情況時(shí)滿足約束條件，均為模型一的最優(yōu)解。此外，我們用VB編程計(jì)算，程序見（附錄2）設(shè)14個(gè)循環(huán)變量，在A車滿足約束條件的前提下，尋找B車滿足約束條件，利用了計(jì)算機(jī)程序，效率大大

11、提高，而且正確率也大大提高。得到六組最優(yōu)解如下表所示（單位：件）表一：X1X2X3X4X5X6X7Y1Y2Y3Y4Y5Y6Y7162600040525212262600041525112362600042525012462600041425122562600042425022662600042325032兩者結(jié)果完全一致，之前模型的建立以及分析思路的正確性得到了驗(yàn)證。二、 再考慮第二種情況，即本題中對(duì)C5、C6、C7類的包裝箱總數(shù)的限制為兩輛鐵路平板車上這類箱子所占的總厚度不能超過302.7cm，則由題意可建立模型二：S.t用lingo計(jì)算出結(jié)果C1C2C3C4C5C6C7twC5C7A車X3

12、0913201019.931.5250.1B車Y57050101019.535.552最少總浪費(fèi)空間T=2040-1019.9-1019.5=0.6cm , 這是一組最優(yōu)解，但是lingo軟件的局限性在于有多組最優(yōu)解時(shí)只給出其中的一組最優(yōu)解，而由t1=t5、t2=t6分析可以得到結(jié)論：此情況最優(yōu)解不止一組，又由于A、B兩車中沒有一輛車的裝載情況（即包裝箱的組合方案）是確定的，所以第一種假設(shè)中所使用的C1與C5、C2與C6相互對(duì)換，從而產(chǎn)生所有解的方法不適用于第二種假設(shè)。對(duì)此，我們換一個(gè)思考角度：先確定兩輛車上所裝包裝總長(zhǎng)度的最優(yōu)解，再將總長(zhǎng)度分配到A、B兩輛車上。通過對(duì)題目的仔細(xì)分析，我們得到

13、一個(gè)結(jié)論：對(duì)任意一組最優(yōu)解，兩輛車的總包裝箱種類和數(shù)量是確定的（即厚度和重量一定）證明：通過計(jì)算不難得出，C1C4包裝箱厚度總長(zhǎng)為1737.3cm，占用總空間最大為2040cm，C5C7三種包裝箱總厚度不能超過2040-1737.3=302.7cm，這也正好符合題目要求。所以最優(yōu)解必須使前四種包裝箱全部用上（即厚度達(dá)到最大），后三種包裝箱的厚度在滿足約束條件下達(dá)到最大，對(duì)于后三種包裝箱占用空間達(dá)到最大，我們建立模型三： s.t由lingo軟件編寫程序（見附錄4）得到最優(yōu)解：Z=302.1cm，此時(shí)c5=3,c6 =3,c7 =0再用反證法，假設(shè)C1C4包裝箱沒有全用上，則前四種包裝箱的總厚度至

14、多為1737.3-48.7=1688.6cm，而1688.6+302.7=1991.3cm，所以達(dá)不到最優(yōu)解2039.4cm，所以C1C4包裝箱必須全用上。證畢所以最優(yōu)解時(shí)，兩輛車的總厚度為2039.4cm，總重量為67噸，至此我們可以將模型二簡(jiǎn)化，僅考慮一輛車（如A車），它的總厚度至少為2039.4-1020=1039.4cm，至多為1020cm；它的總重量至少為67-40=27噸，至多為40噸；并且由模型三的結(jié)果得x5至多為3件，x6至多為三件，x7 =0，其余約束條件不變，于是得到簡(jiǎn)化后的模型四： s.t在滿足這些約束條件之后把剩余部分裝到B車上，B車也滿足題目要求對(duì)于這個(gè)簡(jiǎn)化后的模型，

15、我們可以用vb編程（見附錄5）來實(shí)現(xiàn)，運(yùn)行后結(jié)果共有60組，但考慮到模型假設(shè)3中忽略A、B車次的影響，應(yīng)該把結(jié)果除以2，實(shí)際的結(jié)果共30種，見下表：表二：A車中B車中編號(hào)C1C2C3C4C5C6C7C1C2C3C4C5C6C71056402082323102069003081063003076400080323304079002080063105066400081323206144333073530007154332072530108164331071530209244323063531001025053306291000112543220625311012264321061531201327

16、43210605313014309132057050101531913105605020163291300550503017344313053532001835052305291100193543120525321020360522051911102137431105153220223705210509112023374310050532302440533304743000254091220470511026419121046051202741533204643010284253310454302029429120045051303043533004443030以上30組最優(yōu)解，最終兩輛車?yán)速M(fèi)

17、的總空間最少為0.6cm。六、 模型分析 對(duì)于假設(shè)一中我們建立的模型一：我們將題目的約束條件很直觀地反映出來，使人容易理解和接受。并能利用多種方法通過該模型得到問題的最優(yōu)解，再一次說明了模型一的正確性和適用性。對(duì)于假設(shè)二中建立的三個(gè)模型：模型二是最直觀的，也能最完整地反映題目的本意，但求解起來存在一定難度。模型三對(duì)題目本身沒有直接貢獻(xiàn)，但能幫助求解模型二，起到了縮小范圍的作用。模型四是簡(jiǎn)化后的模型二，即保留了原模型的直觀性又變得更加容易實(shí)現(xiàn)，大大降低了直接求解模型二的計(jì)算復(fù)雜性，是一種較好的模型。七、 結(jié)論對(duì)于第一種理解即每輛車C5、C6、C7這類箱子所占的空間不超過302.7cm的情況，我們

18、建立了模型一，得到6組最優(yōu)解，兩輛車?yán)速M(fèi)的總空間最少為0cm。對(duì)于第二種理解即兩輛車C5、C6、C7這類箱子所占的總空間不超過302.7cm的情況，我們建立了模型二、模型三、模型四，最終得到30組最優(yōu)解，兩輛車?yán)速M(fèi)的總空間最少為0.6cm。八、 參考文獻(xiàn)1趙靜、但琦等，數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)，北京：高等教育出版社，2008。2劉煥彬、庫在強(qiáng)等，數(shù)學(xué)模型與實(shí)驗(yàn) ，北京：科學(xué)技術(shù)出版社，2008。附錄附錄1：max=48.7*(x1+y1)+52.0*(x2+y2)+61.3*(x3+y3)+72.0*(x4+y4)+48.7*(x5+y5)+52.0*(x6+y6)+64.0*(x7+y7);48.

19、7*x1+52.0*x2+61.3*x3+72.0*x4+48.7*x5+52.0*x6+64.0*x7<=1020;48.7*y1+52.0*y2+61.3*y3+72.0*y4+48.7*y5+52.0*y6+64.0*y7<=1020;2*x1+3*x2+1*x3+0.5*x4+4*x5+2*x6+1*x7<=40;2*y1+3*y2+1*y3+0.5*y4+4*y5+2*y6+1*y7<=40;48.7*x5+52.0*x6+64.0*x7<=302.7;48.7*y5+52.0*y6+64.0*y7<=302.7;x1+y1<=8;x2+y2

20、<=7;x3+y3<=9;x4+y4<=6;x5+y5<=6;x6+y6<=4;x7+y7<=8;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);gin(y1);gin(y2);gin(y3);gin(y4);gin(y5);gin(y6);gin(y7);附錄2：Private Sub Command1_Click() Dim i As Integer, j As Integer, k As Integer, l As Integer, m As Integer, n As Integer,

21、p As Integer, q As Integer Dim sum1 As Single, sum2 As Single, sum3 As Single Dim st As String, a As Single, str As String Dim i2 As Integer, p2 As Integer, j2 As Integer, k2 As Integer, m2 As Integer, n2 As Integer, q2 As Integer Dim sum4 As Single, sum5 As Single, sum6 As Single For p = 0 To 8 For

22、 i = 0 To 7 For j = 0 To 9 For k = 0 To 6 For m = 0 To 6 For n = 0 To 4 For q = 0 To 8 sum2 = p * 2 + 3 * i + 1 * j + 0.5 * k + 4 * m + 2 * n + 1 * q sum1 = 48.7 * p + 52 * i + 61.3 * j + 72 * k + 48.7 * m + 52 * n + 64 * q sum3 = 48.7 * m + 52 * n + 64 * q If sum1 = 1020 And sum2 <= 40 And sum3

23、<= 302.7 Then st = p & " " & i & " " & j & " " & k & " " & m & " " & n & " " & q & " " & " " & sum1 & " " & sum2 & " " &

24、sum3 List1.AddItem st For p2 = 0 To 8 - p For i2 = 0 To 7 - i For j2 = 0 To 9 - j For k2 = 0 To 6 - k For m2 = 0 To 6 - m For n2 = 0 To 4 - n For q2 = 0 To 8 - q sum5 = p2 * 2 + 3 * i2 + 1 * j2 + 0.5 * k2 + 4 * m2 + 2 * n2 sum4 = 48.7 * p2 + 52 * i2 + 61.3 * j2 + 72 * k2 + 48.7 * m2 + 52 * n2 + 64 *

25、 q2 sum6 = 48.7 * m2 + 52 * n2 + 64 * q2 If sum4 = 1020 And sum5 <= 40 And sum6 <= 302.7 Then str = p2 & " " & i2 & " " & j2 & " " & k2 & " " & m2 & " " & n2 & " " & q2 & " &quo

26、t; & " " & sum4 & " " & sum5 & " " & sum6 & " " & st List2.AddItem str End If Next Next Next Next Next Next Next End If Next Next Next Next Next Next Next End Sub附錄3：max=48.7*(x1+y1)+52.0*(x2+y2)+61.3*(x3+y3)+72.0*(x4+y4)+48.7*(

27、x5+y5)+52.0*(x6+y6)+64.0*(x7+y7);48.7*x1+52.0*x2+61.3*x3+72.0*x4+48.7*x5+52.0*x6+64.0*x7<=1020;48.7*y1+52.0*y2+61.3*y3+72.0*y4+48.7*y5+52.0*y6+64.0*y7<=1020;2*x1+3*x2+1*x3+0.5*x4+4*x5+2*x6+1*x7<=40;2*y1+3*y2+1*y3+0.5*y4+4*y5+2*y6+1*y7<=40;48.7*x5+52.0*x6+64.0*x7+48.7*y5+52.0*y6+64.0*y7&l

28、t;=302.7;x1+y1<=8;x2+y2<=7;x3+y3<=9;x4+y4<=6;x5+y5<=6;x6+y6<=4;x7+y7<=8;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);gin(y1);gin(y2);gin(y3);gin(y4);gin(y5);gin(y6);gin(y7);附錄4：max=48.7*c5+52.0*c6+64.0*c7;48.7*c5+52.0*c6+64.0*c7<=302.7;c5<=6;c6<=4;c7<=8;gin(c5);gin(c6);gin(c7);附錄5：Private Sub Command1_Click() Dim i As Integer, j A