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

两辆铁路平板车的装货问题第1页两辆铁路平板车的装货问题摘要：铁路运输部门常常会遇到平板车的装货问题。包装箱的宽度和高度是一样的，厚度是不同的。每种装箱策略都会产生不同的浪费。本文所要讨论的就是怎样装箱，使得浪费最小。本题是个整数规划问题，其特点是约束条件比较多，而且涉及到两辆平板车的问题，必须综合考虑。共有七种规格的包装箱要装上两辆平板车，包装箱的总数、后三种包装箱的总厚度、平板车的容量及载重量都有一定的限制。我们根据平板车浪费空间最小的原则列出目标函数，再由各个限制条件列出约束函数。首先我们利用计算机求出30组满足条件的最优解（见表一），得到占用空间最大为2039.4cm，最小浪费空间为0.6cm。其次我们考虑到两辆平板车的载货性能是一样的，应当使两辆车上的货物重量及占用的空间的差量尽可能小，为此我们对模型作出了一些改进，使结果进一步优化（见表二、表三）。一、问题重述有7种规格的包装箱要装到两辆铁路平板车上去。包装箱的宽和高是一样的，但厚度（t，以厘米计）及重量（，以kg计）是不同的。下表给出了每种包装箱的厚度、重量以及数量。每辆平板车有10.2m长的地方可用来装包装箱（象面包片那样），载重为40t。由于当地货运的限制，对765,,CCC类的包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过302.7cm。试把包装箱上平板车而使浪费的空间最小。1C2C3C4C5C6C7C件数8796648cmt48．752.061.372.048.752.064.0kg200030001000500400020001000二、问题假设1、包装箱之间的空隙不计；2、铁路平板车只能放置一列包装箱；三、符号说明ic第i种包装箱ijx第i辆平板车上第j种规格包装箱的数目；jw第j种规格包装箱的重量；jt第j种规格包装箱的厚度；两辆铁路平板车的装货问题第2页js第j种规格包装箱的总数目；其中，2,1i7,6,5,4,3,2,1j四、模型的建立及求解定理一最优解中第七种包装箱的装货量必然为0。证：根据七种包装箱的厚度和件数，我们可以发现前四种包装箱的厚度总数为1737.3cm，后三种包装箱所占的空间不能超过302.7cm，总占用空间为2040cm。所以最优解必须使前四种包装箱与后三种包装箱分别最大。前四种包装箱全部装上平板车时总数达到最大值。我们对后三种包装箱所占空间求最大值，利用线性规划求解：75miniiitcZ)7,6,5(0)7,6,57.30275icisctciiiiii（求得最优解为Z=302.1。此时，0,3,3765ccc。所以在最优解中第七种包装箱的装货量必然为0。证毕。1、问题分析铁路装货过程中主要解决的是减少空间浪费的问题。存在的限制条件包括铁路平板车的长度、载重量、包装箱自身的件数以及包装箱765,,ccc的厚度；还应考虑包装箱长度的一些特殊性：1c与5c，2c与6c厚度相同，这样可能会导致有多个解；同时两辆平板车之间又存在相互的制约关系，在考虑一辆平板车时，必须同时考虑第二辆平板车的装货。2、建立模型我们综合问题分析中的限制条件，建立一个整数规划模型：21712040minijijixtZ两辆铁路平板车的装货问题第3页)7,,2,1;2,1(07.302)7,,2,1(400004000010201020.217121712711712711jixxtjsxxwxwxtxttsijijijjjiijjjjjjjjjjjjj利用计算机求得两辆平板车上七种规格包装箱数目分布如下表（共30组最优解）：第一辆第二辆11x12x13x14x15x16x17x21x22x23x24x25x26x27x056402082323100690030810630007640008032330066401081323201443330735300015433207253010164331071530202443230635310025053306291000254322062531102643210615312027432006053130309132057050103191310560502032913005505030344313053532003505230529110035431205253210两辆铁路平板车的装货问题第4页360522051911103643110515322037052105091120374310050532304053330474300040912204705110419121046051204153320464301042533104543020429120045051304353300444303007900208006310表一最优值Z=0.6五、模型的评价与改进本模型求解出的30组答案达到题目提出的要求，使总的浪费空间最少，均为0.6cm。我们认为铁路部门在考虑空间浪费最少的情况下，也同时要求载重量、占用空间相差尽可能小，将模型进一步改进。1、对载重量要求两辆平板车的载重量差别不应该太大，否则会引发一些安全问题。我们从表一得到的符合题目要求的最优解计算出两辆平板车之间的载重量差值如下（单位：吨）：第一辆平板车载重量第二辆平板车载重量总载重量两平板车载重量差值1274067132333467132839671142938679537.529.5678638.528.56710739.527.56712835.531.5674939.527.567121037.529.56781138.528.567101231.535.56741332.534.56721433.533.56701533.533.56701637.529.56781737.529.5678两辆铁路平板车的装货问题第5页1834.532.56721938.528.567102035.531.56742139.527.567122236.530.56762332.534.56722429.537.56782530.536.56762633.533.56702734.532.56722831.535.56742935.531.5674303433671表二由表二可知，在要求载重量相差最小的情况下应采用14，15，26号方案，即：两辆平板车装载包装箱ic（i=1，2，……，7）分别为319131056050203291300550503041533204643010此时为最优方案。对浪费空间的要求考虑到平板车之间占用空间也不应该相差太大，分别计算满足表一最优解时，两辆平板车的占用空间及它们之间的差值如下表：(单位：cm)第一辆平板车占用空间第二辆平板车占用空间两辆平板车剩余空间二辆平板车占用空间差值11019.81019.60.60.221019.71019.70.6031019.81019.60.60.241019.81019.60.60.2510201019.40.60.6610201019.40.60.6710201019.40.60.6810201019.40.60.691019.51019.90.60.41010201019.40.60.61110201019.40.60.61210201019.40.60.6131019.91019.50.60.4两辆铁路平板车的装货问题第6页141019.91019.50.60.4151019.91019.50.60.41610201019.40.60.6171019.51019.90.60.41810201019.40.60.6191019.51019.90.60.42010201019.40.60.6211019.51019.90.60.42210201019.40.60.6231019.410200.60.6241019.91019.50.60.4251019.91019.50.60.4261019.410200.60.6271019.410200.60.6281019.91019.50.60.4291019.410200.60.6301019.71019.70.60表三从表三中可以得到方案2，30满足两辆平板车占用空间差值最小的要求，此时最优解为0690030810630007900208006310参考文献1李火林等编《数学模型及方法》2洪毅等编《经济数学模型》3吴江等编《运筹学模型与方法教程》两辆铁路平板车的装货问题第7页附录：functionpbch()x1=zeros(1,7);x2=zeros(1,7);t=[48.75261.37248.75264];t1=[000048.75264];w=[200030001000500400020001000];s=[8796648];s1=zeros(1,7);z1=0;z2=0;fori1=1:8x1(1)=i1;fori2=1:7x1(2)=i2;fori3=1:9x1(3)=i3;fori4=1:6x1(4)=i4;fori5=1:6x1(5)=i5;fori6=1:4x1(6)=i6;fori7=1:8x1(7)=i7;两辆铁路平板车的装货问题第8页forj1=1:8x2(1)=j1;forj2=1:7x2(2)=j2;forj3=1:9x2(3)=j3;forj4=1:6x2(4)=j4;forj5=1:6x2(5)=j5;forj6=1:4x2(6)=j6;forj7=1:8x2(7)=j7;m1=quhe(x1,t);m2=quhe(x2,t);m3=quhe(x1,w);m4=quhe(x2,w);m5=quhe(x1,t1);m6=quhe(x2,t1);s1=x1+x2;z=bijiao(s,s1);ifm1=1020&&m2=1020&&m3=40000&&m4=40000&&(m5+m6)=302.7&&z==1ifm1+m2z1+z2z1=m1;a=x1;z2=m2;b=x2;z1z2abendendendendendendendendendendendend两辆铁路平板车的装货问题第9页endendendendfunctionz=bijiao(a,b)z=0;ifb(1)=a(1)&&b(2)=a(2)&&b(3)=a(3)&&b(4)=a(4)&&b(5)=a(5)&&b(6)=a(6)&&b(7)=a(7)z=1;endfunctionz=quhe(a,b)y=a+b;z=0;fori=1:7z=z+y(i);end