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

1、兩輛鐵路平板車裝貨問題的討論摘要本文針對兩輛鐵路平板車裝運包裝箱的問題，建立了鐵路平板車裝運包裝箱的整數(shù)規(guī)劃模型，通過LINGO軟件方便快捷地求出了平板車不同種類包裝箱裝運件數(shù)一組最優(yōu)解，同時使用Fortran編程求出所有符合條件的最優(yōu)解。本文鑒于題目中"當?shù)刎涍\的限制，對C5,C6,C7類的包裝箱的總數(shù)的特別的限制：這類箱子所占的空間（厚度）不能超過302.7cm"的存在的歧義，對該問題分兩種情況進行討論，分別建立模型，得出了不同情況下滿足題設的最優(yōu)方案。第一種情況認為貨運的限制針對于每輛平板車，即每輛車上C5,C6,C7類的包裝箱的總厚度不超過302.7cm。針對該情況

2、，我們建立了兩輛鐵路平板車裝運包裝箱的整數(shù)規(guī)劃模型一，并用LINGO求得最優(yōu)解為兩輛車裝運C1,C2,C7類包裝箱的數(shù)量分別為（6，2，6，0，0，0，4；1，5，2，5，1，1，2），剩余厚度為0cm?？紤]到LINGO求解整數(shù)規(guī)劃只能求出一組最優(yōu)解的局限性，我們進而用Fortran編程求出了所有符合條件的12組最優(yōu)解。因為不考慮兩車先后次序，我們又用對結果去重，最終得到6組最優(yōu)解（詳見表一）。另一種則認為貨運的限制針對于一次貨運，在本題中則為兩輛車上C5,C6,C7類的包裝箱的總厚度不超過302.7cm。針對該情況，我們同樣也建立了鐵路平板車裝運包裝箱的整數(shù)規(guī)劃模型二，并用LINGO求得最優(yōu)

3、解為兩輛車裝運C1,C2,C7類包裝箱的數(shù)量分別為（3，2，9，1，3，0，0；5，5，0，5，0，3，0），剩余厚度為0.6cm。同樣由于LINGO軟件的局限性，我們又用Fortran編程求得所有符合條件的54組最優(yōu)解，經(jīng)過去重后最終得到27組最優(yōu)解（詳見表二）。關鍵詞：整數(shù)線性規(guī)劃 LINGO局限性 Fortran 一、 問題重述 有七種規(guī)格的包裝箱要裝到兩輛鐵路平板車上去。包裝箱的寬和高是一樣的，但厚度（t，以厘米計）及重量（w，以公斤計）是不同的。下表給出了每種包裝箱的厚度、重量以及數(shù)量。每輛平板車有1020cm的地方可用來裝包裝箱（像面包片那樣），載重為40噸。由于當?shù)刎涍\的限制，對

4、C5,C6,C7類的包裝箱的總數(shù)有一個特別的限制：這類箱子所占的空間（厚度）不能超過302.7cm（分兩輛車和一輛車兩種情況討論）。試把包裝箱裝到平板車上去使得浪費的空間最小。 C1 C2 C3 C4 C5 C6 C7t(cm) 48.7 52.0 61.3 72.0 48.7 52.0 64.0w(kg) 2000 3000 1000 500 4000 2000 1000件數(shù) 8 7 9 6 6 4 8二、 問題分析通過理解題目，本例屬于整數(shù)型線性規(guī)劃問題，由題目中給出的條件,我們可以算出貨物的總重量為89噸，而兩輛車的載重量為80噸，所以必然不能將貨物全部裝載完，也就是說必然會有貨物剩余。

5、我們假設平板車上恰好只能放一排包裝箱，且包裝箱之間間隙忽略不計。對于題目中限制條件C5,C6,C7類包裝箱的總厚度不超過302.7cm，存在以下兩種理解：（1）一種是對于每輛車而言，車上C5,C6,C7類包裝箱的總空間不超過302.7cm，（2）另一種是對于兩輛車而言，C5,C6,C7類包裝箱的總空間不超過302.7cm。由此，我們分別對這兩種情況建立模型，并利用LINGO解出該整數(shù)型線性規(guī)劃的最優(yōu)解?？紤]到變量較多以及變量權值的特殊性（如C2、C6 的長度相等，均為52.0cm），我們猜想對每種情況都可能存在多組最優(yōu)解。我們利用lingo軟件解出一組最優(yōu)解作為參考，再根據(jù)Fortran編譯程

