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

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 组最优解（详见表一） 。另一种则认为货运的限制针对于一次货运，在本题中则为两辆车上C567,C ,C 类的包装箱的总厚度不超过302.7cm。针对该情况，我们同样也建立了铁路平

3、板车装运包装箱的整数规划模型二，并用LINGO求得最优解为两辆车装运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，以公斤计）是不同的。下表给出了每种包装箱的厚度、重量以及数量。每辆平板车有1

4、020cm 的地方可用来装包装箱（像面包片那样），载重为 40 吨。由于当地货运的限制，对C5,C6,C7 类的包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过302.7cm（分两辆车和一辆车两种情况讨论）。试把包装箱装到平板车上去使得浪费的空间最小。C1C2C3C4C5C6C7t(cm)48.752.061.372.048.752.064.0w(kg)200030001000500400020001000件数8796648二、 问题分析通过理解题目，本例属于整数型线性规划问题，由题目中给出的条件, 我们可以算出货物的总重量为89 吨，而两辆车的载重量为80 吨，所以必然不能将

5、货物全部装载完，也就是说必然会有货物剩余。我们假设平板车上恰好只能放一排包装箱，且包装箱之间间隙忽略不计。对于题目中限制条件C5,C6,C7类包装箱的总厚度不超过302.7cm，存在以下两种理解：（ 1）一种是对于每辆车而言，车上C5,C6,C7类包装箱的总空间不超过302.7cm ，（ 2）另一种是对于两辆车而言，C5,C6,C7类包装箱的总空间不超过 302.7cm。由此，我们分别对这两种情况建立模型，并利用LINGO 解出该整数型线性规划的最优解。考虑到变量较多以及变量权值的特殊性（如C2652.0cm），我们猜想、C 的长度相等，均为对每种情况都可能存在多组最优解。我们利用 lingo

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

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

8、的空间 f 2040C ij ti 。j 1i 1由于两辆平板车均有各自的长度限制， 所以在两辆平板车上的包装箱总厚度不应超过两辆平板车各自的长度限制。问 题 中 给 出 两 辆 车 的 容 许 长 度 均 为1020cm, 据 此 建 立 第 一 个 约 束 条 件71020Cij ti 0j1,2。i 1由于当地货运的限制，对C56 7类的包装箱的总数有一个特别的限制：这类箱子所占,C ,C7的空间（厚度）不能超过 302.7cm。据此建立第二个约束条件Cij ti 302.7j 1,2 。i5由于两辆平板车均为超出容许的载重，在平板车上的载重为，两辆平板车的载重均为40000Kg。7据此

9、建立第三个约束条件CijWi 40000j 1,2 。i 1若包装箱全部装车，则所需空间为2749.5cm。而两辆平板车的总长仅2040cm,可以发现包装箱不可以完全装到平板车上。因此不应将所有包装箱都装到平板车上。所以七种包装箱的数目在提供的包装箱件数ni 的容许的范围内，并且包装箱在每辆平板车上的数目不为负2值，所以可以建立第四个约束条件0Cijnii1,2,.,7 。j 1根据以上分析可建立以下整数线性规划数学模型：27minf2040Cij tij 1i 171020Cij ti0j1,2i 17Cijti302.7j1,2st. . i75Cij Wi40000j1,2i120Cij

10、nii1,2,.,7j15.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 组最优解（详见下表） 。表一：序C11C21C31C41C51C61C71C12C22C32C42C52C62C72号125250126260004

11、2152511262600043052521262600044242502262600045142512262600046232503262600045.2 模型二的建立与求解5.2.1模型二的建立分析可知模型二与模型一的差别，在于模型一中的第二约束条件。模型二中， 两辆平板车 上 C5,C 6,C 7类箱子所占总空间的（厚度）不能超过302.7cm 。 所 以 约 束 条 件27j 1i 5Cij ti 302.7 。可以建立如下整数线性规划模型：27minf2040Cij tij 1i171020Cij ti0j1,2i 127j1 i 5Cij ti 302.7st.7CijWi4000

