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

数学建模论文题目：两辆铁路平板车的装货问题 小组成员：李航 纪俊吉 刘骏萍 两辆铁路平板车的装货问题摘要：本题是一个装货问题，即在有限的空间内装最多的货物，使空间浪费率最小。包装箱的宽度和高度是一样的，厚度是不同的。每个装箱策略都会产生不同的浪费。本文讨论的就是怎么样装箱，使浪费最小。本文首先建立一个整数规划模型，考虑问题所给的约束条件，使得包装箱装到两辆铁路平板车，并且使得浪费的空间最小。求解时运用LINGO软件和建立在线性规划求解的单纯基础上的分支界限法求的最优解。在求得本问题的最优目标后，进一步运用C语言，求得了本问题的所有最优解，一共有30种。并进一步分析，在实际装货过程中可能遇到的问题，比如在相同的空间利用率的情况下，装货的总重量问题，在30组解中进一步优化，求得最终的结果。 关键字：整数优化 LING最优解 装货问题1、 问题重述：有7种规格的包装箱要装到两辆铁路平板车上。包装箱的高和宽是一样的，但厚度（t,以厘米计）及重量（g，以千克计）是不同的。下表给出来了每种包装箱的厚度，重量以及数量。每辆平板车有10.2m长的地方可以用来装包装箱（像面包片那样），载重为40t。由于当地货运的限制，对C5，C6，C7类的包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过302.7cm。试把包装箱装到平板车上去使得浪费的空间最小。 C1 C2 C3 C4 C5 C6 C7厚度（cm） 48.7 52.0 61.3 72.0 48.7 52.0 64.0重量（kg） 2000 3000 1000 500 4000 2000 1000件数（件） 8 7 9 6 6 4 82、 问题分析：七种包装箱的重量和W= 89t，而两辆平板车只能载2*40=80t，因此不能全部装下，究竟在两辆车上装哪些种类的箱子各多少才合适，必须有评价的标准，这标准是遵守题中说明的重量,厚度方面的约束条件，并且体现出尽可能多装。由题意，只考虑面包重叠那样的装法，把问题简化为：两辆车上装箱总厚度之和尽可能大，解决这一问题，以寻找最合适的方案：所浪费的空间最小，也就是说，是要让使用的空间最大。3、 问题假设：1、铁路平板车只能放一排包装箱；2、包装箱不会因为挤压碰撞发生形变；3、包装箱之间的空隙不计；4、假设包装箱的厚度和重量是精确的； 5、装载的过程中不考虑货物在车上的排列次序及各个货物的重量密度，排除因局部过重而造成的平板车不能行驶的情况；4、 参数、符号说明： 表示第i种包装箱；（i=1,2,3.7） 表示在第j辆平板车的件数； 表示的厚度； 表示的重量； 表示的件数； 表示第j辆铁路平板车的车长；(j=1,2) 表示第j辆铁路平板车的载重； 表示正整数。其他局部符号在引用时将给出具体说明。四、模型的建立与求解：1、目标函数的确定：目标平板车装箱问题目的是使平板车的空间（即题目中所给的长度）浪费最小。即：其中表示在第j辆平板车的件数，表示的厚度。2、约束条件的确定：每辆平板车的长度限制：对每辆平板车而言，它的长度限制为,则每辆车上的箱子所占的总长度小于等于车的长度。即： 每辆平板车的载重限制：对每辆平板车而言，它的载重限制为,则每辆车上的箱子的总重量小于等于车的载重。即： C5，C6，C7类的包装箱总厚度（即他们占用的总空间）的限制：C5，C6，C7类的包装箱的总厚度小于302.7cm。即：C1，C2，C3，C4，C5，C6，C7包装箱数量的限制：每种包装箱装车的数量不能大于自己的总件数。即： 每种箱子在每类车上的件数为整数：即:3、 模型的建立：由上述分析可以建立问题的模型如下： 4、 模型的求解：算法步骤如下：步骤【1】：将包装箱（box）和铁路平板车（car）分别表示为两个集合：box里面有包装箱的厚度（t），重量（w），件数（n）等属性；car里面有平板车的长度（l），载重（z）等属性。再把两个集合创建为一个新的数组，数组元素表示为第i个箱子在第j个平板车里的件数（c）；步骤【2】：导入各属性所对应的数据；步骤【3】：写出目标函数,用for循环、不等式以及取整表示约束条件，当数据C(i，j)满足约束条件且使得目标函数值最大时，即被输出；步骤【4】：用LINGO软件求解。 求得最优的解为20.394米，即有0.6cm的空间剩余。总的空间利用率达到99.97%。其中一组最优解为C( 1, 1)=8，C( 1,2)=0，C( 2, 1)=2,C(2,2)=5，C(3,1)=3，C(3,2)=6，C(4,1)=2，C( 4, 2)=4，C(5,1)=3,C(5,2)=0，C(6,1)=1C(6,2)=2 ，C( 7, 1)=0，C(7,2,)=0。 求出所有的最优解，在求解的过程中，我们首先考虑用穷举法，穷举法虽然简单易用、操作简单，但是对于时间复杂度过大的情况则无法进行计算。本文所涉及的是将7 种 货物装载到 2 辆平板车上去的问题，由此分析可知，应有 14 个变量即拥有 14 重的循环。 以 C1 为例，该种货物在2 辆平板车的装载数量为0 8，则14 重循环的时间复杂度为( 9 8 10 7 7 5 6) 2 =1. 120 2e +012，这显然是计算机无法承受的。进而，分析问题中的约束条件。提出定理。定理一：最优解中第七种包装箱的装货量必然为0。证：根据七种包装箱的厚度和件数，我们可以发现前四种包装箱的厚度总数为1737.3cm，后三种包装箱所占的空间不能超过302.7cm，总占用空间为2040cm。所以最优解必须使前四种包装箱与后三种包装箱分别最大，我们对后第七种货物的分配C71进行约束看能不能求得到最优利用空间2039.4cm，利用lingo软件求证：MODEL:SETS:JIESHOU/1.2/:H,E;GEIYU/1.7/:T,W,X;SHU/1/:M;LINK(GEIYU,JIESHOU):C;Q(SHU):N;ENDSETSDATA:T=487,520,613,720,487,520,640;W=2000,3000,1000,500,4000,2000,1000;X=8,7,9,6,6,4,8;H=10200,10200;E=40000,40000;ENDDATAOBJ MIN=20400-SUM(LINK(I,J):C(I,J)*T(I);FOR(GEIYU(I):SUM(JIESHOU(J):C(I,J)=X(I);FOR(JIESHOU(J):SUM(GEIYU(I):T(I)*C(I,J)=H(J);FOR(JIESHOU(J):SUM(GEIYU(I):W(I)*C(I,J)=E(J);FOR(Q(B):SUM(JIESHOU(J):SUM(GEIYU(I)|I#GT#4:T(I)*C(I,J)3027);BND(1,C(7,1),8);gin(c(1,1);gin(c(1,2);gin(c(2,1);gin(c(2,2);gin(c(3,1);gin(c(3,2);gin(c(4,1);gin(c(4,2);gin(c(5,1);gin(c(5,2);gin(c(6,1);gin(c(6,2);gin(c(7,1);gin(c(7,2);END求得的最优解为2033.3，并不是2039.6。所以定理得证。所以变量减少为8个，计算机可以实现。求得最优的30组解。在30组最优解中（如下），每组解的装载重量都是一样的，均为67000，即不用考虑相同装载空间下，装载的总重量问题。五、模型的评价与改进：本文所建模型有如下特点：1、基于对问题的分解与基本理解，建立了整数线型规划模型，并对模型进行求解，思路完整严密。2、由于LINGO软件功能强大，计算机运行的时间也大大缩小，而且使理论分析和运行结果相互得到证明，采用LINGO语言，在变量更多的情况下，理论分析的作用就更显得重要，不能盲目的运用计算机求解，本文运用了分支界限法从中得到一组优化解。并运用c语言把所有的最优解均求出来了。3、此解能基本反映实际情况，解决实际问题。充分利用题中的数据特点，对模型进行简化，从而对计算简化。4、在模型的推广上，本文结合实际的运输过程，将平板车的装载重量这一因素引进来，从而由单目标规划推广到多目标规划上，使我们的模型更符合实际需求，更具有经济效益。当然，本文的模型还只是针对一种确知的目标函数而定的。当目标函数变为运输成本最小化而需要进行复杂的不确定的多因素动态规划时，模型则需要更进一步的深化与改进。参考文献：【1】 出版社【2】 出版社【1】 出版社附录：1、 采用LINGO编写的代码及其运行结果：LINGO程序：MODEL:Title BOX&CAR PROMBLEM;sets:box/1.7/:t,w,n;car/1.2/:l,z;link(box,car):c;ccc/1/:a;endsetsdata:t=48.7,52.0,61.3,72.0,48.7,52.0,64.0;w=2000,3000,1000,500,4000,2000,1000;n=8,7,9,6,6,4,8;l=1020,1020;z=40000,40000;a=302.7;enddataMIN=20400-SUM(LINK(I,J):C(I,J)*T(I);for(car(i):sum(box(j):c(j,i)*t(j)=l(i);for(car(i):sum(box(j):c(j,i)*w(j)=z(i);for(link:gin(c););for(box(i):sum(car(j):c(i,j)=n(i);for(ccc:sum(box(j)|j#gt#4:sum(car(i):c(j,i)*t(j)=302.7);bnd(1,c(2,1),5);end运行结果：Objective value: 6.000000 Objective bound: 6.000000 Infeasibilities: 0.000000 Extended solver steps: 31016 Total solver iterations: 91360 Variable Value Reduced Cost H( 1) 10200.00 0.000000 H( 2) 10200.00 0.000000 E( 1) 40000.00 0.000000 E( 2) 40000.00 0.000000 T( 1) 487.0000 0.000000 T( 2) 520.0000 0.000000 T( 3) 613.0000 0.000000 T( 4) 720.0000 0.000000 T( 5) 487.0000 0.000000 T( 6) 520.0000 0.000000 T( 7) 640.0000 0.000000 W( 1) 2000.000 0.000000 W( 2) 3000.000 0.000000 W( 3) 1000.000 0.000000 W( 4) 500.0000 0.000000 W( 5) 4000.000 0.000000 W( 6) 2000.000 0.000000 W( 7) 1000.000 0.000000 X( 1) 8.000000 0.000000 X( 2) 7.000000 0.000000 X( 3) 9.000000 0.000000 X( 4) 6.000000 0.000000 X( 5) 6.000000 0.000000 X( 6) 4.000000 0.000000 X( 7) 8.000000 0.000000 M( 1) 0.000000 0.000000 C( 1, 1) 8.000000 -487.0000 C( 1, 2) 0.000000 -487.0000 C( 2, 1) 2.000000 -520.0000 C( 2, 2) 5.000000 -520.0000 C( 3, 1) 3.000000 -613.0000 C( 3, 2) 6.000000 -613.0000 C( 4, 1) 2.000000 -720.0000 C( 4, 2) 4.000000 -720.0000 C( 5, 1) 3.000000 -487.0000 C( 5, 2) 0.000000 -487.0000 C( 6, 1) 1.000000 -520.0000 C( 6, 2) 2.000000 -520.0000 C( 7, 1) 0.000000 -640.0000 C( 7, 2) 0.000000 -640.0000 N( 1) 0.000000 0.000000 Row Slack or Surplus Dual Price OBJ 6.000000 -1.000000 2 0.000000 0.000000 3 0.000000 0.000000 4 0.000000 0.000000 5 0.000000 0.000000 6 3.000000 0.000000 7 1.000000 0.000000 8 8.000000 0.000000 9 4.000000 0.000000 10 2.000000 0.000000 11 0.000000 0.000000 12 13000.00 0.000000 13 6.000000 0.0000002、 C语言程序及其运行结果程序：#includeint main()int t8=0,487,520,613,720,487,520,640; int w8=0,2000,3000,1000,500,4000,2000,1000; int x8=0,8,7,9,6,6,4,8; int h3=0,10200,10200; int e3=0,40000,40000; int y,c11,c12,c21,c22,c31,c32,c41,c42,c51,c52,c61,c62,c71=0,c72=0; for(c11=0;c11=x1;c11=c11+1)for(c21=0;c21=x2;c21=c21+1)for(c31=0;c31=x3;c31=c31+1)for(c41=0;c41=x4;c41+)for(c51=0;c51=x5;c51+) for(c52=0;c52=x5;c52+) for(c61=0;c61=x6;c61+) for(c62=0;c62=x6;c62+) c12=x1-c11,c22=x2-c21,c32=x3-c31,c42=x4-c41;if(c11*t1+c12*t1+c21*t2+c22*t2+c31*t3+c32*t3+c41*t4+c42*t4+c51*t5+c52*t5+c61*t6+c62*t6+c71*t7+c72*t7)=20394)if(c11*t1+c21*t2+c31*t3+c41*t4+c51*t5+c61*t6+c71*t7)=10200)if(c12*t1+c22*t2+c32*t3+c42*t4+c52*t5+c62*t6+c72*t7)=10200)if(c11*w1+c21*w2+c31*w3+c41*w4+c51*w5+c61*w6+c71*w7)=40000)if(c12*w1+c22*w2+c32*w3+c42*w4+c52*w5+c62*w6+c72*w7)=40000)if(c51*t5+c52*t5+c61*t6+c62*t6+c71*t7+c72*t7=3027)printf(%d %d %d %d %d %d %d %d %d %d %d %d %d %d / ,c11,c12,c21,c22,c31,c32,c41,c42,c51,c52,c61,c62,c71,c72); ;运行结果：0 8 5 2 6 3 4 2 0 3 2 1 0 0 /0 8 6 1 6 3 4 2 0 3 1 2 0 0 /0 8 6 1 9 0 0 6 0 3 3 0 0 0 /0 8 7 0 6 3 4 2 0 3 0 3 0 0 /0 8 7 0 9 0