6、序，討論得出所有最優(yōu)解。三、 模型假設一、 每輛平板車上恰好只能裝載一排的包裝箱，不存在并排或者疊加等情況二、 包裝箱之間的間隙可忽略不計三、 兩輛平板車完全相同，不考慮兩車先后次序問題四、 不考慮一輛車上同一種包裝箱組合方案的不同排列五、 在重量符合要求的情況下，不考慮兩車重量差別大小對最優(yōu)解的影響四、 符號系統(tǒng)f浪費的空間Cij第i種包裝箱裝在第j輛平板車上數(shù)目ti第i種包裝箱的厚度Wi第i種包裝箱的質(zhì)量ni第i種包裝箱的數(shù)目五、 模型建立與求解對于題目中所說的對C5,C6,C7類包裝箱的總數(shù)的特別限制，存在以下兩種理解：（1）一種是對于每輛車而言，車上C5,C6,C7類包裝箱的總空間不超

7、過302.7cm，（2）另一種是對于兩輛車而言，C5,C6,C7類包裝箱的總空間不超過302.7cm。對此我們分別建立了以下兩種模型：1、兩輛鐵路平板車裝運包裝箱的整數(shù)規(guī)劃模型一2、兩輛鐵路平板車裝運包裝箱的整數(shù)規(guī)劃模型二5.1模型一的建立與求解5.1.1模型一的建立假設裝箱時每輛平板車上只能裝載一排的包裝箱，不存在并排或者疊加等情況，同時有包裝箱之間的間隙可忽略不計。此時，設第i種包裝箱裝在第j輛平板車上數(shù)目Cij,則包裝箱在兩輛車上所占據(jù)的長度： 即為兩輛平板。車的總長為2040cm，所以浪費的空間。由于兩輛平板車均有各自的長度限制，所以在兩輛平板車上的包裝箱總厚度不應超過兩輛平板車各自的

8、長度限制。問題中給出兩輛車的容許長度均為1020cm,據(jù)此建立第一個約束條件。 由于當?shù)刎涍\的限制，對C5,C6,C7類的包裝箱的總數(shù)有一個特別的限制：這類箱子所占的空間（厚度）不能超過302.7cm。據(jù)此建立第二個約束條件。由于兩輛平板車均為超出容許的載重，在平板車上的載重為，兩輛平板車的載重均為40000Kg。據(jù)此建立第三個約束條件。若包裝箱全部裝車，則所需空間為2749.5cm。而兩輛平板車的總長僅2040cm,可以發(fā)現(xiàn)包裝箱不可以完全裝到平板車上。因此不應將所有包裝箱都裝到平板車上。所以七種包裝箱的數(shù)目在提供的包裝箱件數(shù)ni的容許的范圍內(nèi)，并且包裝箱在每輛平板車上的數(shù)目不為負值，所以可

9、以建立第四個約束條件。根據(jù)以上分析可建立以下整數(shù)線性規(guī)劃數(shù)學模型：5.1.2模型一的求解根據(jù)兩輛鐵路平板車裝運包裝箱的整數(shù)規(guī)劃模型一，我們用LINGO求得最優(yōu)解為兩輛車裝運C1,C2,C7類包裝箱的數(shù)量分別為（6，2，6，0，0，0，4；1，5，2，5，1，1，2），剩余厚度為0cm?？紤]到LINGO求解整數(shù)規(guī)劃只能求出一組最優(yōu)解的局限性，我們進而用Fortran編程求出了所有符合條件的12組最優(yōu)解。因為不考慮兩車先后次序，我們又用對結果去重，最終得到6組最優(yōu)解（詳見下表）。表一：序號1252501262600042152511262600043052521262600044242502262

