两辆铁路平板车的装货问题的讨论

1、两辆铁路平板车装货问题的讨论摘要本文针对两辆铁路平板车装运包装箱的问题，建立了铁路平板车装运包装箱的整数规划模型，通过LINGO软件方便快捷地求出了平板车不同种类包装箱装运件数一组最优解，同时使用Fortran编程求出所有符合条件的最优解。本文鉴于题目中"当地货运的限制，对C5,C6,C7类的包装箱的总数的特别的限制：这类箱子所占的空间（厚度）不能超过302.7cm"的存在的歧义，对该问题分两种情况进行讨论，分别建立模型，得出了不同情况下满足题设的最优方案。第一种情况认为货运的限制针对于每辆平板车，即每辆车上C5,C6,C7类的包装箱的总厚度不超过302.7cm。针对该情况

2、，我们建立了两辆铁路平板车装运包装箱的整数规划模型一，并用LINGO求得最优解为两辆车装运C1,C2,C7类包装箱的数量分别为（6，2，6，0，0，0，4；1，5，2，5，1，1，2），剩余厚度为0cm。考虑到LINGO求解整数规划只能求出一组最优解的局限性，我们进而用Fortran编程求出了所有符合条件的12组最优解。因为不考虑两车先后次序，我们又用对结果去重，最终得到6组最优解（详见表一）。另一种则认为货运的限制针对于一次货运，在本题中则为两辆车上C5,C6,C7类的包装箱的总厚度不超过302.7cm。针对该情况，我们同样也建立了铁路平板车装运包装箱的整数规划模型二，并用LINGO求得最优

3、解为两辆车装运C1,C2,C7类包装箱的数量分别为（3，2，9，1，3，0，0；5，5，0，5，0，3，0），剩余厚度为0.6cm。同样由于LINGO软件的局限性，我们又用Fortran编程求得所有符合条件的54组最优解，经过去重后最终得到27组最优解（详见表二）。关键词：整数线性规划 LINGO局限性 Fortran 一、 问题重述 有七种规格的包装箱要装到两辆铁路平板车上去。包装箱的宽和高是一样的，但厚度（t，以厘米计）及重量（w，以公斤计）是不同的。下表给出了每种包装箱的厚度、重量以及数量。每辆平板车有1020cm的地方可用来装包装箱（像面包片那样），载重为40吨。由于当地货运的限制，对

4、C5,C6,C7类的包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过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件数 8 7 9 6 6 4 8二、 问题分析通过理解题目，本例属于整数型线性规划问题，由题目中给出的条件,我们可以算出货物的总重量为89吨，而两辆车的载重量为80吨，所以必然不能将货物全部装载完，也就是说必然会有货物剩余。

5、我们假设平板车上恰好只能放一排包装箱，且包装箱之间间隙忽略不计。对于题目中限制条件C5,C6,C7类包装箱的总厚度不超过302.7cm，存在以下两种理解：（1）一种是对于每辆车而言，车上C5,C6,C7类包装箱的总空间不超过302.7cm，（2）另一种是对于两辆车而言，C5,C6,C7类包装箱的总空间不超过302.7cm。由此，我们分别对这两种情况建立模型，并利用LINGO解出该整数型线性规划的最优解。考虑到变量较多以及变量权值的特殊性（如C2、C6 的长度相等，均为52.0cm），我们猜想对每种情况都可能存在多组最优解。我们利用lingo软件解出一组最优解作为参考，再根据Fortran编译程

6、序，讨论得出所有最优解。三、 模型假设一、 每辆平板车上恰好只能装载一排的包装箱，不存在并排或者叠加等情况二、 包装箱之间的间隙可忽略不计三、 两辆平板车完全相同，不考虑两车先后次序问题四、 不考虑一辆车上同一种包装箱组合方案的不同排列五、 在重量符合要求的情况下，不考虑两车重量差别大小对最优解的影响四、 符号系统f浪费的空间Cij第i种包装箱装在第j辆平板车上数目ti第i种包装箱的厚度Wi第i种包装箱的质量ni第i种包装箱的数目五、 模型建立与求解对于题目中所说的对C5,C6,C7类包装箱的总数的特别限制，存在以下两种理解：（1）一种是对于每辆车而言，车上C5,C6,C7类包装箱的总空间不超

