油井维护的设置调度与原油运输的网络设计

1、2015年成都理工大学 校内数学建模竞赛论文 题目 编号 B 队编号 88 参 姓名 学号 专业 赛 张萌立 计算机科学与技术 队 何理 空间信息与数字技术 员 何龙 六白住白匕拓心七士*_ 1 亠 | ij | m j 匕、一寸 3 一 0一五年五月一十五日 队编- 号：88 B题油井维护的设置调度与原油运输的网络设计 摘要 本文讨论了如何设置油田维护班、油田维护班与其管辖范围 内的油田采集点的关系以及维护班的调度、原油的运输以及其最 优解的问题。实质上是关于多目标的优化问题。根据题中所给的 条件和问题汲取相关的约束条件和目标函数，建立模型。 对于问题一，是关于油田维护班的分配管辖范围问题，

2、首先 在MATLAB环境下采用Floyd算法求出任意油田维护班与采集点 之间的最短距离，从中提取92*20的矩阵，在引入0-1规划模型, 然后建立以总路程最小为目标函数，以各个维护班工作量均衡为 约束 条 件， 建立 优化 模 型 ，使用 Matlab 编 程实 现 区域的 自 动 划 分。 对于问题二，是关于如何在 13 个采油点同时发生事故时 ， 调度 20 个维护班维修，以一个采油点当 且仅当 与一个维护班相 匹配为约束条件，以维护班到达花费时间最小为目标函数，采用 Hungary 算 法，建 立 相 关模 型， 并用 Matlab 编 程 ，求出 最 优解 ， 并画图。 对 于 问 题

3、三 ，如 何 设 计将部 分 现有 道 路 修建 为 高等级 公 路 以 快速运输原油，实际上是一个关于路线选择的最优化模型。以原 油运输费用与修路费用之和达到最少为目 标函数，采用 Floyd 算 法并在两 点之 间根 据油的 可采储量 进行 平均加 权 ，再用 Matlab 编程，求 出路 线，设 计出 最优 路线方 案。 用原 油可采储量 的 10 倍为加权条件，求出路线，设计出另一个最优路线方案。 对于问题四，如 何根据现有道路修建管道路线，使 修建管道 的费用最少，因为管道输油的成本可以忽略不计，实际上是只要 使得管道路线的总长度最小，就能达到成本最少的目标。以总长 度最 小 为目

4、标函 数， 采 用 Floyd 算 法， 用 Matlab 编程， 求 得 最 短路径，设计出原油运输方案。 关键 字 ： Floyd 算 法 Hungary 算 法 MATLAB 0-1 规 划 最短路径 B题油井维护的设置调度与原油运输的网络设计 一、问题重述 试就某油田设置维护班组和原油运输的相关情况建立数学模型分析研究 下面问题： （1）附件1中的附图给出了某油田A区的交通道路和现有的20个维护班 组的设置情况示意图，相关的数据信息见附件2o维护班组每天的工作是 巡视其管辖范围内的采油井，请为20个维护班组合理分配管辖范围，使 各维护班组的工作量尽量均衡，且在其所管辖油井发生事故时能尽

5、快到 达。 （2）假设13个采油点同时发生漏油事故，需要调度20个维护班组实现 快速维修，恢复生产。实际中一个班组最多维修一个采油点，一个采油点 也仅需一个班组维修，为了尽量减少漏油损失，请给出20个维护班组的 合理调度方案。（注：假设采油点的原油开采速度与可采储量成正比） （3）为了将各采油点的原油快速运输到0点（坐标原点），计划将部分现 有道路修建为高等级公路，作为原油的运输专线。假设公路修建及采油期 内的养护成本合计为1百万/公里，公路运输成本为0.1百万/万吨公里， 请设计一个合理的公路运输网络，使得修路和运输成本最小。再假设经过 勘查，各采油点的可采储量增长了 10倍，请重新设计一个