10、600045142512262600046232503262600045.2模型二的建立與求解5.2.1模型二的建立分析可知模型二與模型一的差別，在于模型一中的第二約束條件。模型二中，兩輛平板車上C5,C6,C7類箱子所占總空間的（厚度）不能超過302.7cm。所以約束條件。 可以建立如下整數(shù)線性規(guī)劃模型：5.2.2模型二的求解根據(jù)鐵路平板車裝運包裝箱的整數(shù)規(guī)劃模型二，用LINGO求得最優(yōu)解為兩輛車裝運C1,C2,C7類包裝箱的數(shù)量分別為（3，2，9，1，3，0，0；5，5，0，5，0，3，0），剩余厚度為0.6cm。同樣由于LINGO軟件的局限性，我們又用Fortran編程求得所有符合條件的

11、54組最優(yōu)解，經(jīng)過去重后最終得到27組最優(yōu)解（詳見下表）。表二：序號16291000250533024743000405333037353000144333045291100350523053743100505323066353100244323074291200450513082743200605313095353200344313010329130055050301143533004443030128106300069003013464301041533201472530101543320155705010309132016519111036052201736431105153220186

12、2531102543220194705110409122020419121046051202126432106153120225253210354312023370521050911202431913105605020251643310715302026425331045430202780063100790020六、 模型分析 本文針對兩輛鐵路平板車裝運包裝箱的問題（視兩輛平板車相同，不考慮方案不同僅僅是AB車車次相互交換的情況）裝貨建立整數(shù)規(guī)劃模型，通過LINGO實現(xiàn)了平板車浪費空間最小的目標，得出了不同種類包裝箱裝運件數(shù)的最優(yōu)解。然而，用LINGO求得最優(yōu)解（僅為多組解中一組），我們采用高

13、級語言：Fortran編譯程序，從而得出其他解系（詳見附件）。七、 模型推廣鐵路平板車裝運包裝箱的整數(shù)規(guī)劃模型在多重約束的線性排列組合問題上具有一定通用性。八、 結論對于第一種理解即每輛車C5、C6、C7這類箱子所占的空間不超過302.7cm的情況，我們建立了模型一，得到6組最優(yōu)解，兩輛車浪費的總空間（厚度）最少為0cm。對于第二種理解即兩輛車C5、C6、C7這類箱子所占的總空間不超過302.7cm的情況，我們建立了模型二、模型三、模型四，最終得到27組最優(yōu)解，兩輛車浪費的總空間（厚度）最少為0.6cm。九、 參考文獻1 馬瑞民，F(xiàn)ORTRAN90程序設計，哈爾濱工程大學出版社，2005。附錄

14、1：程序說明1、pbc1.lg4 平板車裝貨問題規(guī)劃模型1 Lingo求解的輸出數(shù)據(jù)2、pbc1.lgr 平板車裝貨問題規(guī)劃模型1 Lingo求解源程序3、pbc2.lg4 平板車裝貨問題規(guī)劃模型1 Lingo求解源程序4、pbc2.lgr 平板車裝貨問題規(guī)劃模型1 Lingo求解的輸出數(shù)據(jù)5、pbcgh1.dat 平板車裝貨問題規(guī)劃模型1 Fortran90求解的輸出數(shù)據(jù)6、pbcgh1.f90 平板車裝貨問題規(guī)劃模型1 Fortran90求解的源程序7、pbcgh2.dat 平板車裝貨問題規(guī)劃模型2 Fortran90求解的輸出數(shù)據(jù)8、pbcgh2.f90 平板車裝貨問題規(guī)劃模型2 For

15、tran90求解的源程序附錄2：!平板車裝貨問題規(guī)劃模型1program pbcgh1 implicit noneinteger,dimension(14):c !C為第一輛、第二輛平板車裝各類包裝箱數(shù)量的組合；integer :i1,i2,i3,i4,i5,i6,i7,j1,j2,j3,j4,j5,j6,j7,wi,wj，n!i1,i2,.,i7為分別為第一輛車裝C1，C2,.,C7類包裝箱的數(shù)量;!i1,i2,.,i7為分別為第一輛車裝C1，C2,.,C7類包裝箱的數(shù)量; !wi,wj分別為第一輛車、第二輛車上包裝箱總重量; ! n為最優(yōu)解的個數(shù); real:t1,t2,ti,tj,s!t

