數(shù)學(xué)建模在計(jì)算機(jī)專業(yè)的應(yīng)用

1、.應(yīng)用一圖論算法圖論在計(jì)算機(jī)處理問(wèn)題中占有重要地位， 現(xiàn)實(shí)中的很多問(wèn)題最終都可以轉(zhuǎn)化成圖論問(wèn)題， 或者要借助圖結(jié)構(gòu)來(lái)存儲(chǔ)和處理。 但是怎么把一圖存入計(jì)算機(jī)就要涉及到數(shù)學(xué)建模的知識(shí)。比如下面一圖：如果要求出從節(jié)點(diǎn) v1 到節(jié)點(diǎn) v5 的所有路徑，就可以借助計(jì)算機(jī)來(lái)很輕松的解決。 但前提條件是， 必須要把圖以一種計(jì)算機(jī)可以理解的形式存進(jìn)去，即要把它抽象為數(shù)學(xué)問(wèn)題。在此，我們需要定義一些關(guān)于圖的概念，以便更好的描述問(wèn)題。邊與頂點(diǎn)的關(guān)系有如下幾種典型情況：簡(jiǎn)單圖 ：無(wú)自回環(huán)，無(wú)重邊的圖。頁(yè)腳.無(wú)向圖 ：邊沒(méi)有指向，（ e） =vi,vi=vivi. 此時(shí)稱邊 e與頂點(diǎn) vi,vi關(guān)聯(lián)，稱i212i21

2、1頂點(diǎn) v i1 與頂點(diǎn) vi 2 鄰接。uuuuur有向圖 :邊有指向，（ei ）=（vi 1 ,v i2）=vi1 vi 2 .下面是具體涉及到圖如何存儲(chǔ)的問(wèn)題：1. 圖 G(V,E)的關(guān)聯(lián)矩陣 R=(r ij )nx m ，若 G(V,E)為無(wú)向圖，0v與e不關(guān)聯(lián)ijr1v與 e關(guān)聯(lián) , e為非自回環(huán)ijijj2vi與 ej 關(guān)聯(lián) , ej 為自回環(huán)0v 與e不關(guān)聯(lián)ijrij1vi 是ej的起點(diǎn)若 G(V,E)為有向圖，v是e2的終點(diǎn)ij因此該圖可以用關(guān)聯(lián)矩陣表示出來(lái)，如下所示11000001010100R0101001這樣，我們就可以以矩陣的形式將圖存入計(jì)00110100000111算

3、機(jī)頁(yè)腳.2. 鄰接矩陣圖 G(V,E)的鄰接矩陣 A=(a ij ) n xn ,若 G(V,E)為無(wú)向圖， aij = 從vi 到的 vj 邊數(shù)，若不鄰接，取 0；若 G(V,E)為有向圖， aij = 從 vi 到 vj 的有向邊數(shù)，若無(wú)，取 0.0110010011A100110110101110應(yīng)用二動(dòng)態(tài)規(guī)劃問(wèn)題動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過(guò)程最優(yōu)化的數(shù)學(xué)方法。 20 世紀(jì) 50 年代初美國(guó)數(shù)學(xué)家等人在研究多階段決策過(guò)程的優(yōu)化問(wèn)題時(shí)， 提出了著名的最優(yōu)化原理， 把多階段過(guò)程轉(zhuǎn)化為一系列單階段問(wèn)題，利用各階段之間的關(guān)系，逐個(gè)求解，創(chuàng)立了解決這類過(guò)程優(yōu)化問(wèn)題的新方法動(dòng)態(tài)規(guī)劃。也是

