數(shù)學建模在計算機專業(yè)的應用

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

2、1頂點 v i1 與頂點 vi 2 鄰接。uuuuur有向圖 :邊有指向，（ei ）=（vi 1 ,v i2）=vi1 vi 2 .下面是具體涉及到圖如何存儲的問題：1. 圖 G(V,E)的關(guān)聯(lián)矩陣 R=(r ij )nx m ，若 G(V,E)為無向圖，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的起點若 G(V,E)為有向圖，v是e2的終點ij因此該圖可以用關(guān)聯(lián)矩陣表示出來，如下所示11000001010100R0101001這樣，我們就可以以矩陣的形式將圖存入計00110100000111算

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

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

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

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

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

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

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

10、標，記為：vk (sk , uk )表示系統(tǒng)在第k 階段處于狀態(tài)sk 做出決策 uk 時所獲得的階段效益。這里的階段效益在不同的實際問題中有不同的意義。在例 l 中它表示兩個中轉(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）指標函數(shù)指標函數(shù)是用來街量所實現(xiàn)過程的優(yōu)劣的一種數(shù)量指標，它是一個定義在全過程和所有后部子過程上的確定的數(shù)量函數(shù)，記為：Vk ,n (sk ,uk , sk 1 ,uk 1 ,L , sk ,

11、 uk )k1,2,L ,n頁腳.它應具有可分離性，并滿足遞推關(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 )常見的指標函數(shù)的形式是：1）過程和任一子過程的指標是它所包含的各階段指標的和。既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）過程和任一子過程的指標是它所包含的各階段指標的積。既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ù)指標函數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù)，記為f k (sk ) 。它表示系統(tǒng)在第 k 階段處于狀態(tài) sk 時按最優(yōu)策略行動所獲得總的效益。既fk ( sk )opt Vk ,n ( sk ,uk , sk 1 ,uk 1,L , sk , uk )pk , n ( sk )其中 opt 是最優(yōu)化（ optimization ）的縮寫，根據(jù)實際問題可取 max(最大值 ) 和 min(最小值

13、), opt 表示對所有允許策略 pk , n ( sk ) 使后面算式取最優(yōu)。p k ,n (sk )下面利用動態(tài)規(guī)劃的逆推歸納法， 將例 1 從最后一個城市E 逐步推算到第一個城市 A，在此 fk (sk ) 表示第 k 階段從城市 sk 到城市 E 最短路。1)當 k=4 時：要求 f 4 (s4 ) ，由于第 4 階段只有兩個城市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 。頁腳.2)當 k=3時： s的

14、取值為 C 、C、C ，從 C 出發(fā)到 E 有兩條路，一條是經(jīng)31231過 D1到 E，另一條是經(jīng)過 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，相應決策為 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)當 k=2時： s2 的取值為 B1、B2 、B3，從 B1 出發(fā)到 E 有三條路，分別是經(jīng)過 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)當 k=1 時：s1 的只有一個取值為A. 從 A 出發(fā)到 E 有三條路，分別是經(jīng)過B 、B