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

两辆铁路平板车装货问题的讨论两辆铁路平板车装货问题的讨论 摘要摘要 本文针对两辆铁路平板车装运包装箱的问题 建立了铁路平板车装运包装箱的整数规 划模型 通过 LINGO 软件方便快捷地求出了平板车不同种类包装箱装运件数一组最优解 同时使用 Fortran 编程求出所有符合条件的最优解 本文鉴于题目中 当地货运的限制 对 C5 C6 C7类的包装箱的总数的特别的限制 这类 箱子所占的空间 厚度 不能超过 302 7cm 的存在的歧义 对该问题分两种情况进行讨论 分别建立模型 得出了不同情况下满足题设的最优方案 第一种情况认为货运的限制针对于每辆平板车 即每辆车上 C5 C6 C7类的包装箱的总厚 度不超过 302 7cm 针对该情况 我们建立了两辆铁路平板车装运包装箱的整数规划模型 一 并用 LINGO 求得最优解为两辆车装运 C1 C2 C7 类包装箱的数量分别为 6 2 6 0 0 0 4 1 5 2 5 1 1 2 剩余厚度为 0cm 考虑到 LINGO 求解 整数规划只能求出一组最优解的局限性 我们进而用 Fortran 编程求出了所有符合条件的 12 组最优解 因为不考虑两车先后次序 我们又用对结果去重 最终得到 6 组最优解 详 见表一 另一种则认为货运的限制针对于一次货运 在本题中则为两辆车上 C5 C6 C7类的包装箱 的总厚度不超过 302 7cm 针对该情况 我们同样也建立了铁路平板车装运包装箱的整数 规划模型二 并用 LINGO 求得最优解为两辆车装运 C1 C2 C7 类包装箱的数量分别为 3 2 9 1 3 0 0 5 5 0 5 0 3 0 剩余厚度为 0 6cm 同样由于 LINGO 软 件的局限性 我们又用 Fortran 编程求得所有符合条件的 54 组最优解 经过去重后最终得 到 27 组最优解 详见表二 关键词 整数线性规划 LINGO 局限性 Fortran 一 一 问题重述问题重述 有七种规格的包装箱要装到两辆铁路平板车上去 包装箱的宽和高是一样的 但厚 度 t 以厘米计 及重量 w 以公斤计 是不同的 下表给出了每种包装箱的厚度 重 量以及数量 每辆平板车有 1020cm 的地方可用来装包装箱 像面包片那样 载重为 40 吨 由于当地货运的限制 对 C5 C6 C7 类的包装箱的总数有一个特别的限制 这类箱子所 占的空间 厚度 不能超过 302 7cm 分两辆车和一辆车两种情况讨论 试把包装箱装到 平板车上去使得浪费的空间最小 C1 C2 C3 C4 C5 C6 C7 t cm 48 7 52 0 61 3 72 0 48 7 52 0 64 0 w kg 2000 3000 1000 500 4000 2000 1000 件数 8 7 9 6 6 4 8 二 二 问题分析问题分析 通过理解题目 本例属于整数型线性规划问题 由题目中给出的条件 我们可以算出货 物的总重量为 89 吨 而两辆车的载重量为 80 吨 所以必然不能将货物全部装载完 也就 是说必然会有货物剩余 我们假设平板车上恰好只能放一排包装箱 且包装箱之间间隙忽略不计 对于题目中限制条件 C5 C6 C7 类包装箱的总厚度不超过 302 7cm 存在以下两种理解 1 一种是对于每辆车而言 车上 C5 C6 C7 类包装箱的总空间不超过 302 7cm 2 另一种是对于两辆车而言 C5 C6 C7 类包装箱的总空间不超过 302 7cm 由此 我们分别对这两种情况建立模型 并利用 LINGO 解出该整数型线性规划的最优解 考虑到变量较多以及变量权值的特殊性 如 C2 C6 的长度相等 均为 52 0cm 我们猜想 对每种情况都可能存在多组最优解 我们利用 lingo 软件解出一组最优解作为参考 再根据 Fortran 编译程序 讨论得出所 有最优解 三 三 模型假设模型假设 一 每辆平板车上恰好只能装载一排的包装箱 不存在并排或者叠加等情况 二 包装箱之间的间隙可忽略不计 三 两辆平板车完全相同 不考虑两车先后次序问题 四 不考虑一辆车上同一种包装箱组合方案的不同排列 五 在重量符合要求的情况下 不考虑两车重量差别大小对最优解的影响 四 四 符号系统符号系统 f 浪费的空间 Cij 第 i 种包装箱装在第 j 辆平板车上数目 ti 第 i 种包装箱的厚度 Wi 第 i 种包装箱的质量 ni 第 i 种包装箱的数目 五 五 模型建立与求解模型建立与求解 对于题目中所说的对 C5 C6 C7 类包装箱的总数的特别限制 存在以下两种理解 1 一种是对于每辆车而言 车上 C5 C6 C7 类包装箱的总空间不超过 302 7cm 2 另一种是对于两辆车而言 C5 C6 C7 类包装箱的总空间不超过 302 7cm 对此我们分别建立了以下两种模型 1 两辆铁路平板车装运包装箱的整数规划模型一 2 两辆铁路平板车装运包装箱的整数规划模型二 5 15 1 模型一的建立与求解模型一的建立与求解 5 1 15 1 1 模型一的建立模型一的建立 假设装箱时每辆平板车上只能装载一排的包装箱 不存在并排或者叠加等情况 同时 有包装箱之间的间隙可忽略不计 此时 设第 i 种包装箱装在第 j 辆平板车上数目 Cij 则包装箱在两辆车上所占据的长 度 即为两辆平板 车的总长为 2040cm 所以浪费的空间 27 11 2040 ij i ji fC t 由于两辆平板车均有各自的长度限制 所以在两辆平板车上的包装箱总厚度不应超过 两辆平板车各自的长度限制 问题中给出两辆车的容许长度均为 1020cm 据此建立第一个约束条件 7 1 102001 2 ij i i C tj 由于当地货运的限制 对 C5 C6 C7类的包装箱的总数有一个特别的限制 这类箱子所占 的空间 厚度 不能超过 302 7cm 据此建立第二个约束条件 7 5 302 71 2 ij i i C tj 由于两辆平板车均为超出容许的载重 在平板车上的载重为 两辆平板车的载重均为 40000Kg 据此建立第三个约束条件 7 1 400001 2 iji i C Wj 若包装箱全部装车 则所需空间为 2749 5cm 而两辆平板车的总长仅 2040cm 可以发 现包装箱不可以完全装到平板车上 因此不应将所有包装箱都装到平板车上 所以七种包 装箱的数目在提供的包装箱件数 ni 的容许的范围内 并且包装箱在每辆平板车上的数目不 为负值 所以可以建立第四个约束条件 2 1 01 2 7 iji j Cni 根据以上分析可建立以下整数线性规划数学模型 27 11 7 1 7 5 7 1 2 1 min2040 102001 2 302 71 2 400001 2 01 2 7 ij i ji ij i i ij i i iji i iji j fC t C tj C tj st C Wj Cni 5 1 25 1 2 模型一的求解模型一的求解 根据两辆铁路平板车装运包装箱的整数规划模型一 我们用 LINGO 求得最优解为两 辆车装运 C1 C2 C7 类包装箱的数量分别为 6 2 6 0 0 0 4 1 5 2 5 1 1 2 剩余厚度为 0cm 考虑到 LINGO 求解 整数规划只能求出一组最优解的局限性 我们进而用 Fortran 编程求出了所有符合条件的 12 组最优解 因为不考虑两车先后次序 我们又用对结果去重 最终得到 6 组最优解 详 见下表 表一 序 号 11 C 21 C 31 C 41 C 51 C 61 C 71 C 12 C 22 C 32 C 42 C 52 C 62 C 72 C 125250126260004 215251126260004 305252126260004 424250226260004 514251226260004 623250326260004 5 25 2 模型二的建立与求解模型二的建立与求解 5 2 15 2 1 模型二的建立模型二的建立 分析可知模型二与模型一的差别 在于模型一中的第二约束条件 模型二中 两辆平 板车上 C5 C6 C7类箱子所占总空间的 厚度 不能超过 302 7cm 所以约束条件 27 15 302 7 ij i ji C t 可以建立如下整数线性规划模型 27 11 7 1 27 15 7 1 2 1 min2040 102001 2 302 7 400001 2 01 2 7 ij i ji ij i i ij i ji iji i iji j fC t C tj C t st C Wj Cni 5 2 2 模型二的求解模型二的求解 根据铁路平板车装运包装箱的整数规划模型二 用 LINGO 求得最优解为两辆车装运 C1 C2 C7 类包装箱的数量分别为 3 2 9 1 3 0 0 5 5 0 5 0 3 0 剩余 厚度为 0 6cm 同样由于 LINGO 软件的局限性 我们又用 Fortran 编程求得所有符合条件的 54 组最优解 经过去重后最终得到 27 组最优解 详见下表 表二 序 号 11 C 21 C 31 C 41 C 51 C 61 C 71 C 12 C 22 C 32 C 42 C 52 C 62 C 72 C 162910002505330 247430004053330 373530001443330 452911003505230 537431005053230 663531002443230 742912004505130 827432006053130 953532003443130 1032913005505030 1143533004443030 1281063000690030 1346430104153320 1472530101543320 1557050103091320 1651911103605220 1736431105153220 1862531102543220 1947051104091220 2041912104605120 2126432106153120 2252532103543120 2337052105091120 2431913105605020 2516433107153020 2642533104543020 2780063100790020 六 六 模型分析模型分析 本文针对两辆铁路平板车装运包装箱的问题 视两辆平板车相同 不考虑方案不同仅 仅是 AB 车车次相互交换的情况 装货建立整数规划模型 通过 LINGO 实现了平板车浪费 空间最小的目标 得出了不同种类包装箱装运件数的最优解 然而 用 LINGO 求得最优解 仅为多组解中一组 我们采用高级语言 Fortran 编译 程序 从而得出其他解系 详见附件 七 七 模型推广模型推广 铁路平板车装运包装箱的整数规划模型在多重约束的线性排列组合问题上具有一定通 用性 八 八 结论结论 对于第一种理解即每辆车 C5 C6 C7 这类箱子所占的空间不超过 302 7cm 的情况 我们建立了模型一 得到 6 组最优解 两辆车浪费的总空间 厚度 最少为 0cm 对于第二种理解即两辆车 C5 C6 C7 这类箱子所占的总空间不超过 302 7cm 的情况 我们建立了模型二 模型三 模型四 最终得到 27 组最优解 两辆车浪费的总空间 厚度 最少为 0 6cm 九 九 参考文献参考文献 1 马瑞民 FORTRAN90 程序设计 哈尔滨工程大学出版社 2005 附录 1 程序说明 1 pbc1 lg4 平板车装货问题规划模型 1 Lingo 求解的输出数据 2 pbc1 lgr 平板车装货问题规划模型 1 Lingo 求解源程序 3 pbc2 lg4 平板车装货问题规划模型 1 Lingo 求解源程序 4 pbc2 lgr 平板车装货问题规划模型 1 Lingo 求解的输出数据 5 pbcgh1 dat 平板车装货问题规划模型 1 Fortran90 求解的输出数据 6 pbcgh1 f90 平板车装货问题规划模型 1 Fortran90 求解的源程序 7 pbcgh2 dat 平板车装货问题规划模型 2 Fortran90 求解的输出数据 8 pbcgh2 f90 平板车装货问题规划模型 2 Fortran90 求解的源程序 附录 2 平板车装货问题规划模型 1 program pbcgh1 implicit none integer dimension 14 c C 为第一辆 第二辆平板车装各类包装箱数量的组合 integer i1 i2 i3 i4 i5 i6 i7 j1 j2 j3 j4 j5 j6 j7 wi wj n i1 i2 i7 为分别为第一辆车装 C1 C2 C7 类包装箱的数量 i1 i2 i7 为分别为第一辆车装 C1 C2 C7 类包装箱的数量 wi wj 分别为第一辆车 第二辆车上包装箱总重量 n 为最优解的个数 real t1 t2 ti tj s t1 t2 分别为第一辆车 第二辆车上 C5 C6 C7 类的包装箱的总厚度 ti tj 分别为第一辆车 第二辆车上所有包装箱的总厚度 s 为平板车上剩余厚度 空间剩余量 open 1 file pbcgh1 dat status old 文件 pbcgh1 为平板车装货问题模型 1 的数据 文件 s 2040 平板车剩余厚度 为优化算法从 C7 C6 C1 的顺序穷举 do i7 0 8 do i6 0 4 do i5 0 6 t1 48 7 i5 52 0 i6 64 0 i7 if t1 302 7 then 第一辆车 C5 C6 C7 类的包装箱的总厚度不超过 302 7cm do i4 0 6 do i3 0 9 do i2 0 7 do i1 0 8 ti 48 7 i1 52 0 i2 61 3 i3 72 0 i4 48 7 i5 52 0 i6 64 0 i7 if ti 1020 then 第一辆车上所有包装箱的总厚度不超过车长 1020cm wi 2000 i1 3000 i2 1000 i3 500 i4 4000 i5 2000 i6 1000 i7 if wi 40000 then 第一辆车上包装箱总重量不超过 40000Kg do j7 0 8 i7 do j6 0 4 i6 do j5 0 6 i5 t2 48 7 j5 52 0 j6 64 0 j7 if t2 302 7 then 第二辆车 C5 C6 C7 类的包装箱的总厚度不超过 302 7cm do j4 0 6 i4 do j3 0 9 i3 do j2 0 7 i2 do j1 0 8 i1 tj 48 7 j1 52 0 j2 61 3 j3 72 0 j4 48 7 j5 52 0 j6 64 0 j7 if tj 1020 then 第二辆车上所有包装箱的总厚度不超过车长 1020cm wj 2000 j1 3000 j2 1000 j3 500 j4 4000 j5 2000 j6 1000 j7 if wj 40000 then 第二辆车上包装箱总重量不超过 40000Kg 如果该组合下平板车剩余厚度小于 s 最优解的个数记为 1 并将该组合下平板车剩余厚 度记 s 将该最优解组合存放在数组 c 中 并将文件定位到文件初始点在第一行按顺序记录下 n c wi wj ti tj t1 t2 s 的值 if 2040 ti tj s then n 1 s 2040 ti tj c i1 i2 i3 i4 i5 i6 i7 j1 j2 j3 j4 j5 j6 j7 rewind 1 write 1 1X 17I6 5F7 1 n c wi wj ti tj t1 t2 s 如果该组合下平板车剩余厚度等于 s 最优解的个数 n 加 1 将该最优解组合存放在数组 c 中 并将文件定位到文件初始点在第 n 行按顺序记录下 n c wi wj ti tj t1 t2 s 的值 else if 2040 ti tj s then n n 1 c i1 i2 i3 i4 i5 i6 i7 j1 j2 j3 j4 j5 j6 j7 write 1 1X 17I6 5F7 1 n c wi wj ti tj t1 t2 s end if end if end if end do end do end do end do end if end do end do end do end if end if end do end do end do end do end if end do end do end do close 1 end program pbcgh1 附录 3 平板车装货问题规划模型 2 求解的 Fortran 程序 平板车装货问题规划模型 2 program pbcgh2 implicit none integer dimension 14 c C 为第一辆 第二辆平板车装各类包装箱数量的组合 integer wi wj i1 i2 i3 i4 i5 i6 i7 j1 j2 j3 j4 j5 j6 j7 n i1 i2 i7 为分别为第一辆车装 C1 C2 C7 类包装箱的数量 i1 i2 i7 为分别为第一辆车装 C1 C2 C7 类包装箱的数量 wi wj 分别为第一辆车 第二辆车上包装箱总重量 n 为最优解的个数 real ti tj t1 t2 t12 s t1 t2 分别为第一辆车 第二辆车上 C5 C6 C7 类的包装箱的总厚度 ti tj 分别为第一辆车 第二辆车上所有包装箱的总厚度 s 为平板车上剩余厚度 空间剩余量 open 1 file pbcgh2 dat status old 文件 pbcgh2 为平板车装货问题模型 1 的数据 文件 s 2040 平板车剩余厚度 为优化算法从 C7 C6 C1 的顺序穷举 do i7 0 8 do i6 0 4 do i5 0 6 t1 48 7 i5 52 0 i6 64 0 i7 第一辆车 C5 C6 C7 类的包装箱的总厚度不超过 302 7cm do i4 0 6 do i3 0 9 do i2 0 7 do i1 0 8 ti 48 7 i1 52 0 i2 61 3 i3 72 0 i4 48 7 i5 52 0 i6 64 0 i7 if ti 1020 then 第一辆车上所有包装箱的总厚度不超过车长 1020cm wi 2000 i1 3000 i2 1000 i3 500 i4 4000 i5 2000 i6 1000 i7 if wi 40000 then 第一辆车上包装箱总重量不超过 40000Kg do j7 0 8 i7 do j6 0 4 i6 do j5 0 6 i5 t2 48 7 j5 52 0 j6 64 0 j7 t12 t1 t2 if t12 320 7 then 两辆车上 C5 C6 C7 类的包装箱的总厚度不超过 302 7cm do j4 0 6 i4 do j3 0 9 i3 do j2 0 7 i2 do j1 0 8 i1 tj 48 7 j1 52 0 j2 61 3 j3 72 0 j4 48 7 j5 52 0 j6 64 0 j7 if tj 1020 then 第二辆车上所有包装箱的总厚度不超过车长 1020cm wj 2000 j1 3000 j2 1000 j3 500 j4 4000 j5 2000 j6 1000 j7 if wj 40000 then 第二辆车上包装箱总重量不超过 40000Kg 如果该组合下平板车剩余厚度小于 s 最优解的个数记为 1 并将该组合下平板车剩余厚 度记 s 将该最优解组合存放在数组 c 中 并将文件定位到文件初始点在第一行按顺序记录下 n c wi wj ti tj t1 t2 t12 s 的值 if 2040 ti tj s then n 1 s 2040 ti tj c i1 i2 i3 i4 i5 i6 i7 j1 j2 j3 j4 j5 j6 j7 rewind 1 write 1 1X 17I6 6F7 1 n c wi wj ti tj t1 t2 t12 s 如果该组合下平板车剩余厚度等于 s 最优解的个数 n 加 1 将该最优解组合存放在数组 c 中 并将文件定位到文件初始点在第 n 行按顺序记录下 n c wi wj ti tj t1 t2 t12 s 的值 else if 2040 ti tj s then n n 1 c i1 i2 i3 i4 i5 i6 i7 j1 j2 j3 j4 j5 j6 j7 write 1 1X 17I6 6F7 1 n c wi wj ti tj t1 t2 t12 s end if endif end if end do end do end do end do end if end do end do end do end if end if end do end do end do end do end do end do end do close 1 end program pbcgh2 附录 3 平板车装货问题规划模型 1 Lingo 求解的输出数据 Global optimal solution found Objective value 0 E 12 Objective bound 0 Infeasibilitie