6、合理的公路运 输网络。（注：假设各采油点均可修建直线到达O点的公路） （4）管道输油具有建设成本高、输油成本低的特点。假设输油管道的修 建及采油期内的养护成本合计为1千万/公里，输油成本忽略不计，且管 道只能沿着现有道路修建。请对比公路运输分析修建输油管道的经济性， 设计一个合理的原油运输方案。再假设经过勘查，各采油点的可采储量增 长了 10倍，请重新设计一个合理的原油运输方案。（注：假设各采油点均 可修建直线到达O点的输油管道 二、问题分析 因为油田维护班组的职能和人员配置基本相同，所以要考虑每个油田 维护班组工作量的均衡下能在最短时间内到达突发事件现场，主要考虑的 方向是各个维护班组管辖范

7、围内采油点发生事故时赶往总的时间最短（最 短时间转化为最短路程）与均衡每个采油点的事故率这两个因素，显然， 这是个双目标问题，为了求解方便，把双目标函数单一化，将各个维护班 组管辖范围内的采油点事故率均衡转化为约束条件建立模型，进而划分出 区域。其中，我们引入了 0-1规划模型，采用弗洛伊德算法求出图中任意 两个站点之间的最短距离，在根据所建立的模型划分出具体区域。具体做 法如下： 1.1 ）、首先，依据附录中92个节点的横纵坐标，使用MATLAB编程， 进而将每个节点标号、连线。如图2-1所示： 图2-1 采油点之间的路线图 1.2 ）、再用期=少厂叩+ g “公式算出两点之间的距离（如果有

8、路）， 得 出 92*92 的 邻 接 矩 阵 ， 其 中 矩 阵 中 的 元 素 表 示 两 两 之 间 的 距 离 ， 若 不 存 在路 ，则 用一 个无 限大 的数 来代 替， 在 MATLAB 环境 下利 用弗 洛伊 德算 法 求出 两两 之间 的最 短路 径和 最短 路程 ，然 后 从中 抽取 92 个 节点 分别 到 20 个维 护班 组站 点的 最短 距离 。（程 序见 附录 3） 1.3 ）、引 入 0-1 规 划变 量， 然后 以 92 个节 点分 别到 20 个 维护 班组 站点 的 最短 距离 。（ 程序 见附 录 4） 1.4 ）、使用MATLAB编程，将区域划分的最终

9、结果输出。 1.5 ）、 在 根据 工作 量均 衡度 做管 辖范 围的 调 整。 2.1 ）、 对 于如 何在 13 个 采油 点同 时发 生事 故时 ， 调 度 20 个维 护班 维修 的 问题 ， 我 们考 虑， 因为 油田 一直 在漏 油， 为了 将 经 济损失降低 到最 小， 当 一个 维护 班组 附近 出 现 两个 漏油 点时 ， 维 护 班组 如何 抉择 ， 我 们引 入权 ， 其大 小就 是维 护班 组到 漏油 点的 距离 s 乘 以 漏油 点的 储油 量， 这样 才能 在 各个维护班组到达漏油点时将损失降到最小。 2.2） 、再用 弗洛 伊德 算法 进行计算 时 需要 知道 给

10、定 的 矩 阵，我 们 这样构建 ， 取 出 20 个 维 护 班 组 和 13 个 采 油 点 的 坐 标 ，对 两 点 之 间 的 距 离 加 权 ，用 Qij 代替 ， 从 而建 立 20*13 的 矩 阵， 矩阵 中的 元 素即 是权 Qij 的 大 小（ 经济 损 失最 小就 转化 为了 距离 最小 ），建立 模型后，用 matlab 编 程，采用 Hungary 算法 （程 序见 附录 2）， 求 出 如何调 度 20 个维 护班组（ 程序见附 录 5）， 才 能使 损失 达到 最小 ， 并 将结 果输 出 。 3.1 ）、 这 一问 是高 等级 公路 的 修 建， 要求 是 公路