4、信息學(xué)競(jìng)賽中選頁(yè)腳.手必須熟練掌握的一種算法。 多階段決策過(guò)程的最優(yōu)化問(wèn)題。 含有遞推的思想以及各種數(shù)學(xué)原理（加法原理，乘法原理等等） 。動(dòng)態(tài)規(guī)劃一般可分為線性動(dòng)規(guī)， 區(qū)域動(dòng)規(guī)，樹形動(dòng)規(guī)，背包動(dòng)規(guī)四類。舉例線性動(dòng)規(guī)：攔截導(dǎo)彈，合唱隊(duì)形，挖地雷，建學(xué)校，劍客決斗等；區(qū)域動(dòng)規(guī)：石子合并， 加分二叉樹，統(tǒng)計(jì)單詞個(gè)數(shù)，炮兵布陣等；樹形動(dòng)規(guī)：貪吃的九頭龍， 二分查找樹，聚會(huì)的歡樂(lè)，數(shù)字三角形等；背包問(wèn)題： 01 背包問(wèn)題，完全背包問(wèn)題，分組背包問(wèn)題，二維背包，裝箱問(wèn)題，擠牛奶。多階段決策的實(shí)際問(wèn)題很多， 下面通過(guò)具體例子， 說(shuō)明什么是動(dòng)態(tài)規(guī)劃模型中數(shù)學(xué)建模知識(shí)的運(yùn)用。最短路線問(wèn)題：某工廠需要把一批貨物從

5、城市 A 運(yùn)到城市 E，中間可經(jīng)過(guò) B1 、 B2 、B3 、C1、C2、 C3、D1、D2 等城市，各城市之間的交通線和距離如下圖所示，問(wèn)應(yīng)該選擇一條什么路線，使得從A 到 E 的距離最短？頁(yè)腳.B6C113845D1564A89B27C22E661D3738C33B37下面引進(jìn)幾個(gè)動(dòng)態(tài)規(guī)劃的基本概念和相關(guān)符號(hào)。(1)階段 (Stage)把所給問(wèn)題的過(guò)程， 按時(shí)間和空間特征劃分成若干個(gè)相互聯(lián)系的階段，以便按次序去求每個(gè)階段的解， 階段總數(shù)一般用字母n 表示，用字母 k 表示階段變量。如例中(最短路線問(wèn)題 )可看作是 n=4 階段的動(dòng)態(tài)規(guī)劃問(wèn)題， k=2 表示處于第二階段。(2)狀態(tài) (Sta

6、te)狀態(tài)表示每個(gè)階段開始時(shí)系統(tǒng)所處的自然狀況或客觀條件，它描述了研究問(wèn)題過(guò)程狀況。描述各階段狀態(tài)的變量稱為狀態(tài)變量，常用字母 sk 表示第 k 階段的狀態(tài)變量，狀態(tài)變量的取值圍稱為狀態(tài)集，用Sk 表示。如例 l 中，第一階段的狀態(tài)為A（即出發(fā)位置）。第二階段有三個(gè)狀態(tài)：B1 、B2、 B3 ，狀態(tài)變量 s2 =B2 表示第 2 階段系統(tǒng)所處的位置是B2 。第 2 階段的狀態(tài)集S2= B 1 、B2、B3。動(dòng)態(tài)規(guī)劃中的狀態(tài)變量應(yīng)具有如下性質(zhì)：當(dāng)某階段狀態(tài)給定以后， 在這個(gè)階段以后過(guò)程的發(fā)展不受這個(gè)階段以前各個(gè)階段狀態(tài)的影響。也就是說(shuō)，未來(lái)系統(tǒng)頁(yè)腳.所處的狀態(tài)只與系統(tǒng)當(dāng)前所處的狀態(tài)有關(guān)，而與系統(tǒng)

7、過(guò)去所處的狀態(tài)無(wú)關(guān)，即過(guò)去歷史只能通過(guò)當(dāng)前的狀態(tài)去影響它未來(lái)的發(fā)展，這種特點(diǎn)稱為無(wú)后效性 （又稱馬爾可夫性）。如果所選定的狀態(tài)變量不具備無(wú)后效性，就不能作為狀態(tài)變量來(lái)構(gòu)造動(dòng)態(tài)規(guī)劃模型。 如例 1 中，當(dāng)某階段的初始狀態(tài)即所在的城市選定以后，從這個(gè)狀態(tài)以后的運(yùn)貨路線只與這個(gè)城市有關(guān)，不受以前的運(yùn)貨路線影響， 所以是滿足狀態(tài)的無(wú)后效性的。（3）決策 (Decision)當(dāng)系統(tǒng)在某階段處于某種狀態(tài)，可以采取的行動(dòng)（或決定、選擇），從而確定下一階段系統(tǒng)將到達(dá)的狀態(tài)，稱這種行動(dòng)為決策。 描述決策的變量， 稱為決策變量。常用字母u k(sk)表示第 k 階段系統(tǒng)處于狀態(tài)sk 時(shí)的決策變量。決策變量的取值圍