16、1,t2分別為第一輛車、第二輛車上C5,C6,C7類的包裝箱的總厚度；!ti,tj分別為第一輛車、第二輛車上所有包裝箱的總厚度；!s為平板車上剩余厚度（空間剩余量）；open(1,file='pbcgh1.dat',status='old')!文件pbcgh1為平板車裝貨問題模型1的數(shù)據(jù)文件 s=2040 !平板車剩余厚度!為優(yōu)化算法從C7,C6,.,C1的順序窮舉do i7=0,8 do i6=0,4do i5=0,6t1=48.7*i5+52.0*i6+64.0*i7if(t1<=302.7)then !第一輛車C5,C6,C7類的包裝箱的總厚度不超過

17、302.7cm;do i4=0,6do i3=0,9do i2=0,7do i1=0,8ti=48.7*i1+52.0*i2+61.3*i3+72.0*i4+48.7*i5+52.0*i6+64.0*i7if(ti<=1020)then !第一輛車上所有包裝箱的總厚度不超過車長1020cm；wi=2000*i1+3000*i2+1000*i3+500 *i4+4000*i5+2000*i6+1000*i7if(wi<=40000)then !第一輛車上包裝箱總重量不超過40000Kg; do j7=0,8-i7do j6=0,4-i6do j5=0,6-i5t2=48.7*j5+5

18、2.0*j6+64.0*j7if(t2<=302.7)then !第二輛車C5,C6,C7類的包裝箱的總厚度不超過302.7cm;do j4=0,6-i4do j3=0,9-i3do j2=0,7-i2do j1=0,8-i1tj=48.7*j1+52.0*j2+61.3*j3+72.0*j4+48.7*j5+52.0*j6+64.0*j7if(tj<=1020)then !第二輛車上所有包裝箱的總厚度不超過車長1020cm；wj=2000*j1+3000*j2+1000*j3+500 *j4+4000*j5+2000*j6+1000*j7if(wj<=40000)then

19、!第二輛車上包裝箱總重量不超過40000Kg;!如果該組合下平板車剩余厚度小于s，最優(yōu)解的個數(shù)記為1，并將該組合下平板車剩余厚度記s；!將該最優(yōu)解組合存放在數(shù)組c中，并將文件定位到文件初始點在第一行按順序記錄下n,c,wi,wj,ti,tj,t1,t2,s的值if(2040-ti-tj)<s)then n=1s=2040-ti-tjc=(/i1,i2,i3,i4,i5,i6,i7,j1,j2,j3,j4,j5,j6,j7/)rewind(1)write(1,'(1X,17I6,5F7.1)')n,c,wi,wj,ti,tj,t1,t2,s!如果該組合下平板車剩余厚度等于s

20、，最優(yōu)解的個數(shù)n加1；!將該最優(yōu)解組合存放在數(shù)組c中，并將文件定位到文件初始點在第n行按順序記錄下n,c,wi,wj,ti,tj,t1,t2,s的值else if(2040-ti-tj)=s)thenn=n+1c=(/i1,i2,i3,i4,i5,i6,i7,j1,j2,j3,j4,j5,j6,j7/) write(1,'(1X,17I6,5F7.1)')n,c,wi,wj,ti,tj,t1,t2,send ifend if end if end doend doend do end doend if end doend doend do end if end if end d

21、oend doend do end doend if end doend doend do close(1)end program pbcgh1附錄3：平板車裝貨問題規(guī)劃模型2求解的Fortran程序!平板車裝貨問題規(guī)劃模型2program pbcgh2implicit noneinteger,dimension(14):c !C為第一輛、第二輛平板車裝各類包裝箱數(shù)量的組合；integer :wi,wj,i1,i2,i3,i4,i5,i6,i7,j1,j2,j3,j4,j5,j6,j7,n!i1,i2,.,i7為分別為第一輛車裝C1，C2,.,C7類包裝箱的數(shù)量;!i1,i2,.,i7為分別為

22、第一輛車裝C1，C2,.,C7類包裝箱的數(shù)量; !wi,wj分別為第一輛車、第二輛車上包裝箱總重量; ! n為最優(yōu)解的個數(shù); real:ti,tj,t1,t2,t12,s!t1,t2分別為第一輛車、第二輛車上C5,C6,C7類的包裝箱的總厚度；!ti,tj分別為第一輛車、第二輛車上所有包裝箱的總厚度；!s為平板車上剩余厚度（空間剩余量）；open(1,file='pbcgh2.dat',status='old') !文件pbcgh2為平板車裝貨問題模型1的數(shù)據(jù)文件s=2040 !平板車剩余厚度!為優(yōu)化算法從C7,C6,.,C1的順序窮舉 do i7=0,8do