11、 修建 与养 护及 原油 运输 资 金总 和最 小， 这和 第二 问相 似的 地方 就是 前 者是资 金损耗最小 ， 因此这 一 问可 以用 第二 问的 方法 ， 只 不过 就是 权值 改 变了， 此 时权的 大 小就用 总 资 金 Fij 来 表 示 ， 3.2 ）、 但 这只 是两 点之 间的 加权 路径 最短 ， 我 们 要修 建的 是公 路网络， 这 样， 可以 循环 求出 92 个 采油 点到 原点 的 最 短加 权路 径， 把 92 条加 权路 径 综合 起来 就是 我们 要求 的 公 路网 络， 这样 就 能保证 把所有采油 点的 油送 到 原点 时公 路修 建以 及原 油运 输

12、的 总费 用 最 少 。 3.3 ）、利用 matlab 编 程（ 程序 见附录 6），建 立 93*92 的 矩阵 ，利用 Hungary 算 法得 到 任 意 一 点 到 23 点 的 最 小 加 权路 径 ， 循 环 得 到 公 路 网络 ， 并 用 matlab 将 得到的 公路网络 画出 来。 3.4 ）、 当 油田 的 储 油量 增加 到 10 的 时 候 （程 序见 附录 6）， 只 是在 建立 模 型时 ， 两 点之 间的 权值 改变 ， 此 时， 矩阵 中 的元素 用 新得到的 权值 Tij 来 代替 ， 重 复上 述方 法， 得到 新的 公路 网络 。 4.1 ）、 当 用

13、 管 道输 油时 ， 输 油成 本可 以忽 略 不计 ， 管 道修 建费 用 就 只与管 道的 总长 度有 关了 ， 和 第三 问的 算法 相似 ， 经 济费用 最小就转 化为了总 路 径长 度最 小。 4.2 ）、 将 两点 之间 的 路 程作 为权 Rij 赋 值给 两点 之间 的 距 离， 建立 93*92 的 矩 阵 ， 利 用 Hungary 算 法 得 到 任 意 一 点 到 23 点 的 最 小 加 权 路 径 ， 循 环 得到 公路 网络 ，并 用 matlab 编 程（ 程序 见 附录 7）将 得到 的 公 路网 络画 出 来。 4.3 ）、 当 每个 采油 点的 储油 量增

14、 加到 十倍 时， 这 对新 路线的 规 划 并没有 任 何影 响， 因为 此时 输油 管道 的 修 建总 费用 只 与路线 的 路程 有关 ， 与各个 采 油点 的 储 油量 并不 相关 ， 这 样储 油量 对两 点 距离的 权值无影响 ， 因此得 到 的 新 的 规 划 路 线不 变。 三、符号说明 符号 描述 (X, Y) 第i节点坐标，单位mm Dj 第i个节点到第j个节点的最短路径，单位 mm A 第i个油田维护班组的位置标号 U 第i个油田维护班组的管辖节点集 W 第i个油田维护班组的工作量指标 油田维护班组的平均工作量 E 油田维护班组工作量的均衡程度 Cp 第i个油田维护班组所

15、覆盖的路口数量 Cp 第i个油田维护班组所覆盖的路口数量 Qij 第i个维护班组到第j个米油点的距离和米油点j的储油量的乘积 Fij 将第i个采油点的储油运到第j个采油点时，公路修建和原油运输的 总费用 Tij 将第i个采油点的储油运到第j个采油点时，公路修建和原油运输的 总费用 Rij 原油从采油点i运到采油点j的最短路径的长度 Gn 每个采油点到第23个采油点的加权路径 Kn 每个采油点到第23个采油点的路径长度 四、模型建立 模型一的建立 该题要求为各油田维护班组分配管辖范围，要求各个维护班组能以最 快的速度到达突发事件的地点，所以我们要考虑路线问题，选择最优路线， 因此，我们建立了以最

