两辆铁路平板车装货问题的最优化解研究.pdf-资料库

http://www.paper.edu.cn 两辆铁路平板车装货问题的最优化解研究孙莹 1，杨婧 2，徐士君 1 1 江苏省侯集高级中学，江苏徐州（221121） 2 江苏省南京医科大学，江苏南京（211166） E-mail：shforeve@163.com 摘要：本文首先建立一个整数线性规划（ILP）通用模型（A），以包装箱最大占据空间和两车最小剩余空间建立目标函数。本文又提出三个不同的简化模型（B、C、D、E），B 考虑在第一辆车达到 100% 利用率时求第二辆车的配置； C 根据题目的数据之间关系（2040-302.7=1737.3 ，的总厚度为 1737.3 ），在两辆车将箱子装完的假设下，讨论货物配置情况；D 考虑一辆车满载，并且箱子装完的假设条件，讨论货物配置情况。结合问题所给出的约束条件，本文使用 LINGO 软件得到一组最优解，又采用 C++与 vb 两种语言进行编程搜索其它最优解。在模型评价上，本文考虑到在实际运输过程中影响优化装货的因素不止空间利用率这一指标，可能也会对实现优化的这些相关因素具有不同的重视程度，因而将单目标规划推广到多目标规划，引入加权系数，把空间利用率扩展到空间和载重的合理优化上，通过加权组合引入新目标，从而将多目标规划化为单目标规划。关键词：整数线性规划，最优解，约束优化，加权组合 1. 问题重述有七种规格的包装箱要装到两辆铁路平板车上去。包装箱的宽和高是一样的，但厚度（，以厘米计）及重量（，以公斤计）是不同的。表 1-1 给出了每种包装箱的厚度、重量以及数量。每辆平板车有 10.2 米长的地方可用来装包装箱（像面包片那样），载重为 40 吨。由于当地货运的限制，对类的包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过 302.7cm。试把包装箱装到平板车上去使得浪费的空间最小。表 1-1 包装箱的厚度、重量以及数量参数货物种类厚度 (cm) 重量 (kg) 件数 48.7 2000 8 52.0 3000 7 61.3 1000 9 72.0 500 6 48.7 4000 6 52.0 2000 4 64.0 1000 8 请通过理论分析和计算对上述问题建立模型。 2. 问题分析平板车作为被承载的平台，因为题中给出了包装箱的宽和高是一样的，只有厚度不同，因此只需考虑在厚度与平板车长度之间的关系（见下图所示），基于题中在总载重、平板车总长、各货物总件数、后三种货物的厚度的限制等约束条件，可以确定建立线性规划求整数解模型来解决这一问题。本模型属于最优化问题，着重应该解决的问题是如何将货物协调的分配在两个平板车上的，使两个平板车上的空余空间之和最小，或者，考虑装货的总厚度最大。这个问题就转化为有多个限制条件来求最优解问题，这样可以用 LINGO 软件对该问题 - 1 - cm1234,,,CCCCcm1234,,,CCCC1234,,,CCCCtW567,,CCC1C2C3C4C5C6C7CtW

http://www.paper.edu.cn 进行求解，但是由于 LINGO 软件求最优解的方法只能得到一组可行解，而分配方法可能多种。因此要考虑多解的情况如何解决（例如借助 C++、VB 等软件求出所有解的搭配）。对题目中的所说的“由于当地货运的限制，对类的包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过 302.7cm”，一般有两种理解：一种理解是两辆车中所有的类的包装箱所占总厚度不能超过 302.7cm，另一种理解是每一辆车中类的包装箱所占总厚度不能超过 302.7cm。本文只考虑第二种理解。 3. 模型假设图 2-1 平板车装货示意图 1) 各个货物装在车上的概率相同，相互之间的排放不存在关联性； 2) 假定每一辆车上对类的包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过 302.7cm； 3) 在该平板车装载的过程中不考虑各个货物的厚度及重量的误差性，均为题中所给的准确数值； 4) 装载的过程中不考虑货物在车上的排列次序及各个货物的重量密度，排除因局部过重而造成的平板车不能行驶的情况； 5) 各个货物之间排列时靠在一起，忽略其中的间隙及因搬动等带来的一些空隙。 4. 符号系统表 4-1 符号说明第种包装箱装到第辆车上的件数（；）第种包装箱的厚度（第种包装箱的重量（第种包装箱的总件数（）））第辆车上三类包装箱总厚度上限值（）第辆车的载重（）第辆车可用来装包装箱的长度（）目标函数符号权重系数 5. 模型建立与求解对于平板车装货的这个最优化问题，可作如下理解，就是如何分配包装箱使两车剩余空 - 2 - 567,,CCC567,,CCC567,,CCC567,,CCCijxij1,2,,7i1,2jiti1,2,,7iiwi1,2,,7iiui1,2,,7ijlj567,,CCC1,2jjWj1,2jjLj1,2j()Sx,pq