7、过302.7cm，（2）另一种是对于两辆车而言，C5,C6,C7类包装箱的总空间不超过302.7cm。对此我们分别建立了以下两种模型：1、两辆铁路平板车装运包装箱的整数规划模型一2、两辆铁路平板车装运包装箱的整数规划模型二5.1模型一的建立与求解5.1.1模型一的建立假设装箱时每辆平板车上只能装载一排的包装箱，不存在并排或者叠加等情况，同时有包装箱之间的间隙可忽略不计。此时，设第i种包装箱装在第j辆平板车上数目Cij,则包装箱在两辆车上所占据的长度： 即为两辆平板。车的总长为2040cm，所以浪费的空间。由于两辆平板车均有各自的长度限制，所以在两辆平板车上的包装箱总厚度不应超过两辆平板车各自的

8、长度限制。问题中给出两辆车的容许长度均为1020cm,据此建立第一个约束条件。 由于当地货运的限制，对C5,C6,C7类的包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过302.7cm。据此建立第二个约束条件。由于两辆平板车均为超出容许的载重，在平板车上的载重为，两辆平板车的载重均为40000Kg。据此建立第三个约束条件。若包装箱全部装车，则所需空间为2749.5cm。而两辆平板车的总长仅2040cm,可以发现包装箱不可以完全装到平板车上。因此不应将所有包装箱都装到平板车上。所以七种包装箱的数目在提供的包装箱件数ni的容许的范围内，并且包装箱在每辆平板车上的数目不为负值，所以可

9、以建立第四个约束条件。根据以上分析可建立以下整数线性规划数学模型：5.1.2模型一的求解根据两辆铁路平板车装运包装箱的整数规划模型一，我们用LINGO求得最优解为两辆车装运C1,C2,C7类包装箱的数量分别为（6，2，6，0，0，0，4；1，5，2，5，1，1，2），剩余厚度为0cm。考虑到LINGO求解整数规划只能求出一组最优解的局限性，我们进而用Fortran编程求出了所有符合条件的12组最优解。因为不考虑两车先后次序，我们又用对结果去重，最终得到6组最优解（详见下表）。表一：序号1252501262600042152511262600043052521262600044242502262

10、600045142512262600046232503262600045.2模型二的建立与求解5.2.1模型二的建立分析可知模型二与模型一的差别，在于模型一中的第二约束条件。模型二中，两辆平板车上C5,C6,C7类箱子所占总空间的（厚度）不能超过302.7cm。所以约束条件。 可以建立如下整数线性规划模型：5.2.2模型二的求解根据铁路平板车装运包装箱的整数规划模型二，用LINGO求得最优解为两辆车装运C1,C2,C7类包装箱的数量分别为（3，2，9，1，3，0，0；5，5，0，5，0，3，0），剩余厚度为0.6cm。同样由于LINGO软件的局限性，我们又用Fortran编程求得所有符合条件的

11、54组最优解，经过去重后最终得到27组最优解（详见下表）。表二：序号16291000250533024743000405333037353000144333045291100350523053743100505323066353100244323074291200450513082743200605313095353200344313010329130055050301143533004443030128106300069003013464301041533201472530101543320155705010309132016519111036052201736431105153220186

12、2531102543220194705110409122020419121046051202126432106153120225253210354312023370521050911202431913105605020251643310715302026425331045430202780063100790020六、 模型分析 本文针对两辆铁路平板车装运包装箱的问题（视两辆平板车相同，不考虑方案不同仅仅是AB车车次相互交换的情况）装货建立整数规划模型，通过LINGO实现了平板车浪费空间最小的目标，得出了不同种类包装箱装运件数的最优解。然而，用LINGO求得最优解（仅为多组解中一组），我们采用高

