《全国大学生数学建模竞赛 铺路最小费用的优化模型》由会员分享，可在线阅读，更多相关《全国大学生数学建模竞赛 铺路最小费用的优化模型（9页珍藏版）》请在金锄头文库上搜索。
1、1 铺路最小费用的优化模型 摘要 本文对如何在 地与 地之间修建一条地下管线的问题，结合题目中所给 地与 A B A 地的方位数据、地质带的走向、不同地质带的分布与不同地质带下地下管线的造价 B 等条件就最便宜的管线铺设路线进行研究。 问题一：引入平面向量的知识建立了从A到B所化最小费用的优化模型。 问题二：根据题目要求，管线时管线转弯角度至少为 ，结合三角几何与平面向 o 155 量建立了一个非整数线性规划模型，利用 软件解得最便宜的管线铺设路线的造价 lingo 为： 万元 56 . 369 S 利用 软件做出路线图（在正文中） ，最便宜的管线铺设路线为： matlab 0 , 30 6
2、, 521 . 17 9 , 266 . 15 11 , 733 . 14 14 , 478 . 12 20 , 0 B S R Q P A 问题三：在问题二的基础上，并加入铺设管线时要求管线必须通过点P 的新条件， 分阶段考虑全过程建立了一个新的非整数线性规划模型，利用 软件解得最便宜的 lingo 管线铺设路线的造价为： 万元 33 . 372 S 利用 软件做出路线图（在正文中） ，最便宜的管线铺设路线为： matlab 0 , 30 6 , 111 . 22 9 , 233 . 20 10 , 20 11 , 719 . 19 14 , 287 . 17 20 , 0 B T Q P
3、S R A 由于模型未考虑到时间因数，因此我们在模型推广中建立了在一定工期内完成工作 且要求费用最小的模型，此时的模型更加完善，且符合现实与社会的要求。 关键词 非整数线性规划模型 软件 软件 三角几何 平面向量 时间因数 lingo matlab2 一、问题重述 准备在A 地与B 地之间修建一条地下管线，B 地位于A 地正南面 20km 和正东 30km 交汇处，它们之间有东西走向岩石带。地下管线的造价与地质特点有关，下图给 出了整个地区的大致地质情况，显示可分为三条沿东西方向的地质带，其宽度分别为： 沙土地质带宽C 1 ，沙石地质带宽C 2 ，岩石地质带宽C 3 。 (1)试建立一个数学模
4、型，确定最便宜的管线铺设路线。 (2) 在给定的数据的情况下铺设管线时，如果要求管线转弯时，角度至少为 ， o 155 确定最便宜的管线铺设路线，使得费用最小。 (3) 铺设管线时，如果要求管线必须通过位于沙石地质带或岩石地质带中的某一已 知点P（位于A 地正南面 10km 和正东 20km 交汇处）时，确定最便宜的铺设路线。 二、模型假设 1、不考虑时间因数，只须付铺设管道的费用其他的费用均不考虑，时间过长造 成的损失也不考虑。 2、施工队有足够高的水平能按照施工计划进行施工，能够精确的到达预定的地 点。 3、在施工的这段时间里所须的材料不会涨价也不会跌价。 4、各种岩层的排部是均匀且清晰的
5、，在交接处不会参差不齐也不会混合在一起。 5、每种岩层的的内部施工难度是一样的。 三、符号说明 ：从起始点到目标点的水平方向总距离 X ：从起点到目标点的竖直方向的距离 Y ：地质带的总数 m ：相应的每一个地质带中的管道长度 i l ：每一段沿东西方向的地质带 i C ：相应的每一个地质带中的管道的造价 i Z ：每段 相应的方向向量坐标的横坐标 i x i l ：每段 相应的方向向量坐标的纵坐标 i y i l :第三问中第一阶段的起始点到目标点的水平方向的总距离 1 X :第三问中第二阶段的起始点到目标点的水平方向的总距离 2 X :第三问中第一阶段的起始点到目标点的竖直方向的总距离 1
6、 Y :第三问中第二阶段的起始点到目标点的竖直方向的总距离 2 Y3 ：管道铺设路线的最小费用 S 四、建立模型与模型求解 第一问： 由于各种岩层的铺设难度不同费用不同，从而导致在铺设管道时不能单纯的考虑 价格问题或最短路径问题，需要结合考虑，应此尽考虑了距离的方按一可能不是最便 宜的路径，而方按二，仅考虑到价格问题，在铺设相对较贵的岩层时按最短的路径铺 设，而忽略了较便宜的岩层的花费，应此两种方按都不一定是最好的决策。 就此情况下，我们建立了一个最优化问题的连续模型，因为起点A与终点B都以 确定考虑的就是中间过程怎么决策。 在铺路中设每一段沿东西方向的地质带为 。相应的每一个地质带中的管道长
7、度 i C 为 ，造价为 。则目标函数取得最便宜的管道铺设路线 可表示为： i l i Z Si m n i l Z s 1 min 为地质带总数目 m 接着引入倒直角坐标系，设每段 相应的方向向量为 则其坐标 ,则由 可表 i l i r i i y x , i l 示为： 2 2 i i i y x l 且有： 的水平方向总距离 表示从起始点到目标点 X X x m n i 1 的垂直方向总距离 表示从起始点到目标点 Y Y y m n i 1 综上所述模型为：i m n i l Z s 1 min 为地质带总数目 m 0 , 0 . 1 1 2 2 i i m n i m n i i i
8、 i y x Y Y y X X x y x l t s 的垂直方向总距离 表示从起始点到目标点 的水平方向总距离 表示从起始点到目标点 第二问： 模型二中设每一段沿东西方向的地质带为 。相应的每一个地质带中的管道长度 i C4 为 ，造价为 。则目标函数取得最便宜的管线铺设路线的造价 可表示为： i l i Z Si m n i l Z S 1 min 为满足铺设管线时管线转弯时角度至少为 ，则出现如下图的两种情况： o 155图一 图二 则当出现向内转弯，如图一的情况时有： o 25 1 2 0 当出现向外转弯，如图二的情况时有： o 25 2 1 0 将以上两种情况推广并结合题目与所给数
9、据，如表一： 地质条件 沙土 沙石 岩石 费用(万元/千米) 8 12 28 宽度（千米） 6 3 2表一 结合模型一最终得到一个非线性整数规划模型：i n i l Z s 5 1 min 0 , 0 25 ) 1 ( 0 25 ) 1 ( 0 . 5 1 5 1 2 2 i i n i n i i i i y x i i i i B A Y Y y B A X X x y x l t s 当出现向内转弯时 当出现向内转弯时 的垂直方向总距离 到 表示从 的水平方向总距离 到 表示从 o o O 1 2 X1 1 2 2 1 Y O 1 2 X1 1 2 1 2 Y 5 最后经 编程（程序见附
10、录1）得： lingo 万元 56 . 369 S 具体结果如下表： 沙土 沙石 岩石 沙石 沙土 总值 水平分量长度 12.479 2.255 0.533 2.255 12.479 30 垂直分量长度 6 3 2 3 6 20 实际长度 13.846 3.753 2.070 3.753 13.846 37.268 造价（万元/千米 8 12 28 12 8 实际造价 110.770 45.035 57.954 45.035 110.770 369.563 注：所有数据都保留小数点后三位有效数字。 表二 用结合 得最便宜的管线铺设路线如下图所示： matlab 注： 程序见附录二。 matla
11、b 第三问: 引用第二问中的模型并加入限制条件：铺设管线时要求管线必须通过位于沙石地 质带或岩石地质带中的某一已知点P（位于A 地正南面 10km 和正东 20km 交汇处） ， 则把铺设管线分为两个阶段具体如下： 点的水平方向总距离 到 表示从 p A X X x n i 1 1 3 1 6 的水平方向总距离 点到 表示从 B p X X x n i 2 2 3 1 点的垂直方向总距离 到 表示从 p A Y Y y n i 1 1 3 1 的垂直方向总距离 点到 表示从 B p Y Y y n i 2 2 3 1 综上所述得到一个非线性整数规划模型：i n i l Z s 6 1 min
12、0 , 0 25 ) 1 ( 0 25 ) 1 ( 0 . 3 1 2 2 3 1 1 1 3 1 2 2 3 1 1 1 2 2 i i n i n i n i n i i i i y x i i i i B p Y Y y p A Y Y y B p X X x p A X X x y x l t s 当出现向内转弯时 当出现向内转弯时 的垂直方向总距离 到 表示从 的垂直方向总距离 到 表示从 的水平方向总距离 到 表示从 的水平方向总距离 到 表示从 o o 用 编程（程序见附录三）得最终的结果为： lingo 万元 33 . 372 S 具体结果如下表： 沙土 沙石 岩石 p点处 总
13、值 岩石 沙石 沙土 总值 水平分量长度 17.287 2.432 0.280 20 0.234 1.878 7.888 30 垂直分量长度 6 3 1 10 1 3 6 20 实际长度 18.299 3.862 1.039 23.200 1.027 3.539 9.911 37.677 造价（万元/千米） 8 12 28 28 12 8 实际造价 146.39146.34729.080221.817 28.753 42.472 79.288372.330 注：所有数据小数点后三位有效数字 结合 得最便宜的管线铺设路线如下图所示： matlab7 注： 程序见附录四。 matlab 五、模型检
14、验与推广 当今时代是争分夺秒的时代，时间就是金钱，在许多的重大施工项目中，首要问 题不仅仅是费用，还要考虑时间，考虑如何如期完工，而此模型仅考虑了费用情况而 没有考虑到时间因素。不同的岩层施工进度也不一样，因而不同的施工方案所需的时 间也不尽相同，就此我们将时间因素也考虑在内的话，那么此模型将变得更加符合时 代的要求。 假设铺设管道的最长时间不能超过 ； T 各种岩层的施工进度分别为：沙土 ； 沙石 ； 岩石 。 1 V 2 V 3 V 在每一阶段所花费的时间为： i i i V l t 由于工期不得大于 ，所以有 T T V y x m i i i i 1 2 2 因此在考虑到工期的时候，模型为：
