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

1、两辆铁路平车装货问题的讨论摘要本文针对两辆铁路平板车装运包装箱的问题，建立了铁路平板车装运包装箱的整数规划 模型，通过LINGO软件方便快捷地求出了平板车不同种类包装箱装运件数一组最优解，同 时使用Fortran编程求出所有符合条件的最优解。本文鉴于题目中"当地货运的限制，对C5,G,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。针对该情况，我们同样也建立了铁路平板车装运包装

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,以公斤计）是不同的。下表给岀了每种包装箱的厚度、重量以 及数量。每辆平板车有1020cm的地

4、方可用来装包装箱（像而包片那样），载重为40吨。由 于当地货运的限制，对C5,C6,C7类的包装箱的总数有一个特别的限制：这类箱子所占的空 间（厚度）不能超过302.7cm （分两辆车和一辆车两种情况讨论）。试把包装箱装到平板车 上去使得浪费的空间最小。tcm)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解出该整数型线性规划的最优解。 考虑到变量较多以及变量权值的特殊性（如C2、C6的长度相等，均为52.0cm）,我们猜想 对每种情况都可能存在多组最优解。我们利用lingo软件解出一组最优解作为参考，再根据Fortran编译程

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

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

8、辆平板车各自的长度限制。问题中给出两辆车的容许长度均为1020cm,据此建立第一个约束条件1020-工C/no ) = 1,2。r-1由于当地货运的限制，对C5,C“C7类的包装箱的总数有一个特别的限制：这类箱子所占7的空间(厚度)不能超过302.7cma拯此建立第二个约束条件工C/ < 302.7) = 1,2。Z-5由于两俩平板车均为超出容许的载重，在平板车上的载重为，两辆平板车的载重均为 40000Kgu7据此建立第三个约束条件工C州S40000y = l,2or-l若包装箱全部装车，则所需空间为2749. 5cm。而两辆平板车的总长仅2040cm,可以发现 包装箱不可以完全装到平

9、板车上。因此不应将所有包装箱都装到平板车上。所以七种包装箱 的数目在提供的包装箱件数ni的容许的范围内，并且包装箱在每辆平板车上的数目不为负2 值，所以可以建立第四个约束条件i = l,2,7。根据以上分析可建立以下整数线性规划数学模型：根据两辆铁路平板车装运包装箱的整数规划模型一，我们用LINGO求得最优解为两俩 车装运C1,C2Q类包装箱的数量分别为(6, 2, 6, 0, 0, 0, 4； 1, 5, 2, 5, 1, 1> 2), 剩余厚度为0cm.考虑到LINGO求解整数规划只能求岀一组最优解的局限性，我们进而用 Fortran编程求出了所有符合条件的12组最优解。因为不考虑两

