运筹学案例 案例七:两辆铁路平板车的装货问题 案例七:两辆铁路平板车的装货问题 案例概述: 有7种规格的包装箱要装到两辆铁路平板车上去。包装箱的宽和 高是一样的,但厚度(t,以厘米计)及重量(o,以kg计)是不同 的。下表给出了每种包装箱的厚度、重量以及数量。每辆平板车有 10.2m长的地方可用来装包装箱(象面包片那样),载重为40t。由于 当地货运的限制,对c,C,C类的包装箱的总数有一个特别的限制:这 类箱子所占的空间(厚度)不能超过3027cm。试把包装箱上平板车 而使浪费的空间最小。 件数 7 6 613720487520640 o(kg) 200030001000500400020001000 第1页共8页
运筹学案例： 案例七：两辆铁路平板车的装货问题 第 1 页 共 8 页 案例七：两辆铁路平板车的装货问题 案例概述： 有 7 种规格的包装箱要装到两辆铁路平板车上去。包装箱的宽和 高是一样的，但厚度（t，以厘米计）及重量（ω ，以 kg 计）是不同 的。下表给出了每种包装箱的厚度、重量以及数量。每辆平板车有 10.2m 长的地方可用来装包装箱（象面包片那样），载重为 40t。由于 当地货运的限制，对 5 6 7 C ,C ,C 类的包装箱的总数有一个特别的限制：这 类箱子所占的空间（厚度）不能超过 302.7cm。试把包装箱上平板车 而使浪费的空间最小。 C1 C2 C3 C4 C5 C6 C7 件数 8 7 9 6 6 4 8 t( ) cm 48．7 52.0 61.3 72.0 48.7 52.0 64.0 ω( ) kg 2000 3000 1000 500 4000 2000 1000
运筹学案例 案例七:两辆铁路平板车的装货问题 案例分析与求解: 问题重述 有7种规格的包装箱要装到两辆铁路平板车上去。包装箱的宽和 高是一样的,但厚度(t,以厘米计)及重量(o,以kg计)是不同 的。下表给出了每种包装箱的厚度、重量以及数量。每辆平板车有 10.2m长的地方可用来装包装箱(象面包片那样),载重为40t。由于 当地货运的限制,对c,C,C类的包装箱的总数有一个特别的限制:这 类箱子所占的空间(厚度)不能超过3027cm。试把包装箱上平板车 而使浪费的空间最小。 C Cr C C C C 件数 7 6 613720487520640 o(kg) 200030001000500400020001000 问题假设 1、包装箱之间的空隙不计; 2、铁路平板车只能放置一列包装箱; 、符号说明 c;第i种包装箱 第i辆平板车上第j种规格包装箱的数目 v,第j种规格包装箱的重量; 第j种规格包装箱的厚度; 第j种规格包装箱的总数目; 其中,i=1,2 第2页共8页
运筹学案例： 案例七：两辆铁路平板车的装货问题 第 2 页 共 8 页 案例分析与求解： 一、问题重述 有 7 种规格的包装箱要装到两辆铁路平板车上去。包装箱的宽和 高是一样的，但厚度（t，以厘米计）及重量（ω ，以 kg 计）是不同 的。下表给出了每种包装箱的厚度、重量以及数量。每辆平板车有 10.2m 长的地方可用来装包装箱（象面包片那样），载重为 40t。由于 当地货运的限制，对 5 6 7 C ,C ,C 类的包装箱的总数有一个特别的限制：这 类箱子所占的空间（厚度）不能超过 302.7cm。试把包装箱上平板车 而使浪费的空间最小。 C1 C2 C3 C4 C5 C6 C7 件数 8 7 9 6 6 4 8 t( ) cm 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 种规格包装箱的数目； wj 第 j 种规格包装箱的重量； j t 第 j 种规格包装箱的厚度； j s 第 j 种规格包装箱的总数目； 其中， i = 1, 2
运筹学案例 案例七:两辆铁路平板车的装货问题 j=1,2,3,4,5,6,7 四、模型的建立及求解 定理一最优解中第七种包装箱的装货量必然为0。 证:根据七种包装箱的厚度和件数,我们可以发现前四种包装箱 的厚度总数为1737.3cm,后三种包装箱所占的空间不能超过 3027cm,总占用空间为2040cm。所以最优解必须使前四种包装 箱与后三种包装箱分别最大。前四种包装箱全部装上平板车时总 数达到最大值。我们对后三种包装箱所占空间求最大值,利用线 性规划求解: minZ=>c,×t ∑c1×1≤302.7 (i=5,6,7) C1≥0(=56,7) 求得最优解为Z=302.1。此时,c3=3,c6=3c,=0。所以在最优解 中第七种包装箱的装货量必然为0 证毕。 问题分析 铁路装货过程中主要解决的是减少空间浪费的问题。存在的限制 条件包括铁路平板车的长度、载重量、包装箱自身的件数以及包装箱 c3,c6,cn的厚度;还应考虑包装箱长度的一些特殊性:c与cs,c2与c 厚度相同,这样可能会导致有多个解;同时两辆平板车之间又存在 相互的制约关系,在考虑一辆平板车时,必须同时考虑第二辆平板车 第3页共8页
运筹学案例： 案例七：两辆铁路平板车的装货问题 第 3 页 共 8 页 j = 1, 2, 3, 4, 5, 6, 7 四、模型的建立及求解 定理一 最优解中第七种包装箱的装货量必然为 0。 证：根据七种包装箱的厚度和件数，我们可以发现前四种包装箱 的厚度总数为 1737.3cm，后三种包装箱所占的空间不能超过 302.7cm，总占用空间为 2040cm。所以最优解必须使前四种包装 箱与后三种包装箱分别最大。前四种包装箱全部装上平板车时总 数达到最大值。我们对后三种包装箱所占空间求最大值，利用线 性规划求解： ∑= = × 7 5 min i i i Z c t ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ = ≤ = ∑ × ≤ = 0 ( 5,6,7) 5,6,7) 302.7 7 5 c i c s i c t i i i i i i （ 求得最优解为 Z=302.1。此时，c5 = 3,c6 = 3,c7 = 0。所以在最优解 中第七种包装箱的装货量必然为 0。 证毕。 1、 问题分析 铁路装货过程中主要解决的是减少空间浪费的问题。存在的限制 条件包括铁路平板车的长度、载重量、包装箱自身的件数以及包装箱 5 6 7 c ,c ,c 的厚度；还应考虑包装箱长度的一些特殊性： 1 c 与 5 c ， 2 c 与 6 c 厚度相同，这样可能会导致有多个解； 同时两辆平板车之间又存在 相互的制约关系，在考虑一辆平板车时，必须同时考虑第二辆平板车
运筹学案例 案例七:两辆铁路平板车的装货问题 的装货。 2、建立模型 我们综合问题分析中的限制条件,建立一个整数规划模型 min Z= 2040- ∑∑ t,x1,≤1020 ∑1x2≤1020 ≤40000 j=l v,x2;≤40000 S x≤3027 ≥0(i=1,2,j=1,2,,7) 利用计算机求得两辆平板车上七种规格包装箱数目分布如下表(共 30组最优解): 第一辆 第二辆 6 0000 15676 26 9 4404 3 0 455 000000000 888777666 33300 10320 322 200 0000000 第4页共8页
运筹学案例： 案例七：两辆铁路平板车的装货问题 第 4 页 共 8 页 的装货。 2、 建立模型 我们综合问题分析中的限制条件，建立一个整数规划模型： ∑∑= = = − 2 1 7 1 min 2040 i j i ij Z t x ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ = = …… ≤ ≤ = …… ≤ ≤ ≤ ≤ ∑∑ ∑ ∑ ∑ ∑ ∑ = = = = = = = 0 ( 1,2; 1,2, ,7) 302.7 ( 1,2, ,7) 40000 40000 1020 1020 . 2 1 7 1 2 1 7 1 2 7 1 1 7 1 2 7 1 1 x i j t x x s j w x w x t x t x st ij i j j ij j i ij j j j j j j j j j j j j 利用计算机求得两辆平板车上七种规格包装箱数目分布如下表（共 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
运筹学案例 案例七:两辆铁路平板车的装货问题 670 0 66 5500 11000 03322 00000000000000000000 2312300 33333 5667 5555 2110 959 2 2230 4444 00000000000000000000 002 00103 0 7900 448 006 最优值Z=0.6 五、模型的评价与改进 本模型求解出的30组答案达到题目提出的要求,使总的浪费空 间最少,均为0.6cm。我们认为铁路部门在考虑空间浪费最少的情况 下,也同时要求载重量、占用空间相差尽可能小,将模型进一步改进。 对载重量要求 两辆平板车的载重量差别不应该太大,否则会引发一些安全问 题。我们从表一得到的符合题目要求的最优解计算出两辆平板车之间 的载重量差值如下(单位:吨): 表 车载重量 车载重量总载重量/两平板车载 第一辆平板|第二辆平板 重量差值 33 第5页共8页
运筹学案例： 案例七：两辆铁路平板车的装货问题 第 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
运筹学案例 案例七:两辆铁路平板车的装货问题 3 28 11 9 38.5 8.5 39.5 35.5 31.5 lI 12 31.5 35.5 34.5 777777777 8042 3.5 375 29.5 37.5 29.5 088 32.5 38.5 777 35.5 31.5 36.5 30.5 29.5 30.5 62860 33.5 33.5 32.5 35.5 34 由表二可知,在要求载重量相差最小的情况下应采用14,15,26号 方案,即:两辆平板车装载包装箱c(i=1,2,……,7)分别为 此时为最优方案。 2、对浪费空间的要求 考虑到平板车之间占用空间也不应该相差太大,分别计算满足表 最优解时,两辆平板车的占用空间及它们之间的差值如下表:(单 第6页共8页
运筹学案例： 案例七：两辆铁路平板车的装货问题 第 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、 对浪费空间的要求 考虑到平板车之间占用空间也不应该相差太大，分别计算满足表 一最优解时，两辆平板车的占用空间及它们之间的差值如下表：(单
运筹学案例 案例七:两辆铁路平板车的装货问题 位:cm) 表三 第一辆平板第二辆平板两辆平板车二辆平板车占 车占用空间车占用空间剩余空间用空间差值 10198 10196 0.6 0.2 10197 10197 0.6 0 10198 10196 1019.8 1019.6 0.2 0.6 1020 10194 0.6 0.6 10194 0.6 1020 10194 0.6 910195 10199 0.6 0.4 10 1020 10194 0.6 0.6 lI 1020 10194 0.6 0.6 12 10194 0.6 0.6 10199 10195 0.4 10199 19.5 0.4 10199 10195 16 1020 10194 0.6 0.6 10195 10199 10194 19 1019.5 10199 0.6 0.4 20 1020 10194 0.6 0.6 211019.5 10199 0.6 1020 10194 10194 1020 0.6 10199 1019.5 10199 10195 0.6 0.4 10194 1020 0.6 10199 1019.5 0.4 10194 1020 0.6 10197 10197 0.6 0 从表三中可以得到方案2,30满足两辆平板车占用空间差值最小的要 求,此时最优解为 07900 参考文献: 第7页共8页
运筹学案例： 案例七：两辆铁路平板车的装货问题 第 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 参考文献：
运筹学案例 案例七:两辆铁路平板车的装货问题 【1】李火林等编,《数学模型及方法》,江西高校出版社,南昌,1997 【2】洪毅等编,《经济数学模型》,华南理工大学出版社,广州,2002 【3】吴江等编,《运筹学模型与方法教程》:清华大学出版社,北京 2000 第8页共8页
运筹学案例： 案例七：两辆铁路平板车的装货问题 第 8 页 共 8 页 【1】 李火林等编,《数学模型及方法》,江西高校出版社,南昌,1997 【2】 洪毅等编,《经济数学模型》,华南理工大学出版社,广州,2002 【3】 吴江等编,《运筹学模型与方法教程》,清华大学出版社,北京, 2000