12、0j1,2i120Cijnii1,2,.,7j15.2.2 模型二的求解根据铁路平板车装运包装箱的整数规划模型二，用LINGO 求得最优解为两辆车装运C1,C2, ,C7 类包装箱的数量分别为（3， 2， 9， 1， 3， 0，0； 5， 5， 0，5， 0， 3， 0），剩余厚度为0.6cm。同样由于 LINGO 软件的局限性，我们又用Fortran 编程求得所有符合条件的54 组最优解，经过去重后最终得到27 组最优解（详见下表） 。表二：序C11C21C31C41C51C61C71C12C22C32C42C52C62C72号16291000250533024743000405333037

13、353000144333045291100350523053743100505323066353100244323074291200450513082743200605313095353200344313010329130055050301143533004443030128106300069003013464301041533201472530101543320155705010309132016519111036052201736431105153220186253110254322019470511040912202041912104605120212643210615312022525

14、3210354312023370521050911202431913105605020251643310715302026425331045430202780063100790020六、 模型分析本文针对两辆铁路平板车装运包装箱的问题（视两辆平板车相同，不考虑方案不同仅仅是 AB车车次相互交换的情况）装货建立整数规划模型，通过 LINGO实现了平板车浪费空间最小的目标，得出了不同种类包装箱装运件数的最优解。然而，用 LINGO 求得最优解（仅为多组解中一组） ，我们采用高级语言： Fortran 编译程序，从而得出其他解系（详见附件） 。七、模型推广铁路平板车装运包装箱的整数规划模型在多重约束

15、的线性排列组合问题上具有一定通用性。八、 结论对于第一种理解即每辆车C5、C6、C7 这类箱子所占的空间不超过302.7cm 的情况，我们建立了模型一，得到6 组最优解，两辆车浪费的总空间（厚度）最少为0cm。对于第二种理解即两辆车C5、C6、 C7 这类箱子所占的总空间不超过302.7cm 的情况，我们建立了模型二、模型三、模型四，最终得到27 组最优解，两辆车浪费的总空间（厚度）最少为 0.6cm。九、 参考文献1马瑞民， FORTRAN90程序设计，哈尔滨工程大学出版社，2005。附录 1：程序说明1、 pbc1.lg4平板车装货问题规划模型1Lingo求解的输出数据2、 pbc1.lg

16、r平板车装货问题规划模型1Lingo求解源程序3、 pbc2.lg4平板车装货问题规划模型1Lingo求解源程序4、 pbc2.lgr平板车装货问题规划模型1Lingo求解的输出数据5、 pbcgh1.dat平板车装货问题规划模型1Fortran90求解的输出数据6、 pbcgh1.f90平板车装货问题规划模型1Fortran90求解的源程序7、 pbcgh2.dat平板车装货问题规划模型2Fortran90求解的输出数据8、 pbcgh2.f90平板车装货问题规划模型2Fortran90求解的源程序附录 2：! 平板车装货问题规划模型1program pbcgh1implicit nonei

17、nteger,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!t1,t2!ti,tj分别为第一辆车、第二辆车上C5,C6,C7 类的包装箱的总厚度；分别为第一辆车、第二辆

18、车上所有包装箱的总厚度；!s为平板车上剩余厚度（空间剩余量）；open(1,file=pbcgh1.dat,status=old)!文件pbcgh1 为平板车装货问题模型1 的数据文件s=2040!平板车剩余厚度! 为优化算法从C7,C6,.,C1的顺序穷举do i7=0,8do i6=0,4do i5=0,6t1=48.7*i5+52.0*i6+64.0*i7if(t1=302.7)then !第一辆车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

19、*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+52.0*j6+64.0*j7if(t2=302.7)then !第二辆车C5,C6,C7 类的包装箱的总厚度不超过302.7cm;do j4=0,6-i4do j3=0