8、稱為決策集，用Dk(sk)表示。在例 l 的第二階段中，若從狀態(tài)B2 出發(fā)，可以做出三種不同的決策，其允許的決策集為 D2(B2)= C 1、 C2、C3，決策 u 2(B2)= C 2 表示第二階段處于狀態(tài)B2，選擇的確行動(dòng)下一階段是走到C2 。（4）策略 (Policy)系統(tǒng)從第k 階段的狀態(tài)sk 開始由每階段的決策按順序組成的決策序列 uk(sk )，u k+1(sk+1 )， ，u n(sn )稱為一個(gè)策略（ k=1,2, ，n）,記作 pk,n (sk ) 。在例 l 中， p2,4(B2)= u 2(B2 )= C2， u3 (C2)= D 1，u 4(D1)=E是一個(gè)策略，表示第

9、二階段從狀態(tài) B2 出發(fā)，沿著 B2 C2 D1 E 的方向走到終點(diǎn)。注意策略必須是一串實(shí)際可行的序列行動(dòng)。頁(yè)腳.（5）狀態(tài)轉(zhuǎn)移方程系統(tǒng)由這一階段的 個(gè)狀態(tài)進(jìn)行決策后轉(zhuǎn)變到下 階段的另 個(gè)狀態(tài)稱為狀態(tài)轉(zhuǎn)移，狀態(tài)轉(zhuǎn)移既與狀態(tài)有關(guān)， 又與決策有關(guān)， 描述狀態(tài)轉(zhuǎn)移關(guān)系的方程稱為狀態(tài)轉(zhuǎn)移方程，記為：sk+1 =T k(sk， uk)它的實(shí)際意義是當(dāng)系統(tǒng)第k 階段處于狀態(tài) sk 做決策 uk 時(shí)，第 k+1 階段系統(tǒng)轉(zhuǎn)移到狀態(tài) sk+1 。狀態(tài)轉(zhuǎn)移方程在不同的問(wèn)題中有不同的具體表現(xiàn)形式，在例l 中，狀態(tài)轉(zhuǎn)移方程表示為： sk+1 =u k(sk)。（6）階段指標(biāo)階段效益是衡量系統(tǒng)階段決策結(jié)果的一種數(shù)量指