23、i6=0,4do i5=0,6t1=48.7*i5+52.0*i6+64.0*i7 !第一輛車C5,C6,C7類的包裝箱的總厚度不超過302.7cm;do i4=0,6do i3=0,9do i2=0,7do i1=0,8ti=48.7*i1+52.0*i2+61.3*i3+72.0*i4+48.7*i5+52.0*i6+64.0*i7if(ti<=1020)then !第一輛車上所有包裝箱的總厚度不超過車長1020cm；wi=2000*i1+3000*i2+1000*i3+500 *i4+4000*i5+2000*i6+1000*i7if(wi<=40000)then !第一輛車

24、上包裝箱總重量不超過40000Kg; do j7=0,8-i7do j6=0,4-i6do j5=0,6-i5t2=48.7*j5+52.0*j6+64.0*j7t12=t1+t2if(t12<=320.7)then !兩輛車上C5,C6,C7類的包裝箱的總厚度不超過302.7cm;do j4=0,6-i4do j3=0,9-i3do j2=0,7-i2do j1=0,8-i1tj=48.7*j1+52.0*j2+61.3*j3+72.0*j4+48.7*j5+52.0*j6+64.0*j7if(tj<=1020)then !第二輛車上所有包裝箱的總厚度不超過車長1020cm；wj

25、=2000*j1+3000*j2+1000*j3+500 *j4+4000*j5+2000*j6+1000*j7if(wj<=40000)then !第二輛車上包裝箱總重量不超過40000Kg;!如果該組合下平板車剩余厚度小于s，最優(yōu)解的個數(shù)記為1，并將該組合下平板車剩余厚度記s；!將該最優(yōu)解組合存放在數(shù)組c中，并將文件定位到文件初始點在第一行按順序記錄下n,c,wi,wj,ti,tj,t1,t2,t12,s的值if(2040-ti-tj)<s)thenn=1s=2040-ti-tjc=(/i1,i2,i3,i4,i5,i6,i7,j1,j2,j3,j4,j5,j6,j7/)rew

26、ind(1)write(1,'(1X,17I6,6F7.1)')n,c,wi,wj,ti,tj,t1,t2,t12,s!如果該組合下平板車剩余厚度等于s，最優(yōu)解的個數(shù)n加1；!將該最優(yōu)解組合存放在數(shù)組c中，并將文件定位到文件初始點在第n行按順序記錄下n,c,wi,wj,ti,tj,t1,t2,t12,s的值else if(2040-ti-tj)=s)thenn=n+1c=(/i1,i2,i3,i4,i5,i6,i7,j1,j2,j3,j4,j5,j6,j7/)write(1,'(1X,17I6,6F7.1)')n,c,wi,wj,ti,tj,t1,t2,t12,

27、send if endifend if end doend doend do end doend if end doend doend do end if end if end doend doend do end do end doend doend do close(1)end program pbcgh2附錄3：平板車裝貨問題規(guī)劃模型1 Lingo求解的輸出數(shù)據(jù):Global optimal solution found. Objective value: -0.1705303E-12 Objective bound: 0.000000 Infeasibilities: 0.115463

28、2E-12 Extended solver steps: 231161 Total solver iterations: 380690 Model Title: 兩輛鐵路平板車的裝貨問題 Variable Value Reduced Cost A1 6.000000 -48.70000 A2 2.000000 -52.00000 A3 6.000000 -61.30000 A4 0.000000 -72.00000 A5 0.000000 -48.70000 A6 0.000000 -52.00000 A7 4.000000 -64.00000 B1 1.000000 -48.70000 B2

29、 5.000000 -52.00000 B3 2.000000 -61.30000 B4 5.000000 -72.00000 B5 1.000000 -48.70000 B6 1.000000 -52.00000 B7 2.000000 -64.00000 Row Slack or Surplus Dual Price 1 0.000000 -1.000000 2 0.000000 0.000000 3 0.000000 0.000000 4 12.00000 0.000000 5 10.50000 0.000000 6 46.70000 0.000000 7 74.00000 0.000000 8 1.000000 0.000000 9 0.000000 0.0000