數(shù)學建模課程設計---閉路電視監(jiān)控系統(tǒng)的優(yōu)化設計

1、<p>　　閉路電視監(jiān)控系統(tǒng)的優(yōu)化設計</p><p><b>　　摘要:</b></p><p>　　本題主要解決的問題是選擇安裝攝像頭的位置，并且在保證所有區(qū)域被監(jiān)控的條件下安裝攝像頭數(shù)目最少。我們首先將這一問題轉(zhuǎn)化為0—1整數(shù)規(guī)劃問題，并用LINDO軟件求解。由于每條街道的兩端基本（也有極少數(shù)街道只有一端可以安裝攝像頭）都是可以安裝攝像頭的位置，我們可

2、以把街道看做線段，安裝攝像頭的位置看作點，這樣工業(yè)區(qū)的布局圖就轉(zhuǎn)化為一個圖論模型，本題就轉(zhuǎn)化為求圖的最小點覆蓋的問題了。利用圖的關聯(lián)矩陣求出最小覆蓋的點，這些點就是安裝攝像頭的位置！</p><p>　　關鍵字：0—1整數(shù)規(guī)劃 關聯(lián)矩陣 最小點覆蓋</p><p>　　Abstract :</p><p>　　The aim of this term is to

3、 choose the places of fixing web-cameras，and make sure the whole aeras are under the control .Under this condition ,we should make sure that the number of fixed web-cameras is minimal. Firstly ,we convert this problem to

4、 the case of zero –one integer programming ,and LINDO can solve this changing case .Secondly,we can change our idea to think about this problem .Because the two points of each street are available places for fixing web-c

5、ameras (only a very few streets ha</p><p>　　Keywords: zero—one integral layout </p><p>　　correlative matrix </p><p>　　minimal vertex covering</p><p><b>　

6、　問題重述</b></p><p>　　某市的工業(yè)區(qū)發(fā)生多起夜間入室行竊案件，此工業(yè)區(qū)有保安巡邏，但保安人數(shù)太少，因此負責此區(qū)域安全的相關市政部門決定安裝監(jiān)控攝像頭，以協(xié)助保安工作。下圖給出了該工業(yè)區(qū)的地圖，其中給出了需要用閉路電視進行監(jiān)控的區(qū)域范圍，并標記44個可以安裝攝像頭的位置，要求設計一種安裝方案使安裝的攝像頭數(shù)目最少但保證需監(jiān)控的區(qū)域全在監(jiān)控范圍。</p><p>&

7、lt;b>　　圖一</b></p><p><b>　　名詞和符號說明</b></p><p>　　xn 二值變量，取0或1</p><p>　　表示位置n和m在同一條街道上</p><p>　　關聯(lián)矩陣R= (n為定點數(shù)，m為邊數(shù))，其中= 即僅當以i為頂點的鄰邊是時，=1 </p&g

8、t;<p>　　（4） 覆蓋 ： 若圖G的每條邊都至少有一個端點在頂點集V的一個子集K之中，則稱K為G的覆蓋。</p><p>　?。?）一個圖可以有很多覆蓋，含頂點個數(shù)最少的覆蓋稱為最小覆蓋。</p><p><b>　　3模型假設</b></p><p>　　（1）所安裝的監(jiān)控攝像頭都可以360度旋轉(zhuǎn)，因此在幾條街道的交匯處安

9、裝一個攝像頭就可以同時對這些街道進行監(jiān)控</p><p>　?。?）可以安裝攝像頭的地方都是一條街道的末端，即一般可以安裝攝像頭的相鄰的地點之間是一條街道</p><p>　?。?）轉(zhuǎn)化為圖論問題時假定所有的路口都是可以安裝攝像頭的位置</p><p><b>　　問題分析與模型建立</b></p><p>　　題目給我

10、們提供了可以安裝攝像頭進行監(jiān)控的地方，我們只需要考慮在某地方是否安裝攝像頭。安與不安是兩個方面，我們考慮用0—1規(guī)劃來解決此問題。定義二值變量xn（n=1，2，…，43，44），當且僅當在位置n處設置了攝像頭此時的變量踩取1，否則為0.要使安裝的攝像頭數(shù)量最少，即的值最??！</p><p>　　為了保證監(jiān)控到位，必須限定每條街道都應至少處于一個攝像頭監(jiān)控之下。因此，如果位置n和m之間存在一條街道，則需要在位置n上

11、()或位置m上（）安裝一個攝像頭，或者在這兩個位置上都安裝攝像頭。可以同時用兩個攝像頭監(jiān)控一條街道，并且有些時候這樣做能夠帶來一些好處：在圖一中，在位置4和位置8上同時安裝攝像頭似乎對這條街道顯得有些多余，但這兩個攝像頭同時能夠?qū)ξ恢?，6和7方向的死胡同進行監(jiān)控。</p><p>　　經(jīng)過上述分析我們可以建立一個非常簡單的0—1整數(shù)規(guī)劃模型：</p><p>　　Minimize &l