10、车先后次序，我们又用对结 果去重，最终得到6组最优解(详见下表九表一:序 号1252501262600042152511262600043052521262600044242502262600045142512262600046232503262600045. 2模型二的建立与求解5. 2.1模型二的建立分析可知模型二与模型一的差别，在于模型一中的第二约朿条件。模型二中，两辆平板车上C5, Cs, CT类箱子所占总空间的(厚度)不能超过302.7cm。所以约束条件27为C/S 302.7。;-1 r-5可以建立如下整数线性规划模型：5.2.2模型二的求解根据铁路平板车装运包装箱的整数规划模型二

11、，用LINGO求得最优解为两辆车装运C1Q.Q类包装箱的数量分别为(3, 2, 9, 1, 3, 0, 0： 5, 5, 0, 5, 0, 3, 0),剩余厚度0.6cmo同样由于LINGO软件的局限性，我们又用Fortran编程求得所有符合条件的 54组最优解，经过去重后最终得到27组最优解（详见下表）。表二:序 号162910002505330247430004053330373530001443330452911003505230537431005053230663531002443230742912004505130827432006053130953L5320034431301032

12、9130055050301143L533004443030128106300069003013464301041533201472530101543320155705010309132016519111036052201736431105153220186253110254322019470511040912202041912104605120212643210615312022525321035431202337052105091120243191310L5605020251643310715302026425331045430202780063100790020六、模型分析本文针对两辆铁路

13、平板车装运包装箱的问题（视两辆平板车相同，不考虑方案不同仅仅 是AB车车次相互交换的情况）装货建立整数规划模型，通过LING0实现了平板车浪费空间 最小的目标，得出了不同种类包装箱装运件数的最优解。然而，用LINGO求得最优解（仅为多组解中一组），我们采用高级语言：Fortran编译程 序，从而得岀其他解系（详见附件）。七、模型推广铁路平板车装运包装箱的整数规划模型在多重约束的线性排列组合问题上具有一泄通 用性。八、结论对于第一种理解即每辆车C5、C6、C7这类箱子所占的空间不超过302.7cm的情况，我 们建立了模型一，得到6组最优解，两辆车浪费的总空间（厚度）最少为Ocmo对于第二种理解即

14、两辆车C5、C6、C7这类箱子所占的总空间不超过302.7cm的情况， 我们建立了模型二、模型三、模型四，最终得到27组最优解，两辆车浪费的总空间（厚度） 最少为0.6cm九、参考文献1马瑞民，F0RTRAN90程序设计，哈尔滨工程大学岀版社，2005o程序说明1> pbcl. Ig42 pbcl 1护3、pbc2. Ig44、pbc2lgr5 pbcgh1. dat6、pbcghl. f907 pbcgh2dat8、pbcgh2. f90附录1：平板车装货问题规划模型1 Lingo求解的输岀数据 平板车装货问题规划模型1 Lingo求解源程序 平板车装货问题规划模型1 Lingo求解源

15、程序 平板车装货问题规划模型1 Lingo求解的输出数据平板车装货问题规划模型1 Fortwn90求解的输出数据平板车装货问题规划模型1 Fortwn90求解的源程序平板车装货问题规划模型2 Fortran90求解的输出数据平板车装货问题规划模型2 Fortran90求解的源程序附录2：!平板车装货问题规划模型1program pbcghlimplicit noneinteger, dimension（14）:c !C为第一辆、第二辆T板车装各类包装箱数量的组合； integer : il, i2, i3, i4, i5, i6, i7, jl, j2, j3, j4, j5, j6, j7,

16、wi, wj, n!il, i2, i7为分别为第一辆车装Cl, C2,., C7类包装箱的数量;!il, i2, i7为分别为第一辆车装Cl, C2,., C7类包装箱的数量;分别为第一辆车、第二辆车上包装箱总重量；! n为最优解的个数；real: :tl, t2, ti, tj, s!tl, t2分别为第一辆车、第二辆车上C5, C6, C7类的包装箱的总厚度：!ti, tj分别为第一辆车、第二辆车上所有包装箱的总厚度：!s为平板车上剩余厚度（空间剩余:open（l, file二'pbcghl. dat', status- old*）!文件pbcghl为平板车装货问题模型1

17、的数据文 件S二2040!平板车剩余厚度!为优化算法从C7, C6,., C1的顺序穷举do i7=0, 8do i6=0, 4do i5=0, 6tl=48. 7*i5+52. 0*i6+64. 0*i7if (tl<=302. 7) then !第一辆车C5, C6, C7类的包装箱的总厚度不超过302. 7cm;do i4=0, 6do i3=0,9do i2=0,7do il=0,8ti=48. 7*il+52. 0*i2+61. 3*i3+72. 0*i4+48. 7*i5+52. 0*i6+64. 0*i7辻(ti<=1020)then !第一辆车上所有包装箱的总厚度不

18、超过车长1020cm：wi=2000*il+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, 9-i3do j2=0, 7-i2do jl=0, 8-iltj=48. 7*

19、j1+52. 0*j2+61. 3幻3+72. 0*j4+48. 7*j5+52. 0巧6+64.0*j7辻(tj<=1020)then!第二辆车上所有包装箱的总厚度不超过车长1020cm；wj=2000*j1+3000*J2+1000*J3+500 *j4+4000*j5+2000*j6+1000*j7辻(wj<=40000)then !第二辆车上包装箱总重量不超过40000Kg;!如果该组合下平板车剩余厚度小于s,最优解的个数记为1,并将该组合下平板车剩余厚度 记S：!将该最优解组合存放在数组c中，并将文件左位到文件初始点在第一行按顺序记录下n, c, wi, wj, ti,

20、t j, tl, t2, s 的值if(2040-ti-tj)<s)thenn=ls二2040-ti-tjc=(/il, i2, i3, i4, i5, i6, i7, jl, j2, j3, j4, j5, j6, j7/)rewind(l)write (1,'(IX, 1716, 5F7 1)' )n, c, wi, wj, ti, t j, tl, t2, s!如果该组合下平板车剩余厚度等于s,最优解的个数n加1：!将该最优解组合存放在数组c中，并将文件左位到文件初始点在第n行按顺序记录下n, c, wi, wj, ti, t j, tl, t2, s 的值else

21、 if(2040-ti-tj)=s)thenn=n+lc=(/il, i2, i3, i4, i5,16, i7, jl, j2, j3, j4, j5, j6, j7/)write (1,'(IX, 1716, 5F7 1)' )n, c, wi, wj, ti, t j, tl, 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 progr

