《【大学竞赛】数学建模 钢管订购和运输优化模型PPT.ppt》由会员分享，可在线阅读，更多相关《【大学竞赛】数学建模 钢管订购和运输优化模型PPT.ppt（32页珍藏版）》请在三一文库上搜索。
1、建模案例：钢管订购和运输优化模型 2000年“网易杯”全国大学生数学建模竞赛B 综合案例分析 葬 垢 腿 剥 绑 普 躇 她 局 颊 拥 俩 讫 昏 豆 荆 首 啡 踢 滩 寺 霄 瓷 抠 离 禽 渊 锈 拱 绥 蹈 宴 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 一.问题的提出 二.基本假设 1.沿铺设的主管道已有公路或者有施工公路. 2.1km 主管道钢管称为一单位钢管，在主管道上，每 千米卸1单位的钢管. 3.公路运输费用为1单位钢管每千米0
2、.1万元 （不足整千米部分按整千米计算） 4.在计算总费用时，只考虑运输费用和购买钢管的费用， 而不考虑其他的费用（诸如中转费用） 5.假设钢管在铁路运输路程超过1000km,铁路每增加1 至100km,1单位钢管运输的运价增至5万元. 6.订购的钢管数量刚好等于需要铺设的钢管数量 7.销售价和运输价不受市场价格变化的影响 挠 友 秃 烩 噎 矣 劣 篆 肉 久 叔 醋 蜗 吩 柞 彩 蘑 恐 篷 噎 孽 侮 负 衡 酚 瞪 犹 酬 量 胃 虫 眺 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订
3、 购 和 运 输 优 化 模 型 P P T 三. 符号说明 第 个钢厂, 第个钢厂的最大产量， 输送天然气的主管道上的第个点， 第个钢厂 1 单位钢管的销售价格， 钢厂向第个点运输的钢管数量（单位） 在点与点之间的公路上，运输点向点 方向铺设的钢管数量， 1 单位钢管从钢厂到点的最少总费用，即公路运费，铁路运费和钢管销售 之和， 与第个点相连的公路和铁路的相交点, 与第个点相连的的第m条公路和铁路的相交点, 相邻结点与点之间的距离, 橙 叭 等 如 训 谊 湛 鞠 雇 臼 雄 纽 遮 荡 蹿 标 否 天 猴 畦 掌 青 冉 勋 止 佰 净 此 饮 糜 黄 啥 【 大 学 竞 赛 】 数 学
4、建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 四. 模型的建立与求解 问题一：讨论如何调整主管道钢管的订购和运输方案使总费用最小 1.求钢管从钢厂 运到运输点的最小费用 1）将图1转换为一系列以单位钢管的运输费用为权的赋权图. 所以可先求出钢厂 到铁路与公路相交点的最短路径.如图3 由题意可知：将钢管从钢厂运到运输点的费用包括钢管的销售价格、 钢管的铁路运输费用和钢管的公路运输费用.在费用最小时，对钢管的订购和运输 进行分配，可得出本问题的最佳方案. 总费用=钢厂到各节点的费用+主
5、管道的运输（铺设费用） 阀 签 日 骨 在 娜 彬 淋 希 桂 侨 栗 喂 占 剑 靡 蚊 糜 替 们 百 髓 吾 馈 鸟 胃 峨 设 殊 铰 生 蝉 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 450 80 1150 1100 306 195 20 202 1200 720 690 520 170 690 160 88 462 70 320 160 70 290 30 锨 磅 拒 砍 楔 站 撇 惟 顺 但 螺 考 骏 劣 痪 醚 恢 准 陵 估
6、 彪 赶 模 啡 争 婿 洛 钞 便 慕 佛 有 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 图-4 迭 蔬 决 栅 棚 瑶 洼 掸 养 舷 憾 钧 玩 尧 喇 惜 烹 呻 扮 少 斟 炭 周 雹 坪 拟 蹲 甚 茹 蛰 摈 膳 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 2）计算单位钢管从到的最少运输
7、费用 根据图图4，借助图论软图论软 件包中求最短路的方法求出单单位钢钢管从到 的最短路，从而得出将单位钢管从 运输到各运输点最小费用。 运输费用依次为：170.7，160.3，140.2，98.6，38，20.5，3.1，21.2， 64.2，92，96，106，121.2，128，142（单位：万元） 加上单位钢管的销售价 得出从钢厂购买单位钢管运输到点 的最小费用依次为: 330.3，320.3，300.2，258.6，198，180.5，163.1，181.2， 224.2，252，256，266，281.2，288，302（单位：万元）. 同理，可用同样的方法求出钢厂 到 的最小费用，
8、从而得出各钢厂Si到运输节点 Aj 最小运总费用。见表1. LINGO 程序：min-cost1.lg4 计算结果：min-cost1.lgr 茶 馒 袄 暴 急 朴 膜 砖 笋 连 扫 喳 舵 肪 旋 啤 忱 撼 丢 岸 谷 例 癌 恐 田 毡 滦 锡 倚 匣 靛 壕 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 表1 Si 到点 Aj 的最小费用 2. 建立模型 运输总费用可分为两部分： 运输总费用=钢厂到各点的运输费用+主管道的运输（铺设）费用
9、. 日 涟 坞 肇 叶 哟 述 乍 桔 三 迸 咆 萍 竭 藉 承 订 克 啥 削 粤 挤 仍 践 沏 找 祷 旱 榜 俏 鹿 涵 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 边 容 条 兼 闺 弊 计 刺 桐 嗡 算 赠 钠 宴 弘 烹 债 厕 汐 累 汾 躇 揩 囊 痴 治 埋 箍 娃 到 舱 蒙 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订
10、购 和 运 输 优 化 模 型 P P T 从而得出总费用： 2) 约束条件 灯 藏 畔 阔 嗅 斥 步 祝 啄 蹿 显 掘 邪 陵 删 罗 吵 车 娩 困 伙 淌 刚 点 又 忙 缔 劫 俺 蚊 避 眯 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 因此本问题可建立如下的非线性规划模型： 非线性规划模型可用LINGO软件包或MATLAB软件包来求解，但这些软件包不能 直接处理约束条件： 可用分支定界法将此条件改为 模型变为 干 润 歌 殴 抓 贱
11、痒 使 板 鸳 衅 纳 蚁 芳 芝 稗 境 搁 蘸 墨 狈 唱 寂 为 判 揪 颓 祟 詹 般 欠 践 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 1）不让钢厂S7生产，模型变为: 狗 杀 剿 僳 水 酣 三 破 泳 殊 薛 绩 隅 原 转 栖 崔 谁 驴 杠 恿 峡 潜 惕 冲 犁 与 瘸 哉 蛔 旁 韶 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管
12、 订 购 和 运 输 优 化 模 型 P P T 计算结果：1278632（万元）（此时每个钢厂的产量都满足条件） 2）要求钢厂S7 产量不小于500个单位，模型变为: 计算结果： 1279664（万元）（此时每个钢厂的产量都满足条件）. 栖 蛀 簧 兆 搐 形 湖 娩 悲 备 祟 涂 蚕 个 臂 晨 痰 嘻 告 逻 蓄 绅 撰 征 舱 排 呐 隅 盂 噪 福 盼 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 比较这两种情况，得最优解为S7不让生产:
13、 =1278632（万元）具体的购运计划如表2： 订购 量 A2A3A4A5A6A7A8A9A10A11A12A13A14A15 S18000201133200266000000000 S28001791114295003000000000 S31000139111860006640000000 S4000000000000000 S5101503582420000004150000 S6155600000000035186333621165 S7000000000000000 表2 问题1的订购和调运方案 障 悉 挂 媒 四 麦 孵 绝 萍 淹 炽 芯 浸 操 嗅 陵 化 游 锦 嗽 捕 坍
14、 闸 掐 糊 锅 乏 糠 送 谈 迈 摸 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T fi表示钢厂i是否使用；xij是从钢厂i运到节点j的钢管量 yj是从节点j向左铺设的钢管量；zj是向右铺设的钢管量 比较好的方法：引入0-1变量 LINDO/LINGO 得到的结果比 matlab得到的好 yj zj j GUANDAO.lg4 参考程序 术 镶 轴 睫 溪 沧 擅 诈 淡 些 铭 粤 跳 讨 条 黄 葫 版 龋 贩 央 刊 蒙 劲 那 甫 痴 陪
15、 兹 驻 珠 挣 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 1）运输问题的0-1规划模型 将全长5171km的管道按公里分段，共5171个需求点 ，钢厂为7个供应点，构成如下的运输问题 cij为从供应点i到需求点j的最小购运费 xij=1表示从点i到点j购运1单位钢管 求解时要 针对规模 问题寻求 改进算法 Cij 规模太大麻烦 修 坚 匠 陋 肿 衡 崎 一 沏 步 硕 间 谰 伪 杯 害 严 斤 脆 士 摘 葱 硷 荡 卿 霉 梯 缸 劫 唬
16、 两 岔 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 问题二、就（1）的模型分析：哪个钢厂钢管的销价的变 化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上 限的变化对购运计划和总费用的影响最大，并给出相应的数 字结果. 由于钢厂钢管的销售价格变化和钢厂钢管产量的上限变化对购运计划和总费用 造成影响，为更好地考察影响，下面分别进行讨论 方案中运往各点的运输量的变化量的绝对值之和称为运输方案变化量 1）讨论钢厂钢管的销售价格变化对购运计划和总费用的
17、影响 当钢厂钢管的销售价格 变化时，会对购运计划和总费用造成影响。为更好 地观察每一个钢厂的销售价格 变化时所造成的影响，本问题采用比较法。即 ：每次只让一个钢厂钢管的销售价格发生相同的变化，其余钢厂钢管的销售价 格不发生变化；当每个钢厂的销售价个发生同样的变化 C 时，求出相应的总 费用，然后比较。 分析： 锗 扦 醉 寝 然 莉 总 揪 璃 金 卵 欠 无 序 飞 嘲 弯 负 劣 扒 孔 荐 梢 埂 雌 信 戚 徘 沉 豪 插 卤 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运
18、输 优 化 模 型 P P T 表3 C=-5 表4 C=5 犯 椿 陋 吁 谗 买 羔 欠 离 坞 茹 仟 峨 法 哼 巨 喘 膛 利 毗 啮 嫁 粪 盖 韦 怨 粥 葡 盛 催 造 汕 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 表5 C=1 表6 C=-1 从上述四个表格中可以看出：钢厂钢管的销售价格变化时，S6对总费用 影响最大，S5对购运计划影响最大。 旗 围 执 阉 归 恒 岿 孕 情 降 桐 松 拼 湍 殷 蹭 乎 衬 援 猎 竿 按
19、 礼 翠 促 钞 氯 释 纯 描 盟 敲 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 2) 讨论钢厂产量的上限变化对购运计划和总费用的影响 本问题同样采用比较法。即：每次只改变一个钢厂钢管产量的上限，其余 钢厂钢管产量上限不发生变化的情况，利用问题一中的模型进行讨论。 a. 对产量不受限制的情况计算得到下表 表7 产量不受限制的情形 b. 对产量下降100的情况计算得到下表 表8 产量下降100的情况 苏 料 矣 鞘 疥 肮 惩 变 础 还 哮 桂
20、 官 鹤 蛇 茬 虞 酿 磊 艺 败 嗅 狼 枯 缄 释 防 崎 钾 汗 虎 相 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T c.对产量升高100 的情况计算得到下表 表9 产量升高100的情况 结论：从上述表格中可以看出钢厂钢管产量的上限变化时，S1对 总费用和购运计划影响最大。 问题三、讨论铁路、公路构成网络的情形 本问题是讨论铺设的管道是树形图，铁路、公路构成网络的情形，对于这种 问题的求解过程，以图-2进行说明。 坦 渴 直 幌 朵 喊 凑
21、 令 岗 或 百 普 茬 蓬 举 箕 循 篆 柄 爽 茂 妓 城 社 妒 编 网 诗 祟 镜 赏 嫡 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 1. 铺设管道是树形图时，基本解法原理 图-3 A1 3 2 5 80 10 10 31 20 12 42 70 10 88 10 70 62 70 30 20 20 30 450 104 301 750 606 194 205 201 680 480 300 220 210 420 500 600 30
22、6 195 202 720 690 520 170 690 462 160 320 160 110 290 1150 1100 1200 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 S1 S2 S3 S4 S5 S6 S7 粮 件 羌 瞎 寨 狂 滑 眠 搓 树 瀑 忽 买 麓 撬 谩 拌 邦 齿 厄 申 妥 澎 阎 姐 瘩 卸 纂 着 配 炎 送 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 为求
23、出一般由铁路、公路、管道构成网络情况下的最优购运和最小总费用 方案，首先必须求出各钢厂到个管道节点的最短费用路径。由于在途中可能 发生火车汽车火车的转运方案，而这种情况发生的前提条件是公路 （或管道）的两端必须都是火车站点，由于铁路运输的费用是分段函数，故 求各钢厂到各管道结点的最小费用步骤如下： 1）首先找出公路的两个端点都是火车站站点的结点V1,V2,Vs 2) 把公路网和铁路网分开，分别组成网络； 3）在铁路网中求出各钢厂Si及各点Vi到各火车站点的最短路，并把它转化 为最小费用路 4)在公路网中求出各管道结点到各火车站点的最短路，并把它转化为最小 费用路 5）把前面的结点合并成一个网络
24、，分别求出各钢厂Si 到各管道结点的最小 运输费用路。并求出各钢厂 Si到各管道结点Aj的最小费用，由此可得到 最小费用 Aij 见下表 逝 岩 崔 撬 褥 洪 裔 具 濒 殷 杰 鸽 伪 堰 此 抱 垂 辕 旨 骡 催 哈 值 准 彬 塌 天 丹 伐 硒 婿 蒋 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 10.430.175 0.3 205 (1)(2)(3) S2(34) (22) (23) 190 0.2 (4) (24) 60 125 (
25、5) 60.6 1 (25) 110 (6) 19.4 0.5 95 (26) 1 (27) (28) 3.1 (7)(8) 20.5 20.1 1.2 (29) (9) 68 (16) 4.2 (30) (10) 7 48 (11) (17) (18) (12) 30 1 13 7 (19) 19 (13) (20) (21) (14) (15) (31) (32)(33) 1 222142 50 26 6.2 11 3 22 190190 175 180 165 10 85 85 70110135 145 150 145 程序：min-cost 2.lg4 侨 褒 诽 肾 蛛 赤 吏 狭
26、尧 锹 米 敝 灭 绘 葫 挡 愉 元 按 刮 荐 粥 善 坍 员 帘 涸 剥 臼 美 孵 散 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 未 寿 蔚 随 腊 梧 看 延 费 雀 熄 浇 打 主 庞 掖 姜 硅 拍 蓬 而 旁 蓖 庶 付 徒 花 踞 夷 悯 龟 隔 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P
27、P T 2.一般模型 故有： 辉 交 拽 组 阻 仇 齐 狠 羹 碳 现 愿 逃 颖 榆 桥 梯 何 的 篆 棍 枷 紫 掸 达 烁 谗 充 瑟 剖 讽 粤 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 糕 钓 砰 娘 子 彬 荷 钩 里 钵 湛 茧 朴 窑 姓 稚 包 航 慷 爬 简 合 拥 麓 衙 绷 婉 眶 坷 尽 晕 吧 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数
28、 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 3.问题三的求解 融 一 耳 媳 煎 通 差 岳 厕 匪 内 睡 悄 鸳 乙 里 杨 庸 静 蝉 乞 保 淳 颜 溃 蘸 徽 轧 珍 涕 卞 缄 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 槛 苟 辙 罪 腔 愚 沁 惫 泼 署 钳 偶 贼 捷 没 绎 乒 滩 迟 如 饱 盛 屎 篮 适 皋 乘 矾 岿 讥 嚼 谰 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运
29、输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 1）不让钢厂S7生产，计算结果为: 1405611（万元）（此时每个钢厂的产量都满足条件） 2）要求钢厂S7 产量不小于500个单位，计算结果为: 1405197（万元）（此时每个钢厂的产量都满足条件）. 比较这两种情况的最优解: 其订购方案见表11 和表12 昆 尘 振 氟 王 性 醚 容 娄 驻 驳 潍 仓 协 褐 楞 陕 熔 帆 柬 汗 员 奢 黍 洁 呛 久 撼 稽 鼓 饱 吮 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型
30、 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 锚 袁 轧 侣 桶 坞 钾 律 御 胸 桩 胶 城 酱 淫 未 擎 嗽 驮 掷 付 懦 翘 鱼 捻 锚 供 房 屋 毙 使 渺 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 70 10 88 10 70 62 300 220 210 170 690 462 160 320 160 A10 A11 A12 S4 S5 S6 130 A17 A18 A19 A20 190 260 100 (jk)是连接Aj,Ak的边，E是树形图的边集， ljk是 (jk)的长度， yjk是由Aj沿(jk)铺设的钢管数量 模型简单表示 勒 钢 遇 肆 资 剧 莎 受 能 衰 逻 窒 拍 溪 乃 他 湾 悉 嚎 汹 喘 搓 趟 速 制 祝 鞘 芥 卿 毙 促 言 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T 【 大 学 竞 赛 】 数 学 建 模 钢 管 订 购 和 运 输 优 化 模 型 P P T