1、數(shù)學(xué)建模與運(yùn)籌模型,上海海事大學(xué) 鄧偉 ,線性規(guī)劃 運(yùn)輸問題 指派問題 網(wǎng)絡(luò)優(yōu)化 動態(tài)規(guī)劃,目錄,例 某工廠在計(jì)劃期內(nèi)要安排，兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn) 單位產(chǎn)品所需的設(shè)備臺時(shí)及A，B兩種原材料的消耗、資源的限制，如下表。問題：工廠應(yīng)分別生產(chǎn)多少單位，產(chǎn)品才能使工廠獲利最多？,線性規(guī)劃,例 下料問題 某工廠要做100套鋼架，每套用長為2.9m，2.1m，1.5m的圓鋼各一根，已知原料每根長7.4m。應(yīng)如何下料，可使所用原料最?。?解：共可設(shè)計(jì)下列5種下料方案,線性規(guī)劃,建模步驟： (1)確定決策變量：我們需要作出決策或者選擇的量，一般情況下，題目問什么就設(shè)什么為決策變量。 (2)找出約束條件：即

2、決策變量受到的所有的約束。 (3)寫出目標(biāo)函數(shù)：即問題所要達(dá)到的目標(biāo)，并明確是求max還是min。,線性規(guī)劃,例 混合配料問題 某糖果廠用原料1、2、3加工三種不同牌號的糖果甲、乙、丙。已知各種牌號糖果中原料1、2、3的含量、原料每月限用量、三種牌號糖果的加工費(fèi)及售價(jià)，如下表所示。該廠每月如何生產(chǎn)才能獲利最大？,線性規(guī)劃,解：用i=1,2,3代表原料1,2,3, j=1,2,3代表糖果甲、乙、丙。Xij表示第j中產(chǎn)品中原料i的含量，則 對于原料1： x11, x12, x13; 對于原料2： x21, x22, x23; 對于原料3： x31, x32, x33; 對于甲： x11, x21,

3、 x31; 對于乙： x12, x22, x32; 對于丙： x13, x23, x33; 目標(biāo)函數(shù)：利潤最大，利潤=收入-原料成本-加工費(fèi) 約束條件：原料用量限制，含量限制,線性規(guī)劃,線性規(guī)劃,求解方法： 1.圖解法 適合含有兩個(gè)決策變量的模型； max z = x1+3x2 s.t. x1+ x26 -x1+2x28 x1 0, x20,可行域,目標(biāo)函數(shù)等值線,最優(yōu)解,6,4,-8,6,0,x1,x2,線性規(guī)劃,2.單純形法(人工變量法、對偶單純形法) 軟件求解：lingo，lindo，Matlab Min f= 0.4x1+1.5x2+x3+1.3x4 S.t. 0.3x1+3x2 +

4、+1.5x4=320 0.5x1+ +2x3+x4 =240 1.4x1+ +0.7x4=420,線性規(guī)劃,將某種物資從m個(gè)產(chǎn)地遇到n個(gè)銷地，每個(gè)產(chǎn)地都有一定的產(chǎn)量ai，i=1,2,m，每個(gè)銷地都對物資有一定的需求量bj,j=1,2,n。已知從第i個(gè)產(chǎn)地向第j個(gè)銷地運(yùn)送單位物資的運(yùn)價(jià)為cij，總產(chǎn)量等于總需求量( )。如何調(diào)運(yùn)物資，才能使總運(yùn)費(fèi)最小？ 設(shè)xij為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，,運(yùn)輸問題,運(yùn)輸表： (產(chǎn)銷平衡的運(yùn)輸問題)求解方法： 1.確定初始基本可行解（西北角法、最小元素法、vogal法） 2.最優(yōu)性檢驗(yàn)； 3.迭代求新的基本可行解。,運(yùn)輸問題,例 某食品公司下屬的三個(gè)食品廠

