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

1、兩輛鐵路平板車的裝貨問題 2014摘要：將七種規(guī)格的包裝箱裝到兩輛鐵路平板車上并要求浪費空間最小的問題，實質上 就是整數線性規(guī)劃問題。建立整數線性規(guī)劃模型，并用 lingo 軟件求得目標函數最小值 得給出一組最優(yōu)解。然而由于 LINGO 軟件的缺陷性，我們發(fā)現仍然存在其他多組最優(yōu) 解。通過對原始數據的分析論證，我們得到一個結論：對任意一組最優(yōu)解，兩輛車的總 包裝箱種類和數量是確定的（即浪費空間最小的情況下，裝載包裝箱的厚度和重量一 定）。在此結論的基礎上，通過窮舉法，并利用 Java高級計算機語言進行編程，大大減 少了計算量，加快了運算速度，最終求解出 24 組等價最優(yōu)解。關鍵詞： 裝貨問題

2、整數線性規(guī)劃 窮舉法 LINGO Java 語言1、問題重述有七種規(guī)格的包裝箱要裝到兩輛鐵路平板車上去。包裝箱的寬和高是一樣的，但厚 度（t，以 cm計）及重量（ w，以 kg計）是不同的。表一給出了每種包裝箱的厚度、重 量以及數量。每輛平板車有 10.2 米長的地方可用來裝包裝箱（像面包片那樣） ，載重為 40 噸。由于當地貨運的限制，對 C5，C6，C7 類的包裝箱的總數有一個特別的限制：這 類箱子所占的空間（厚度）不能超過 302.7cm。試把包裝箱裝到平板車上去使得浪費的 空間最小。表C1C2C3C4C5C6C7TI(cm)48.752.061.372.048.752.064.0WE(

3、kg)200030001000500400020001000件數87966482、問題分析優(yōu)化問題，一般是指用“最好”的方式，使用或分配有限的資源，即勞動力、原材1 料、機器、資金等，使得費用最小或者利潤最低 1 。在此問題中，要求浪費的空間最小， 且存在車長 10.2m、載重 40t、貨運限制 C5，C6，C7 類的包裝箱的總數 302.7cm三個 約束條件，并且自變量(包裝箱的數量)取整數值才有意義，所以此問題可以通過建立 整數線性規(guī)劃來求解。其一般形式為：nmin zcj x jj1 naij xj bi (i 1,2, , m)s.t. j 1 xj為非負整數 ( j 1,2, ,n)

4、。3、模型假設(1) 假設包裝箱在平板車上只能排列一層，不能重疊擺放2 。(2) 不考慮兩輛平板車先后運載問題，也就是說，假設兩輛平板車完全相同，不 存在車次不同的問題。(3) 為提高對此問題研究的針對性，在此問題中，假設裝貨時貨物與貨物之間沒 有空隙，從而排除其他非主要矛盾的干擾。(4) 假設包裝箱在運載過程中不會因相互擠壓而產生形變，從而使厚度減小。4、問題分析TI(i) 第 Ci類包裝箱的厚度；WE(i) 第Ci 類包裝箱的重量；FI (i) 第Ci類包裝箱能裝上第一輛車的數量；SE(i) 第Ci 類包裝箱能裝上第二輛車的數量；NU(i) 第Ci 類包裝箱的總數量；5、模型建立與求解5.

5、1 整數線性規(guī)劃模型5.1.1模型建立及求解根據空間浪費最小目標以及約束條件建立模型一如下：7min z 2040 TI (i)*FI (i) SE(i)i17FI (i)*TI (i) 1020i17SE(i)*TI (i) 1020i17s.t. TI(i)*FI (i) SE(i) 302.7s.t. i 5FI (i) SE(i) NU (i)(i 1,2,.,7)7WE(i )* FI (i) 40000i17WE(i)* SE(i) 40000i1這是一個純整數規(guī)劃問題，針對此模型，我們利用 LINGO 軟件編寫程序(見附錄 1)解得一組最優(yōu)解如表二所示：表二C1C2C3C4C5C

