蒙特卡羅算法隨機(jī)數(shù)數(shù)學(xué)建模wjj講課

題 基于貪婪算法的巡邏方案設(shè) 要100m的小段，近似認(rèn)為事發(fā)現(xiàn)場和警其次，分析巡邏方案問題，將其歸納為以下兩類子問題：(1)求解滿足D1要求分別建立對應(yīng)的整數(shù)規(guī)劃模型。但由于整數(shù)變量較多，約束條件復(fù)雜，精確求解，7問題一：欲滿足D1條件，最少需要配置17輛巡邏（均處于運(yùn)動狀態(tài)。越高，巡邏缺失率越低，巡邏效果越顯著。問題三：給出了19輛的巡邏方案，巡隱蔽性的指標(biāo)，給出了兼顧巡邏效果和隱蔽性的19輛巡邏方案。問題五：給出了給出13輛的巡邏方案，巡邏效果顯著。問題七：簡單探討了事發(fā)概率不均和交通狀況等因素對巡邏造成的影響。：１、巡邏效果顯著程度Floyd算法建立所有離散點(diǎn)之間的最短路徑，建立整數(shù)規(guī)劃模第三問的求解４、總的評價：指標(biāo)選取不夠全面、不夠合理，算法較簡單，動態(tài)結(jié)果不夠理110在街道上巡弋，既能夠震懾違法分子，降低率，又能夠增加市民的安全感，同時也加快了接處警（接受并趕往現(xiàn)場處理）時間，提高了反應(yīng)時D2.D3.巡邏規(guī)律應(yīng)有一定的隱蔽2問題3：確定滿足D1條件盡量滿足D2條件的巡邏方案及其評價指標(biāo)值4：在滿足D1條件并盡量滿足D2D3條件，優(yōu)化巡邏方問題5：在僅有10輛條件下，給出盡量滿足D1、D2條件的巡邏方案。問題6：接警后平均行駛速度提高到50km/h，求問題3。7考慮在道設(shè)置標(biāo)記點(diǎn)，將道路均勻分割為長度約100m的小段，標(biāo)記點(diǎn)基本設(shè)ln

100lnln