5、A1、A2、A3生產(chǎn)食品，3個(gè)廠每月的生產(chǎn)能力分別為7噸、4噸、9噸，食品被運(yùn)到B1、B2、B3、B4四個(gè)銷售點(diǎn)，它們對方便食品的月需求量分別為3噸、6噸、5噸、6噸，運(yùn)輸表如下表，試制定最優(yōu)運(yùn)送方案。,運(yùn)輸問題,解：1.確定初始基可行解 最小元素法：,運(yùn)輸問題,解：1.確定初始基可行解(最小元素法) 初始基本可行解對應(yīng)的目標(biāo)函數(shù)值： f=3*4+10*3+1*3+2*1+4*6+5*3=86,運(yùn)輸問題,解：2.最優(yōu)性檢驗(yàn) (1)位勢： ui+vj =cij (i=1,2,m,j=1,2,n) 其中cij 為基本可行解中基變量對應(yīng)的單位運(yùn)價(jià)。 注：m+n-1個(gè)方程，m+n個(gè)變量。 (2)利用位

6、勢求非基變量檢驗(yàn)數(shù) 檢驗(yàn)數(shù)計(jì)算公式： cij -ui-vj (3)檢驗(yàn)數(shù)全都大于等于零時(shí)對應(yīng)的解為最優(yōu)解。,運(yùn)輸問題,位勢： 檢驗(yàn)數(shù)：,運(yùn)輸問題,3.迭代求新基本可行解 (1)負(fù)檢驗(yàn)數(shù)中最小者對應(yīng)的變量進(jìn)基； (2)在運(yùn)輸表中找一個(gè)包含進(jìn)基變量的閉回路，這個(gè)回路上其他頂點(diǎn)均為基變量。依次對閉回路的四個(gè)頂點(diǎn)標(biāo)號，將頂點(diǎn)分為奇點(diǎn)格和偶點(diǎn)格； (3)偶點(diǎn)格的最小值作為調(diào)整量，所有奇點(diǎn)格+調(diào)整量；偶點(diǎn)格-調(diào)整量，即一次迭代。 (4)按位勢方程求新解對應(yīng)的位勢及檢驗(yàn)數(shù)，判別最優(yōu)性。,運(yùn)輸問題,閉回路：,運(yùn)輸問題,迭代及新基本可行解的檢驗(yàn)數(shù)計(jì)算：,運(yùn)輸問題,產(chǎn)銷不平衡運(yùn)輸問題： 1. 供大于求，引入虛擬銷

7、售點(diǎn)，并假設(shè)它的需求量為 供不應(yīng)求，引入虛擬的產(chǎn)地，并假設(shè)它的產(chǎn)量為 由于虛擬銷地是不存在的，實(shí)際上這個(gè)差值是在產(chǎn)地貯存的，故從產(chǎn)地到虛擬銷地的單位運(yùn)價(jià)為0； 同理，由于虛擬產(chǎn)地是不存在的，所以虛設(shè)的產(chǎn)地到各個(gè)銷地的單位運(yùn)價(jià)也為0.,運(yùn)輸問題,例 2個(gè)化肥廠供應(yīng)3個(gè)地區(qū)的化肥，試決定運(yùn)費(fèi)最小的調(diào)運(yùn)方案。 解：增加虛設(shè)的銷地B4，銷量為10，構(gòu)造產(chǎn)銷平衡的運(yùn)輸表。,運(yùn)輸問題,初始基可行解及其檢驗(yàn)數(shù)： 迭代求新基本可行解：,運(yùn)輸問題,n項(xiàng)任務(wù)，恰好有n個(gè)人承擔(dān)，由于每個(gè)人的專長不同，完成各工作的效率不同，于是產(chǎn)生了應(yīng)指派哪個(gè)人去完成哪項(xiàng)，使得完成n項(xiàng)任務(wù)的總效率最高的問題，這類問題稱為指派問題。