6、6C7FI0690030SE8106300最小浪費空間為 0.6cm。5.1.2定理及證明定理：由 TI(1)=TI(5)=48.7 、TI(2)=TI(6)=52 (即 C1+2C2 C5+2C6)分析得出此情況 最優(yōu)解不止一組。在已知兩輛車上所裝包裝總長度最優(yōu)解的條件下，求出裝上車的 各規(guī)格的包裝箱的總數量， 再將數量分配到兩輛車上。 通過分析我們得出一個結論： 對任意一組最優(yōu)解，兩輛車的總包裝箱種類和數量是確定的(即浪費空間最小的情 況下，裝載包裝箱的厚度和重量一定) 。證明：通過計算得出， C1C4 包裝箱厚度總長為 1737.3cm，占用總空間最大為 2040cm，C5C7 三種包裝

7、箱總厚度不能超過 2040-1737.3=302.7cm，這也正好符合題目要求。所 以最優(yōu)解必須使前四種包裝箱全部用上(即厚度達到最大) ，后三種包裝箱的厚度在滿 足約束條件下達到最大，對于后三種包裝箱占用空間達到最大，我們建立模型二：7maxz TI(i)*FI (i) SE(I )i57s.t. TI (i)*FI (i) SE(i) 302.7s.t. i 50 FI (i) SE(i) NU (i)(i 5,6,7)利用 LINGO 軟件編寫程序(見附錄 2)得到最優(yōu)解： Z=302.1cm，此時 FI(5)+SE(5)=3， FI(6)+SE(6)=3，FI(7)+SE(7) =0

8、。再用反證法，假設 C1C4 包裝箱沒有全用上，則前四種包裝箱的總厚度至多為1737.3-48.7=1688.6cm，而 1688.6+302.7=1991.3cm，所以達不到最優(yōu)解 2039.4cm，所以 C1C4 包裝箱必須全用上。證畢。所以最優(yōu)解為 0.6 時，各規(guī)格包裝箱所裝數量的總和如表三：表三C1C2C3C4C5C6C7FI+SE87963305.2 窮舉法由表三可知，各規(guī)格包裝箱裝載總數分配到兩輛車上有 9*8*10*7*4*4*1=80640 種 情況，在已知最小空間為 0.6cm 的情況下，仍滿足車長 10.2m、載重 40t 兩個約束條件 且自變量為整數。利用 Java 語

9、言編寫程序(見附錄 3)對上述情況進行篩選，得出 24 組解(在實際運算中， 由于考慮車次問題， 所以解的數量會翻倍為 48 組)，如表四所示：表四序號FI(1)FI(2)FI(3)FI(4)FI(5)FI(6)FI(7)SE(1)SE(2)SE(3)SE(4)SE(5)SE(6)SE(7)1056402082323102066401081323203069003081063004076400080323305079002080063106244323063531007250533062910008254322062531109264321061531201027432006053130113

10、091320570501012319131056050201332913005505030143443130535320015350523052911001636052205191110173705210509112018405333047430001940912204705110204153320464301021419121046051202242533104543020234291200450513024435330044430302544430304353300264505130429120027454302042533102846051204191210294643010415332

11、030470511040912203147430004053330325091120370521033519111036052203452911003505230355353200344313036550503032913003756050203191310385705010309132039605313027432004061531202643210416253110254322042629100025053304363531002443230448006310079002045803233007640004681063000690030478132320066401048823231005

12、640206、模型分析優(yōu)點：利用整數線性規(guī)劃模型解出其中一組最優(yōu)解，從這一組解出發(fā)，證明其存在多組最 優(yōu)解，再通過窮舉算法， 利用 Java 語言編程，求出所有最優(yōu)解。 此方法可將所有最優(yōu)方 案呈現出來，從理論角度來說，方法合理，理論嚴謹。缺點：結果共有 48組最優(yōu)解（不考慮車次因素為 24 組最優(yōu)解），在實際生產生活中，如 想得到最優(yōu)運載方案，則還需通過貨物重量這個限制條件進行進一步比較篩選，從而使 運載成本降到最低。7、模型推廣 在實際生產生活中，文中的理論和方法不僅可用于其他貨物裝載問題中，在其他最 優(yōu)解問題的解決過程中也具有可觀的參考價值。但在有些問題的解決過程中，我們還需 利用更多的