间最少或包装箱的总厚度最大。这也是本文考虑考虑该问题的最优化原则，并以此建立目标函数。主要模型有下述 A、B、C、D 四种。首先进行相关符号赋值说明： http://www.paper.edu.cn （单位：厘米“ ”）（单位：吨“ ”）（单位：件）（单位：厘米“ ”）（单位：吨“ ”）（单位：厘米“ ”）上述符号赋值对下述五个模型均适用。 5.1. 模型目标函数：① ② 约束条件：注：以目标函数①或②求得的最优化整数解相同。对于此模型，以目标函数①为例，本文主要先用 LINGO 软件确定目标函数的最优解 [1][2]，其中一组最优化计算结果如下： Global optimal solution found. Objective value: 0.000000 Extended solver steps: 38219 Total solver iterations: 75613 Variable Value Reduced Cost X11 2.000000 -48.70000 X12 6.000000 -48.70000 X21 5.000000 -52.00000 X22 2.000000 -52.00000 X31 2.000000 -61.30000 X32 6.000000 -61.30000 X41 5.000000 -72.00000 X42 0.000000 -72.00000 X51 0.000000 -48.70000 X52 0.000000 -48.70000 - 3 - 123456748.7,52.0,61.3,72.0,48.7,52.0,64.0tttttttcm12345672,3,1,0.5,4,2,1wwwwwwwt12345678,7,9,6,6,4,8uuuuuuu12302.7,302.7llcm1240,40WWt121020,1020LLcmA227111()jiijjjiSxminLtx2711()iijjiSxmaxtx21717175..1,2,,71,2ijijiijjiiijjiiijjiijxuwxWtxLsttxlxNij　

http://www.paper.edu.cn X61 1.000000 -52.00000 X62 0.000000 -52.00000 X71 2.000000 -64.00000 X72 4.000000 -64.00000 从上述数据可知，两辆平板车上剩余空间为 0 厘米，空间利用率达 100%。然后，结合 C++和 VB 两种语言编译程序（见附录），求出满足目标函数最优解（即满足：① ）的的所有解的组合共 6 组，其中，如表 5-1。表 5-1 两车装货分配表平板车一装货情况平板车二装货情况 0 1 1 2 2 2 5 4 5 3 4 5 2 2 2 2 2 2 5 5 5 5 5 5 2 1 1 0 0 0 1 2 1 3 2 1 2 2 2 2 2 2 6 6 6 6 6 6 2 2 2 2 2 2 6 6 6 6 6 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 4 4 组数 1 2 3 4 5 6 5.2. 模型假设其中一辆车满载，讨论另外一辆的装载情况，不妨设平板车一满载，考虑平板车二的装载情况。目标函数：约束条件：对于此模型，本文主要先用 LINGO 软件确定目标函数的最优解，其中一组最优化计算结果如下： Global optimal solution found. Objective value: 1020.000 Extended solver steps: 27623 Total solver iterations: 49712 Variable Value Reduced Cost X11 0.000000 -48.70000 - 4 - ()0Sxijx(1,2,,71,2)ij　1C2C3C4C5C6C7C1C2C3C4C5C6C7CB721()iiiSxmaxtx217217211722175..1,2,,71,2ijijiijiiiiiiiiijjiijxuwxWtxLsttxLtxlxNij