16、短路程为主要目标，以维护班组管辖范围内的事故 率均衡为限制条件的模型来划分区域。因此，建模如下（代码见附录4） 目标函数： 约束条件: 第i个采油点到第i个和护点._. 第i个采油点不到第i个那护点】=1,m92j 模型二的建立 该题要求调度20个油田维护班组对发生漏油事故的13个采油点进行 紧急维修，且一个油田维护班组仅且只能维修一个采油点，当一个维护班 组附近发生多起漏油事故无法抉择时，我们引入抉择机制， 根据假设采油点的原油开采速度与可采储量成正比，由此可根据维修班组 到采油点的距离计算采油点在漏油期间未采油的损失，为了让13个漏油 点的总损失到达最小，以此建立一个20*13的矩阵，矩阵

17、中的每个元素我 们用权值来表示，权值的大小为距离与储油量的乘积，这样就转化为最优 路径问题，因此，根据Hungary算法，建立模型如下(程序见附录5)： 目标函数： V= u = i 1 表征第j个维护班组到第i个漏油点的加权距离 模型三的建立 要求在现有部分道路的基础上修建高等级公路，来将各个采油点的 储油运到远点，而原点可以直接修通往任意一个采油点的公路，我们可以 将问题划分92个相同的小问题，就是每个采油点到采油点23的最短加权 路径，因为，23是距离远点最近的点，而且原点与23点的直线距离最短。 然后再综合这92条最短加权路径，就能得到最优的公路线路网。而每个 采油点储油量增加到十倍后

18、，只是权重发生变化，函数模型并不会改变， 因此，根据Floyd算法，建立模型如下： 目标函数： 92 V MlN(Gn) 1 九表征的是每个采油点到第23个采油点的加权路径 模型四的建立 要修建各采油点到原点的输油管道，权重只与距离相关，和第三问 类似，我们可以将问题划分92个相同的小问题，就是每个采油点到采油 点23的最短路径，因为，23是距离远点最近的点，而且原点与23点的直 线距离最短。然后再综合这92条最短路径，就能得到最优的公路线路网。 而每个采油点储油量增加到十倍后，只是权重发生变化，函数模型并不会 改变，因此，建立模型如下： 目标函数 92 丫陋111（叫） S m 1 叫表征的

19、是每个采油点到第23个采油点的路径长度。 五、模型求解 模型一的求解 用matlab 求解（程序见附录）得出结果，各个维护班组对应管辖范 围内的采油点如表3-1所示： 表3-1每个维护班组及其管辖范围内的采油点 维护班组 所管辖节点 1 1 67 68 69 71 73 74 75 76 78 2 2 39 40 43 44 70 72 3 3 54 55 65 66 4 4 57 60 62 63 64 5 5 49 50 51 52 53 56 58 59 6 6 7 7 30 32 47 48 61 8 8 33 46 9 9 31 34 35 45 10 10 11 11 26 27

20、12 12 25 13 13 21 22 23 24 14 14 15 15 28 29 16 16 36 37 38 17 17 41 42 18 18 80 81 82 83 19 19 77 79 20 20 84 85 86 87 88 89 90 91 92 表3-2 油田维护班组到其管辖范围内的各采油点的距离 维护班组 油田维护班组到其管辖范围内的各米油点的距离 1 0 16.19 12.07 5.00 11.40 10.30 6.27 9.30 12.84 6.40 2 0 36.82 19.14 8.00 9.49 8.60 16.06 3 0 22.71 12.66 15.2

21、4 18.40 4 0 18.68 17.39 3.50 10.31 19.36 5 0 5.00 8.49 12.29 16.59 11.71 20.84 23.02 15.21 6 0 7 0 5.83 11.40 12.81 12.90 41.90 8 0 8.28 9.30 9 0 20.56 5.02 4.24 10.95 10 0 11 0 9.00 16.43 12 0 17.89 13 0 27.08 9.06 5.00 23.85 14 0 15 0 47.52 57.01 16 0 6.08 11.18 34.06 17 0 8.50 9.85 18 0 8.06 6.71

