运筹学案例 案例七:两辆铁路平板车的装货问题 案例七:两辆铁路平板车的装货问题 案例概述: 有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