蒙特卡罗算法随机数数学建模wjj讲课

题 基于贪婪算法的巡逻方案设 要100m的小段，近似认为事发现场和警其次，分析巡逻方案问题，将其归纳为以下两类子问题：(1)求解满足D1要求分别建立对应的整数规划模型。但由于整数变量较多，约束条件复杂，精确求解，7问题一：欲满足D1条件，最少需要配置17辆巡逻（均处于运动状态。越高，巡逻缺失率越低，巡逻效果越显著。问题三：给出了19辆的巡逻方案，巡隐蔽性的指标，给出了兼顾巡逻效果和隐蔽性的19辆巡逻方案。问题五：给出了给出13辆的巡逻方案，巡逻效果显著。问题七：简单探讨了事发概率不均和交通状况等因素对巡逻造成的影响。：１、巡逻效果显著程度Floyd算法建立所有离散点之间的最短路径，建立整数规划模第三问的求解４、总的评价：指标选取不够全面、不够合理，算法较简单，动态结果不够理110在街道上巡弋，既能够震慑违法分子，降低率，又能够增加市民的安全感，同时也加快了接处警（接受并赶往现场处理）时间，提高了反应时D2.D3.巡逻规律应有一定的隐蔽2问题3：确定满足D1条件尽量满足D2条件的巡逻方案及其评价指标值4：在满足D1条件并尽量满足D2D3条件，优化巡逻方问题5：在仅有10辆条件下，给出尽量满足D1、D2条件的巡逻方案。问题6：接警后平均行驶速度提高到50km/h，求问题3。7考虑在道设置标记点，将道路均匀分割为长度约100m的小段，标记点基本设ln

100lnln