8、例 有一份說明書，需要譯成英、日、德、俄四種文字，現(xiàn)有甲乙丙丁四個(gè)人，他們將說明書譯成不同文字所需要的時(shí)間如下表所示，問應(yīng)指派哪個(gè)人完成哪項(xiàng)工作，耗用的總時(shí)間最少？,指派問題,一般地，有n項(xiàng)任務(wù)、n個(gè)完成人，第i人完成第j項(xiàng)任務(wù)的代價(jià)為cij(i,j=1,2,n),為了求得總代價(jià)最小的指派方案，引入0-1型變量xij ,令 數(shù)學(xué)模型為 注：指派問題是0-1整數(shù)規(guī)劃的特例，也是運(yùn)輸問題的特例，其產(chǎn)地和銷地?cái)?shù)均為1，各產(chǎn)地產(chǎn)量和各銷地銷量均為1.,指派問題,指派問題的求解方法：匈牙利法。 匈牙利法基于下面的事實(shí)：如果系數(shù)矩陣的所有元素滿足：cij=0，而其中有n個(gè)位于不同行不同列的一組0元素，則只

9、要令對應(yīng)于這些0元素位置的xij=1，其余的xij=0，就得到最優(yōu)解。 如 則,指派問題,求解上例： 行變換得 列變換得 畫出最少覆蓋0元素的直線，r=4=矩陣階數(shù)， 則可以找到最優(yōu)解,所需最少時(shí)間=4+4+9+11=28 甲-俄語 從而得到最優(yōu)指派：乙-日語 丙-英語 丁-德語,指派問題,例 分配甲、乙、丙、丁四個(gè)人去完成A、B、C、D、E五項(xiàng)任務(wù)，每人完成各項(xiàng)任務(wù)的時(shí)間如下表所示，由于任務(wù)重，人手少，考慮以下兩種情況下的最優(yōu)分配方案，使得完成任務(wù)的總時(shí)間最少。 (1)任務(wù)E必須完成，其他4項(xiàng)任務(wù)可選3項(xiàng)完成，但甲不能做A項(xiàng)工作；(2)其中有一人完成2項(xiàng)，其他人每人完成1項(xiàng)。 解：這是一人數(shù)

10、與任務(wù)數(shù)不等的指派問題，若用匈牙利法求解，需作以下處理。,指派問題,(1)由于任務(wù)數(shù)大于人數(shù)，所以需要有一個(gè)虛擬的人，設(shè)為戊。因?yàn)楣ぷ鱁必須完成，故設(shè)戊完成E的時(shí)間為M(M為非常大的正數(shù))，即戊不能做工作E，其余的假想時(shí)間為0，建立的效率矩陣為： 采用匈牙利解法求解過程如下：,指派問題,(1)由于r=4矩陣階數(shù)=5，需要調(diào)整0元素的分布。 從該矩陣可看出，r=5=矩陣階數(shù)，因此能找到最優(yōu)指派方案。 甲-B 乙-D 丙-E 丁-A 戊-C（戊 為虛擬人，即任務(wù)C無人完成） 最少的耗時(shí)數(shù) z=29+20+32+24=105,指派問題,(2)思路： 方案1：甲，【甲】，乙，丙，丁 方案2：甲，乙，【

11、乙】，丙，丁 方案3：甲，乙，丙，【丙】，丁 方案4：甲，乙，丙，丁，【丁】 方案5：甲，【甲】，乙，【乙】，丙，【丙】，丁，【丁】，工作A，B，C，D，E，虛擬工作F，G，H。 這些方案較煩瑣，采用以下思路更為簡便。 設(shè)有虛擬人戊，他集五人的優(yōu)勢為一身，即戊的費(fèi)用是每人的最低，戊所做的工作即為此項(xiàng)工作的費(fèi)用最低者的工作，效率矩陣分配表為：,指派問題,采用匈牙利解法求解： 對C3做0元素的最小直線覆蓋，得r=5=n。結(jié)果為 甲-B 乙-D 丙-E 丁-A 戊-C 但戊為虛擬人，不能真做，它做C工作是借乙(此列最小時(shí)數(shù)26是C所創(chuàng)業(yè)績)的優(yōu)勢，應(yīng)由乙來做，即乙做兩件工作：D、C。,指派問題,例