13、级语言：Fortran编译程序，从而得出其他解系（详见附件）。七、 模型推广铁路平板车装运包装箱的整数规划模型在多重约束的线性排列组合问题上具有一定通用性。八、 结论对于第一种理解即每辆车C5、C6、C7这类箱子所占的空间不超过302.7cm的情况，我们建立了模型一，得到6组最优解，两辆车浪费的总空间（厚度）最少为0cm。对于第二种理解即两辆车C5、C6、C7这类箱子所占的总空间不超过302.7cm的情况，我们建立了模型二、模型三、模型四，最终得到27组最优解，两辆车浪费的总空间（厚度）最少为0.6cm。九、 参考文献1 马瑞民，FORTRAN90程序设计，哈尔滨工程大学出版社，2005。附录

14、1：程序说明1、pbc1.lg4 平板车装货问题规划模型1 Lingo求解的输出数据2、pbc1.lgr 平板车装货问题规划模型1 Lingo求解源程序3、pbc2.lg4 平板车装货问题规划模型1 Lingo求解源程序4、pbc2.lgr 平板车装货问题规划模型1 Lingo求解的输出数据5、pbcgh1.dat 平板车装货问题规划模型1 Fortran90求解的输出数据6、pbcgh1.f90 平板车装货问题规划模型1 Fortran90求解的源程序7、pbcgh2.dat 平板车装货问题规划模型2 Fortran90求解的输出数据8、pbcgh2.f90 平板车装货问题规划模型2 For

15、tran90求解的源程序附录2：!平板车装货问题规划模型1program pbcgh1 implicit noneinteger,dimension(14):c !C为第一辆、第二辆平板车装各类包装箱数量的组合；integer :i1,i2,i3,i4,i5,i6,i7,j1,j2,j3,j4,j5,j6,j7,wi,wj，n!i1,i2,.,i7为分别为第一辆车装C1，C2,.,C7类包装箱的数量;!i1,i2,.,i7为分别为第一辆车装C1，C2,.,C7类包装箱的数量; !wi,wj分别为第一辆车、第二辆车上包装箱总重量; ! n为最优解的个数; 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的数据文件 s=2040 !平板车剩余厚度!为优化算法从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，最优解的个数记为1，并将该组合下平板车剩余厚度记s；!将该最优解组合存放在数组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、，最优解的个数n加1；!将该最优解组合存放在数组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：平板车装货问题规划模型2求解的Fortran程序!平板车装货问题规划模型2program pbcgh2implicit noneinteger,dimension(14):c !C为第一辆、第二辆平板车装各类包装箱数量的组合；integer :wi,wj,i1,i2,i3,i4,i5,i6,i7,j1,j2,j3,j4,j5,j6,j7,n!i1,i2,.,i7为分别为第一辆车装C1，C2,.,C7类包装箱的数量;!i1,i2,.,i7为分别为

22、第一辆车装C1，C2,.,C7类包装箱的数量; !wi,wj分别为第一辆车、第二辆车上包装箱总重量; ! n为最优解的个数; real:ti,tj,t1,t2,t12,s!t1,t2分别为第一辆车、第二辆车上C5,C6,C7类的包装箱的总厚度；!ti,tj分别为第一辆车、第二辆车上所有包装箱的总厚度；!s为平板车上剩余厚度（空间剩余量）；open(1,file='pbcgh2.dat',status='old') !文件pbcgh2为平板车装货问题模型1的数据文件s=2040 !平板车剩余厚度!为优化算法从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，最优解的个数记为1，并将该组合下平板车剩余厚度记s；!将该最优解组合存放在数组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，最优解的个数n加1；!将该最优解组合存放在数组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：平板车装货问题规划模型1 Lingo求解的输出数据: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