22、am pbcghl附录3：平板车装货问题规划模型2求解的Fortran程序!平板车装货问题规划模型2program pbcgh2implicit noneinteger, dimension(14):c !C为第一辆、第二辆T板车装各类包装箱数量的组合； integer :wi, wj, il, i2, i3, i4, i5, i6, i7, jl, j2, j3, j4, j5, j6, j7, n!il, i2, i7为分别为第一辆车装Cl, C2,., C7类包装箱的数量;!il, i2, i7为分别为第一辆车装Cl, C2,., C7类包装箱的数量;分别为第一辆车、第二辆车上包装箱总重

23、量；! n为最优解的个数；real: :ti, tj, tl, t2, tl2, s!tl, t2分别为第一辆车、第二辆车上C5, C6, C7类的包装箱的总厚度；Iti.tj分別为第一辆车、第二辆车上所有包装箱的总厚度：!s为平板车上剩余厚度(空间剩余呈：)：open(l, file- pbcgh2. dat', status- old') !文件pbcgh2为平板车装货问题模型1的数据 文件s=2040 !平板车剩余厚度!为优化算法从C7, C6,., C1的顺序穷举do i7=0, 8do i6=0,4do i5=0, 6tl二48. 7*15+52. 0*16+64.

24、0*i7 !第一辆车C5, C6, C7类的包装箱的总厚度不超过302. 7cm;do i4=0, 6do i3=0,9do i2=0, 7do il=0,8ti=48. 7*il+52. 0*i2+61. 3斌3+72. 0*i4+48. 7*i5+52. 0*i6+64. 0*i7辻(ti<=1020)then !第一辆车上所有包装箱的总厚度不超过车长1020cm；wi=2000*il+3000*i2+1000*i3+500 *i4+4000*i5+2000*i6+1000*i7 if(wi<=40000)then !第一辆车上包装箱总重量不超过-lOOOOKg;do j7=0

25、, 8-i7do j6=0,4-i6do j5=0, 6-i5t2=48. 7*j5+52. 0*j6+64. 0*j7tl2=tl+t2if(tl2<=320. 7) then !两辆车上C5, C6, C7类的包装箱的总厚度不超过302. 7cm;do j4=0, 6-i4do j3=0, 9-i3do j2=0, 7-i2do jl=0, 8-iltj=48. 7*j1+52. 0*j2+61. 3幻3+72. 0*j4+48. 7*j5+52. 0*j6+64.0*j7辻(tj<=1020)then!第二辆车上所有包装箱的总厚度不超过车长1020cm；wj=2000*j1+

26、3000*j2+1000*j3+500 *j4+4000*j5+2000*j6+1000*j7辻(wj<=40000)then !第二辆车上包装箱总重疑不超过40000Kg;!如果该组合下平板车剩余厚度小于s,最优解的个数记为1,并将该组合下平板车剩余厚度 ids；!将该最优解组合存放在数组c中，并将文件左位到文件初始点在第一行按顺序记录下n, c, wi, wj, ti, t j, tl, t2f tl2, s 的值if(2040-ti-tj)<s)thenn=ls二2040-ti-tjc二(/il, i2, i3, i4, i5, i6, i7, jl, j2, j3, j4,

27、 j5, j6, j7/)rewind (1)write (1,'(IX, 1716, 6F7. 1)' )n, c, wi, wj, ti, t j, tl, t2, tl2, s!如果该组合下平板车剩余厚度等于s,最优解的个数n加1：!将该最优解组合存放在数组c中，并将文件左位到文件初始点在第n行按顺序记录下n, c,wi, wj, ti, t j, tl, t2, tl2, s 的值else if(2040-ti-tj)=s)thenn=n+lc=(/il, i2,13, i4, i5, i6, i7, jl, j2, j3, j4, j5, j6, j7/)write

28、(1,'(IX, 1716, 6F7. 1)' )n, c, wi, wj, ti, t j, tl, t2, tl2, send ifendifend ifend doend doend doend doend if end do end do end do end if end if end do end do end do end do end do end do end do close (1) end program pbcgh2 附录3：平板车装货问题规划模型1 Lingo求解的输岀数据:Global optimal solution foundObjective

29、value:-0. 1705303E-12Objective bound:0.000000Infeasibilities：0. U54632E-12Extended solver steps:231161Total solver iterations：380690Model Title：两辆铁路平板车的装货问题VariableValueReduced CostAl6.000000-48.70000A22.000000-52. 00000A36.000000-61. 30000A40.000000-72. 00000A50.000000-4& 70000A60.000000-52. 00000A74.000000-64. 00000Bl1. 000000-4& 70000B25.000000-52. 00000B32.000000-61. 30000B45.000000-72. 00000B51. 000000-48 70000B61. 000000-52. 00000B72.000000-64.00000RowSlack or SurplusDual Price10.000000-1.00000020.0000000. 00000030.0000000. 000