运筹学案例： 案例七：两辆铁路平板车的装货问题 第 1 页 共 8 页 案例七：两辆铁路平板车的装货问题 案例概述： 有7种规格的包装箱要装到两辆铁路平板车上去。包装箱的宽和 高是一样的，但厚度（t，以厘米计）及重量（ω，以kg计）是不同 的。下表给出了每种包装箱的厚度、重量以及数量。每辆平板车有 10.2m长的地方可用来装包装箱（象面包片那样），载重为40t。由于 当地货运的限制，对 765 ,, CCC类的包装箱的总数有一个特别的限制：这 类箱子所占的空间（厚度）不能超过302.7cm。试把包装箱上平板车 而使浪费的空间最小。 1 C 2 C 3 C 4 C 5 C 6 C 7 C 件数 8 7 9 6 6 4 8 ()cmt 48．7 52.0 61.3 72.0 48.7 52.0 64.0 ()kgω 2000 3000 1000 500 4000 2000 1000 运筹学案例： 案例七：两辆铁路平板车的装货问题 第 2 页 共 8 页 案例分析与求解： 一、问题重述 有7种规格的包装箱要装到两辆铁路平板车上去。包装箱的宽和 高是一样的，但厚度（t，以厘米计）及重量（ω，以kg计）是不同 的。下表给出了每种包装箱的厚度、重量以及数量。每辆平板车有 10.2m长的地方可用来装包装箱（象面包片那样），载重为40t。由于 当地货运的限制，对 765 ,, CCC类的包装箱的总数有一个特别的限制：这 类箱子所占的空间（厚度）不能超过302.7cm。试把包装箱上平板车 而使浪费的空间最小。 1 C 2 C 3 C 4 C 5 C 6 C 7 C 件数 8 7 9 6 6 4 8 ()cmt 48．7 52.0 61.3 72.0 48.7 52.0 64.0 ()kgω 2000 3000 1000 500 4000 2000 1000 二、问题假设 1、 包装箱之间的空隙不计； 2、 铁路平板车只能放置一列包装箱； 三、符号说明 i c 第i种包装箱 ij x 第i辆平板车上第j种规格包装箱的数目； j w 第j种规格包装箱的重量； j t 第j种规格包装箱的厚度； j s 第j种规格包装箱的总数目； 其中， 2,1=i 运筹学案例： 案例七：两辆铁路平板车的装货问题 第 3 页 共 8 页 7,6,5,4,3,2,1=j 四、模型的建立及求解 定理一 最优解中第七种包装箱的装货量必然为0。 证：根据七种包装箱的厚度和件数，我们可以发现前四种包装箱 的厚度总数为1737.3cm，后三种包装箱所占的空间不能超过 302.7cm，总占用空间为2040cm。所以最优解必须使前四种包装 箱与后三种包装箱分别最大。前四种包装箱全部装上平板车时总 数达到最大值。我们对后三种包装箱所占空间求最大值，利用线 性规划求解： ∑ = ×= 7 5 min i ii tcZ ? ? ? ? ? ? ? ? ? =≥ =≤ ≤× ∑ = )7,6,5(0 )7,6,5 7.302 7 5 ic isc tc i ii i ii （ 求得最优解为Z=302.1。此时，0,3,3 765 === ccc。所以在最优解 中第七种包装箱的装货量必然为0。 证毕。 1、 问题分析 铁路装货过程中主要解决的是减少空间浪费的问题。存在的限制 条件包括铁路平板车的长度、载重量、包装箱自身的件数以及包装箱 765 ,, ccc的厚度；还应考虑包装箱长度的一些特殊性： 1 c与 5 c， 2 c与 6 c 厚度相同，这样可能会导致有多个解； 同时两辆平板车之间又存在 相互的制约关系，在考虑一辆平板车时，必须同时考虑第二辆平板车 运筹学案例： 案例七：两辆铁路平板车的装货问题 第 4 页 共 8 页 的装货。 2、 建立模型 我们综合问题分析中的限制条件，建立一个整数规划模型： ∑∑ == ?= 2 1 7 1 2040min ij iji xtZ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ……==≥ ≤ ……=≤ ≤ ≤ ≤ ≤ ∑∑ ∑ ∑ ∑ ∑ ∑ == = = = = = )7,,2,1;2,1(0 7.302 )7,,2,1( 40000 40000 1020 1020 . 2 1 7 1 2 1 7 1 2 7 1 1 7 1 2 7 1 1 jix xt jsx xw xw xt xt ts ij ij ijj j i ij j jj j jj j jj j jj 利用计算机求得两辆平板车上七种规格包装箱数目分布如下表（共 30组最优解）： 表 一 第一辆 第二辆 11 x 12 x 13 x 14 x 15 x 16 x 17 x 21 x 22 x 23 x 24 x 25 x 26 x 27 x 0 5 6 4 0 2 0 8 2 3 2 3 1 0 0 6 9 0 0 3 0 8 1 0 6 3 0 0 0 7 6 4 0 0 0 8 0 3 2 3 3 0 0 6 6 4 0 1 0 8 1 3 2 3 2 0 1 4 4 3 3 3 0 7 3 5 3 0 0 0 1 5 4 3 3 2 0 7 2 5 3 0 1 0 1 6 4 3 3 1 0 7 1 5 3 0 2 0 2 4 4 3 2 3 0 6 3 5 3 1 0 0 2 5 0 5 3 3 0 6 2 9 1 0 0 0 2 5 4 3 2 2 0 6 2 5 3 1 1 0 运筹学案例： 案例七：两辆铁路平板车的装货问题 第 5 页 共 8 页 2 6 4 3 2 1 0 6 1 5 3 1 2 0 2 7 4 3 2 0 0 6 0 5 3 1 3 0 3 0 9 1 3 2 0 5 7 0 5 0 1 0 3 1 9 1 3 1 0 5 6 0 5 0 2 0 3 2 9 1 3 0 0 5 5 0 5 0 3 0 3 4 4 3 1 3 0 5 3 5 3 2 0 0 3 5 0 5 2 3 0 5 2 9 1 1 0 0 3 5 4 3 1 2 0 5 2 5 3 2 1 0 3 6 0 5 2 2 0 5 1 9 1 1 1 0 3 6 4 3 1 1 0 5 1 5 3 2 2 0 3 7 0 5 2 1 0 5 0 9 1 1 2 0 3 7 4 3 1 0 0 5 0 5 3 2 3 0 4 0 5 3 3 3 0 4 7 4 3 0 0 0 4 0 9 1 2 2 0 4 7 0 5 1 1 0 4 1 9 1 2 1 0 4 6 0 5 1 2 0 4 1 5 3 3 2 0 4 6 4 3 0 1 0 4 2 5 3 3 1 0 4 5 4 3 0 2 0 4 2 9 1 2 0 0 4 5 0 5 1 3 0 4 3 5 3 3 0 0 4 4 4 3 0 3 0 0 7 9 0 0 2 0 8 0 0 6 3 1 0 最优值Z=0.6 五、模型的评价与改进 本模型求解出的30组答案达到题目提出的要求，使总的浪费空 间最少，均为0.6cm。我们认为铁路部门在考虑空间浪费最少的情况 下，也同时要求载重量、占用空间相差尽可能小，将模型进一步改进。 1、 对载重量要求 两辆平板车的载重量差别不应该太大，否则会引发一些安全问 题。我们从表一得到的符合题目要求的最优解计算出两辆平板车之间 的载重量差值如下（单位：吨）： 表 二 第一辆平板 车载重量 第二辆平板 车载重量 总载重量 两平板车载 重量差值 1 27 40 67 13 2 33 34 67 1 运筹学案例： 案例七：两辆铁路平板车的装货问题 第 6 页 共 8 页 3 28 39 67 11 4 29 38 67 9 5 37.5 29.5 67 8 6 38.5 28.5 67 10 7 39.5 27.5 67 12 8 35.5 31.5 67 4 9 39.5 27.5 67 12 10 37.5 29.5 67 8 11 38.5 28.5 67 10 12 31.5 35.5 67 4 13 32.5 34.5 67 2 14 33.5 33.5 67 0 15 33.5 33.5 67 0 16 37.5 29.5 67 8 17 37.5 29.5 67 8 18 34.5 32.5 67 2 19 38.5 28.5 67 10 20 35.5 31.5 67 4 21 39.5 27.5 67 12 22 36.5 30.5 67 6 23 32.5 34.5 67 2 24 29.5 37.5 67 8 25 30.5 36.5 67 6 26 33.5 33.5 67 0 27 34.5 32.5 67 2 28 31.5 35.5 67 4 29 35.5 31.5 67 4 30 34 33 67 1 由表二可知，在要求载重量相差最小的情况下应采用14，15，26号 方案，即：两辆平板车装载包装箱 i c（ i=1，2，……，7）分别为 3 1 9 1 3 1 0 5 6 0 5 0 2 0 3 2 9 1 3 0 0 5 5 0 5 0 3 0 4 1 5 3 3 2 0 4 6 4 3 0 1 0 此时为最优方案。 2、 对浪费空间的要求 考虑到平板车之间占用空间也不应该相差太大，分别计算满足表 一最优解时，两辆平板车的占用空间及它们之间的差值如下表：(单 运筹学案例： 案例七：两辆铁路平板车的装货问题 第 7 页 共 8 页 位：cm ) 表 三 第一辆平板 车占用空间 第二辆平板 车占用空间 两辆平板车 剩余空间 二辆平板车占 用空间差值 1 1019.8 1019.6 0.6 0.2 2 1019.7 1019.7 0.6 0 3 1019.8 1019.6 0.6 0.2 4 1019.8 1019.6 0.6 0.2 5 1020 1019.4 0.6 0.6 6 1020 1019.4 0.6 0.6 7 1020 1019.4 0.6 0.6 8 1020 1019.4 0.6 0.6 9 1019.5 1019.9 0.6 0.4 10 1020 1019.4 0.6 0.6 11 1020 1019.4 0.6 0.6 12 1020 1019.4 0.6 0.6 13 1019.9 1019.5 0.6 0.4 14 1019.9 1019.5 0.6 0.4 15 1019.9 1019.5 0.6 0.4 16 1020 1019.4 0.6 0.6 17 1019.5 1019.9 0.6 0.4 18 1020 1019.4 0.6 0.6 19 1019.5 1019.9 0.6 0.4 20 1020 1019.4 0.6 0.6 21 1019.5 1019.9 0.6 0.4 22 1020 1019.4 0.6 0.6 23 1019.4 1020 0.6 0.6 24 1019.9 1019.5 0.6 0.4 25 1019.9 1019.5 0.6 0.4 26 1019.4 1020 0.6 0.6 27 1019.4 1020 0.6 0.6 28 1019.9 1019.5 0.6 0.4 29 1019.4 1020 0.6 0.6 30 1019.7 1019.7 0.6 0 从表三中可以得到方案2，30满足两辆平板车占用空间差值最小的要 求，此时最优解为 0 6 9 0 0 3 0 8 1 0 6 3 0 0 0 7 9 0 0 2 0 8 0 0 6 3 1 0 参考文献： 运筹学案例： 案例七：两辆铁路平板车的装货问题 第 8 页 共 8 页 【1】 李火林等编,《数学模型及方法》,江西高校出版社,南昌,1997 【2】 洪毅等编,《经济数学模型》,华南理工大学出版社,广州,2002 【3】 吴江等编,《运筹学模型与方法教程》,清华大学出版社,北京, 2000