1巡邏時，駛過每小段道路花費(fèi)時間也較短(約為18s)。當(dāng)時間發(fā)生時，由圖1可知，若道路平均長度為100m，平均誤差不超過50m。根據(jù)接警后的行駛速度計問題，該問題可以方便地利用Floyd算法來求解。 ,7.2s標(biāo)記點(diǎn)的集合，為此時刻的控制區(qū)域。某一時刻的控制率是指巡邏缺失率：一段時間（4小時）內(nèi)，一直處在的控制區(qū)域之外的標(biāo)記點(diǎn)數(shù)50%5%越好。本文認(rèn)為巡邏周期平均值和巡邏時間標(biāo)準(zhǔn)差平均值均達(dá)到600s性較好。3.1(2)巡警過程中可往復(fù)運(yùn)動，但不能停止，其平均巡邏速度為20km/h，接警后僅位于離散化后的道路標(biāo)記點(diǎn)上，其移動方式為由一標(biāo)記點(diǎn)跳到鄰近標(biāo)記認(rèn)為到達(dá)距重點(diǎn)部位最近的標(biāo)記點(diǎn)時，即到達(dá)了重點(diǎn)部位3.2N輛LmC%%%TsSsD/第i輛放置的標(biāo)記點(diǎn)編/個條距第i輛三分鐘車程內(nèi)標(biāo)記點(diǎn)集/i/距第i輛兩分鐘車程內(nèi)重點(diǎn)標(biāo)記點(diǎn)集/第i個標(biāo)記點(diǎn)是否有(有為1，沒有為/[1]實(shí)現(xiàn)。307個交叉口、4602404個標(biāo)記點(diǎn)、25556m0 2（圖中所有的點(diǎn)均為對道路離散化后的標(biāo)記點(diǎn)，其中畫圈的標(biāo)記點(diǎn)為原道路交叉口道路離散化處理后，D1(1)控制率

控制區(qū)域的標(biāo)記點(diǎn)數(shù)量100(2)控制區(qū)域同時包含3個重要標(biāo)記點(diǎn)（相關(guān)概念見問題分析2.3；O(n3)。考慮標(biāo)記點(diǎn)數(shù)量較大(2404個)Fortran編程計算任意兩標(biāo)記點(diǎn)之間的最短路徑長度，執(zhí)行速度較快。鑒于Floyd算法為圖論中基本算法，此處不再列出本文分析巡邏問題，將其歸納為以下兩類問題求解滿足D1要求的最少數(shù)求解限定數(shù)量的最優(yōu)布模型1滿足D1條件的最少數(shù)量模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]分支定界法屬于非多項式算法，當(dāng)整數(shù)變量較多時求解在3分鐘內(nèi)到達(dá)事發(fā)地點(diǎn)的比例不低于90%2分鐘到達(dá)重點(diǎn)部位的約束條束的刻畫更加。首先確定數(shù)量N所有的位于標(biāo)記點(diǎn)上，每隔一段時間，移動到鄰近標(biāo)記點(diǎn)；盡可能采用貪婪算法，獲得當(dāng)前時刻N(yùn)輛的最優(yōu)位置判斷此時控制區(qū)域是否滿足D1條件：如果不滿足，則考慮將部分后退至前一位置。后退的原則是：從第一輛開始依次后退，直至控制區(qū)域滿足D1條件。若無法后退，意味著數(shù)量N不足，需要增加數(shù)量N。滿足，輸出4小時的巡邏方案。3。圖3求解巡邏方案總體流程在問題求解過程中采用了貪婪算法以獲得當(dāng)前N輛的最優(yōu)位置步驟如下賦值i=i+1。確定第i輛可以放置的位置，具體方案如下：若是初始時刻，第i輛的位置可以任意標(biāo)記點(diǎn)上放置；若是非初始時刻，第i輛只能選擇與前一時刻所處位置相鄰的標(biāo)記點(diǎn)上；確定第i輛的最優(yōu)位置，選取原則是：在最優(yōu)位置放置，可以最大限度記點(diǎn)。具體而言，對第i輛的每一個可行位置，計算下面的指標(biāo)：=控制區(qū)域中位置，w5~100，以保證未曾遍歷的標(biāo)記點(diǎn)優(yōu)先權(quán)。在所得的最優(yōu)位置上放置，并更新的控制區(qū)域若所有都已放置，則輸出的控制區(qū)域和位置，否則返回步驟(2)。4。否是圖4貪婪算法求解放置位置流程以上算法均通過編程實(shí)現(xiàn)根據(jù)建立的模型，將數(shù)量N取10~20輛一一驗(yàn)算，發(fā)現(xiàn)當(dāng)數(shù)量少于16輛時，找不到滿足D1條件的初始位置當(dāng)數(shù)量為16輛時，通過調(diào)整試算，可以找到滿足D1條件的初始位置，但無法找到巡邏路線，靜止于初始位置不動，這與題意不符。當(dāng)數(shù)量為17輛以上時，開始有一定的活動區(qū)域，可以找到滿足D1條綜上，欲滿足D1條件，該區(qū)最少需配置17輛巡邏。17輛的初始位置和5。圖5滿足D1的最少巡邏方50%5%分別求解N=17~20時滿足D1條件的巡邏方案，并給出相應(yīng)的巡邏效果顯著指表2不同數(shù)量的巡邏效果顯著程度指6。圖 19輛的巡邏方案示意▲ 道路平均長度99m，按20km/h速度行駛 從一個標(biāo)記點(diǎn)移動到相鄰標(biāo)記點(diǎn)需 D3600s，巡邏規(guī)律隱蔽性較好。本文同樣試算數(shù)量在17~20的情況得出巡邏效果顯著程度和隱蔽性指標(biāo)數(shù)據(jù)，3。表3不同數(shù)量的巡邏效果顯著程度和隱蔽性指 巡邏遍歷

巡邏周期平均T(s)