12、最大收益的最優(yōu)分配問題：有5名工人完成5項(xiàng)不同的任務(wù)收 益如表所示： 求使總收益達(dá)到最高的任務(wù)分配方案。 解：這是一個(gè)尋求總收益為最大值的極大化問題，需要轉(zhuǎn)化為極小化問題才能用匈牙利解法。 收益矩陣B=（bij），設(shè)b=maxbij，令cij=b-bij ，C=（cij），以C為效率矩陣的極小化問題即是原最大收益的極大化問題轉(zhuǎn)化而來。,指派問題,b=maxbij=19，令cij=19-bij ，C=（cij）， 繼續(xù)對C矩陣采用匈牙利法求解，得到C的最優(yōu)分配方案為 即 甲-D 乙-B 丙-E 丁-A 戊-C ，求得的最大總收益為74.,指派問題,2,3,7,1,8,4,5,6,6,1,3,4,

13、10,5,2,7,5,9,3,4,6,8,2,網(wǎng)絡(luò)優(yōu)化,最短路徑問題：有一批貨物要從節(jié)點(diǎn)1運(yùn)送到節(jié)點(diǎn)8，這兩點(diǎn)間的通路如下圖，每條弧旁邊的數(shù)字表明該弧的長度?？偮窂皆蕉蹋\(yùn)費(fèi)越低，為節(jié)省運(yùn)輸費(fèi)用，應(yīng)該選擇怎樣的運(yùn)輸路線？,求從1到8的最短路徑。,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1, w1=0,min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1 X=1,4, w4=1,w1=0,w1=0,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,4,m

14、in c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2 X=1,2,4, w2=2,w1=0,w4=1,w2=2,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,min c16,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3 X=1,2,4,6, w6=3,w2=2,w4=1,w1=0,w6=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,min c23,c25,c4

15、7,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3 X=1,2,4,6,7, w7=3,w2=2,w4=1,w1=0,w6=3,w7=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,min c23,c25,c75,c78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6 X=1,2,4,5,6,7, w5=6,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,

16、4,6,7,min c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8 X=1,2,3,4,5,6,7, w3=8,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,w3=8,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,min c38,c58,c78=min 8+6,6+4,3+8=min 14,10,11=10 X=1,2,3,4,5,6,7,8, w8=10,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,w3=8,w8=10,2,3,7

17、,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,8,1到10的最短路徑為1，4，7，5，8，長度為10。,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,w3=8,w8=10,網(wǎng)絡(luò)優(yōu)化,最大流問題：給出一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容量，在不超過每條弧的容量的前提下，求出從發(fā)點(diǎn)到收點(diǎn)的最大流量。,邊的容量和流量：容量uij，流量xij 可行流： 滿足以下條件的流稱為可行流： 1、每一個(gè)節(jié)點(diǎn)流量平衡 2、0 xij uij 如果xij=uij，邊從i到j(luò)的方向是飽和的； 如果xijuij，邊從i到j(luò)的方向是不飽

18、和的；,網(wǎng)絡(luò)優(yōu)化,（1，2）是飽和的,（1，2）是不飽和的 間隙為12=u12-x12=5-3=2,如果xij=0，邊從j到i的方向是飽和的 （2，1）是飽和的 如果xij0，邊從j到i的方向是不飽和的,網(wǎng)絡(luò)優(yōu)化,（2，1）是不飽和的 間隙為12=x12=5,給出一個(gè)初始的可行流xij=0,網(wǎng)絡(luò)優(yōu)化,2,3,5,4,6,7,1,f=0,f=0,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,找到所有的不飽和邊，以及各邊可以調(diào)整流量的方向,2,3,5,4