http://www.paper.edu.cn X21 5.000000 -52.00000 X31 2.000000 -61.30000 X41 5.000000 -72.00000 X51 2.000000 -48.70000 X61 1.000000 -52.00000 X71 2.000000 -64.00000 X12 6.000000 0.000000 X22 2.000000 0.000000 X32 6.000000 0.000000 X42 0.000000 0.000000 X52 0.000000 0.000000 X62 0.000000 0.000000 X72 4.000000 0.000000 从上述数据可知，第一辆车满载，第二两车上包装箱厚度为 1020 厘米，两车空间利用率达 100%。同模型 A，结合 C++和 VB 两种语言编译程序，求出满足目标函数最优解（即）的的所有解的组合共 6 组，其中，数据同满足：表 5-1。 5.3. 模型假设四种货物被完全装完，因为 2040-302.7=1737.3 ，而前四种箱子的总厚度为 1737.3 ，要使三种箱子的厚度不超过 302.7 ，在满足约束条件的情况下，将四种类型的箱子尽量装完，以保证两辆车浪费的空间最小。不妨设四种类型的箱子装完，再作讨论。目标函数：① 或 ② 约束条件：注：以目标函数①或②求得的最优化整数解相同。对于此模型，以目标函数②为例，本文主要先用 LINGO 软件确定目标函数的最优解，其中一组最优化计算结果如下： Global optimal solution found. Objective value: 2039.400 Extended solver steps: 15816 - 5 - ()1020Sxijx(1,2,,71,2)ij　C1234,,,CCCCcm1234,,,CCCCcm567,,CCCcm1234,,,CCCC1234,,,CCCC227111()jiijjjiSxminLtx2711()iijjiSxmaxtx21217171751,2,3,45,6,7..1,2,,71,2ijijijijiijjiiijjiiijjiijxuixuiwxWsttxLtxlxNij　　　　　　　　　　　　

Total solver iterations: 29711 Variable Value Reduced Cost http://www.paper.edu.cn X11 8.000000 -48.70000 X12 0.000000 -48.70000 X21 1.000000 -52.00000 X22 6.000000 -52.00000 X31 3.000000 -61.30000 X32 6.000000 -61.30000 X41 2.000000 -72.00000 X42 4.000000 -72.00000 X51 3.000000 -48.70000 X52 0.000000 -48.70000 X61 2.000000 -52.00000 X62 1.000000 -52.00000 X71 0.000000 -64.00000 X72 0.000000 -64.00000 从上述数据可知，七类包装箱在两辆平板车上的厚度之和达到最大值 2039.4 厘米，浪费空间仅为 0.6 厘米，空间利用率达 99.97%。同模型 A，结合 C++和 VB 两种语言编译程序，求出满足目标函数最优解（即满足：）的的所有解的组合共 30 组，其中，数据同表 5-2。表 5-2 两车装货分配表组数平板车一装货情况平板车二装货情况 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 3 3 3 4 4 4 4 4 4 4 5 5 5 5 5 5 5 6 6 6 6 6 7 7 0 1 2 0 0 1 1 2 2 3 0 0 1 1 2 2 3 0 1 2 2 3 1 2 9 9 9 5 9 5 9 5 9 5 5 9 5 9 5 9 5 5 5 5 9 5 5 5 1 1 1 3 1 3 1 3 1 3 3 1 3 1 3 1 3 3 3 3 1 3 3 3 3 3 3 3 2 3 2 3 2 3 2 1 2 1 2 1 2 1 1 1 0 1 0 0 2 1 0 3 2 2 1 1 0 0 3 2 2 1 1 0 0 3 2 1 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 5 3 4 4 4 4 4 4 4 3 3 3 3 3 3 3 2 2 2 2 2 1 1 7 6 5 7 7 6 6 5 5 4 7 7 6 6 5 5 4 7 6 5 5 4 6 5 0 0 5 4 0 4 0 4 0 4 4 0 4 0 4 0 4 4 4 4 0 4 4 4 5 5 0 3 5 3 5 3 5 3 3 5 3 5 3 5 3 3 3 3 5 3 3 3 0 0 5 0 1 0 1 0 1 0 1 2 1 2 1 2 1 2 2 2 3 2 3 3 1 2 0 0 1 1 2 2 3 3 0 1 1 2 2 3 3 0 1 2 3 3 1 2 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - 6 - ()2039.4Sxijx(1,2,,71,2)ij　1C2C3C4C5C6C7C1C2C3C4C5C6C7C