巡邏時間標(biāo)準(zhǔn)S(s) 由上表可知，增加數(shù)量，巡邏周期平均值和巡邏時間標(biāo)準(zhǔn)差平均值均會有所增加，即隱蔽性有所提高。當(dāng)數(shù)量為19輛時，巡邏周期平均值為812s，巡邏時間標(biāo)D1D2的前提下能保證較好的隱蔽性。于3個重點(diǎn)部位的控制，可以始終滿足。研究不同控制率C下巡邏方案的巡邏效表 10輛不同控制率下的巡邏效果顯著程對上表分析可知，巡邏的遍歷率較低，表明幾乎處于固定位置，雖然可以保證3綜合各項指標(biāo)，控制率C=67%的巡邏方案，可保證較高的巡邏遍歷率10輛的較好巡邏方案。10輛的初始位置和巡邏區(qū)域見圖7圖 10輛的巡邏方案分布當(dāng)接警后行駛速度提高到50km/h時，分別求解N=11~13時滿足D1條件的警表5不同數(shù)量巡邏方案的巡邏效果顯著性指8圖 13輛的巡邏方案示意D190%的比例，本文采用統(tǒng)計標(biāo)記點(diǎn)的方式計算，精確性較高。稍加改進(jìn)可用于其他有類似特點(diǎn)的巡邏問題，如移動等，，：[1]等航空航天大學(xué)，2004，第259-264頁，，：日期：2009日期：2009：謝金星等，優(yōu)化建模與LINDO/LINGO軟件，284-297

21，2005,首先讀入node.txtway.txt根據(jù)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計算任兩點(diǎn)間最短路徑長度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標(biāo)記點(diǎn)坐標(biāo)(已擴(kuò)充loadway_new.txt%道路，已擴(kuò)充loaddist.txt任意兩點(diǎn)間最短距離N=size(node_new,1);%節(jié)點(diǎn)數(shù)目imppos=[5112,4806;9126,4266;7434,1332重點(diǎn)坐標(biāo)fori=1:3x1=imppos(i,1y1=imppos(i,2);dismin=1e8;%最短距離dismin_n=0;%for

%重要標(biāo)記點(diǎn)編號 %速度40km/h,3分鐘行駛2000m，2分鐘行駛%速度50km/h,3分鐘行駛2500m，2分鐘行駛%關(guān)系矩陣dd(i,j)表示從i點(diǎn)出發(fā)，以40km/h按i,j間最短路徑行駛，能否在3分內(nèi)到達(dá)，若j2分鐘內(nèi)。%1%關(guān)系矩陣ddd(i,j)表示從i點(diǎn)出發(fā)，以50km/h按i,j間最短路徑行駛，能否在3分內(nèi)到達(dá)，若j2分鐘內(nèi)。%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%趕不到

%將計算結(jié)果為data.mat(手動進(jìn)行計算完全滿足D1的路線（速度40km/h）將dd修改為ddd即可計算速(50km/h的情況closeallloadpicout=0;%是否輸出car=19;%數(shù)量(最少17)TIME=810;17.8s，4h810leiji(1:N)=0;%是否已經(jīng)過某標(biāo)記點(diǎn)，經(jīng)過則為1，否則為0。cp(1:car,1:TIME)=0;%第i輛某一步的位置holdonfortm=1:TIME按步循環(huán)cur(1:N)=0;%代表第i個點(diǎn)是否被覆蓋,覆蓋則取1，否則取0。每一步最開始未確定位置，所以均取0。%/////////////////////////對當(dāng)前步放置/////////////////////////////////////foriii=1:car%依次放置，從第一輛開始fprintf('%dif(tm==1)%初始時刻可放置于任何位(1:N)=0;%標(biāo)記能否放置。=1則此處不可放置(無法到達(dá));=0代

(1:N)=1;t=cp(iii,tm-1);%第iii輛，tm-1時刻(tm>1)位置。%非初始時刻可能%搜索與t位置直連的點(diǎn)，即將可以到達(dá)的位置標(biāo)記為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位置放置，計算覆蓋范 %兼顧覆蓋范圍和重點(diǎn)部位，計算判斷指標(biāo),imp為重點(diǎn)標(biāo)記點(diǎn)編號 nmax=i;%最大指標(biāo)及對應(yīng)標(biāo)記點(diǎn)編

pos(iii)=nmax;%記錄當(dāng)前步第iii個的位,:));%%檢驗(yàn)當(dāng)前的放置方案，若不滿足覆蓋條件和重點(diǎn)部位條件，依次回crit_fg=90;%90%10輛車是要修改放松。crit_imp=3;%重點(diǎn)部位三個都顧及if(tm<=2)%如果前兩步不滿足條件，則數(shù)量不夠，輸出'NotEnoughCar!'%從第一個開始回forcur(1:N)=0;forii=1:carcur=or(cur,dd(pos(iiendbreak;%滿足條件