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

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

2、以把街道看做線段，安裝攝像頭的位置看作點(diǎn)，這樣工業(yè)區(qū)的布局圖就轉(zhuǎn)化為一個圖論模型，本題就轉(zhuǎn)化為求圖的最小點(diǎn)覆蓋的問題了。利用圖的關(guān)聯(lián)矩陣求出最小覆蓋的點(diǎn)，這些點(diǎn)就是安裝攝像頭的位置！</p><p>　　關(guān)鍵字：0—1整數(shù)規(guī)劃 關(guān)聯(lián)矩陣 最小點(diǎ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ù)太少，因此負(fù)責(zé)此區(qū)域安全的相關(guān)市政部門決定安裝監(jiān)控攝像頭，以協(xié)助保安工作。下圖給出了該工業(yè)區(qū)的地圖，其中給出了需要用閉路電視進(jìn)行監(jiān)控的區(qū)域范圍，并標(biāo)記44個可以安裝攝像頭的位置，要求設(shè)計一種安裝方案使安裝的攝像頭數(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>　　關(guān)聯(lián)矩陣R= (n為定點(diǎn)數(shù)，m為邊數(shù))，其中= 即僅當(dāng)以i為頂點(diǎn)的鄰邊是時，=1 </p&g

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

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

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

11、()或位置m上（）安裝一個攝像頭，或者在這兩個位置上都安裝攝像頭?？梢酝瑫r用兩個攝像頭監(jiān)控一條街道，并且有些時候這樣做能夠帶來一些好處：在圖一中，在位置4和位置8上同時安裝攝像頭似乎對這條街道顯得有些多余，但這兩個攝像頭同時能夠?qū)ξ恢?，6和7方向的死胡同進(jìn)行監(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、機(jī)求解就必須先完成這個步驟。通過人工查找共有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>　　運(yùn)行程序得到的結(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個攝像頭，即在標(biāo)號為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)控范圍！圖二用橢圓標(biāo)記出了這些攝像頭的位置。</p><p>　　嘗試轉(zhuǎn)化為圖論中的最小點(diǎn)覆蓋問題</p><p>　　5.1 問題分析與模型建立</p><p>　　上面我們已經(jīng)用0—1整數(shù)規(guī)劃求出了最優(yōu)解，再仔細(xì)觀察該工業(yè)區(qū)的布局圖，不難發(fā)現(xiàn)基本每條街道的路口都是可以安裝攝像頭的位置

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

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

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

30、t;<p>　?、?Ⅱ Ⅲ Ⅳ Ⅴ Ⅵ Ⅶ</p><p>　　下面從該矩陣出發(fā)求對應(yīng)圖的最小點(diǎn)覆蓋，步驟如下</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、通過上面的例子我們可以簡單的概括最小點(diǎn)覆蓋的啟發(fā)式算法：在關(guān)聯(lián)矩陣中找出恰有兩個“1“的那一列中”1“所在的行,選取其中任意的一行i，i點(diǎn)就歸屬最小覆蓋集，劃去i行及i行中元素”1“所在的列，這樣便得到一個新的矩陣。對新矩陣重復(fù)上述操作直到不能繼續(xù)進(jìn)行此操作。</p><p>　　用此算法可以求解出圖三的最小點(diǎn)覆蓋集，即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 }，要注意特殊點(diǎn)位置45也在其中，我們把位置45附近的點(diǎn)集做細(xì)微的調(diào)整，把位置41和位置45換成位置43和位置44也可以滿足題目的要求。所以最終安裝攝像頭的位置是點(diǎn)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的點(diǎn)的位置就是安裝攝像頭的位置。由于每條街道的兩端基本（也有極少數(shù)街道只有一端可以安裝攝像頭）都是可以安裝攝像頭的位置，我們可以把街道看做線段，安

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

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