木材运输最优设置

1 木材运输的最优方案木材运输的最优方案 一一 摘摘要要 运输是实现人和物空间位置变化的活动 是社会物质生产的必要条件之一 与人 类的生产生活息息相关 高效的运输方案能够节约资源和能源 同时也能够节约费用 从而带来经济上的收益 本文讨论的就是木材运输费用最优化的问题 对运输问题中的产销平衡进行分析和 评价 以运费成本最低作为目标优化对象 在供应量 需求量和单位运费确定的情况下 求解总运费最少的木材运输分配方案 我们遵循运输成本最低原则 采用线性规划的方法 借助 matlab 和 lingo 软件分别 对三个问题进行了分析 建模和求解 对于第一个问题 仅采用火车运输木材 在满足从每个产地运出的货物等于其产量 运输到每个市场的货物等于其需求量的约束条件下 利用 matlab 软件进行线性规划 建 立总运费最小的目标函数 求解得到运输费用最小的分配方案 最小运费为 2816 千美元 对于第二个问题 全部木材改用水路运输 在满足与第一个问题相同约束的条件下 还需考虑每年在每条线路上的船只的投资费用 采用某一运输路线时即对其进行投资 否则不需要 为了解决这一问题 我们引入了 0 1 规划 利用 lingo 软件进行线性规划 建立总运费最小的目标函数 求解得到运输费用最小的分配方案 最小运费为 1628 1 千 美元 针对第三问 在可以任意选择交通工具的情况下 确定最优的木材运输方案 假设 把木材分为分别用火车和船只运输的两部分 先用最小元素法求最优解 在满足约束条 件的基础上 对这两部分所需的费用相加 得到的最小的运输费用为 模型的建立遵循了简单明了的原则 运用专业数学软件求解 结果可行性高 具有 推广性 关键词 关键词 木材运输 线性规划 matlab lingo 0 1 规划 最小元素法 闭回路 法 2 二 问题的重述二 问题的重述 ALA 是一个木材公司 它有 3 个木材产地和 5 个销售市场 木材产地 1 产地 2 产地 3 每年的产量分别为 15 百万个单位 20 百万个单位 15 百万个单位 5 个市场每 年能卖出的木材量分别为 11 百万个单位 12 百万个单位 9 百万个单位 10 百万个单 位 8 百万个单位 在过去 这个公司是用火车来运送木材的 后来随着火车运费的增加 公司正在考 虑用船来运输木材 采用这种方式需要公司在使用船只上进行一些投资 除了投资成本 以外 在不同线路上用火车运输和用船运输每百万单位的费用如下表所示 表1 运输费用情况 用火车运输每百万木材费用 千美元 用船只运输每百万木材费用 千美元 产 地 市场 1 市场 2 市场 3 市场 4 市场 5 市场1 市场 2 市场 3 市场 4 市场 5 1 61 72 45 55 66 31 38 24 35 2 69 78 60 49 56 36 43 28 24 31 3 59 66 63 61 47 33 36 32 26 其中 表示不能用船只运输的路线 如果用船只运输的话 每年在每条线路上对船只的投资费用如下 表2 新船运路线投资费用情况 对船只的投资 千美元 产 地 市场一市场二市场三市场四市场五 1 27 5 30 3 23 8 28 5 2 29 3 31 8 27 25 26 5 3 28 3 27 5 26 8 24 问题一 假设还是全部货物都沿用火车运输 运输费用最少的运输方案是什么 最少运费是多少 问题二 假设全部货物都改用船只运输 运输费用最少的运输方案是什么 最少运费是多少 问题三 3 假设货物既可以用火车运输 也可以用船只运输 为使总运费最少 如何选择运输方案 最少的运费为多少 三三 模模型型假假设设 1 木材生产地生产量恒定 满足题中已知条件 不会出现突发状况影响产量 2 木材销售市场销售量稳定 不会出现经济紧缩 市场萧条等动荡因素等影响销售量 3 木材运输途中没有突发状况产生影响 不会造成木材的浪费 4 运输过程中不会出现其它客观问题 如交通事故 天气影响和工具维修等不利因素 木材可以安全到达目的地 四四 模模型型的的建建立立 问问题题一一 1 问题分析 3 个木材生产地的总生产量与5 个木材销售市场的销售总量是相等 运用线性规划的知识建立运输费用最小的目标函数 生产基地的产量与输 出量相等 销售市场的销量与输入量相等作为约束条件 求解得到最小运 输费用的运输分配方案 2 符号说明 符号表示意义 A 木材生产地A B木材生产地B C 木材生产地C 1 销售市场1 2 销售市场2 3 销售市场3 4 销售市场4 5 销售市场5 Xi i 1 15 货物运输量 fval 运输费用 3 建立线性规划模型 模型一 由上述问题分析 得到以运输费用最小的规划模型 目标函数 f x 61x1 72x2 45x3 55x4 66x5 69x6 78x7 60 x8 49x9 56x10 59x11 66x12 63x13 61x14 47x15 4 约束条件的建立如下 x1 x2 x3 x4 x5 15 x6 x7 x8 x9 x10 20 x11 x12 x13 x14 x15 15 x1 x6 x11 11 x2 x7 x12 12 x3 x8 x13 9 x4 x9 x14 10 x5 x10 x15 8 x1 0 11 x2 0 12 x3 0 9 s t x4 0 10 x5 0 8 x6 0 11 x7 0 12 x8 0 9 x9 0 10 x10 0 8 x11 0 11 x12 0 12 x13 0 9 x14 0 10 x15 0 8 问问题题二二 1 问题分析 假设全部木材都用船只运输 从三个产地运到五个市场 分别从三个产地 运出的总量必须小于产地的产量 运到五个市场的总量必须不小于市场的需求 量 并且如果从i地运到 j市场 则这条路就需要船只投资费用 如果不需要 从 i地运到 j市场 那么就不需要额外的费用 最后 用从i地运到 j市场 单位运费乘以从i地运到 j市场的木材的量再求和在与从i地运到 j市场路 线的船只费用相加 就可以得到运输木材的所有费用 2 符号的说明 Vi 第 i个木材产地 Wj 第 j个木材市场 Dij 从 i地运到 j市场的运费 Mij 从 i地运到 j市场所运木材的质量 Xij 描述 木材是否从 i地运到 j市场 5 Cij 从 i地运到 j市场所需要的船只投资费用 3 建立模型 假设从 i地运到 j市场的运费为Dij 所运木材的质量为mij 所需要的 船只投资费用为cij 用 xij 0或 1表示木材从 i地运到 j市场或者不从i地运 到 j市场 总费用为 Z Cij Mij Xij Dij 3 1i 5 1j 约束条件如下 1 从三个产地运出的总量必须小于产地的产量 M1j 15 M2j 20 M3j 15 5 1j 5 1j 5 1j 2 运到五个市场的总量必须不小于市场的需求量 3 从 i地运到 j市场 则这条路就需要船只投资费用 如果不需要从i地 运到 j市场 那么就不需要额外的费用 Xij 0或 1 若 Mij 0 则 Xij 0 综合以上分析 建立问题二的模型如下 Min Cij Mij Xij Dij 3 1i 5 1j M1j 15 M2j 20 M3j 15 5 1j 5 1j 5 1j Mi1 11 Mi2 12 Mi3 9 3 1i 3 1i 3 1i s t Mi4 10 Mi5 8 3 1i 3 1i Xij 0或 1 Mij 0 则 Xij 0 对对模模型型三三 1 问题的分析 在第一问的与第二问的基础上 可以比较俩种不同运输方式的运费的大小 明显木材用船只运输的费用不管是运输多少单位的木材都比火车要小 所以只 考虑全部木材都用船只运输 从三个产地运到五个市场 并且场地的供应量与 需求量相等 这是产销平衡运输问题 如果从i地运到 j市场 则要加上 这条路的船只投资费用 如果不需要从i地运到 j市场 那么就不需要对 船只投资额外的费用 最后 用从i地运到 j市场单位运费乘以从i地运 到 j市场的木材的量再求和在与从i地运到 j市场路线的船只费用相加 就 可以得到运输木材的所有费用 2 符号的说明 Vi 第 i个木材产地 6 Wj 第 j个木材市场 Xij 从 i地用火车运到j市场的质量 Cij 从 i地用火车运到j市场 每单位物资的运价 Yij 木材从 i地用船只运到j市场的质量 Dij 木材从 i地用船只运到j市场 每单位物资的运价 Qij 描述木材是否从i地用船只运到j市场 Pij 需要的船只投资费用 3 模型的建立 为了解决只有船只运输的情况下运费最少 下面用最小元素法分析求出最 优解 最小元素法的基本思想是优先满足单位运价最小的供销业务 首先找 出运价最小的 并以最大限度满足其供销量为原则确定供销业务 同样的方法 反复进行直到确定了所有的供销业务 得到一个完整的调运方案即初始基本可 行解为止 首先列出船的运费表 如下 并在此基础上用最小元素法找到木材用船运输的 方案表 船的方案表与运费表 方案表运费表 产地 销量 V1V2V3V4V5产量V1V2V3V4V5 3 1 3 8 2 4 3 5 W1 11415 3 6 4 3 2 8 2 4 3 1 W2 510520 3 3 3 6 3 2 2 6 W3 12315 需求 量 11129108 以此 得到一初始方案 V1 V2 V3 V4V5 7 W1 11 4 W2 5105 W3 123 D11 11 D13 4 D23 5 D24 10 D25 5 D32 12 D35 3 有数格 D12 D15 D21 D22 D33 D34 0 空格 说明 由题可知D14 D31不能用船只运输 不考虑这两处的运输量 所以初始运费方案为 Ymin 11x31 27 5 24x4 23 8 5x28 27 24x10 25 31x5 26 5 3 3x12 28 3 26x3 24 1628 1 千美元 注 有数格是基变量 共m n 1 3 5 1 7个 空格是非基变量 共划 去 m n 8条线 如果填上一个变量之后能同时划去两条线 一行与一列 就须在所划 去的该行或该列填一个0 此 0格当有数格对待 由上面的结论可知最小费用为1628 1千美元 为了检验上面的结果的精确性 又建立了0 1线性规划模型 假设木材从 i地用火车运到j市场的质量为Xij 所需运费为Cij 木材从 i地用船只运到j市场的质量为Yij 所需运费为Dij 用 Qij 0或 1表示木材 从 i地用船只运到j市场或者不从i地用船只运到j市场 所对应需要的船 只投资费用为Pij 可得总费用为 Z Cij Xij Yij Dij PijQij 3 1i 5 1j 约束条件如下 1 从三个产地运出的总量必须小于产地的产量 X1j Y1j 15 X2j Y2j 20 X3j Y3j 15 5 1j 5 1j 5 1j 2 运到五个市场的总量必须不小于市场的需求量 Xi1 Yi1 11 Xi2 Yi2 12 Xi3 Yi3 9 3 1i 3 1i 3 1i Xi4 Yi4 10 Xi5 Yi5 8 3 1i 3 1i 4 从 i地运到 j市场 则这条路就需要船只投资费用 如果不需要从i地 运到 j市场 那么就不需要额外的费用 Qij 0或 1 若 Yij 0 则 Qij 0 综合以上分析 建立问题三的模型如下 Min Cij Xij Yij Dij PijQij 3 1i 5 1j X1j Y1j 15 X2j Y2j 20 5 1j 5 1j 8 X3j Y3j 15 5 1j Xi1 Yi1 11 Xi2 Yi2 12 Xi3 Yi3 9 3 1i 3 1i 3 1i s t Xi4 Yi4 10 Xi5 Yi5 8 3 1i 3 1i Qij 0或 1 若 Yij 0 则 Qij 0 五 模型的求解五 模型的求解 问问题题一一 以上模型为一次线性问题 可以借助matlab 软件求解 在matlab 中编辑窗口中输入程序 可得到用火车运输木材的最优化方案 结果如下表格 所示 木材最优运输分配方案 单位 百万木材 市场 产地 V1 V2 V3 V4V5 W1 6 0 9 00 W2 200108 W3 312000 所以得到的最小运输费用为2816 千美元 问问题题二二 以上模型的目标函数是一次型 即线性问题 可以用lingo软件求解 编写 lingo程序见附录 点击 求解 按钮 得到最优解 总费用为 1628 100千美元 木材的运输计划如图 木材最优运输分配方案 单位 百万木材 市场 产地 V1 V2 V3 V4V5 总 和 W1 11 0 4 0015 W2 00510520 W3 01200315 总和 11129108 所以得到的最小运输费用为1628 100 千美元 9 由图可知满足从三个产地运出的总量小于产地的产量 运到五个市场的总 量等于市场的需求量 所以此结果符合约束条件 问问题题三三 用最小元素法所得结果如下 木材最优运输分配方案 单位 百万木材 市 场 产地 V1 V2 V3 V4V5 W1 11 0 4 00 W2 005105 W3 012003 用 0 1规划验证 与lingo求解结果一样 编程见附录 综合以上方案 为了使木材的运费最少的运输分配方案为只用船只运输 即 得到的最小运输费用为1628 100 千美元 六六 结结果果的的分分析析与与检检验验 对对问问题题三三 用最小元素法解线性规划问题时 在迭代过程中每次求得一个基本可行解以后 都要检验它是不是最优解 如果不是最优解 就要继续进行迭代 直到求得最 优解或者判定无最优解 下面用闭回路法来检验是不是最优解 在运输问题中 每个空格对应一个非基变量 因此 我们需要求出每个空格的检验数 由于目 标要求极小 用闭回路法比较简单 因此 当所有的检验数都大于或等于零时 该调运方案就是最优方案 对方案表中每一空格 确定一条由空格出发的闭回路 闭回路是由水平或垂直线组成的闭合图形 闭回路上的顶点除了这个 空格外 其余均为有数格 10 表 1 市 场 产地 V1 V2 V3 V4V5 4 W1 11 5 W2 5105 W3 123 可以证明 对每一个空格都存在而且惟一存在这样一条封闭回路 表 2 市 场 产地 V1 V2 V3 V4V5 4 W1 11 105 W2 5 12 W3 3 3 表 3 市 场 V1 V2 V3 V4V5 11 产地 4 W1 11 5 10 W2 5 W3 123 表 4 市 场 产地 V1 V2 V3 V4V5 W1 11 4 5105 W2 3 3 W3 12 表 5 市 场 产地 V1 V2 V3 V4V5 W1 11 4 5105 W2 W3 12 3 表 6 计算出空格的检验数 等于闭回路上由此空格起奇数顶点运价与 偶数顶点运价负值的代数和 表一 不同产地船的运输费用 单位 千美元 V1 V2 V3 V4V5 W1 11 4 105 W2 5 W3 12 3 12 如表 一 与表 1 6 的数据得各 个表 1 6 的检验数 g21 36 31 24 28 1 g12 38 24 28 31 26 33 4 g34 32 31 24 26 13 g15 35 28 24 31 8 g22 43 26 31 33 5 g33 36 31 28 26 13 当所有空格检验数 gij 0 则当前方案是最优的 若尚有空格检验数小于零 表明当前方案尚有待调整 g ij 具有确切的经济意义 它表示由wi往 vj增运 1 单位时 引起的总运 输成本的变化数 若所有的空格检验数都大于等于零 表明任何一个空格处调 运 1 单位都会引起总成本的上升 这表明当前方案不能再改进 即定为最优方 案案 由此可知上面的用船只运输的方案为最优方案 七 模型评价七 模型评价 模型的优点 1 本文建立的函数是以最少运费为目标的单目标规划函数 采用 matlab和 lingo编程 实用价值高 结果准确 2 本文所建立的模型分析思路简洁清晰 可以紧密联系到现实实际问题 只需要更改数据便可求其他的运输问题 具有推广性 3 对第三问 我们先对其分析得到最优解 再用lingo编程验证了结 果的最优性 使最后的结果更加真实可靠 具有说服力 模型的缺点 1 在实际生活中 运输问题一把不会达到供求量与需求量相等的情况 而 我们的模型只是针对产销平衡运输问题的 具有狭隘性 2 模型给出的约束条件可能也不太现实 八八 参参考考文文献献 1 袁新生 邵大宏 郁时炼 LINGO和 EXCEL在数学建模中的应用 北京 科学出版社 2008年 11月 2 吴建国 数学建模案列精编 北京 中国水利水电出版社 2005 3 运输问题的资源模型 2012年 7月 18日 九九 附附录录 对问题一用 matlab的编程 程序代码 火车运输优化方案 用船只运输每百万木材费用 千美 元 产地 市场 1 市场 2 市场 3 市场 4 市场 5 1313824 35 23643282431 3 33363226 13 c 61 72 45 55 66 69 78 60 49 56 59 66 63 61 47 Aeq 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 beq 15 20 15 11 12 9 10 8 vlb 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 vub 11 12 9 10 8 11 12 9 10 8 11 12 9 10 8 x fval linprog c Aeq beq vlb vub 程序运行结果 x 6 0000 0 0000 9 0000 0 0000 0 0000 2 0000 0 0000 0 0000 10 0000 8 0000 3 0000 12 0000 0 0000 0 0000 0 0000 fval 2 8160e 003 对问题二 用 lingo软件求解 编写lingo程序如下 MODEL SETS AB W1 W2 W3 WI 该集合表示 3个场地 属性 WI表示各产地的 最大供货能力 BC V1 V5 VJ 该集合表示 5个市场 属性 VJ表示市场的需 求 LINKS AB BC C X M D 衍生集合 LINKS有 3 5 15个成员 定义 4个与集合 LINKS有关的属性 C X M和 D 其中 D和 C相当于具有 15个元素的常数矩阵 X和 M为决策变量 ENDSETS DATA WI 15 20 15 VJ 11 12 9 10 8 D 27 5 30 3 23 8 100 28 5 29 3 31 8 27 25 26 5 100 28 3 27 5 26 8 24 C 31 38 24 100 35 14 36 43 28 24 31 100 33 36 32 26 ENDDATA MIN SUM LINKS I J C I J M I J X I J D I J FOR AB I SUM BC J M I J WI I 各产地生产能力约 束 FOR BC J SUM AB I M I J VJ J 各市场所需的约束 FOR LINKS BIN X 对 X进行 0 1 约束 FOR LINKS I J X I J IF M I J EQ 0 0 1 即约束 条件 Mij 0 则 Xij 0 END 程序结果如下 Local optimal solution found Objective value 1628 100 Extended solver steps 0 Total solver iterations 82 Variable Value Reduced Cost WI W1 15 00000 0 WI W2 20 00000 0 WI W3 15 00000 0 VJ V1 11 00000 0 VJ V2 12 00000 0 VJ V3 9 0 VJ V4 10 00000 0 VJ V5 8 0 C W1 V1 31 00000 0 C W1 V2 38 00000 0 C W1 V3 24 00000 0 C W1 V4 100 0000 0 C W1 V5 35 00000 0 C W2 V1 36 00000 0 C W2 V2 43 00000 15 0 C W2 V3 28 00000 0 C W2 V4 24 00000 0 C W2 V5 31 00000 0 C W3 V1 100 0000 0 C W3 V2 33 00000 0 C W3 V3 36 00000 0 C W3 V4 32 00000 0 C W3 V5 26 00000 0 X W1 V1 1 0 X W1 V2 0 0 X W1 V3 1 0 X W1 V4 0 0 X W1 V5 0 0 X W2 V1 0 0 X W2 V2 0 0 X W2 V3 1 0 X W2 V4 1 0 X W2 V5 1 0 X W3 V1 0 0 X W3 V2 1 0 X W3 V3 0 0 X W3 V4 0 0 X W3 V5 1 0 M W1 V1 11 00000 0 M W1 V2 0 4 M W1 V3 4 0 M W1 V4 0 80 00000 16 M W1 V5 0 8 M W2 V1 0 1 M W2 V2 0 5 M W2 V3 5 0 M W2 V4 10 00000 0 M W2 V5 5 0 M W3 V1 0 70 00000 M W3 V2 12 00000 0 M W3 V3 0 13 00000 M W3 V4 0 13 00000 M W3 V5 3 0 D W1 V1 27 50000 0 D W1 V2 30 30000 0 D W1 V3 23 80000 0 D W1 V4 100 0000 0 D W1 V5 28 50000 0 D W2 V1 29 30000 0 D W2 V2 31 80000 0 D W2 V3 27 00000 0 D W2 V4 25 00000 0 D W2 V5 26 50000 0 D W3 V1 100 0000 0 D W3 V2 28 30000 0 D W3 V3 27 50000 0 D W3 V4 26 80000 0 D W3 V5 24 00000 0 Row Slack or Surplus Dual Price 17 1 1628 100 1 2 0 4 3 0 0 4 0 5 5 0 35 00000 6 0 38 00000 7 0 28 00000 8 0 24 00000 9 0 31 00000 10 0 27 50000 11 0 30 30000 12 0 23 80000 13 0 100 0000 14 0 28 50000 15 0 29 30000 16 0 31 80000 17 0 27 00000 18 0 25 00000 19 0 26 50000 20 0 100 0000 21 0 28 30000 22 0 27 50000 23 0 26 80000 24 0 24 00000 对问题三 用 lingo软件求解 编写lingo程序如下 MODEL SETS AB W1 W2 W3 WI 该集合表示 3个场地 属性 WI表示各产地的 最大供货能力 18 BC V1 V5 VJ 该集合 表示 5个市场 属性VJ表示市场的 需 求 LINKS AB BC X Y C D P Q 衍生集合 LINKS有 3 5 15个成员 定义 6个与集合 LINKS有关的属性 C X M和 D 其中 D C和 P相当于 具有 15个元素的常数矩阵 X Y和 Q为决策变量 ENDSETS DATA WI 15 20 15 VJ 11 12 9 10 8 P 27 5 30 3 23 8 1000 28 5 29 3 31 8 27 25 26 5 1000 28 3 27 5 26 8 24 D 31 38 24 1000 35 36 43 28 24 31 1000 33 36 32 26 C 61 72 45 55 66 69 78 60 49 56 59 66 63 61 47 ENDDATA MIN SUM LINKS I J C I J X I J Y I J D I J P I J Q I J FOR AB I SUM BC J X I J Y I J VJ J 各市 场所需的约束 FOR LINKS BIN Q 对 X进行 0 1约束 FOR LINKS I J Q I J IF Y I J EQ 0 0 1 即约 束条件 Yij 0 则 Qij 0 END 程序结果如下 Local optimal solution found Objective value 1628 100 Extended solver steps 0 Total solver iterations 17 Variable Value Reduced Cost WI W1 15 00000 0 WI W2 20 00000 0 WI W3 15 00000 0 VJ V1 11 00000 0 VJ V2 12 00000 19 0 VJ V3 9 0 VJ V4 10 00000 0 VJ V5 8 0 X W1 V1 0 30 00000 X W1 V2 0 38 00000 X W1 V3 0 21 00000 X W1 V4 0 35 00000 X W1 V5 0 39 00000 X W2 V1 0 34 00000 X W2 V2 0 40 00000 X W2 V3 0 32 00000 X W2 V4 0 25 00000 X W2 V5 0 25 00000 X W3 V1 0 29 00000 X W3 V2 0 33 00000 X W3 V3 0 40 00000 X W3 V4 0 42 00000 X W3 V5 0 21 00000 Y W1 V1 11 00000 0 Y W1 V2 0 4 Y W1 V3 4 0 Y W1 V4 0 980 0000 Y W1 V5 0 8 Y W2 V1 0 1 Y W2 V2 0 5 Y W2 V3 5 0 Y W2 V4 10 00000 0 20 Y W2 V5 5 0 Y W3 V1 0 970 0000 Y W3 V2 12 00000 0 Y W3 V3 0 13 00000 Y W3 V4 0 13 00000 Y W3 V5 3 0 C W1 V1 61 00000 0 C W1 V2 72 00000 0 C W1 V3 45 00000 0 C W1 V4 55 00000 0 C W1 V5 66 00000 0 C W2 V1 69 00000 0 C