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

2015年成都理工大学校内数学建模竞赛论文题 目编 号B队编号88参赛队员姓 名学号专业张萌立201313030206计算机科学与技术何理201305090108空间信息与数字技术何龙201305090110空间信息与数字技术二0一五年五月二十五日队编号：88B题油井维护的设置调度与原油运输的网络设计摘要本文讨论了如何设置油田维护班、油田维护班与其管辖范围内的油田采集点的关系以及维护班的调度、原油的运输以及其最优解的问题。实质上是关于多目标的优化问题。根据题中所给的条件和问题汲取相关的约束条件和目标函数，建立模型。对于问题一，是关于油田维护班的分配管辖范围问题，首先在MATLAB环境下采用Floyd算法求出任意油田维护班与采集点之间的最短距离，从中提取92*20的矩阵，在引入0-1规划模型，然后建立以总路程最小为目标函数，以各个维护班工作量均衡为约束条件，建立优化模型，使用Matlab编程实现区域的自动划分。对于问题二，是关于如何在13个采油点同时发生事故时，调度20个维护班维修，以一个采油点当且仅当与一个维护班相匹配为约束条件，以维护班到达花费时间最小为目标函数，采用Hungary算法，建立相关模型，并用Matlab编程，求出最优解，并画图。对于问题三，如何设计将部分现有道路修建为高等级公路以快速运输原油，实际上是一个关于路线选择的最优化模型。以原油运输费用与修路费用之和达到最少为目标函数，采用Floyd算法并在两点之间根据油的可采储量进行平均加权，再用Matlab编程，求出路线，设计出最优路线方案。用原油可采储量的10倍为加权条件，求出路线，设计出另一个最优路线方案。对于问题四，如何根据现有道路修建管道路线，使修建管道的费用最少，因为管道输油的成本可以忽略不计，实际上是只要使得管道路线的总长度最小，就能达到成本最少的目标。以总长度最小为目标函数，采用Floyd算法，用Matlab编程，求得最短路径，设计出原油运输方案。关键字：Floyd算法 Hungary算法 MATLAB 0-1规划最短路径B题油井维护的设置调度与原油运输的网络设计 一、问题重述试就某油田设置维护班组和原油运输的相关情况建立数学模型分析研究下面问题：（1） 附件1中的附图给出了某油田A区的交通道路和现有的20个维护班组的设置情况示意图，相关的数据信息见附件2。维护班组每天的工作是巡视其管辖范围内的采油井，请为20个维护班组合理分配管辖范围，使各维护班组的工作量尽量均衡，且在其所管辖油井发生事故时能尽快到达。（2） 假设13个采油点同时发生漏油事故，需要调度20个维护班组实现快速维修，恢复生产。实际中一个班组最多维修一个采油点，一个采油点也仅需一个班组维修，为了尽量减少漏油损失，请给出20个维护班组的合理调度方案。（注：假设采油点的原油开采速度与可采储量成正比）（3）为了将各采油点的原油快速运输到O点（坐标原点），计划将部分现有道路修建为高等级公路，作为原油的运输专线。假设公路修建及采油期内的养护成本合计为1百万/公里，公路运输成本为0.1百万/万吨公里，请设计一个合理的公路运输网络，使得修路和运输成本最小。再假设经过勘查，各采油点的可采储量增长了10倍，请重新设计一个合理的公路运输网络。（注：假设各采油点均可修建直线到达O点的公路）（4）管道输油具有建设成本高、输油成本低的特点。假设输油管道的修建及采油期内的养护成本合计为1千万/公里，输油成本忽略不计，且管道只能沿着现有道路修建。请对比公路运输分析修建输油管道的经济性，设计一个合理的原油运输方案。再假设经过勘查，各采油点的可采储量增长了10倍，请重新设计一个合理的原油运输方案。（注：假设各采油点均可修建直线到达O点的输油管道）二、问题分析因为油田维护班组的职能和人员配置基本相同，所以要考虑每个油田维护班组工作量的均衡下能在最短时间内到达突发事件现场，主要考虑的方向是各个维护班组管辖范围内采油点发生事故时赶往总的时间最短（最短时间转化为最短路程）与均衡每个采油点的事故率这两个因素，显然，这是个双目标问题，为了求解方便，把双目标函数单一化，将各个维护班组管辖范围内的采油点事故率均衡转化为约束条件建立模型，进而划分出区域。其中，我们引入了0-1规划模型，采用弗洛伊德算法求出图中任意两个站点之间的最短距离，在根据所建立的模型划分出具体区域。具体做法如下：1.1）、首先，依据附录中92个节点的横纵坐标，使用MATLAB编程，进而将每个节点标号、连线。如图2-1所示: 图2-1 采油点之间的路线图1.2）、再用dij=2(xi-xj)2+(yi-yj)2公式算出两点之间的距离（如果有路），得出92*92的邻接矩阵，其中矩阵中的元素表示两两之间的距离，若不存在路，则用一个无限大的数来代替，在MATLAB环境下利用弗洛伊德算法求出两两之间的最短路径和最短路程，然后从中抽取92个节点分别到20个维护班组站点的最短距离。（程序见附录3）1.3）、引入0-1规划变量，然后以92个节点分别到20个维护班组站点的最短距离。（程序见附录4）1.4）、使用MATLAB编程，将区域划分的最终结果输出。1.5）、在根据工作量均衡度做管辖范围的调整。2.1）、对于如何在13个采油点同时发生事故时，调度20个维护班维修的问题，我们考虑，因为油田一直在漏油，为了将经济损失降低到最小，当一个维护班组附近出现两个漏油点时，维护班组如何抉择，我们引入权，其大小就是维护班组到漏油点的距离s乘以漏油点的储油量，这样才能在各个维护班组到达漏油点时将损失降到最小。2.2)、再用弗洛伊德算法进行计算时需要知道给定的矩阵，我们这样构建，取出20个维护班组和13个采油点的坐标，对两点之间的距离加权，用Qij代替，从而建立20*13的矩阵，矩阵中的元素即是权Qij的大小（经济损失最小就转化为了距离最小），建立模型后，用matlab编程，采用Hungary算法（程序见附录2），求出如何调度20个维护班组（程序见附录5），才能使损失达到最小，并将结果输出。3.1）、这一问是高等级公路的修建，要求是公路修建与养护及原油运输资金总和最小，这和第二问相似的地方就是前者是资金损耗最小，因此这一问可以用第二问的方法，只不过就是权值改变了，此时权的大小就用总资金Fij来表示，3.2）、但这只是两点之间的加权路径最短，我们要修建的是公路网络，这样，可以循环求出92个采油点到原点的最短加权路径，把92条加权路径综合起来就是我们要求的公路网络，这样就能保证把所有采油点的油送到原点时公路修建以及原油运输的总费用最少。3.3）、利用matlab编程（程序见附录6），建立93*92的矩阵，利用Hungary算法得到任意一点到23点的最小加权路径，循环得到公路网络，并用matlab将得到的公路网络画出来。3.4）、当油田的储油量增加到10的时候（程序见附录6），只是在建立模型时，两点之间的权值改变，此时，矩阵中的元素用新得到的权值Tij来代替，重复上述方法，得到新的公路网络。4.1）、当用管道输油时，输油成本可以忽略不计，管道修建费用就只与管道的总长度有关了，和第三问的算法相似，经济费用最小就转化为了总路径长度最小。4.2）、将两点之间的路程作为权Rij赋值给两点之间的距离，建立93*92的矩阵，利用Hungary算法得到任意一点到23点的最小加权路径，循环得到公路网络，并用matlab编程（程序见附录7）将得到的公路网络画出来。4.3）、当每个采油点的储油量增加到十倍时，这对新路线的规划并没有任何影响，因为此时输油管道的修建总费用只与路线的路程有关，与各个采油点的储油量并不相关，这样储油量对两点距离的权值无影响，因此得到的新的规划路线不变。三、符号说明符号描述(Xi , Yi)第i节点坐标，单位mmDij第i 个节点到第j个节点的最短路径，单位mmAi第i个油田维护班组的位置标号Ui第i个油田维护班组的管辖节点集Wi第i个油田维护班组的工作量指标油田维护班组的平均工作量E油田维护班组工作量的均衡程度Cpi第i个油田维护班组所覆盖的路口数量Cpi第i个油田维护班组所覆盖的路口数量Qij第i个维护班组到第j个采油点的距离和采油点j的储油量的乘积Fij将第i个采油点的储油运到第j个采油点时，公路修建和原油运输的总费用Tij将第i个采油点的储油运到第j个采油点时，公路修建和原油运输的总费用Rij原油从采油点i运到采油点j的最短路径的长度Gn每个采油点到第23个采油点的加权路径Kn每个采油点到第23个采油点的路径长度四、模型建立模型一的建立该题要求为各油田维护班组分配管辖范围，要求各个维护班组能以最快的速度到达突发事件的地点，所以我们要考虑路线问题，选择最优路线，因此，我们建立了以最短路程为主要目标，以维护班组管辖范围内的事故率均衡为限制条件的模型来划分区域。因此，建模如下（代码见附录4）目标函数：Mini=192j=120dij*xij约束条件：xij=1 0 第i个采油点到第j个维护点 第i个采油点不到第j个维护点i=1,92,j=1,20xjj=1j=120xij=1模型二的建立该题要求调度20个油田维护班组对发生漏油事故的13个采油点进行紧急维修，且一个油田维护班组仅且只能维修一个采油点，当一个维护班组附近发生多起漏油事故无法抉择时，我们引入抉择机制，根据假设采油点的原油开采速度与可采储量成正比，由此可根据维修班组到采油点的距离计算采油点在漏油期间未采油的损失，为了让13个漏油点的总损失到达最小，以此建立一个20*13的矩阵，矩阵中的每个元素我们用权值来表示，权值的大小为距离与储油量的乘积，这样就转化为最优路径问题，因此，根据Hungary算法，建立模型如下（程序见附录5）：目标函数：MINi=113j=120QijQij表征第j个维护班组到第i个漏油点的加权距离模型三的建立 要求在现有部分道路的基础上修建高等级公路，来将各个采油点的储油运到远点，而原点可以直接修通往任意一个采油点的公路，我们可以将问题划分92个相同的小问题，就是每个采油点到采油点23的最短加权路径，因为，23是距离远点最近的点，而且原点与23点的直线距离最短。然后再综合这92条最短加权路径，就能得到最优的公路线路网。而每个采油点储油量增加到十倍后，只是权重发生变化，函数模型并不会改变，因此，根据Floyd算法，建立模型如下：目标函数：n=192MIN（Gn）Gn表征的是每个采油点到第23个采油点的加权路径模型四的建立 要修建各采油点到原点的输油管道，权重只与距离相关，和第三问类似，我们可以将问题划分92个相同的小问题，就是每个采油点到采油点23的最短路径，因为，23是距离远点最近的点，而且原点与23点的直线距离最短。然后再综合这92条最短路径，就能得到最优的公路线路网。而每个采油点储油量增加到十倍后，只是权重发生变化，函数模型并不会改变，因此，建立模型如下：目标函数i=192MIN（Ki）Ki表征的是每个采油点到第23个采油点的路径长度。五、模型求解模型一的求解用matlab求解（程序见附录）得出结果，各个维护班组对应管辖范围内的采油点如表3-1所示：表3-1 每个维护班组及其管辖范围内的采油点维护班组所管辖节点11676869717374757678223940434470723354556566445760626364554950515253565859667730324748618833469931343545101011112627121225131321222324141415152829161636373817174142181880818283191977792020848586878889909192表3-2 油田维护班组到其管辖范围内的各采油点的距离维护班组油田维护班组到其管辖范围内的各采油点的距离1016.19 12.07 5.00 11.40 10.30 6.27 9.30 12.84 6.40 2036.82 19.14 8.00 9.49 8.60 16.06 3022.71 12.66 15.24 18.40 4018.68 17.39 3.50 10.31 19.36 505.00 8.49 12.29 16.59 11.71 20.84 23.02 15.21 60705.83 11.40 12.81 12.90 41.90 808.28 9.30 9020.56 5.02 4.24 10.95 1001109.00 16.43 12017.89 13027.08 9.06 5.00 23.85 14015047.52 57.01 1606.08 11.18 34.06 1708.50 9.85 1808.06 6.71 10.79 5.39 1909.85 4.47 20011.75 4.47 3.61 14.65 12.95 9.49 13.02 15.99 36.01 在此，我们首先给出工作量指标的定义，工作量Wi = 油田维护班组到各采油点的距离之和。由定义，第i个交巡警服务平台的工作量为：Wi=jUiDij则油田维护班组的平均工作量为：W=i=120Wi20工作量均衡程度可用各维护班组与平均值的偏离程度，即维护班组工作量的方差之和来表示：。其中，E表示油田维护工作量的均衡程度。可计算出上述划分方案中所有油田维护班组的工作总量为1055.155（单位）由表3-1和表3-2中数据可知，维护点1、2、5、20工作量较大，而维护点0、12管辖范围内的节点过少，只有它本身，说明此方案在工作量均衡性方面存在很大问题。由表2中的结果可知，整个辖区的划分结果中，始终有六个路口节点（28、29、38、39、61、92 ）到服务平台的距离较大。我们以维护点到采油点的总距离为均衡条件对表一种的结果进行调整，调整的步骤如下：（1）对维护点1、2、5、20中的所有采油点重新调整，先计算出它到20个维护班组距离；（2）对于距离较小的所有采油点，该节点优先划分到包含节点数最少的那个维护点的管辖范围；（3）如果距离较小的所有维护班组包含的节点数相等，则优先选择距离最近的那个维护班组。经过调整后的划分结果如表3-3所示： 表3-3 各个维护班组及其管辖范围内的采油点分布维护班组 管辖区域内采油点1167686971737422394043447072335455656644576062636455495051525356667730324748618833469931343545101011112627121225131321222324141415152829161636373817174142181880818283191977792020848586878889经过调整后，油田维护班组到其管辖范围内的各采油点的距离如表3-4所示： 表3-4 调整后油田维护班组到其管辖范围内的各采油点的距离维护班组 维护班组到采油点的距离1016.19 5.00 11.40 10.30 6.27 9.30 2036.82 19.14 21.06 8.60 16.06 3011.63 22.71 12.66 15.24 18.40 4018.68 17.39 3.50 10.31 19.36 505.00 16.59 11.71 20.84 23.02 6014.87 22.75 18.95 16.03 705.83 11.40 12.90 41.90 808.28 9.30 9020.56 5.02 4.24 10.95 10035.38 11016.43 12017.89 1309.06 5.00 23.85 14032.65 15047.52 57.01 1606.08 11.18 34.06 1708.50 9.85 17.91 1806.71 10.79 5.39 15.23 19.53 24.27 1909.85 4.47 14.32 11.18 8.94 2004.47 3.61 14.65 12.95 9.49 36.01 可以看出虽然总工作量增加了，变成了1134.41 但是各个维护点的工作均衡程度改善了57.99%。因此最后结果如表3-5所示：表3-5 调整后各个维护班组及其管辖范围内的采油点分布维护班组 管辖采油点1167686971737422394043447072335455656644576062636455495051525356667730324748618833469931343545101011112627121225131321222324141415152829161636373817174142181880818283191977792020848586878889模型二的求解根据Hungary算法，利用matlab编程后得出的结果，这是13*20的矩阵，行从左到右分别表示漏油点1-13的序号，列从上到下分别表示维护班组1-20的班组号，如果该漏油点选中某个维护班组就用1表示，未选中就用0表示，way表示13个漏油点最终对应的维护班组号，结果如图3-1所示：图3-1 20个油田维护班组的调度图再根据序号为1-13的漏油点对应的采油点标号，对应得出20个维护班组的最优调度方案如表3-6所示：表3-6 20维护班组最优调度方案采油点12141621222324282930384862维护班组号12141691113101587254调度方案可以从图3-2中可以看出：图3-2 20个油田维护班组的调度方案直观图模型三的求解1）根据Floyd算法，利用matlab编程后得出的结果如图3-3所示： 图3-3 原始储油量高等级公路网络图2）可以得出公路网络的修建和维护，以及各将各采油点的储油运到远点的总费用为：2.522*104（百万）。3）当每个采油点的储油量增加到十倍时，新规划的公路网络如图3-4所示：图3-4 储油量增加到十倍后的高等级公路网络图4）可以得出公路网络的修建和维护，以及各将各采油点的储油运到原点的总费用为：4.803*105（百万）5）为了更清楚的看出两次规划路线的不同之处，我们特地对一些不同之处做了放大处理，储油量没改变前的部分路线如图3-5所示：图3-5 原始储油量高等级公路网络的部分放大图6）储油量增加到十倍以后的部分路线如图3-6所示：图3-6 储油量增加到十倍后的高等级公路网络图部分放大图模型四的求解1）对建立的模型，用matlab编程得到的结果如下原油运输管道路线如图3-7所示：图3-7 输油管道的网络分布图2）可以得出输油管道网络的修建和维护总费用为：1.7645*105（百万），我们发现当储油量增加到十倍时，费用不变。3）而第三问中两个结果却相差甚大，油量增加后的公路网络修建费用为4.803*105（百万），此时修建输油管道要比修建高等级公路的花费要少很多。4）为了更清晰地分辨出和第三问的部分路线的些许不同之处，我们特地将部分管道线路做放大处理，如图3-3所示：图3-8 输油管道的网络分布部分放大图六、模型评价与推广本题的模型有效的解决了维护班组管辖范围的合理分配问题；采油点漏油以后维护班组合理安排，以最小的漏油代价修复所有的采油点；可采储量变化时，专线公路修建的经济最优公路运输网，以及输油管道修建的管道运输网设计方案。整个建模的思路清晰，遵循可操作性原则，可比性原则，及科学性原则。该模型建立了在较为理想的状态下维护班组的管辖范围，减少了维护班组的工作量，提高了工作效率，及在理想的条件下维护班组的紧急调配方案。但该模型有一定的局限性，如没考虑到紧急调配任务时公路的畅通程度，维护班组的人员和维修准备可行性等不定因素；也没有考虑到各个采油点的漏油率，公高等级公路和输油管道修建的地理条件等未知条件。本模型采用了大量的MATLAB软件编程，虽然本题数据量大，种类多，但是本模型使用了Floyd算法和Hungary算法编程使得计算效率大大提高，节约了计算时间。本论文建立的模型应用范围比较广，不仅对本题的维护范围分配有较强的实用性，而且其他的分配问题也有一定的参考作用，兼顾了公平与效率的原则。在其余紧急分配方案中可以用到本论文的模型二，可以实现损失的最小化。本论文的模型三和模型四的运输网络方案对交通网络设计，物流配送网络设计，通信网络设计等具有一定的参考性。七、参考文献1 胡桔州.Floyd 最短路径算法在配送中心选址中的应用J ：湖南农业大学学报.自然科学版 ，30(4) ，2004.08 2 姜启源.谢金星.叶俊.数学模型（第三版）M .北京：高等教育出版社，20033 (美)E米涅卡.网络和图的最优化算法M .中国铁道出版社图书，20074 张德全.吴果林.最短路问题的Floyd算法优化.许昌学院学报，20095 毛圆洁.最短路问题的Floyd算法与MATLAB程序实现.河北北方学院学报.自然科学版, 20136 柳毅.佟明安.匈牙利算法在多目标分配中的应用.火力与指挥控制，20027 李艳艳.0-1规划问题的连续化方法研究及应用. 博士学位论文 .大连：大连理工大学，20098 苏金明.刘宏.刘波.MATLAB高级编程.北京：电子工业出版社，2005八、附录附录1：（Floyd算法求最短路径及距离matlab代码）function D,path = floyd( a )%UNTITLED2 Summary of this function goes here% Detailed explanation goes heren=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 endendfor 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; end if ii P_size; exit_flag = 0; end 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 endendfunction M,r_cov,c_cov,stepnum = step5(M,Z_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(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(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_cov)-sum(c_cov);附录3（92个采油点分布图matlab代码）clear all;numA=xlsread(powerpointX); numB=xlsread(powerpointY);roadsA=xlsread(roadsA);roadsB=xlsread(roadsB);for a=1:1:92 x=numA(a,:); y=numB(a,:); plot(x,y,.,markersize,12); str=int2str(a); text(x+1,y,str); hold on; if a=1 | a=2 | a=3 | 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) endendfor b=1:1:140 x1=roadsA(b,:); y1=roadsB(b,:); x2=numA(x1,:); y2=numB(x1,:); x3=numA(y1,:); y3=numB(y1,:); X=x2 x3; Y=y2 y3; plot(X,Y); hold on;end附录4（问题一求20个维护班组的管辖范围划分matlab代码）clear all;numA=xlsread(powerpointX);numB=xlsread(powerpointY);roadsA=xlsread(roadsA);roadsB=xlsread(roadsB);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;endfor m=1:92 for n=1:92 if(A(m,n)=1) A(m,n)=sqrt(x(m)-x(n)2+(y(m)-y(n)2); else A(m,n)=inf; end endendD,path=floyd(A);T=zeros(72,3);for p=21:92min =inf; for q=1:20 if minD(p,q) min=D(p,q); T(p-20,:)=p q min; end endendB=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:92 if i=j D(i,j)=0; end endendfor n=1:92 if n=12 | n=14 | n=16 | n=21 | n=22 | n=23 | n=24 | n=28 | n=29 | n=30 | n=38 | n=48 | n=62 b=x(n); a=D(:,n)*b; Oil=Oil a; endendOil(:,1)=;Oil=Oil(1:20,:);result=H