22、 10.79 5.39 19 0 9.85 4.47 20 0 11.75 4.47 3.61 14.65 12.95 9.49 13.02 15.99 36.01 在此，我们首先给出工作量指标的定义， 工作量，=油田维护班组到各采油点的距离 之和。由定义，第i个交巡警服务平台的工作量为： wi=Z ii iuu： 则油田维护班组的平均工作量为： 20 W = 20 工作量均衡程度可用各维护班组与平均值的偏离程度，即维护班组工作量的方差 2 之和来表示：E（Wi W）。其中，E表示油田维护工作量的均衡程度。 i 可计算出上述划分方案中所有油田维护班组的工作总量为1055.155 （单位）由表3

23、-1和表3-2中数据可知，维护点1、2、5、20工作量较大， 而维护点0、12管辖范围内的节点过少，只有它本身，说明此方案在工作 量均衡性方面存在很大问题。 由表2中的结果可知，整个辖区的划分结果中，始终有六个路口节点（28、 29、38、39、61、92 ）到服务平台的距离较大。 我们以维护点到采油点的总距离为均衡条件对表一种的结果进行调 整，调整的步骤如下： （1）对维护点1、2、5、20中的所有采油点重新调整，先计算出它到 20个维护班组距离； （2）对于距离较小的所有采油点，该节点优先划分到包含节点数最少 的那个维护点的管辖范围； （3）如果距离较小的所有维护班组包含的节点数相等，则优

24、先选择距 离最近的那个维护班组。 维护班组 管辖区域内米油点 1 1 67 68 69 71 73 74 2 2 39 40 43 44 70 72 3 3 54 55 65 66 4 4 57 60 62 63 64 5 5 49 50 51 52 53 56 6 6 7 7 30 32 47 48 61 8 8 33 46 9 9 31 34 35 45 10 10 11 11 26 27 12 12 25 13 13 21 22 23 24 14 14 15 15 28 29 16 16 36 37 38 17 17 41 42 18 18 80 81 82 83 19 19 77 79

25、 20 20 84 85 86 87 88 89 经过调整后，油田维护班组到其管辖范围内的各采油点的距离如表 3-4所示: 表3-4 调整后油田维护班组到其管辖范围内的各采油点的距 离 维护班组 维护班组到米油点的距离 1 0 16.19 5.00 11.40 10.30 6.27 9.30 2 0 36.82 19.14 21.06 8.60 16.06 3 0 11.63 22.71 12.66 15.24 18.40 4 0 18.68 17.39 3.50 10.31 19.36 5 0 5.00 16.59 11.71 20.84 23.02 6 0 14.87 22.75 18.9

26、5 16.03 7 0 5.83 11.40 12.90 41.90 8 0 8.28 9.30 9 0 20.56 5.02 4.24 10.95 10 0 35.38 11 0 16.43 12 0 17.89 13 0 9.06 5.00 23.85 14 0 32.65 15 0 47.52 57.01 16 0 6.08 11.18 34.06 17 0 8.50 9.85 17.91 18 0 6.71 10.79 5.39 15.23 19.53 24.27 19 0 9.85 4.47 14.32 11.18 8.94 20 0 4.47 3.61 14.65 12.95 9.

27、49 36.01 可以看出虽然总工作量增加了，变成了 1134.41 但是各个维护点的工 作均衡程度改善了 57.99%。 因此最后结果如表3-5所示： 维护班组 管辖采油点 1 1 67 68 69 71 73 74 2 2 39 40 43 44 70 72 3 3 54 55 65 66 4 4 57 60 62 63 64 5 5 49 50 51 52 53 56 6 6 7 7 30 32 47 48 61 8 8 33 46 9 9 31 34 35 45 10 10 11 11 26 27 12 12 25 13 13 21 22 23 24 14 14 15 15 28 29