19、,6,7,1,f=0,f=0,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,=3,=1,=8,=8,x=0,找到一條從1到7的不飽和鏈,鏈的間隙為： = min8,3,1,8=1 調(diào)整鏈的流量：xij=xij+ ,2,3,5,4,6,7,1,f=1,f=1,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=1,x=1,x=1,x=1,調(diào)整流量，f

20、=1。繼續(xù)求出網(wǎng)絡(luò)的不飽和邊,2,3,5,4,6,7,1,f=1,f=1,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=1,x=1,x=1,x=1,=1,=6,=9,=7,求出一條從1到7的不飽和鏈,=min 7,1,6,9=1, 調(diào)整流量 xij=xij+1, f=f+1=2,2,3,5,4,6,7,1,f=2,f=2,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=1,x=0,x=0,x=1,x=0,x=0,x=0,x=1

21、,x=1,x=1,x=1,x=0,調(diào)整流量，繼續(xù)求出網(wǎng)絡(luò)的不飽和邊,=5,=8,=7,求出一條從1到7的不飽和鏈,=min 7,5,8=5, 調(diào)整流量 xij=xij+5, f=f+5=2+5=7,2,3,5,4,6,7,1,f=7,f=7,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=6,x=0,x=0,x=1,x=0,x=0,x=0,x=6,x=1,x=1,x=6,x=0,調(diào)整流量，繼續(xù)求出網(wǎng)絡(luò)的不飽和邊,=4,=4,=3,=6,求出一條從1到7的不飽和鏈,=min 6,7,4,3=3, 調(diào)整流量 xij=xij+3, f=f+3=7+

22、3=10,2,3,5,4,6,7,1,f=10,f=10,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=6,x=0,x=3,x=4,x=3,x=0,x=0,x=9,x=1,x=1,x=6,x=0,調(diào)整流量，繼續(xù)求出網(wǎng)絡(luò)的不飽和邊,2,3,5,4,6,7,1,f=10,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=6,x=0,x=3,x=4,x=3,x=0,x=0,x=9,x=1,x=1,x=6,x=0,f=10,=1,=3,=7,=3,求出一條從1到7的不飽和鏈,=min 3,1,3,7

23、=1, 調(diào)整流量 xij=xij+1, f=f+1=10+1=11,2,3,5,4,6,7,1,f=11,f=11,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=6,x=0,x=4,x=5,x=3,x=1,x=0,x=9,x=2,x=1,x=6,x=0,調(diào)整流量，繼續(xù)求出網(wǎng)絡(luò)的不飽和邊,已找不到一條從1到7的不飽和鏈，從1開始可以到達(dá)的節(jié)點(diǎn)為1，2，3,2,3,5,4,6,7,1,f=11,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=6,x=0,x=4,x=5,x=3,x=1,x=0,

24、x=9,x=2,x=1,x=6,x=0,f=11,已求得最大流,最大流f=11，最小割集為（2,5）（3,4）（3,5） u25+u34+u35=6+4+1=11,最短路問題： 給定一個(gè)運(yùn)輸網(wǎng)絡(luò)，兩點(diǎn)之間連線上的數(shù)字表示兩點(diǎn)之間的距離，試求一條從A到B的運(yùn)輸路線，使總距離最短。 可將問題分為四個(gè)階段：第一階段，從A到B；第二階段，從B到C；第三階段，從C到D；第四階段，從D到E。 完全枚舉：3*3*2*1=24條。 最優(yōu)解：AB3 C2 D2 E,動態(tài)規(guī)劃,階段：將所給問題的過程，按時(shí)間或空間特征分解成相互聯(lián)系的階段，以便按次序求每階段的解 k描述階段的變量 狀態(tài)：表示每個(gè)階段開始時(shí)所處的自然