10、標(biāo)，記為：vk (sk , uk )表示系統(tǒng)在第k 階段處于狀態(tài)sk 做出決策 uk 時(shí)所獲得的階段效益。這里的階段效益在不同的實(shí)際問(wèn)題中有不同的意義。在例 l 中它表示兩個(gè)中轉(zhuǎn)站的距離，如 v2 (B2 ,u2 (B2 ) C2 ) d (B2, C2 ) 7 表示從中轉(zhuǎn)站 B2 走到中轉(zhuǎn)站 C2 之間的距離為7。更一般地有 vk (sk ,uk ( sk )d (sk , uk ( sk ) 。（7）指標(biāo)函數(shù)指標(biāo)函數(shù)是用來(lái)街量所實(shí)現(xiàn)過(guò)程的優(yōu)劣的一種數(shù)量指標(biāo)，它是一個(gè)定義在全過(guò)程和所有后部子過(guò)程上的確定的數(shù)量函數(shù)，記為：Vk ,n (sk ,uk , sk 1 ,uk 1 ,L , sk ,

11、 uk )k1,2,L ,n頁(yè)腳.它應(yīng)具有可分離性，并滿足遞推關(guān)系式：Vk ,n (sk , uk , sk 1 , uk 1 ,L , sk ,uk )sk , uk ,Vk 1,n (sk 1, uk 1 ,L , sk ,uk )常見(jiàn)的指標(biāo)函數(shù)的形式是：1）過(guò)程和任一子過(guò)程的指標(biāo)是它所包含的各階段指標(biāo)的和。既nLv j ( sj ,u j ) vk (sk , uk ) Vk 1,n (sk 1 ,uk 1 ,L, sk , uk )Vk,n (sk ,uk , sk 1, uk 1 , , sk , uk )j 12）過(guò)程和任一子過(guò)程的指標(biāo)是它所包含的各階段指標(biāo)的積。既nVk,n (s

12、k , uk , sk 1, uk 1 ,L , sk ,uk )v j ( sj , u j )vk ( sk ,uk ) Vk 1,n (sk 1, uk 1 ,L , sk ,uk )j 1（8）最優(yōu)值函數(shù)指標(biāo)函數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù)，記為f k (sk ) 。它表示系統(tǒng)在第 k 階段處于狀態(tài) sk 時(shí)按最優(yōu)策略行動(dòng)所獲得總的效益。既f(wàn)k ( sk )opt Vk ,n ( sk ,uk , sk 1 ,uk 1,L , sk , uk )pk , n ( sk )其中 opt 是最優(yōu)化（ optimization ）的縮寫，根據(jù)實(shí)際問(wèn)題可取 max(最大值 ) 和 min(最小值

13、), opt 表示對(duì)所有允許策略 pk , n ( sk ) 使后面算式取最優(yōu)。p k ,n (sk )下面利用動(dòng)態(tài)規(guī)劃的逆推歸納法， 將例 1 從最后一個(gè)城市E 逐步推算到第一個(gè)城市 A，在此 fk (sk ) 表示第 k 階段從城市 sk 到城市 E 最短路。1)當(dāng) k=4 時(shí)：要求 f 4 (s4 ) ，由于第 4 階段只有兩個(gè)城市D1、 D2（即 s4 的取值為 D1 、D2），從 D1 到 E 只有一條路，故 f 4 ( D1 )d (D1 , E)4, u4 * ( D1 )E ，同理f4 (D2 )d ( D2 , E)3, u4* (D2 )E 。頁(yè)腳.2)當(dāng) k=3時(shí)： s的

14、取值為 C 、C、C ，從 C 出發(fā)到 E 有兩條路，一條是經(jīng)31231過(guò) D1到 E，另一條是經(jīng)過(guò) D2到 E ，顯然：f(C )d (C1 , D1 ) f 4 (D1 )min3 4*(C )Dmin7, u31d (C1 , D2 ) f 4 (D2 )5 3311即從 C1 出發(fā)到 E 的最短路為7，相應(yīng)決策為 u3* (C1)D1 ，最短路線是 C1D1E。同理f3 (C2 )d (C2 , D1 ) f 4 ( D1)6 45,u3* (C2 ) D2d (C2 , D2 ) f4 (D2 )2 3f3 (C3 )d (C3 , D1) f 4 ( D1 )1 45,u3* (C

15、3 ) D1d (C3 , D2 ) f4 ( D2 )3 32)當(dāng) k=2時(shí)： s2 的取值為 B1、B2 、B3，從 B1 出發(fā)到 E 有三條路，分別是經(jīng)過(guò) C、C、C到 E，則有：123d (B1, C1) f3 (C1 )6 7f2 (B1 )d (B1, C2 ) f3 (C2 )4 59,u2* (B1 ) C2d (B1, C3 ) f3 (C3 )5 5d( B2 , C1 ) f3 (C1)8 7同理f 2 ( B2 )d( B2 , C2 )f3 (C2 )7511,u2*(B2)C3d( B2 , C3 ) f3 (C3 )6 5d(B3 ,C1) f 3 (C1 )7 7f2 (B3 )d(B3 ,C2 )f 3 (C2 )8512,u2* (B3)C3d(B3, C3 )f 3 (C3 )752)當(dāng) k=1 時(shí)：s1 的只有一個(gè)取值為A. 從 A 出發(fā)到 E 有三條路，分別是經(jīng)過(guò)B 、B