28、 16 16 36 37 38 17 17 41 42 18 18 80 81 82 83 19 19 77 79 20 20 84 85 86 87 88 89 模型二的求解 根据Hungary算法，利用matlab 编程后得出的结果，这是13*20的 矩阵，行从左到右分别表示漏油点1-13的序号，列从上到下分别表示维 护班组1-20的班组号，如果该漏油点选中某个维护班组就用1表示，未 选中就用0表示，way表示13个漏油点最终对应的维护班组号，结果如图 3-1所示： 图3-1 20 个油田维护班组的调度图 再根据序号为1-13的漏油点对应的采油点标号，对应得出20个维护 班组的最优调度方案

29、如表3-6所示： 表3-620维护班组最优调度方案 采油点 12 14 16 21 22 23 24 28 29 30 38 48 62 维护班组 号 12 14 16 9 11 13 10 15 8 7 2 5 4 调度方案可以从图3-2中可以看出： 图3-2 20 个油田维护班组的调度方案直观图 模型三的求解 1）根据Floyd算法，利用matlab编程后得出的结果如图3-3所示： 图3-3 原始储油量高等级公路网络图 2）可以得出公路网络的修建和维护，以及各将各采油点的储油 运到远点的总费用为：2.522*10A4（百万）。 3）当每个采油点的储油量增加到十倍时，新规划的公路网络如图3-

30、4 所示： 图3-4 储油量增加到十倍后的高等级公路网络图 4）可以得出公路网络的修建和维护，以及各将各采油点的储油运到 原点的总费用为：4.803*10八5 （百万） 5）为了更清楚的看出两次规划路线的不同之处，我们特地对一些不 同之处做了放大处理，储油量没改变前的部分路线如图3-5所示： 图3-5 原始储油量高等级公路网络的部分放大图 6）储油量增加到十倍以后的部分路线如图3-6所示： 图3-6 储油量增加到十倍后的高等级公路网络图部分放大图 模型四的求解 1）对建立的模型，用matlab编程得到的结果如下 原油运输管道路线如图3-7所示： 图 3-7 输 油 管 道 的 网 络 分 布

31、图 2）可以得出输油管道网络的修建和维护总费用为：1.7645*10八5 （百 万），我们发现当储油量增加到十倍时，费用不变。 3）而第三问中两个结果却相差甚大，油量增加后的 公路网络修建费 用为4.803*10A5 （百万），此时修建输油管道要比修建高等级公路的花费 要少很多。 4）为了更清晰地分辨出 和第三问的部分路线的些许不同之处， 我们 特地将部分管道线路做放大处理， 如图 3-3 所示： 图 3-8 输 油 管 道 的 网 络 分 布 部 分 放 大 图 六、模型评价与推广 本题的模型有效的解决了维护班组管辖范围的合理分配问题；采油点漏油以后维 护班组合理安排，以最小的漏油代价修复所

32、有的采油点；可采储量变化时，专线公路 修建的经济最优公路运输网，以及输油管道修建的管道运输网设计方案。整个建模的 思路清晰，遵循可操作性原则，可比性原则，及科学性原则。该模型建立了在较为理 想的状态下维护班组的管辖范围，减少了维护班组的工作量，提高了工作效率，及在 理想的条件下维护班组的紧急调配方案。但该模型有一定的局限性，如没考虑到紧急 调配任务时公路的畅通程度，维护班组的人员和维修准备可行性等不定因素；也没有 考虑到各个采油点的漏油率，公高等级公路和输油管道修建的地理条件等未知条件。 本模型采用了大量的MATLAB件编程，虽然本题数据量大，种类多，但是本模型 使用了 Floyd 算法和 H