25、狀況或條件，描述了研究問題的狀況。 sk狀態(tài)變量 Sk狀態(tài)集合 S1=A,S2=B1,B2,B3,S3=C1,C2,C3, S4=D1,D2 動態(tài)規(guī)劃中狀態(tài)的性質(zhì)：無后效性，即如果某個(gè)階段狀態(tài)給定之后，則在這階段以后過程的發(fā)展不受這階段以前各階段狀態(tài)的影響。 決策：指在某階段對可供選擇狀態(tài)的選擇，描述的變量稱為決策變量。 dk( sk )決策變量 Dk( sk )允許決策集合 D2(B1)=C1,C2,C3,動態(tài)規(guī)劃,全過程策略：由所有各階段組成的決策函數(shù)序列,簡稱策略。記為： P1,n(s1) 或P1,n(s1)=d1(s1), d2(s2), dn(sn) k子過程策略(后部子策略)：由k

26、階段開始到最后階段結(jié)束，組成的決策函數(shù)序列。 Pk,n(sk)=dk(sk), dk+1(sk+1), dn(sn) 最優(yōu)策略：使整個(gè)問題達(dá)到最優(yōu)效果的策略。 P*1,n(A)=B3,C2,D2 ,E AB3 C2 D2 E 允許策略集：可供選擇策略的范圍，用P表示。 動態(tài)規(guī)劃方法就是要從允許策略集P中找出最優(yōu)策略 P*k,n,動態(tài)規(guī)劃,狀態(tài)轉(zhuǎn)移方程： 本階段狀態(tài)與上一階段狀態(tài)和上一階段決策的關(guān)系，用狀態(tài)轉(zhuǎn)移方程來表示。 sk+1=Tk(sk,dk) 該方程描述了由第k階段到第k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律，又稱為狀態(tài)轉(zhuǎn)移函數(shù)。 sk+1=dk (sk) 階段指標(biāo)：衡量某階段決策效益優(yōu)劣的策略指標(biāo)，

27、如距離，成本，利潤等。 vk (sk,dk) 指標(biāo)函數(shù)：衡量所選定策略優(yōu)劣的數(shù)量指標(biāo)。 Vk,n (sk,Pk,n)= Vk,n (sk,dk,sk+1,sn+1 ),動態(tài)規(guī)劃,常見指標(biāo)函數(shù)形式(分離性，遞推關(guān)系) Vk,n (sk,Pk,n)= Vk,n (sk,dk,sk+1,sn+1 ) = Vk (sk,dk )+ Vk+1 (sk+1, Pk,n) Vk,n (sk,Pk,n)= Vk,n (sk,dk,sk+1,sn+1 ) = Vk (sk,dk )* Vk+1 (sk+1, Pk,n) 最優(yōu)指標(biāo)函數(shù):指標(biāo)函數(shù)的最優(yōu)值，fk(sk)表示從第k階段狀態(tài)sk開始采用最優(yōu)策略P*k,n

28、到過程終止時(shí)的最佳效益值。 fk(sk)=opt Vk,n (sk,dk,sk+1,sn+1 ) f1(s1)表示從第1階段狀態(tài)s1采用最優(yōu)策略P*1,n到過程終止時(shí)的最佳效益值。,動態(tài)規(guī)劃,動態(tài)規(guī)劃的基本思想： 1. 多階段決策過程劃分階段，恰當(dāng)?shù)倪x取狀態(tài)變量、決策變量和定義最優(yōu)指標(biāo)函數(shù)，從而將問題化為一族同類型的子問題逐個(gè)求解。 2. 求解時(shí)從邊界條件開始，逆（或順）過程行進(jìn)方向，逐段遞推尋優(yōu)。 3. 既將當(dāng)前一段與未來各段分開，又將當(dāng)前效益與未來效益結(jié)合起來考慮的一種最優(yōu)化方法。 如何建立動態(tài)規(guī)劃模型： 1. 分析識別問題的多階段特性，按時(shí)間或空間的先后順序適當(dāng)?shù)貏澐譂M足遞推關(guān)系的若干階