12、t;/p><p>　　: xm+xn>=1</p><p>　　n=1,2,3,….,43,44</p><p><b>　　模型求解</b></p><p>　　要求解上述0—1整數(shù)規(guī)劃模型，我們首先要把約束條件滿足的等式全部找出來，即每條街道上安裝攝像頭的位置的xn值之和大于等于1.這個過程比較繁瑣，但使用計算

13、機求解就必須先完成這個步驟。通過人工查找共有52條街道，即可寫出52個約束不等式，因為這些不等式?jīng)]有規(guī)律，故只能一個一個的寫出。我們知道解50個以下的變量的0—1規(guī)劃問題LINDO比較方便，本題只有44個變量故用LINDO軟件求解</p><p>　　將根據(jù)題目列出的不等式帶入上面建立的0—1規(guī)劃模型，并輸入LINDO：</p><p>　　MIN X1+X2+X3+X4+X5+X6+X

14、7+X8+X9+X10+X11+X12+X13+X14+X15</p><p>　　+X16+X17+X18+X19+X20+X21+X22+X23+X24+X25+X26+X27+X28+X29</p><p>　　+X30+X31+X32+X33+X34+X35+X36+X37+X38+X39</p><p>　　+X40+X41+X42+X43+X44<

15、/p><p>　　SUBJECT TO</p><p>　　X43 >=1</p><p>　　X41+X43 >=1</p><p>　　X41+X42 >=1</p><p>　　X42+X44 >=1</p><p>　　X40+X39 >=1 </

16、p><p>　　X39+X38>=1</p><p>　　X38+X37>=1</p><p>　　X43+X42>=1</p><p>　　X42+X38>=1</p><p>　　X44 >=1</p><p>　　X44+X37>=1</p>

17、;<p>　　X41+X39>=1</p><p>　　X37+X35>=1</p><p>　　X34+X36>=1</p><p>　　X32+X33>=1</p><p>　　X33+X34>=1</p><p>　　X34+X35>=1</p>&

18、lt;p>　　X35+X10>=1</p><p><b>　　X10+X9>=1</b></p><p><b>　　X3+X10>=1</b></p><p><b>　　X3+X1>=1</b></p><p><b>　　X3+X

19、4>=1</b></p><p><b>　　X4+X5>=1</b></p><p><b>　　X4+X8>=1</b></p><p><b>　　X8+X7>=1</b></p><p><b>　　X8+X6>=1&

20、lt;/b></p><p>　　X33+X31>=1</p><p>　　X31+X28>=1</p><p>　　X28+X29>=1</p><p>　　X29+X30>=1</p><p>　　X23+X24>=1</p><p>　　X24+X25&

21、gt;=1</p><p>　　X25+X26>=1</p><p>　　X26+X27>=1</p><p>　　X34+X15>=1</p><p>　　X15+X18>=1</p><p>　　X18+X19>=1</p><p>　　X19+X20>=

22、1</p><p>　　X20+X21>=1</p><p>　　X21+X22>=1</p><p>　　X21+X25>=1</p><p>　　X18+X12>=1</p><p>　　X19+X16>=1</p><p>　　X10+X12>=1<

23、;/p><p>　　X12+X16>=1</p><p>　　X11+X12>=1</p><p>　　X11+X13>=1</p><p>　　X13+X16>=1</p><p>　　X13+X14>=1</p><p>　　X14+X17>=1</p&

24、gt;<p><b>　　X14+X2>=1</b></p><p><b>　　X1+X2>=1</b></p><p><b>　　END</b></p><p><b>　　INT 44</b></p><p>　　最后一行

25、表示44個決策變量全部為0—1變量</p><p>　　運行程序得到的結(jié)果x1=x4=x8=x10=x12=x13=x14=x18=x19=x21=x24=x26=x28=x30=x33=x34=x37=x39=x42=x43=x44=1</p><p>　　由此可見最佳方案需要安裝21個攝像頭，即在標號為1，4，8，10，12，13，14，18，19，21，24，26，28，30，33，

26、34，37，39，42，43，44的道口安裝攝像頭就可保證整個工業(yè)區(qū)的道路全在監(jiān)控范圍！圖二用橢圓標記出了這些攝像頭的位置。</p><p>　　嘗試轉(zhuǎn)化為圖論中的最小點覆蓋問題</p><p>　　5.1 問題分析與模型建立</p><p>　　上面我們已經(jīng)用0—1整數(shù)規(guī)劃求出了最優(yōu)解，再仔細觀察該工業(yè)區(qū)的布局圖，不難發(fā)現(xiàn)基本每條街道的路口都是可以安裝攝像頭的位置

27、，但有且僅有一個路口不是，我們考慮大量位置的時候可以忽略這個位置，假設它也可以安裝攝像頭。我們可以把該工業(yè)區(qū)的布局圖轉(zhuǎn)化成一個圖論模型，每條街道表示邊，街道兩端的路口表示頂點。我們把每條邊和每個頂點分別標號，可以得到下面的點邊圖（圖三）</p><p>　　我們必須先介紹覆蓋和最小覆蓋兩個概念：</p><p>　　（1）若圖G的每條邊都至少有一個端點在頂點集V的一個子集K之中，則稱K為G