33、ungary 算法编程使得计算效率大大提高，节约了计算时间。 本论文建立的模型应用范围比较广， 不仅对本题的维护范围分配有较强的实用性， 而且其他的分配问题也有一定的参考作用，兼顾了公平与效率的原则。在其余紧急分 配方案中可以用到本论文的模型二，可以实现损失的最小化。本论文的模型三和模型 四的运输网络方案对交通网络设计，物流配送网络设计，通信网络设计等具有一定的 参考性。 七、参考文献 1 胡桔州.Floyd最短路径算法在配送中心选址中的应用J:湖南农业大学 学报. 自然科学版 ， 30（4） ， 2004.08 2 姜启源.谢金星.叶俊.数学模型（第三版） M .北京：高等教育出版社， 20

34、03 3 （美）E 米涅卡.网络和图的最优化算法M.中国铁道出版社图书，2007 4 张德全.吴果林.最短路问题的 Floyd 算法优化.许昌学院学报， 2009 5 毛圆洁.最短路问题的Floyd算法与MATLABS序实现.河北北方学院学报.自 然科学版 , 2013 6 柳毅. 佟明安. 匈牙利算法在多目标分配中的应用 . 火力与指挥控制， 2002 7 李艳艳 .0-1 规划问题的连续化方法研究及应用 . 博士学位论文 . 大连：大 连理工大学， 2009 8 苏金明.刘宏.刘波.MATLAB高级编程北京：电子工业出版社，2005 八、附录 附 录 1 ：( Floyd 算 法 求 最

35、短 路 径 及 距 离 matlab 代 码 ) function D,path = floyd( a ) %UNTITLED2 Summary of this function goes here % Detailed explanation goes here n=size(a,1); D=a; path=zeros(n,n); for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j; end end end for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j) P_size; jj = 1; ii = ii+1;