29、段。 2. 確定狀態(tài)變量，滿足可知性和無后效性。一般為累計(jì)量和隨遞推過程變化的量。 3.找到狀態(tài)轉(zhuǎn)移方程。 4.正確確定基本方程。,基礎(chǔ)：最優(yōu)化定理 作為整個(gè)過程的最優(yōu)策略具有如下性質(zhì)：不管在此最優(yōu)策略上的某個(gè)狀態(tài)以前的狀態(tài)和決策如何，對該狀態(tài)而言，以后所有的決策必定構(gòu)成最優(yōu)子策略。 對最短路問題而言,從最短路上任一點(diǎn)到終點(diǎn)的部分道路（最短路上的子路）也一定是從該點(diǎn)到終點(diǎn)的最短路。,動態(tài)規(guī)劃,從最后一段開始計(jì)算，由后向前逐步推移至A點(diǎn)。 第四階段，由D1到E只有一條線路，其長度f4(D1)=3，同理f4(D2)=4； 第三階段，由Cj到Di均有兩種選擇，即 第二階段，由Bj到Ci均有三種選擇，

30、即,動態(tài)規(guī)劃,第一階段，由A到B，有三種選擇，即 f1(A)=12，說明從A到E的最短距離為12，最短路線的確定可按計(jì)算順序反推而得，即A-B3-C2-D2-E,動態(tài)規(guī)劃,一個(gè)著名的命題：一個(gè)串村走戶的賣貨郎，他從某個(gè)村莊出發(fā)，通過若干個(gè)村莊一次且僅一次，最后仍回到原出發(fā)的村莊，問：應(yīng)如何選擇行走路線，能使得總的行程最短。 設(shè)有n個(gè)城市，1,2,n。Dij表示從i城到j(luò)城的距離。 規(guī)定推銷員是從城市1開始的，設(shè)推銷員走到i城，記Ni2,3,i-1,i+1,n 表示由1城到i城的中間城市集合。 S表示到達(dá)i城中途所經(jīng)過的城市的集合，則有S Ni 1）選取（i,S）作為狀態(tài)變量，表示推銷員從城市1

31、開始走到i城，經(jīng)過若干個(gè)城市，構(gòu)成集合S。 2）最優(yōu)值函數(shù)fk(i,S)為從城市1開始經(jīng)過k個(gè)中間城市的S集到達(dá)i城的最短路線的距離。,貨郎擔(dān)問題 （TSP問題traveling salesperson problem）,3）遞推關(guān)系式： fk(i,S)=min fk-1(j,Sj)+Dji (k=1,2, ,n-1. i=2,3,n. S Ni) 邊界條件：f0(i,)= D1i 4） Pk(i,S)為最優(yōu)決策函數(shù)，表示從1城開始經(jīng)k個(gè)中間城市到i城的最短路線上緊挨著i城前面的那個(gè)城市。,例：當(dāng)推銷員從1城出發(fā)，經(jīng)過每個(gè)城市一次且僅一次，最后回到1城，問按怎樣的路線走，使總的行程距離最短。（

32、四個(gè)城市，其距離矩陣如下表）,5）由邊界條件可知： f0(i,)= D1i f0(2,)= D128，f0(3,)= D135，f0(4,)= D146 當(dāng)k=1時(shí)，即從1城開始，中間經(jīng)過一個(gè)城市到達(dá)i城的最短距離是： f1(2,3)= f0(3,)+ D325+9=14 f1(2,4)= f0(4,)+ D426+7=13 f1(3,2)= f0(2,)+ D238+8=16 f1(3,4)= f0(4,)+ D436+8=14 f1(4,2)= f0(2,)+ D248+5=13 f1(4,3)= f0(3,)+ D345+5=10,當(dāng)k=2時(shí)，即從1城開始，中間經(jīng)過兩個(gè)城市到達(dá)i城的最短距離是： f2(2,3,4)=min f1(3, 4)+D32 f1(4, 3)+D42 =min14+9,10+7=17 P2(2,3,4)=4,f2(3,2,4)=min f1(2, 4)+D23 f1(4, 2)+D43 =min13+8 ,13+8=21 P2(3,2,4)=2或