20、,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 !第二辆车上包装箱总重量不超过40000Kg;! 如果该组合下平板车剩余厚度小于s，最优解的个数记为 1，并将该组合下平板车剩余厚度记 s；! 将该最优解组合存放在数组c 中，并将文件定位到

21、文件初始点在第一行按顺序记录下n,c,wi,wj,ti,tj,t1,t2,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/)rewind(1)write(1,(1X,17I6,5F7.1)n,c,wi,wj,ti,tj,t1,t2,s! 如果该组合下平板车剩余厚度等于s，最优解的个数n 加 1；! 将该最优解组合存放在数组c 中，并将文件定位到文件初始点在第n,c,wi,wj,ti,tj,t1,t2,s的值else if(2040-ti-tj)=s)thenn=n+1n 行按

22、顺序记录下c=(/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 ifend ifend doend doend doend doend ifend doend doend doend ifend ifend doend doend doend doend ifend doend doend doclose(1)end program pbcgh1附录 3：平板车装货问题规划模型2 求解的Fortran程序! 平板车装货问题规划模型2progra

23、m 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为分别为第一辆车装C1， C2,.,C7类包装箱的数量 ;!wi,wj 分别为第一辆车、第二辆车上包装箱总重量;! n 为最优解的个数 ; real:ti,tj,t1,t2,t12,s!t1,t2 分别为第一辆车、第二辆车上C5,C6,C7

24、类的包装箱的总厚度；!ti,tj分别为第一辆车、第二辆车上所有包装箱的总厚度；!s 为平板车上剩余厚度（空间剩余量）；open(1,file=pbcgh2.dat,status=old) !文件 pbcgh2 为平板车装货问题模型1 的数据文件s=2040 !平板车剩余厚度! 为优化算法从C7,C6,.,C1do i7=0,8do i6=0,4do i5=0,6t1=48.7*i5+52.0*i6+64.0*i7 !do i4=0,6的顺序穷举第一辆车C5,C6,C7类的包装箱的总厚度不超过302.7cm;do i3=0,9do i2=0,7do i1=0,8ti=48.7*i1+52.0*i

25、2+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+52.0*j6+64.0*j7t12=t1+t2if(t12=320.7)then!两辆车上C5,C6,C7 类的包装箱的总厚度不超过302.

26、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 !第二辆车上包装箱总重量不超过40000Kg;! 如果该组合下平板车剩余厚度小于 s，最优解的个数记为 1，并将该组合下平板车剩余厚度记 s；!

27、 将该最优解组合存放在数组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/)rewind(1)write(1,(1X,17I6,6F7.1)n,c,wi,wj,ti,tj,t1,t2,t12,s! 如果该组合下平板车剩余厚度等于s，最优解的个数n 加 1；! 将该最优解组合存放在数组c 中，并将文件定位到文件初始点在第n,c,wi,wj,ti,tj,t1,t2,t12,s的

28、值else if(2040-ti-tj)=s)thenn=n+1n 行按顺序记录下c=(/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,send ifendifend ifend doend doend doend doend ifend doend doend doend ifend ifend doend doend doend doend doend doend doclose(1)end program pbcgh2附录 3：平板车装货问题规划模型1

29、 Lingo求解的输出数据 :Global optimal solution found.Objective value:-0.1705303E-12Objective bound:0.000000Infeasibilities:0.1154632E-12Extended solver steps:231161Total solver iterations:380690Model Title:两辆铁路平板车的装货问题VariableValueReduced CostA16.000000-48.70000A22.000000-52.00000A36.000000-61.30000A40.000000-72.00000A50.000000-48.70000A60.000000-52.00000A74.000000-64.00000B11.000000-48.70000B25.000000-52.00000B32.000000-61.30000B45.000000-72.00000B51.000000-48.70000B61.000000-52.00000B72.000000-64.00000RowSlack or SurplusDual Price10.000000-1.0000002