36、 if ii P_size; exit_flag = 0; end if row = 0 stepnum = 6; zflag = 0; Z_r = 0; Z_c = 0; else M(row,col) = 2; if sum(find(M(row,:)=1) = 0 r_cov(row) = 1; zcol = find(M(row,:)=1); c_cov(zcol) = 0; else stepnum = 5; zflag = 0; Z_r = row; Z_c = col; end end end function M,r_cov,c_cov,stepnum = step5(M,Z_

37、r,Z_c,r_cov,c_cov) zflag = 1; ii = 1; while zflag rindex = find(M(:,Z_c(ii)=1); if rindex 0 ii = ii+1; Z_r(ii,1) = rindex; Z_c(ii,1) = Z_c(ii-1); else zflag = 0; end if zflag = 1; cindex = find(M(Z_r(ii),:)=2); ii = ii+1; Z_r(ii,1) = Z_r(ii-1); Z_c(ii,1) = cindex; end end for ii = 1:length(Z_r) if M

38、(Z_r(ii),Z_c(ii) = 1 M(Z_r(ii),Z_c(ii) = 0; else M(Z_r(ii),Z_c(ii) = 1; end end r_cov = r_cov.*0; c_cov = c_cov.*0; M(M=2) = 0; stepnum = 3; function P_cond,stepnum = step6(P_cond,r_cov,c_cov) a = find(r_cov = 0); b = find(c_cov = 0); minval = min(min(P_cond(a,b); P_cond(find(r_cov = 1),:) = P_cond(

39、find(r_cov = 1),:) + minval; P_cond(:,find(c_cov = 0) = P_cond(:,find(c_cov = 0) - minval; stepnum = 4; function cnum = min_line_cover(Edge) r_cov,c_cov,M,stepnum = step2(Edge); c_cov,stepnum = step3(M,length(Edge); M,r_cov,c_cov,Z_r,Z_c,stepnum = step4(Edge,r_cov,c_cov,M); cnum = length(Edge)-sum(r

40、_cov)-sum(c_cov); 附录 3（ 92 个采 油点 分 布 图 matlab 代码 ） clear all numA=xlsread( numB=xlsread( roadsA=xlsread( roadsB=xlsread( for a=1:1:92 x=numA(a,:); y=numB(a,:); plot(x,y, str=int2str(a); text(x+1,y,str); hold on; powerpointX ); powerpointY ); roadsA ); roadsB ); , markersize ,12); if a=1 | a=2 | a=3

41、| a=4 | a=5 | a=6 | a=7 | a=8 | a=9 | a=10 | a=11 | a=12 | a=13 | a=14 | a=15 | a=16 | a=17 | a=18 | a=19 | a=20 plot(x,y, rs , markersize ,12) end if a=12 |a=14 |a=16 |a=21 |a=22 |a=23 |a=24 |a=28 |a=29 |a=30 |a=38 |a=48 |a=62 plot(x,y, r* , markersize ,12) end end for b=1:1:140 x1=roadsA(b,:); y1=

42、roadsB(b,:); x2=numA(x1,:); y2=numB(x1,:); x3=numA(y1,:); y3=numB(y1,:);e X=x2 x3; Y=y2 y3; plot(X,Y); hold on ; end 附录 4（ 问 题一求 20 个维 护 班 组的 管辖 范围 划 分 matlab 代码） clear all numA=xlsread( numB=xlsread( roadsA=xlsread( powerpointX); powerpointY); roadsA ); roadsB=xlsread( roadsB ); x=numA(:,1); y=numB

43、(:,1); i=roadsA(:,1); j=roadsB(:,1); A=zeros(92,92); for k=1:140 a=i(k); b=j(k); A(a,b)=1; A(b,a)=1; end for m=1:92 for n=1:92 if (A(m,n)=1) A(m, n)=sqrt(x(m)-x( n)F2+(y(m)-y( n)f2); else A(m,n)=inf; end end end D,path=floyd(A); T=zeros(72,3); for p=21:92 min =inf; for q=1:20 if minD(p,q) min=D(p,q)

44、; T(p-20,:)=p q min; end end end B=T(:,2); T(:,2)=T(:,1); T(:,1)=B; T=sortrows(T); T 附录 5( 问 题二漏 油 点 与维 修组 最佳 匹 配 matlab 代码) oil=xlsread(oil ); Oil=zeros(92,1); x=oil(:,1); for i=1:92 for j=1:92if i=j D(i,j)=0; end end end for n=1:92 if n=12 | n=14 | n=16 | n=21 | n=22 | n=23 | n=24 | n=28 | n=29 |

45、n=30 | n=38 | n=48 | n=62 b=x(n); a=D(:,n)*b; Oil=Oil a; end end Oil(:,1)=; Oil=Oil(1:20,:); result=Hungarian(Oil); way=; for p=1:13 for q=1:20 if result(q,p)=1 way=way q; end end end way 附录 6( 问 题三修 路 费 与运 费之 和的 最 少 费用 matlab 代 码 ) 原油可采量不变的路线修建代码 powerpointX); powerpointY); roadsA ); roadsB ); oil

46、); clear all ; numA=xlsread( numB=xlsread( roadsA=xlsread( roadsB=xlsread( oil=xlsread( Oi=oil(:,1); x=numA(:,1); y=numB(:,1); i=roadsA(:,1); j=roadsB(:,1); A=zeros(92,92); for k=1:140 a=i(k); b=j(k); A(a,b)=1; A(b,a)=1; end for m=1:92 for n=1:92 if (A(m,n)=1) A(m, n)=(sqrt(x(m)-x( n)F2+(y(m)-y( n)F

47、2).*(1+0.05.*(oil(m,:)+oil( n,:); else A(m,n)=inf; end end end D,path=floyd(A); for r=1:92 end for a=1:1:92 x=numA(a,:); y=numB(a,:); plot(x,y,., markersize ,12); str=int2str(a); text(x+1,y,str); holdon; end plot(0,0,., markersize ,12); for i=1:92 point=path(23,i); for j=1:100 Lpoint=point; point=path(point,i); Npoint=point; x1=numA(Lpoint,:); y1=numB(Lpoint,:); x2=numA(Npoint,:); y2=numB(Npoint,:); X=x1 x2; Y=y1 y2; plot(X,Y); holdon; if point=i break ; end end end x=numA(23,:); y=numB(23,:); X=0 x;