1巡逻时，驶过每小段道路花费时间也较短(约为18s)。当时间发生时，由图1可知，若道路平均长度为100m，平均误差不超过50m。根据接警后的行驶速度计问题，该问题可以方便地利用Floyd算法来求解。 ,7.2s标记点的集合，为此时刻的控制区域。某一时刻的控制率是指巡逻缺失率：一段时间（4小时）内，一直处在的控制区域之外的标记点数50%5%越好。本文认为巡逻周期平均值和巡逻时间标准差平均值均达到600s性较好。3.1(2)巡警过程中可往复运动，但不能停止，其平均巡逻速度为20km/h，接警后仅位于离散化后的道路标记点上，其移动方式为由一标记点跳到邻近标记认为到达距重点部位最近的标记点时，即到达了重点部位3.2N辆LmC%%%TsSsD/第i辆放置的标记点编/个条距第i辆三分钟车程内标记点集/i/距第i辆两分钟车程内重点标记点集/第i个标记点是否有(有为1，没有为/[1]实现。307个交叉口、4602404个标记点、25556m0 2（图中所有的点均为对道路离散化后的标记点，其中画圈的标记点为原道路交叉口道路离散化处理后，D1(1)控制率

控制区域的标记点数量100(2)控制区域同时包含3个重要标记点（相关概念见问题分析2.3；O(n3)。考虑标记点数量较大(2404个)Fortran编程计算任意两标记点之间的最短路径长度，执行速度较快。鉴于Floyd算法为图论中基本算法，此处不再列出本文分析巡逻问题，将其归纳为以下两类问题求解满足D1要求的最少数求解限定数量的最优布模型1满足D1条件的最少数量模minAjD(x,j)

AijD(i,j)2000zi

4000

BQD(i,Q) k1,2,A0.9 BQD(x,QA0.9

iAi0.9NBNBi

NBiAP

ziAPxZ,1

2404,i1,2,3...,

z0or1,i1,2,NN AjD(x,j)

AijD(i,j)2000zi

BQD(i,Q)4000

4000

BQD(x,Q) k1,2,

NBNBi

N BiAP

s.t.ziAPixZ,i1,2,3...,i

1x2404,i1,2,3...,

zii12，采用Lingo、Lindo等软件按分支定界法求得精确解是十分[3]分支定界法属于非多项式算法，当整数变量较多时求解在3分钟内到达事发地点的比例不低于90%2分钟到达重点部位的约束条束的刻画更加。首先确定数量N所有的位于标记点上，每隔一段时间，移动到邻近标记点；尽可能采用贪婪算法，获得当前时刻N辆的最优位置判断此时控制区域是否满足D1条件：如果不满足，则考虑将部分后退至前一位置。后退的原则是：从第一辆开始依次后退，直至控制区域满足D1条件。若无法后退，意味着数量N不足，需要增加数量N。满足，输出4小时的巡逻方案。3。图3求解巡逻方案总体流程在问题求解过程中采用了贪婪算法以获得当前N辆的最优位置步骤如下赋值i=i+1。确定第i辆可以放置的位置，具体方案如下：若是初始时刻，第i辆的位置可以任意标记点上放置；若是非初始时刻，第i辆只能选择与前一时刻所处位置相邻的标记点上；确定第i辆的最优位置，选取原则是：在最优位置放置，可以最大限度记点。具体而言，对第i辆的每一个可行位置，计算下面的指标：=控制区域中位置，w5~100，以保证未曾遍历的标记点优先权。在所得的最优位置上放置，并更新的控制区域若所有都已放置，则输出的控制区域和位置，否则返回步骤(2)。4。否是图4贪婪算法求解放置位置流程以上算法均通过编程实现根据建立的模型，将数量N取10~20辆一一验算，发现当数量少于16辆时，找不到满足D1条件的初始位置当数量为16辆时，通过调整试算，可以找到满足D1条件的初始位置，但无法找到巡逻路线，静止于初始位置不动，这与题意不符。当数量为17辆以上时，开始有一定的活动区域，可以找到满足D1条综上，欲满足D1条件，该区最少需配置17辆巡逻。17辆的初始位置和5。图5满足D1的最少巡逻方50%5%分别求解N=17~20时满足D1条件的巡逻方案，并给出相应的巡逻效果显著指表2不同数量的巡逻效果显著程度指6。图 19辆的巡逻方案示意▲ 道路平均长度99m，按20km/h速度行驶 从一个标记点移动到相邻标记点需 D3600s，巡逻规律隐蔽性较好。本文同样试算数量在17~20的情况得出巡逻效果显著程度和隐蔽性指标数据，3。表3不同数量的巡逻效果显著程度和隐蔽性指 巡逻遍历

巡逻周期平均T(s)

巡逻时间标准S(s) 由上表可知，增加数量，巡逻周期平均值和巡逻时间标准差平均值均会有所增加，即隐蔽性有所提高。当数量为19辆时，巡逻周期平均值为812s，巡逻时间标D1D2的前提下能保证较好的隐蔽性。于3个重点部位的控制，可以始终满足。研究不同控制率C下巡逻方案的巡逻效表 10辆不同控制率下的巡逻效果显著程对上表分析可知，巡逻的遍历率较低，表明几乎处于固定位置，虽然可以保证3综合各项指标，控制率C=67%的巡逻方案，可保证较高的巡逻遍历率10辆的较好巡逻方案。10辆的初始位置和巡逻区域见图7图 10辆的巡逻方案分布当接警后行驶速度提高到50km/h时，分别求解N=11~13时满足D1条件的警表5不同数量巡逻方案的巡逻效果显著性指8图 13辆的巡逻方案示意D190%的比例，本文采用统计标记点的方式计算，精确性较高。稍加改进可用于其他有类似特点的巡逻问题，如移动等，，：[1]等航空航天大学，2004，第259-264页，，：日期：2009日期：2009：谢金星等，优化建模与LINDO/LINGO软件，284-297

21，2005,首先读入node.txtway.txt根据excelloadnode.txtloadway.txtfori=1:size(way,1)k1=way(i,1);k2=way(i,2);x1=node(k1,1);y1=node(k1,2);x2=node(k2,1);y2=node(k2,2);%fori=1:size(way,1)k1=way(i,1);k2=way(i,2);x1=node(k1,1);y1=node(k1,2);x2=node(k2,1);y2=node(k2,2);kk1=ceil(wlen/dd);%

if(k<=1)continueend该路段作废forj=1:k-1

fori=size(way,1):-1:1fori=1:size(way,1)k1=way(i,1);k2=way(i,2);x1=node(k1,1);y1=node(k1,2);x2=node(k2,1);y2=node(k2,2);Fortran计算任两点间最短路径长度doi=1,NDread(1,*)node(:,i)doread(2,*)way(:,i)!生成omegadok1=way(1,i);k2=way(2,i);x1=node(1,k1);y1=node(2,k1);x2=node(1,k2);y2=node(2,k2);dodododoprint*,kdoi=1,NDdoif(d(i,k)+d(k,j)<d(i,j))doi=1,NDprint*,iwrite(1,'(<ND>I10)')d(i,:)loadnode_new.txt标记点坐标(已扩充loadway_new.txt%道路，已扩充loaddist.txt任意两点间最短距离N=size(node_new,1);%节点数目imppos=[5112,4806;9126,4266;7434,1332重点坐标fori=1:3x1=imppos(i,1y1=imppos(i,2);dismin=1e8;%最短距离dismin_n=0;%for

%重要标记点编号 %速度40km/h,3分钟行驶2000m，2分钟行驶%速度50km/h,3分钟行驶2500m，2分钟行驶%关系矩阵dd(i,j)表示从i点出发，以40km/h按i,j间最短路径行驶，能否在3分内到达，若j2分钟内。%1%关系矩阵ddd(i,j)表示从i点出发，以50km/h按i,j间最短路径行驶，能否在3分内到达，若j2分钟内。%1fori=1:Niforif(dist(i,j)<=2000&&length(find(imp==j))==0)%3elseif(dist(i,j)<=1333&&length(find(imp==j))==1)%2else%赶不到

fori=1:Nforif(dist(i,j)<=2500&&length(find(imp==j))==0)%3elseif(dist(i,j)<=1667&&length(find(imp==j))==1)%2else%赶不到

%将计算结果为data.mat(手动进行计算完全满足D1的路线（速度40km/h）将dd修改为ddd即可计算速(50km/h的情况closeallloadpicout=0;%是否输出car=19;%数量(最少17)TIME=810;17.8s，4h810leiji(1:N)=0;%是否已经过某标记点，经过则为1，否则为0。cp(1:car,1:TIME)=0;%第i辆某一步的位置holdonfortm=1:TIME按步循环cur(1:N)=0;%代表第i个点是否被覆盖,覆盖则取1，否则取0。每一步最开始未确定位置，所以均取0。%/////////////////////////对当前步放置/////////////////////////////////////foriii=1:car%依次放置，从第一辆开始fprintf('%dif(tm==1)%初始时刻可放置于任何位(1:N)=0;%标记能否放置。=1则此处不可放置(无法到达);=0代

(1:N)=1;t=cp(iii,tm-1);%第iii辆，tm-1时刻(tm>1)位置。%非初始时刻可能%搜索与t位置直连的点，即将可以到达的位置标记为0(可放置)。forj=1:size(way_new,1)

%,if(tm>2)(cp(iii,tm-2))=1;if(sum()==N)(cp(iii,tm-2))=0;endsmax=0;fori=1:N%搜索最大if((i)==1)continue;endtmp=or(cur,dd(i,:));%若选择第i位置放置，计算覆盖范 %兼顾覆盖范围和重点部位，计算判断指标,imp为重点标记点编号 nmax=i;%最大指标及对应标记点编

pos(iii)=nmax;%记录当前步第iii个的位,:));%%检验当前的放置方案，若不满足覆盖条件和重点部位条件，依次回crit_fg=90;%90%10辆车是要修改放松。crit_imp=3;%重点部位三个都顾及if(tm<=2)%如果前两步不满足条件，则数量不够，输出'NotEnoughCar!'%从第一个开始回forcur(1:N)=0;forii=1:carcur=or(cur,dd(pos(iiendbreak;%满足条件