13、限制條件，對得到的最優(yōu)解進行進一步的篩選，從而減少生產成本，提高生 產效率。8、結論本文針對兩輛鐵路平板車的裝貨問題，建立整數線性規(guī)劃模型，并用 lingo 軟件求 得目標函數最小值得給出一組最優(yōu)解，并得出定理：對任意一組最優(yōu)解，兩輛車的總包 裝箱種類和數量是確定的（即浪費空間最小的情況下，裝載包裝箱的厚度和重量一定） 。 在此定理的基礎上，通過窮舉法，并利用 Java 高級計算機語言進行編程，最終求解出 24 組等價最優(yōu)解。本文模型從理論角度上來說，方案合理，嚴謹科學，但在實際生產生 活中，還需尋找更多限制條件，對結果進行進一步篩選，從而得到最佳方案。9、參考文獻1 趙靜，數學建模與數學實驗

14、，北京：高等教育出版社， 2008 年。2 湯曉波， 基于數模理論的鐵路裝載配貨問題最優(yōu)解分析，產業(yè)與科技論壇，第 10卷 第 9 期：108，2011 年。附錄 1： LINGO 程序（整數線性規(guī)劃）model:sets: numbers/1,2,3,4,5,6,7/:FI,SE,TI,WE,NU;endsetsdata:TI=48.7,52,61.3,72,48.7,52,64;WE=2000,3000,1000,500,4000,2000,1000;NU=8,7,9,6,6,4,8;enddata min=2040-sum(numbers:TI*(FI+SE); sum(numbers:

15、TI*FI)<=1020;sum(numbers:TI*SE)<=1020; sum(numbers:WE*FI)<=40000;sum(numbers:WE*SE)<=40000;TI(5)*(FI(5)+SE(5)+TI(6)*(FI(6)+SE(6)+TI(7)*(FI(7)+SE(7)<=302.7; for(numbers:FI+SE<=NU);for(numbers:GIN(FI);for(numbers:GIN(SE);end附錄 2： LINGO 程序(定理證明)model:sets:numbers/5,6,7/:FI,SE,TI,NU;en

16、dsetsdata:TI,NU=48.7,652,464,8;enddata sum(numbers:(FI+SE)*TI)<=302.7; for(numbers:FI+SE<=NU);MAX=sum(numbers:(FI+SE)*TI);for(numbers:GIN(FI);for(numbers:GIN(SE);END附錄 3： Java 程序(求出全部最優(yōu)解)package LIN;import java.util.LinkedList;import java.util.List;public class guiLight int a1,a2,a3,a4,a5,a6,a

17、7;int b1,b2,b3,b4,b5,b6,b7;public guiLight(int x1,int x2,int x3,int x4,int x5,int x6,int x7, int y1,int y2,int y3,int y4,int y5,int y6,int y7) a1=x1;a2=x2;a3=x3;a4=x4;a5=x5;a6=x6;a7=x7;b1=y1;b2=y2;b3=y3;b4=y4;b5=y5;b6=y6;b7=y7;public static void main(String args)int x1,x2,x3,x4,x5,x6,x7;int y1,y2,y3

18、,y4,y5,y6,y7;List answer=new LinkedList<guiLight>();guiLight gl=null;/gl=new guiLight(0,6,9,0,0,3,0,/ 8,1,0,6,3,0,0);/answer.add(gl);for(x1=0;x1<=8;x1+)for(x2=0;x2<=7;x2+)for(x3=0;x3<=9;x3+)for(x4=0;x4<=6;x4+)for(x5=0;x5<=3;x5+)for(x6=0;x6<=3;x6+)x7=0;y7=0;y1=8-x1;y2=7-x2;y3=

19、9-x3;y4=6-x4;y5=3-x5;y6=3-x6;if( 2040 48.7*(x1+y1)-52*(x2+y2)-61.3*(x3+y3)-72*(x4+y4)-48.7*(x5+y5)-52*(x6+y6)-64*(x7+y7) - 0.6 < 1e-8&&102048.7*x1-52*x2-61.3*x3-72*x4-48.7*x5-52*x6-64*x7 >= 0&&102048.7*y1-52*y2-61.3*y3-72*y4-48.7*y5-52*y6-64*y7 >= 0&& 2000*x1+3000*x2+1000*x3+500*x4+4000*x5+