28、的覆蓋。</p><p>　?。?）一個圖可以有很多覆蓋，含頂點個數(shù)最少的覆蓋稱為最小覆蓋。</p><p>　　換言之在本道題目中就是要求每條街道都至少有一個路口安裝攝像頭，并且保證安裝攝像頭的數(shù)目最小。我們可以清晰的看到攝像頭的安置問題實際為求圖的最小點覆蓋。</p><p><b>　　5.2 模型求解</b></p>&l

29、t;p>　　因為關聯(lián)矩陣表示的是頂點和邊之間的關系，所以關聯(lián)矩陣與覆蓋密切相關。頂點集V的子集K是圖G的一個覆蓋，當且僅當G的關聯(lián)矩陣K中的各頂點所對應的行內(nèi)，每列至少存在一個元素“1”。從關聯(lián)矩陣可以找出一個最小覆蓋。</p><p>　　最小點覆蓋問題沒什么高效的算法，先就以一個簡化的圖的為例子說明最小點覆蓋的求解方法。</p><p>　　該圖的關聯(lián)矩陣為 R=</p&g

30、t;<p>　　Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ Ⅵ Ⅶ</p><p>　　下面從該矩陣出發(fā)求對應圖的最小點覆蓋，步驟如下</p><p>　　在矩陣中取恰有兩個“1”的那一列中“1”所在的行（如3行），令3∈k，劃去3行及3行中元素所在的Ⅱ， Ⅲ，Ⅵ列，得</p><p><b>　?、?Ⅳ Ⅴ Ⅶ</b></p><

31、p>　　在上面新矩陣中再取恰有兩個“1”的那一列中“1”所在的行（如5行），令5∈k，劃去5行及5行中元素“1”所在的列Ⅴ，Ⅶ，得</p><p><b>　?、?Ⅳ </b></p><p>　　因為1’大于’2，1‘大于‘4（若對所有的j有，記j大于k），劃去2，4行，1∈k，過程結(jié)束，最小覆蓋k=（1，3，5）</p><p>　　

32、通過上面的例子我們可以簡單的概括最小點覆蓋的啟發(fā)式算法：在關聯(lián)矩陣中找出恰有兩個“1“的那一列中”1“所在的行,選取其中任意的一行i，i點就歸屬最小覆蓋集，劃去i行及i行中元素”1“所在的列，這樣便得到一個新的矩陣。對新矩陣重復上述操作直到不能繼續(xù)進行此操作。</p><p>　　用此算法可以求解出圖三的最小點覆蓋集，即k={ X1, X4, X8, X10, X12, X13, X14, X18, X19, X

33、21, X24, X26, X28 ,X30, X33, X34, X37, X39, X 41,X42, X45 }，要注意特殊點位置45也在其中，我們把位置45附近的點集做細微的調(diào)整，把位置41和位置45換成位置43和位置44也可以滿足題目的要求。所以最終安裝攝像頭的位置是點1，4，8，10，12，13，14，18，19，21，24，26，28，30，33，34，37，39，42，43，44，和0—1規(guī)劃的求解相同。</p&g

34、t;<p><b>　　6總結(jié)</b></p><p>　　本題主要解決的問題是選擇安裝攝像頭的位置，并且在保證所有區(qū)域被監(jiān)控的條件下安裝攝像頭數(shù)目最少。我們首先將這一問題轉(zhuǎn)化為0—1整數(shù)規(guī)劃問題，并用LINDO軟件求解，求出的值為1的點的位置就是安裝攝像頭的位置。由于每條街道的兩端基本（也有極少數(shù)街道只有一端可以安裝攝像頭）都是可以安裝攝像頭的位置，我們可以把街道看做線段，安

35、裝攝像頭的位置看作點，這樣工業(yè)區(qū)的布局圖就轉(zhuǎn)化為一個圖論模型，本題就轉(zhuǎn)化為求圖的最小點覆蓋的問題了。利用圖的關聯(lián)矩陣求出最小覆蓋的點集，這些點就是安裝攝像頭的位置！</p><p>　　我們發(fā)現(xiàn)兩種方法都可以求出閉路電視系統(tǒng)的最優(yōu)監(jiān)控方案，但轉(zhuǎn)化圖的頂點數(shù)目比較多時用最小點覆蓋問題求解過程比較麻煩，像本題45個頂點求解就很麻煩，但用0—1整數(shù)規(guī)劃問題求解就比較容易，所以最小點覆蓋的啟發(fā)算法比較適合頂點數(shù)目少的圖論

36、模型!并且用最小點覆蓋求解的前提是必須能轉(zhuǎn)化為圖論模型！</p><p><b>　　參考文獻：</b></p><p>　　熊啟才 數(shù)學模型方法及應用 重慶大學出版社 2005年</p><p>　　劉建州 實用數(shù)學建模教程 武漢理工大學出版社 2003年</p><p>　　Christelle gueret