http://www.paper.edu.cn 25 26 27 28 29 30 7 8 8 8 8 8 3 0 0 1 1 2 5 9 3 0 3 3 3 6 2 6 2 2 0 3 3 3 3 3 0 1 3 0 2 1 0 0 0 0 0 0 1 0 0 0 0 0 4 7 7 6 6 5 4 0 6 9 6 6 3 0 4 0 4 4 3 0 0 0 0 0 3 2 0 3 1 2 0 0 0 0 0 0 5.4. 模型假设其中一辆车满载，并且四种类型的箱子装完，讨论另外一辆的装载情况，不妨设第一辆满载。目标函数：约束条件： Global optimal solution found. Objective value: 1019.400 Extended solver steps: 15940 Total solver iterations: 30511 Variable Value Reduced Cost X11 4.000000 -48.70000 X21 2.000000 -52.00000 X31 5.000000 -61.30000 X41 3.000000 -72.00000 X51 3.000000 -48.70000 X61 1.000000 -52.00000 X71 0.000000 -64.00000 X12 4.000000 0.000000 X22 5.000000 0.000000 X32 4.000000 0.000000 X42 3.000000 0.000000 X52 0.000000 0.000000 X62 2.000000 0.000000 X72 0.000000 0.000000 从上述数据可知，第一辆车满载，第二两车上包装箱厚度为 1109.4 厘米，两车空间利 - 7 - D1234,,,CCCC721()iiiSxmaxtx21217172117221751,2,3,45,6,7..1,2,,71,2ijijijijiijjiiiiiiiiijjiijxuixuiwxWsttxLtxLtxlxNij　　　　　　　　　　　　　

用率达 99.97%。同模型 A，结合 C++和 VB 两种语言编译程序，求出满足目标函数最优解（即满足：）的的所有解的组合共 6 组，其中， http://www.paper.edu.cn 数据同表 5-2。 6. 模型分析上述模型是在整数线性规划原理的基础上建立起来的。在模型一中，共有 14 个变量，运用 LINGO 和 VB、C++相结合，提高了运算的准确性。但 VB 编程的运算量较大，运算时间很长，如果面对大数据量的计算，上述方法中的多重循环就显得力不从心了，变量众多是解决该问题的困难所在，因此寻求更高效的算法和数据规律才是解决问题行之有效的途径，模型二、三、四就很好地体现了这一点。另外，C++利用数据分解结合约束条件进行动态规划，求解效率较高。通过理论分析，减少了变量的个数，缩小了变量的取值范围，使问题大大简化，计算机运行的时间也大大缩小，而且使得理论分析和运行结果相互得到了证明。在变量更多的情况下，理论分析的作用就显得更加重要，不能盲目的运用计算机求解。 7. 模型推广本文的模型是建立在对平板车的空间进行充分利用、使得剩余空间最小的情况下考虑的，并将这一要求视为建立模型求解的唯一目标。但在实际运输过程中会遇到诸多因素，而各种因素有可能在运输优化配置中起着相反的作用，正像本题中的数据显示的包装箱的厚度并不和它的重量成正比。各种因素处于何种地位的确立取决于决策者在综合此次运送货物的性质及运输的时间等各种条件限制后，对每种因素的重视程度。所以，也会有这样的可能：在一次运输中让每辆车在其载重范围内尽可能多地承载重量才是我们考虑装货方案的首要目标。假使在此次装载及运输的过程中，题设条件不变（对类的包装箱的厚度要求定为模型假设中的规定），而目标不再是使两辆车上浪费的空间最小，并且我们只将空间利用和载重最大化作为衡量优化装货问题的两个指标，其它因素的影响可以忽略。下面我们将建立多目标规划模型，并就各种可能出现的情况分别进行讨论。为了将目标函数扩展为与空间和承重都有关，我们作函数如下：鉴于实际情况中载重与空间的重要性并不一定等同，所以我们在式中加入了权重系数、，其中满足，。这样，目标函数既考虑了最大化利用空间，又考虑了最大化利用载重。要得到多目标规划的解，通常需要知道决策者对每个目标的重视程度，也称为偏好程度 [3][3]。在我们所建立的模型中，、的取值与对运送货物种类的要求和对运送时间的要求都有关。（1）如果决策者根据运输的要求，认为在装货时只需考虑使平板车的空间得到最大利用，而不管两辆车上承载包装箱的重量是否达到了最大，即，或只须考虑使两辆车上包装箱的重量达到最大（在承重范围内），而不管占用了平板车上多大的空间，即 - 8 - ()1019.4Sxijx(1,2,,71,2)ij　567,,CCC27271111204080ijiijijijixtxwsumpq pqqp和0,1pq1qppq1,0pq

资料库

两辆铁路平板车装货问题的最优化解研究.pdf

相关推荐

开发技术

热门标签

最新资料