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

應(yīng)用一 圖論算法 圖論在計(jì)算機(jī)處理問題中占有重要地位，現(xiàn)實(shí)中的很多問題最終都可以轉(zhuǎ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é)問題。在此，我們需要定義一些關(guān)于圖的概念，以便更好的描述問題。邊與頂點(diǎn)的關(guān)系有如下幾種典型情況：簡(jiǎn)單圖：無(wú)自回環(huán)，無(wú)重邊的圖。無(wú)向圖：邊沒有指向， 此時(shí)稱邊 與頂點(diǎn)關(guān)聯(lián)，稱頂點(diǎn)與頂點(diǎn)鄰接。有向圖:邊有指向，下面是具體涉及到圖如何存儲(chǔ)的問題：1. 圖G(V,E)的關(guān)聯(lián)矩陣 ，若G(V,E)為無(wú)向圖， 若G(V,E)為有向圖，因此該圖可以用關(guān)聯(lián)矩陣表示出來(lái)，如下所示這樣，我們就可以以矩陣的形式將圖存入計(jì)算機(jī)2. 鄰接矩陣圖G(V,E)的鄰接矩陣 ,若G(V,E)為無(wú)向圖，=從到的邊數(shù)，若不鄰接，取0；若G(V,E)為有向圖，=從到的有向邊數(shù)，若無(wú)，取0.應(yīng)用二 動(dòng)態(tài)規(guī)劃問題 動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過(guò)程最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國(guó)數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過(guò)程的優(yōu)化問題時(shí)，提出了著名的最優(yōu)化原理，把多階段過(guò)程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系，逐個(gè)求解，創(chuàng)立了解決這類過(guò)程優(yōu)化問題的新方法動(dòng)態(tài)規(guī)劃。也是信息學(xué)競(jìng)賽中選手必須熟練掌握的一種算法。多階段決策過(guò)程的最優(yōu)化問題。含有遞推的思想以及各種數(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ì)的歡樂，數(shù)字三角形等；背包問題：01背包問題，完全背包問題，分組背包問題，二維背包，裝箱問題，擠牛奶。多階段決策的實(shí)際問題很多，下面通過(guò)具體例子，說(shuō)明什么是動(dòng)態(tài)規(guī)劃模型中數(shù)學(xué)建模知識(shí)的運(yùn)用。最短路線問題：某工廠需要把一批貨物從城市A運(yùn)到城市E，中間可經(jīng)過(guò)B1 、B2、B3、C1、C2、C3、D1、D2等城市，各城市之間的交通線和距離如下圖所示，問應(yīng)該選擇一條什么路線，使得從A到E的距離最短？C1B1 6 3D1 8 4 5AB2 5 6 4 EC2 9 8 7 2D3 6 3 6 7 1 C3B3 8 3 7下面引進(jìn)幾個(gè)動(dòng)態(tài)規(guī)劃的基本概念和相關(guān)符號(hào)。(1)階段(Stage)把所給問題的過(guò)程，按時(shí)間和空間特征劃分成若干個(gè)相互聯(lián)系的階段，以便按次序去求每個(gè)階段的解，階段總數(shù)一般用字母n表示，用字母k表示階段變量。 如例中 (最短路線問題)可看作是n=4階段的動(dòng)態(tài)規(guī)劃問題，k=2表示處于第二階段。 (2)狀態(tài)(State)狀態(tài)表示每個(gè)階段開始時(shí)系統(tǒng)所處的自然狀況或客觀條件，它描述了研究問題過(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= B1 、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)所處的狀態(tài)只與系統(tǒng)當(dāng)前所處的狀態(tài)有關(guān)，而與系統(tǒng)過(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í)的決策變量。決策變量的取值范圍稱為決策集，用Dk(sk)表示。 在例l的第二階段中，若從狀態(tài)B2出發(fā)，可以做出三種不同的決策，其允許的決策集為D2(B2)= C1、C2、C3，決策u 2(B2)= C2表示第二階段處于狀態(tài)B2，選擇的確行動(dòng)下一階段是走到C2。 （4）策略(Policy)系統(tǒng)從第k階段的狀態(tài)sk開始由每階段的決策按順序組成的決策序列 u k(sk) ，u k+1(sk+1)，u n(sn)稱為一個(gè)策略（k=1,2, ，n）,記作。在例l中，p2,4(B2)= u 2(B2)= C2，u3(C2)= D1，u 4(D1)=E是一個(gè)策略，表示第二階段從狀態(tài)B2出發(fā)，沿著B2C2D1E的方向走到終點(diǎn)。注意策略必須是一串實(shí)際可行的序列行動(dòng)。（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=Tk(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)移方程在不同的問題中有不同的具體表現(xiàn)形式，在例l中，狀態(tài)轉(zhuǎn)移方程表示為：sk+1=uk(sk)。（6）階段指標(biāo)階段效益是衡量系統(tǒng)階段決策結(jié)果的一種數(shù)量指標(biāo)，記為：表示系統(tǒng)在第k階段處于狀態(tài)sk做出決策uk時(shí)所獲得的階段效益。這里的階段效益在不同的實(shí)際問題中有不同的意義。在例l中它表示兩個(gè)中轉(zhuǎn)站的距離，如表示從中轉(zhuǎn)站B2走到中轉(zhuǎn)站C2之間的距離為7。更一般地有。（7）指標(biāo)函數(shù)指標(biāo)函數(shù)是用來(lái)街量所實(shí)現(xiàn)過(guò)程的優(yōu)劣的一種數(shù)量指標(biāo)，它是一個(gè)定義在全過(guò)程和所有后部子過(guò)程上的確定的數(shù)量函數(shù)，記為：它應(yīng)具有可分離性，并滿足遞推關(guān)系式：常見的指標(biāo)函數(shù)的形式是：1）過(guò)程和任一子過(guò)程的指標(biāo)是它所包含的各階段指標(biāo)的和。既2）過(guò)程和任一子過(guò)程的指標(biāo)是它所包含的各階段指標(biāo)的積。既（8）最優(yōu)值函數(shù)指標(biāo)函數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù)，記為。它表示系統(tǒng)在第k階段處于狀態(tài)sk時(shí)按最優(yōu)策略行動(dòng)所獲得總的效益。既 其中opt是最優(yōu)化（optimization）的縮寫，根據(jù)實(shí)際問題可取max(最大值)和min(最小值),表示對(duì)所有允許策略使后面算式取最優(yōu)。下面利用動(dòng)態(tài)規(guī)劃的逆推歸納法，將例1從最后一個(gè)城市E逐步推算到第一個(gè)城市A，在此表示第k階段從城市sk到城市E最短路。1)當(dāng)k=4時(shí)：要求，由于第4階段只有兩個(gè)城市D1、D2（即s4的取值為D1、D2），從D1到E只有一條路，故，同理。2)當(dāng)k=3時(shí)：s3的取值為C1、C2、C3，從C1出發(fā)到E有兩條路，一條是經(jīng)過(guò)D1到E，另一條是經(jīng)過(guò)D2到E ，顯然：即從C1出發(fā)到E的最短路為7，相應(yīng)決策為，最短路線是C1D1E。同理 2)當(dāng)k=2時(shí)：s2的取值為B