數(shù)學(xué)建模(美賽)數(shù)學(xué)規(guī)劃

1、 線性規(guī)劃線性規(guī)劃 整數(shù)規(guī)劃整數(shù)規(guī)劃 目標(biāo)規(guī)劃目標(biāo)規(guī)劃非線性規(guī)劃非線性規(guī)劃 動態(tài)規(guī)劃動態(tài)規(guī)劃 圖圖 論論 排排 隊(duì)隊(duì) 論論數(shù)學(xué)規(guī)劃模型數(shù)學(xué)規(guī)劃模型線線 性性 規(guī)規(guī) 劃劃目的目的內(nèi)容內(nèi)容2. 掌握用數(shù)學(xué)軟件包求解線性規(guī)劃問題掌握用數(shù)學(xué)軟件包求解線性規(guī)劃問題.1. 了解線性規(guī)劃的基本內(nèi)容了解線性規(guī)劃的基本內(nèi)容.2. 用數(shù)學(xué)軟件包用數(shù)學(xué)軟件包MATLAB求解線性規(guī)劃問題求解線性規(guī)劃問題.1. 兩個引例兩個引例. 3. 建模案例：投資的收益與風(fēng)險建模案例：投資的收益與風(fēng)險.問題問題 ： 任務(wù)分配問題：某車間有甲、乙兩臺機(jī)床，可用于加工三種工件.假定這兩臺車床的可用臺時數(shù)分別為800和900，三種工件的

2、數(shù)量分別為400、600和500，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺時數(shù)和加工費(fèi)用如下表.問怎樣分配車床的加工任務(wù)，才能既滿足加工工件的要求，又使加工費(fèi)用最低？ 單位工件所需加工臺時數(shù) 單位工件的加工費(fèi)用 車床類 型 工件1 工件2 工件3 工件1 工件2 工件3 可用臺時數(shù) 甲 0.4 1.1 1.0 13 9 10 800 乙 0.5 1.2 1.3 11 12 8 900 引例引例解解 設(shè)在甲車床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，在乙車床上加工工件1、2、3的數(shù)量分別為x4、x5、x6,可建立以下線性規(guī)劃模型： 解答線性規(guī)劃模型的一般形式線性規(guī)劃模型的一般形

3、式11min,1,2,., .s.t.0,1,2,., .ni iinik kikiucxa xb inxin 目標(biāo)函數(shù)和所有的約束條件都是設(shè)計(jì)變量目標(biāo)函數(shù)和所有的約束條件都是設(shè)計(jì)變量的線性函數(shù)的線性函數(shù).min. s.tucxAxbvlbxvub矩矩陣陣形形式式：用用MATLAB優(yōu)化工具箱解線性規(guī)劃優(yōu)化工具箱解線性規(guī)劃min z=cX s.t.AXb1. 模型：命令：x=linprog（c, A, b） 2. 模型：min z=cX s.t.AXbbeqXAeq命令：x=linprog（c，A，b，Aeq,beq）注意：若沒有不等式： 存在，則令A(yù)= ，b= .bAX 3. 模型：min z

4、=cX s.t.AXbbeqXAeqVLBXVUB命令：1 x=linprog（c，A，b，Aeq,beq, VLB，VUB） 2 x=linprog（c，A，b，Aeq,beq, VLB，VUB, X0） 注意：1 若沒有等式約束: , 則令A(yù)eq= , beq= . 2其中X0表示初始點(diǎn) beqXAeq4. 命令：x,fval=linprog()返回最優(yōu)解及處的目標(biāo)函數(shù)值fval.解解 編寫編寫M文件文件xxgh1.m如下：如下：c=-0.4 -0.28 -0.32 -0.72 -0.64 -0.6; A=0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.0

5、5 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08; b=850;700;100;900; Aeq=; beq=; vlb=0;0;0;0;0;0; vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub) To MATLAB (xxgh1)解解: 編寫編寫M文件文件xxgh2.m如下：如下： c=6 3 4; A=0 1 0; b=50; Aeq=1 1 1; beq=120; vlb=30,0,20; vub=; x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)To MATLAB (xxgh2)123m

6、in( 634 )xzxx32120030 xxx1231111 2 0s .t. 0105 0 xxxs.t.Xz8121110913min 9008003 . 12 . 15 . 000000011 . 14 . 0X改寫為：例例3 問題一的解答 問題問題編寫編寫M文件文件xxgh3.m如下如下:f = 13 9 10 11 12 8;A = 0.4 1.1 1 0 0 0 0 0 0 0.5 1.2 1.3;b = 800; 900;Aeq=1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1;beq=400 600 500;vlb = zeros(6,1);vub=;

7、x,fval = linprog(f,A,b,Aeq,beq,vlb,vub)To MATLAB (xxgh3)結(jié)果結(jié)果:x = 0.0000 600.0000 0.0000 400.0000 0.0000 500.0000fval =1.3800e+004 即在甲機(jī)床上加工600個工件2,在乙機(jī)床上加工400個工件1、500個工件3，可在滿足條件的情況下使總加工費(fèi)最小為13800. 投資的收益和風(fēng)險投資的收益和風(fēng)險二、基本假設(shè)和符號規(guī)定二、基本假設(shè)和符號規(guī)定三、模型的建立與分析三、模型的建立與分析1.總體風(fēng)險用所投資的Si中最大的一個風(fēng)險來衡量,即max qixi|i=1，2,n4. 模型簡

8、化：四、模型四、模型1 1的求解的求解 由于a是任意給定的風(fēng)險度，到底怎樣給定沒有一個準(zhǔn)則，不同的投資者有不同的風(fēng)險度.我們從a=0開始，以步長a=0.001進(jìn)行循環(huán)搜索，編制程序如下：a=0;while(1.1-a)1 c=-0.05 -0.27 -0.19 -0.185 -0.185; Aeq=1 1.01 1.02 1.045 1.065; beq=1; A=0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.055 0;0 0 0 0 0.026; b=a;a;a;a; vlb=0,0,0,0,0;vub=; x,val=linprog(c,A,b,Aeq,beq,

9、vlb,vub); a x=x Q=-val plot(a,Q,.)，axis(0 0.1 0 0.5)，hold on a=a+0.001;end xlabel(a),ylabel(Q)To MATLAB（xxgh5）計(jì)算結(jié)果：計(jì)算結(jié)果：五、五、 結(jié)果分析結(jié)果分析返 回4 4.在a=0.006附近有一個轉(zhuǎn)折點(diǎn)，在這一點(diǎn)左邊，風(fēng)險增加很少時，利潤增長 很快.在這一點(diǎn)右邊，風(fēng)險增加很大時，利潤增長很緩慢，所以對于風(fēng)險和 收益沒有特殊偏好的投資者來說，應(yīng)該選擇曲線的拐點(diǎn)作為最優(yōu)投資組合， 大約是a*=0.6%，Q*=20% ，所對應(yīng)投資方案為: 風(fēng)險度 收益 x0 x1 x2 x3 x4 0.00

10、60 0.2019 0 0.2400 0.4000 0.1091 0.2212 3.3.曲線上的任一點(diǎn)都表示該風(fēng)險水平的最大可能收益和該收益要求的最小風(fēng)險.對于不同風(fēng)險的承受能力，選擇該風(fēng)險水平下的最優(yōu)投資組合.2 2.當(dāng)投資越分散時，投資者承擔(dān)的風(fēng)險越小，這與題意一致.即: 冒險的投資者會出現(xiàn)集中投資的情況，保守的投資者則盡量分散投資.1.1.風(fēng)險大，收益也大.整數(shù)規(guī)劃整數(shù)規(guī)劃解解 設(shè)在甲車床上加工工件1、2、3的數(shù)量分別為整數(shù)x1、x2、x3，在乙車床上加工工件1、2、3的數(shù)量分別為整數(shù)x4、x5、x6,可建立以下整數(shù)線性規(guī)劃模型： 解答）為整數(shù)，（且621iix）為整數(shù)，（且521iix

11、 目目 標(biāo)標(biāo) 規(guī)規(guī) 劃劃一、多一、多 目標(biāo)目標(biāo) 規(guī)規(guī) 劃劃 及及 其其 解解 多目標(biāo)規(guī)劃包含有三大要素：多目標(biāo)規(guī)劃包含有三大要素： 目標(biāo)、方案和決策者目標(biāo)、方案和決策者 多目標(biāo)規(guī)劃中的方案即為決策變量，也稱為多目標(biāo)問題的多目標(biāo)規(guī)劃中的方案即為決策變量，也稱為多目標(biāo)問題的解。備選方案即決策問題的可行解。在多目標(biāo)決策中，有解。備選方案即決策問題的可行解。在多目標(biāo)決策中，有些問題的方案是有限的，有些問題的方案是無限的。方案些問題的方案是有限的，有些問題的方案是無限的。方案有其特征或特性，稱之為屬性。有其特征或特性，稱之為屬性。例題例題 某工廠在一個計(jì)劃期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，某工廠在一個計(jì)劃期內(nèi)生產(chǎn)

12、甲、乙兩種產(chǎn)品，各產(chǎn)品都要消耗各產(chǎn)品都要消耗A A，B B，C C三種不同的資源。每件產(chǎn)品三種不同的資源。每件產(chǎn)品對資源的單位消耗、各種資源的限量以及各產(chǎn)品的對資源的單位消耗、各種資源的限量以及各產(chǎn)品的單位價格、單位利潤和所造成的單位污染如下表。單位價格、單位利潤和所造成的單位污染如下表。假定產(chǎn)品能全部銷售出去，問每期怎樣安排生產(chǎn)，假定產(chǎn)品能全部銷售出去，問每期怎樣安排生產(chǎn)，才能使利潤和產(chǎn)值都最大，且造成的污染最?。坎拍苁估麧櫤彤a(chǎn)值都最大，且造成的污染最小？甲甲乙乙資源限量資源限量資源資源A A單位消耗單位消耗資源資源B B單位消耗單位消耗資源資源C C單位消耗單位消耗9 94 43 34 4

13、5 51010240240200200300300單位產(chǎn)品的價格單位產(chǎn)品的價格400400600600單位產(chǎn)品的利潤單位產(chǎn)品的利潤7070120120單位產(chǎn)品的污染單位產(chǎn)品的污染3 32 2解：問題的多目標(biāo)模型如下解：問題的多目標(biāo)模型如下0,300103200542404923)(max(600400)(max12070)(max21212121213212211xxxxxxxxxxXfxxXfxxXf對于此模型的三個目標(biāo)，工對于此模型的三個目標(biāo)，工廠確定利潤最大為主要目標(biāo)。廠確定利潤最大為主要目標(biāo)。另兩個目標(biāo)則通過預(yù)測預(yù)先另兩個目標(biāo)則通過預(yù)測預(yù)先給定的希望達(dá)到的目標(biāo)值轉(zhuǎn)給定的希望達(dá)到的目標(biāo)值

14、轉(zhuǎn)化為約束條件。經(jīng)研究，工化為約束條件。經(jīng)研究，工廠認(rèn)為總產(chǎn)值至少應(yīng)達(dá)到廠認(rèn)為總產(chǎn)值至少應(yīng)達(dá)到2000020000個單位，而污染控制個單位，而污染控制在在9090個單位以下，即個單位以下，即9023)(20000600400)(213212xxXfxxXf （一）任何多目標(biāo)規(guī)劃問題，都由兩個（一）任何多目標(biāo)規(guī)劃問題，都由兩個基本部分組成基本部分組成: : （1 1）兩個以上的目標(biāo)函數(shù)；）兩個以上的目標(biāo)函數(shù)； （2 2）若干個約束條件。）若干個約束條件。 （二）對于多目標(biāo)規(guī)劃問題，可以將（二）對于多目標(biāo)規(guī)劃問題，可以將其數(shù)學(xué)模型一般地描寫為如下形式：其數(shù)學(xué)模型一般地描寫為如下形式： （2 2）)

15、(max(min)(max(min)(max(min)(max(min)21XfXfXfXFZkmmgggGXXXX2121)()()()(（1 1）式中：式中： 為決策變量向量。為決策變量向量。 TnxxxX,21 （三）多目標(biāo)規(guī)劃解的特點(diǎn)（三）多目標(biāo)規(guī)劃解的特點(diǎn) 對于上述多目標(biāo)規(guī)劃問題，求解就意味著需要對于上述多目標(biāo)規(guī)劃問題，求解就意味著需要做出如下的復(fù)合選擇：做出如下的復(fù)合選擇： （1 1）每一個目標(biāo)函數(shù)取什么值，原問題可以得）每一個目標(biāo)函數(shù)取什么值，原問題可以得到最滿意的解決？到最滿意的解決？ （2 2）每一個決策變量取什么值，原問題可以得）每一個決策變量取什么值，原問題可以得到最滿意

16、的解決到最滿意的解決 ？ 多目標(biāo)規(guī)劃問題的求解不能只追求一個目標(biāo)的多目標(biāo)規(guī)劃問題的求解不能只追求一個目標(biāo)的最優(yōu)化（最大或最?。?，而不顧其它目標(biāo)。最優(yōu)化（最大或最?。?，而不顧其它目標(biāo)。 當(dāng)目標(biāo)函數(shù)處于沖突狀態(tài)時，就不會當(dāng)目標(biāo)函數(shù)處于沖突狀態(tài)時，就不會存在使所有目標(biāo)函數(shù)同時達(dá)到最大或最小存在使所有目標(biāo)函數(shù)同時達(dá)到最大或最小值的最優(yōu)解，于是我們只能尋求非劣解值的最優(yōu)解，于是我們只能尋求非劣解（又稱非支配解或帕累托解）。（又稱非支配解或帕累托解）。 非劣解：可以用圖非劣解：可以用圖3 3說明。說明。圖圖3 多目標(biāo)規(guī)劃的劣解與非劣解多目標(biāo)規(guī)劃的劣解與非劣解二、多二、多 目目 標(biāo)標(biāo) 規(guī)規(guī) 劃劃 問問 題題

17、 的的 建建 模模 方方 法法 為了求得多目標(biāo)規(guī)劃問題的非劣解，為了求得多目標(biāo)規(guī)劃問題的非劣解，常常需要將多目標(biāo)規(guī)劃問題轉(zhuǎn)化為單目標(biāo)常常需要將多目標(biāo)規(guī)劃問題轉(zhuǎn)化為單目標(biāo)規(guī)劃問題去處理。實(shí)現(xiàn)這種轉(zhuǎn)化，有如下規(guī)劃問題去處理。實(shí)現(xiàn)這種轉(zhuǎn)化，有如下幾種建模方法。幾種建模方法。（三）約束模型三）約束模型 理論依據(jù)理論依據(jù) ：若規(guī)劃問題的某一目標(biāo)可以給：若規(guī)劃問題的某一目標(biāo)可以給出一個可供選擇的范圍，則該目標(biāo)就可以出一個可供選擇的范圍，則該目標(biāo)就可以作為約束條件而被排除出目標(biāo)組，進(jìn)入約作為約束條件而被排除出目標(biāo)組，進(jìn)入約束條件組中。束條件組中。假如，除第一個目標(biāo)外，其余目標(biāo)都可以假如，除第一個目標(biāo)外，其余

18、目標(biāo)都可以提出一個可供選擇的范圍，則該多目標(biāo)規(guī)提出一個可供選擇的范圍，則該多目標(biāo)規(guī)劃問題就可以轉(zhuǎn)化為單目標(biāo)規(guī)劃問題：劃問題就可以轉(zhuǎn)化為單目標(biāo)規(guī)劃問題： 用目標(biāo)達(dá)到法求解多目標(biāo)規(guī)劃的計(jì)用目標(biāo)達(dá)到法求解多目標(biāo)規(guī)劃的計(jì)算過程，可以通過調(diào)用算過程，可以通過調(diào)用MatlabMatlab軟件系統(tǒng)軟件系統(tǒng)優(yōu)化工具箱中的優(yōu)化工具箱中的fgoalattainfgoalattain函數(shù)實(shí)現(xiàn)。函數(shù)實(shí)現(xiàn)。三、多目標(biāo)規(guī)劃問題的求解(化多為少的方法)1 1、主要目標(biāo)法、主要目標(biāo)法 在有些多目標(biāo)決策問題中，各種目標(biāo)的重在有些多目標(biāo)決策問題中，各種目標(biāo)的重要性程度往往不一樣。其中一個重要性程度最要性程度往往不一樣。其中一個重

19、要性程度最高和最為關(guān)鍵的目標(biāo)，稱之為主要目標(biāo)法。其高和最為關(guān)鍵的目標(biāo)，稱之為主要目標(biāo)法。其余的目標(biāo)則稱為非主要目標(biāo)。余的目標(biāo)則稱為非主要目標(biāo)。0)(0)(. .)(. .)(),.,(),()(21XhXgtsorGXtsXfXfXfXoptFjiTk例如，在上述多目標(biāo)問題中，假定例如，在上述多目標(biāo)問題中，假定f1(X)為主要為主要目標(biāo)，其余目標(biāo)，其余p p-1-1個為非主要目標(biāo)。這時，希望個為非主要目標(biāo)。這時，希望主要目標(biāo)達(dá)到極大值，并要求其余的目標(biāo)滿足主要目標(biāo)達(dá)到極大值，并要求其余的目標(biāo)滿足一定的條件，即一定的條件，即1,.,2 , 1,)(,.,2 , 1, 0)(,.,2 , 1, 0

20、)(. .)(max1pkXfmjXhniXgtsXfkkji例題例題 某工廠在一個計(jì)劃期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，某工廠在一個計(jì)劃期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，各產(chǎn)品都要消耗各產(chǎn)品都要消耗A A，B B，C C三種不同的資源。每件產(chǎn)品三種不同的資源。每件產(chǎn)品對資源的單位消耗、各種資源的限量以及各產(chǎn)品的對資源的單位消耗、各種資源的限量以及各產(chǎn)品的單位價格、單位利潤和所造成的單位污染如下表。單位價格、單位利潤和所造成的單位污染如下表。假定產(chǎn)品能全部銷售出去，問每期怎樣安排生產(chǎn)，假定產(chǎn)品能全部銷售出去，問每期怎樣安排生產(chǎn)，才能使利潤和產(chǎn)值都最大，且造成的污染最??？才能使利潤和產(chǎn)值都最大，且造成的污染最??？甲

21、甲乙乙資源限量資源限量資源資源A A單位消耗單位消耗資源資源B B單位消耗單位消耗資源資源C C單位消耗單位消耗9 94 43 34 45 51010240240200200300300單位產(chǎn)品的價格單位產(chǎn)品的價格400400600600單位產(chǎn)品的利潤單位產(chǎn)品的利潤7070120120單位產(chǎn)品的污染單位產(chǎn)品的污染3 32 2解：問題的多目標(biāo)模型如下解：問題的多目標(biāo)模型如下0,300103200542404923)(max(600400)(max12070)(max21212121213212211xxxxxxxxxxXfxxXfxxXf對于此模型的三個目標(biāo)，工對于此模型的三個目標(biāo)，工廠確定利潤

22、最大為主要目標(biāo)。廠確定利潤最大為主要目標(biāo)。另兩個目標(biāo)則通過預(yù)測預(yù)先另兩個目標(biāo)則通過預(yù)測預(yù)先給定的希望達(dá)到的目標(biāo)值轉(zhuǎn)給定的希望達(dá)到的目標(biāo)值轉(zhuǎn)化為約束條件。經(jīng)研究，工化為約束條件。經(jīng)研究，工廠認(rèn)為總產(chǎn)值至少應(yīng)達(dá)到廠認(rèn)為總產(chǎn)值至少應(yīng)達(dá)到2000020000個單位，而污染控制個單位，而污染控制在在9090個單位以下，即個單位以下，即9023)(20000600400)(213212xxXfxxXf由主要目標(biāo)法化為單目標(biāo)問題由主要目標(biāo)法化為單目標(biāo)問題0,300103200542404990232000060040012070)(max212121212121211xxxxxxxxxxxxxxXf用單純形

23、法求得其最優(yōu)解為用單純形法求得其最優(yōu)解為90)(,20750)(,4025)(,25.26, 5 .1232121xfxfxfxx2 2、線性加權(quán)和目標(biāo)規(guī)劃、線性加權(quán)和目標(biāo)規(guī)劃0)(0)(. .)(),.,(),()(21XhXgtsXfXfXfXoptFjiTp在上述目標(biāo)規(guī)劃中，假定在上述目標(biāo)規(guī)劃中，假定f1 1(X),(X),f2 2(X),(X),fp p(X)(X)具有具有相同的量綱相同的量綱, ,按照一定的規(guī)則分別給按照一定的規(guī)則分別給f fi i賦予相同的權(quán)賦予相同的權(quán)系數(shù)系數(shù)i，作線性加權(quán)和評價函數(shù)，作線性加權(quán)和評價函數(shù)piiiXfXU1)()(0)(0)(. .)()(max1

24、XhXgtsXfXUjipiii則多目標(biāo)問題化為如下的單目標(biāo)問題則多目標(biāo)問題化為如下的單目標(biāo)問題例如，某公司計(jì)劃購進(jìn)一批新卡車，可供選擇的卡車有例如，某公司計(jì)劃購進(jìn)一批新卡車，可供選擇的卡車有如下如下4 4種類型：種類型：A1A1，A2A2，A3A3，A4A4。現(xiàn)考慮。現(xiàn)考慮6 6個方案屬性：個方案屬性：維修期限維修期限f1 1，每，每100100升汽油所跑的里數(shù)升汽油所跑的里數(shù)f2 2，最大載重噸數(shù)，最大載重噸數(shù)f3 3，價格（萬元），價格（萬元）f4 4，可靠性，可靠性f5 5，靈敏性，靈敏性f6 6。這。這4 4種型號的種型號的卡車分別關(guān)于目標(biāo)屬性的指標(biāo)值卡車分別關(guān)于目標(biāo)屬性的指標(biāo)值fi

25、jij如下表所示。如下表所示。fijf1f2f3f4f5f6A12.01500455一般一般高高A22.527003.665低低一般一般A32.020004.245高高很高很高A42.21800450很高很高一般一般首先對不同度量單位和不同數(shù)量級的指標(biāo)值進(jìn)行標(biāo)準(zhǔn)首先對不同度量單位和不同數(shù)量級的指標(biāo)值進(jìn)行標(biāo)準(zhǔn)化處理。先將定性指標(biāo)定量化：化處理。先將定性指標(biāo)定量化：變換后的指標(biāo)值矩陣為：變換后的指標(biāo)值矩陣為：aijf1f2f3f4f5f6A1116750.53450.5A2100100110011A3142.25100167100A440.625.756725.751001設(shè)權(quán)系數(shù)向量為設(shè)權(quán)系數(shù)向

26、量為W=（0.2,0.1,0.1,0.1,0.2,0.3),則則925.57)(max*27.40)(925.57)(6 .40)(34)(36144613361226111XUUUaXUaXUaXUaXUjjjjjjjjjjjj故最優(yōu)方案為選購故最優(yōu)方案為選購A3A3型卡車型卡車4 4、步驟法（、步驟法（STEMSTEM法）法） 這是一種交互方法，其求解過程通過分析者與決策這是一種交互方法，其求解過程通過分析者與決策者之間的對話逐步進(jìn)行，故稱步驟法。者之間的對話逐步進(jìn)行，故稱步驟法。 步驟法的基本思想是，首先需要求出原多目標(biāo)問題步驟法的基本思想是，首先需要求出原多目標(biāo)問題的一組理想解的一組理

27、想解(f(f1 1* *,f,f2 2* *,f,fk k* *) )。實(shí)際上，這些解。實(shí)際上，這些解f fi i* *(i=1,2,k)(i=1,2,k)無法同時達(dá)到，但可以當(dāng)作一組理想的無法同時達(dá)到，但可以當(dāng)作一組理想的最優(yōu)值。以理想解作為一個標(biāo)準(zhǔn)，可以估計(jì)有效解，然后最優(yōu)值。以理想解作為一個標(biāo)準(zhǔn)，可以估計(jì)有效解，然后通過對話，不斷修改目標(biāo)值，并把降低要求的目標(biāo)作為新通過對話，不斷修改目標(biāo)值，并把降低要求的目標(biāo)作為新的約束條件加入原來的約束條件中去重新計(jì)算，直到?jīng)Q策的約束條件加入原來的約束條件中去重新計(jì)算，直到?jīng)Q策者得到滿意的解。者得到滿意的解。把上述計(jì)算結(jié)果列入下表把上述計(jì)算結(jié)果列入下表

28、*21*21*11211*121pipppppiiiiipipifzzzXzfzzXzzzfXffffX例題：例題：某公司考慮生產(chǎn)兩種光電太陽能電池：產(chǎn)品甲和某公司考慮生產(chǎn)兩種光電太陽能電池：產(chǎn)品甲和產(chǎn)品乙。這種生產(chǎn)過程會在空氣中引起放射性污染。因產(chǎn)品乙。這種生產(chǎn)過程會在空氣中引起放射性污染。因此，公司經(jīng)理有兩個目標(biāo)：極大化利潤與極小化總的放此，公司經(jīng)理有兩個目標(biāo)：極大化利潤與極小化總的放射性污染。已知在一個生產(chǎn)周期內(nèi)，每單位甲產(chǎn)品的收射性污染。已知在一個生產(chǎn)周期內(nèi)，每單位甲產(chǎn)品的收益是益是1 1元，每單位乙產(chǎn)品的收益是元，每單位乙產(chǎn)品的收益是3 3元。而放射性污染的元。而放射性污染的數(shù)量，每

29、單位甲產(chǎn)品是數(shù)量，每單位甲產(chǎn)品是1.51.5個單位個單位, ,每單位乙產(chǎn)品是每單位乙產(chǎn)品是1 1個個單位單位. .由于機(jī)器能力由于機(jī)器能力( (小時小時) )、裝配能力（人時）和可用、裝配能力（人時）和可用的原材料（單位）的限制，約束條件是的原材料（單位）的限制，約束條件是)(725)(42 . 02 . 0)(825. 05 . 0212121原材料裝配能力機(jī)器能力xxxxxx)(725)(42 . 02 . 0)(825. 05 . 05 . 1)(,3)()(),()(max21212121221121原材料裝配能力機(jī)器能力xxxxxxxxXfxxXfXfXfXFT目標(biāo)有兩個目標(biāo)有兩個:

30、 :一是利潤最大一是利潤最大, ,二是污染最小二是污染最小. .該問題該問題的多目標(biāo)規(guī)劃模型如下的多目標(biāo)規(guī)劃模型如下: :解解: :首先首先, ,分別求解兩個單目標(biāo)問題的最優(yōu)解分別求解兩個單目標(biāo)問題的最優(yōu)解, ,由它們由它們得到的目標(biāo)函數(shù)值組成理想解得到的目標(biāo)函數(shù)值組成理想解. .)(725)(42 . 02 . 0)(825. 05 . 03)(max212121211原材料裝配能力機(jī)器能力xxxxxxxxXf)(725)(42 . 02 . 0)(825. 05 . 05 . 1)(max212121212原材料裝配能力機(jī)器能力xxxxxxxxXf46*)13, 7(1*1fX0*)0 ,

31、 0(1*2fX由此由此, ,構(gòu)造支付表構(gòu)造支付表Xf1*f2*(7,13)(0,0)460-23.50由此計(jì)算兩個目標(biāo)與理由此計(jì)算兩個目標(biāo)與理想值偏離的權(quán)重：想值偏離的權(quán)重：637. 0,363. 0,555. 0,316. 02121解下列線性規(guī)劃問題解下列線性規(guī)劃問題: :0,7254)2 . 02 . 08)25. 05 . 0)230(637. 0)346(363. 0min212121212121xxxxxxxxxxxx0,7254)2 . 02 . 08)25. 05 . 0192.21310)5 . 1346min21212121212121xxxxxxxxxxxxxx進(jìn)行下一

32、輪迭代進(jìn)行下一輪迭代. .首先設(shè)首先設(shè)2 2=0,=0,并計(jì)算得并計(jì)算得1 1=1.=1.將將模型修改為模型修改為由此求得由此求得: :10,3010, 02121ffxx決策者把這一結(jié)果與前一輪的解及理想值作比較決策者把這一結(jié)果與前一輪的解及理想值作比較, ,認(rèn)為兩個目標(biāo)值都比較滿意認(rèn)為兩個目標(biāo)值都比較滿意, ,則迭代結(jié)束則迭代結(jié)束. .線線 性性 目目 標(biāo)標(biāo) 規(guī)規(guī) 劃劃 模模 型型 線性規(guī)劃問題都是處理單個目標(biāo)的情況，但是在現(xiàn)實(shí)世界線性規(guī)劃問題都是處理單個目標(biāo)的情況，但是在現(xiàn)實(shí)世界中有許多問題具有多個目標(biāo)，這些目標(biāo)的重要性各不相同，中有許多問題具有多個目標(biāo)，這些目標(biāo)的重要性各不相同，往往有

33、不同的量綱，有的目標(biāo)相互依賴，例如決策者既希望往往有不同的量綱，有的目標(biāo)相互依賴，例如決策者既希望實(shí)現(xiàn)利潤最大，又希望實(shí)現(xiàn)產(chǎn)值最大；有的相互抵觸，如決實(shí)現(xiàn)利潤最大，又希望實(shí)現(xiàn)產(chǎn)值最大；有的相互抵觸，如決策者既希望充分利用資源，又不希望超越資源限量。而決策策者既希望充分利用資源，又不希望超越資源限量。而決策者希望在某些限制條件下，依次實(shí)現(xiàn)這些目標(biāo)。這就是目標(biāo)者希望在某些限制條件下，依次實(shí)現(xiàn)這些目標(biāo)。這就是目標(biāo)規(guī)劃所要解決的問題。當(dāng)所有的目標(biāo)函數(shù)和約束條件都是線規(guī)劃所要解決的問題。當(dāng)所有的目標(biāo)函數(shù)和約束條件都是線性時，我們稱其為線性目標(biāo)規(guī)劃問題。在這里我們主要討論性時，我們稱其為線性目標(biāo)規(guī)劃問題。

34、在這里我們主要討論線性目標(biāo)規(guī)劃問題。線性目標(biāo)規(guī)劃問題。一、線性目標(biāo)規(guī)劃模型的建立一、線性目標(biāo)規(guī)劃模型的建立 例例1 1：某一個企業(yè)利用某種原材料和現(xiàn)有設(shè)備可生某一個企業(yè)利用某種原材料和現(xiàn)有設(shè)備可生產(chǎn)甲、乙兩種產(chǎn)品，其中，甲、乙兩種產(chǎn)品的單價產(chǎn)甲、乙兩種產(chǎn)品，其中，甲、乙兩種產(chǎn)品的單價分別為分別為8 8元和元和1010元；生產(chǎn)單位甲、乙兩種產(chǎn)品需要元；生產(chǎn)單位甲、乙兩種產(chǎn)品需要消耗的原材料分別為消耗的原材料分別為2 2個單位和個單位和1 1個單位，需要占用個單位，需要占用的設(shè)備分別為的設(shè)備分別為1 1臺時和臺時和2 2臺時；原材料擁有量為臺時；原材料擁有量為1111個個單位；可利用的設(shè)備總臺時為

35、單位；可利用的設(shè)備總臺時為1010臺時。試問：如何臺時。試問：如何確定其生產(chǎn)方案？確定其生產(chǎn)方案？ 但是，在實(shí)際決策時，企業(yè)領(lǐng)導(dǎo)者必須考慮市場但是，在實(shí)際決策時，企業(yè)領(lǐng)導(dǎo)者必須考慮市場等一系列其它條件，如：等一系列其它條件，如：根據(jù)市場信息，甲種產(chǎn)品的需求量有下降的趨勢，根據(jù)市場信息，甲種產(chǎn)品的需求量有下降的趨勢，因此甲種產(chǎn)品的產(chǎn)量不應(yīng)大于乙種產(chǎn)品的產(chǎn)量。因此甲種產(chǎn)品的產(chǎn)量不應(yīng)大于乙種產(chǎn)品的產(chǎn)量。超過計(jì)劃供應(yīng)的原材料，需用高價采購，這就會使超過計(jì)劃供應(yīng)的原材料，需用高價采購，這就會使生產(chǎn)成本增加。生產(chǎn)成本增加。應(yīng)盡可能地充分利用設(shè)備的有效臺時，但不希望加應(yīng)盡可能地充分利用設(shè)備的有效臺時，但不希

36、望加班。班。應(yīng)盡可能達(dá)到并超過計(jì)劃產(chǎn)值指標(biāo)應(yīng)盡可能達(dá)到并超過計(jì)劃產(chǎn)值指標(biāo)5656元。元。 這樣，該企業(yè)生產(chǎn)方案的確定，便成為一個多這樣，該企業(yè)生產(chǎn)方案的確定，便成為一個多目標(biāo)決策問題，這一問題可以運(yùn)用目標(biāo)規(guī)劃方法進(jìn)目標(biāo)決策問題，這一問題可以運(yùn)用目標(biāo)規(guī)劃方法進(jìn)行求解。行求解。目標(biāo)規(guī)劃模型的有關(guān)概念目標(biāo)規(guī)劃模型的有關(guān)概念2 2、絕對約束和目標(biāo)約束、絕對約束和目標(biāo)約束 絕對約束：絕對約束：必須嚴(yán)格滿足的等式約束和不等必須嚴(yán)格滿足的等式約束和不等式約束，譬如，線性規(guī)劃問題的所有約束條件都式約束，譬如，線性規(guī)劃問題的所有約束條件都是絕對約束，不能滿足這些約束條件的解稱為非是絕對約束，不能滿足這些約束條件

37、的解稱為非可行解，所以它們是硬約束?？尚薪?，所以它們是硬約束。 目標(biāo)約束：目標(biāo)約束：目標(biāo)規(guī)劃所特有的，可以將約束目標(biāo)規(guī)劃所特有的，可以將約束方程右端項(xiàng)看作是追求的目標(biāo)值，在達(dá)到此目標(biāo)方程右端項(xiàng)看作是追求的目標(biāo)值，在達(dá)到此目標(biāo)值時允許發(fā)生正的或負(fù)的偏差值時允許發(fā)生正的或負(fù)的偏差 ，可加入正負(fù)偏，可加入正負(fù)偏差變量，是軟約束。差變量，是軟約束。 線性規(guī)劃問題的目標(biāo)函數(shù)，在給定目標(biāo)值和線性規(guī)劃問題的目標(biāo)函數(shù)，在給定目標(biāo)值和加入正、負(fù)偏差變量后可以轉(zhuǎn)化為目標(biāo)約束，也加入正、負(fù)偏差變量后可以轉(zhuǎn)化為目標(biāo)約束，也可以根據(jù)問題的需要將絕對約束轉(zhuǎn)化為目標(biāo)約束可以根據(jù)問題的需要將絕對約束轉(zhuǎn)化為目標(biāo)約束。 目標(biāo)規(guī)劃

38、模型的有關(guān)概念目標(biāo)規(guī)劃模型的有關(guān)概念目標(biāo)規(guī)劃模型的有關(guān)概念目標(biāo)規(guī)劃模型的有關(guān)概念目標(biāo)規(guī)劃模型的有關(guān)概念目標(biāo)規(guī)劃模型的有關(guān)概念b) b) 要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，就是正偏差變量要盡可能小，即值，就是正偏差變量要盡可能小，即)(mindfZ（23） c) c) 要求超過目標(biāo)值，也就是超過量不限，要求超過目標(biāo)值，也就是超過量不限，但負(fù)偏差變量要盡可能小，即但負(fù)偏差變量要盡可能小，即 )(mindfZ（24） 在實(shí)際問題中，可以根據(jù)決策者的要求，在實(shí)際問題中，可以根據(jù)決策者的要求，引入正、負(fù)偏差變量和目標(biāo)約束，并給不同引入正、負(fù)偏差變量和目標(biāo)約束，并給不

39、同目標(biāo)賦予相應(yīng)的優(yōu)先因子和權(quán)系數(shù)，構(gòu)造目目標(biāo)賦予相應(yīng)的優(yōu)先因子和權(quán)系數(shù)，構(gòu)造目標(biāo)函數(shù)，建立模型。標(biāo)函數(shù)，建立模型。 例例2 2：在例在例1 1中，如果決策者在原材料供中，如果決策者在原材料供應(yīng)受嚴(yán)格控制的基礎(chǔ)上考慮：首先是甲應(yīng)受嚴(yán)格控制的基礎(chǔ)上考慮：首先是甲種產(chǎn)品的產(chǎn)量不超過乙種產(chǎn)品的產(chǎn)量；種產(chǎn)品的產(chǎn)量不超過乙種產(chǎn)品的產(chǎn)量；其次是充分利用設(shè)備的有限臺時，不加其次是充分利用設(shè)備的有限臺時，不加班；再次是產(chǎn)值不小于班；再次是產(chǎn)值不小于5656元。并分別賦元。并分別賦予這三個目標(biāo)優(yōu)先因子予這三個目標(biāo)優(yōu)先因子 。試建立。試建立該問題的目標(biāo)規(guī)劃模型。該問題的目標(biāo)規(guī)劃模型。321,PPP在以上各式中，在以

40、上各式中， 、 分別為賦予分別為賦予 優(yōu)先因子的第優(yōu)先因子的第 個目標(biāo)的正、負(fù)個目標(biāo)的正、負(fù)偏差變量的權(quán)系數(shù)，偏差變量的權(quán)系數(shù)， 為第為第 個目標(biāo)的預(yù)期值，個目標(biāo)的預(yù)期值， 為決策變量，為決策變量， 、 分別為第分別為第 個目標(biāo)的正、負(fù)偏差變量，個目標(biāo)的正、負(fù)偏差變量，（2525）式為目標(biāo)函數(shù)，（）式為目標(biāo)函數(shù)，（2626）式為目標(biāo)約束，（）式為目標(biāo)約束，（2727）式）式為絕對約束，（為絕對約束，（2828）式和（）式和（2929）式為非負(fù)約束，）式為非負(fù)約束， 、 、 分別為目標(biāo)約束和絕對約束中決策變量的系數(shù)及約束值。分別為目標(biāo)約束和絕對約束中決策變量的系數(shù)及約束值。其中，其中， ； ；

41、； 。 lklklpkkgkjxkdkdk)(kjcijaibmi, 2 , 1nj, 2 , 1Ll, 2 , 1Kk, 2 , 1非線性規(guī)劃非線性規(guī)劃 實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)?zāi)康膶?shí)驗(yàn)內(nèi)容實(shí)驗(yàn)內(nèi)容2、掌握用數(shù)學(xué)軟件求解優(yōu)化問題。、掌握用數(shù)學(xué)軟件求解優(yōu)化問題。1、直觀了解非線性規(guī)劃的基本內(nèi)容。、直觀了解非線性規(guī)劃的基本內(nèi)容。1 1、非線性規(guī)劃的基本理論。、非線性規(guī)劃的基本理論。4 4、實(shí)驗(yàn)作業(yè)。、實(shí)驗(yàn)作業(yè)。2、用數(shù)學(xué)軟件求解非線性規(guī)劃。、用數(shù)學(xué)軟件求解非線性規(guī)劃。3、鋼管訂購及運(yùn)輸優(yōu)化模型、鋼管訂購及運(yùn)輸優(yōu)化模型*非線性規(guī)劃的基本解法非線性規(guī)劃的基本解法非線性規(guī)劃的基本概念非線性規(guī)劃的基本概念非線性規(guī)劃

42、非線性規(guī)劃 返回返回 定義定義 如果目標(biāo)函數(shù)或約束條件中至少有一個是非線性函數(shù)時的最優(yōu)化問題就叫做非線性規(guī)劃問題非線性規(guī)劃問題非線性規(guī)劃的基本概念非線性規(guī)劃的基本概念 一般形式一般形式: （1） 其中 ， 是定義在 En 上的實(shí)值函數(shù)，簡記: Xfmin .,.,2 , 1 0 m;1,2,., 0. . ljXhiXgtsjinTnExxxX,21jihgf,1nj1ni1nE :h ,E :g ,E :EEEf 其它情況其它情況: 求目標(biāo)函數(shù)的最大值或約束條件為小于等于零的情況，都可通過取其相反數(shù)化為上述一般形式計(jì)算機(jī)求解方法 1. 首先建立M文件fun.m,定義目標(biāo)函數(shù)F（X）:func

43、tion f=fun(X);f=F(X);標(biāo)準(zhǔn)型為： min F(X) s.t AX0的的 最短路問題最短路問題(2) Lij)P(vP(vi i)+)+w wijij ，則把，則把T T(v(vj j) )改變?yōu)楦淖優(yōu)镻 P( (v vi i)+)+w wijij，把，把( (v vj j) )改變?yōu)楦淖優(yōu)閕 i，否則轉(zhuǎn)入（，否則轉(zhuǎn)入（3 3）（3 3）令）令T(T(v vj j)=min)=minT T( (v vl l) ) v vl l S Si i ，如果，如果T T( (v vj ji i)+)+，則把，則把v vj j的的T T 標(biāo)號改變?yōu)闃?biāo)號改變?yōu)镻 P 標(biāo)號標(biāo)號P P( (v

44、 vj j)=)=T T( (v vj j) )，令，令S Si+1i+1= =S Si iv vj j ，k k= =j j，把，把i i換成換成i i+1+1，轉(zhuǎn)入（轉(zhuǎn)入（1 1）；否則結(jié)束。）；否則結(jié)束。這時，對每一個這時，對每一個v v S Si i，d d( (v vs s, ,v v)=)=P P( (v v) )。對每一個。對每一個v v不屬于不屬于S Si i，d d（v vs s, ,v v）= =T T（v v）。）。 現(xiàn)在用現(xiàn)在用DijkstraDijkstra算法求例算法求例1 1中從中從v vs s到各個點(diǎn)的最短路，到各個點(diǎn)的最短路，此時此時S S=1=1。i i=0

45、=0：S S0 0=v v1 1 ，P P( (v v1 1)=0,)=0,( (v v1 1)=0)=0，T T( (v vi i)=+)=+，( (v vi i)=)=m m，i i=2,3,=2,3,9 9，k k=1=1。 （ 2 2 ） 因 為 （） 因 為 （v v1 1, v, v2 2） A A，v v2 2不 屬 于不 屬 于S S0 0，P P( (v v1 1)+)+w w1212 )w w3232+ +P P( (v v3 3) )，將，將T T( (v v2 2) )改變?yōu)楦淖優(yōu)镻 P( (v v3 3)+)+w w3232=5=5，( (v v2 2) )改變?yōu)楦淖?/p>

46、為3 3。（3 3）在所有的）在所有的T T標(biāo)號中，標(biāo)號中，T T( (v v2 2)=5)=5最小，于是令最小，于是令P P( (v v2 2)=5)=5，S S3 3=v v1 1, ,v v4 4, ,v v3 3 ，k k=2=2。 i i=3=3：（2 2）將）將T T( (v v5 5) )改變?yōu)楦淖優(yōu)镻 P( (v v2 2)+)+w w2525=6=6，( (v v5 5) )改變?yōu)楦淖優(yōu)? 2。（3 3）在所有的）在所有的T T標(biāo)號中，標(biāo)號中，T T( (v v5 5)=6)=6最小，于是令最小，于是令P P( (v v5 5)=6)=6，S S4 4=v v1 1, ,v

47、v4 4, ,v v3 3 ，k k=5=5。 i i=4:=4: （2 2）將）將T T( (v v6 6) )，T T( (v v7 7) )，T T( (v v8 8) )分別改變?yōu)榉謩e改變?yōu)?010， 9 9，1212，將，將( (v v0 0) )，( (v v7 7) )，( (v v8 8) )改變?yōu)楦淖優(yōu)? 5。 （3 3）在所有的）在所有的T T標(biāo)號中，標(biāo)號中，T T( (v v7 7)=9)=9最小，于最小，于 是令是令P P( (v v7 7)=9)=9，S S5 5=v v1 1, ,v v4 4, ,v v3 3, ,v v2 2, ,v v5 5, ,v v7 7

48、，v v=7=7。 i i=5=5： （2 2）（）（v v7 7, ,v v8 8）A A，v v8 8不屬于不屬于S S5 5， 但但T T( (v v8 8)w w7878+ +P P( (v v7 7) )，故，故T T( (v v8 8) )不變。不變。 （3 3）在所有的）在所有的T T標(biāo)號中，標(biāo)號中，T(T(v v6 6)=10)=10最小，于最小，于 是是, ,令令P P( (v v6 6)=10)=10，S S6 6=v v1 1,v,v4 4,v,v3 3,v,v2 2,v,v5 5,v,v7 7, v, v6 6 ， k k=6=6。 i i=6=6：（2 2）從）從v

49、v6 6出發(fā)沒有弧指向不屬于出發(fā)沒有弧指向不屬于S S6 6的點(diǎn)，因此轉(zhuǎn)的點(diǎn)，因此轉(zhuǎn)入（入（3 3）。）。3 3）在所有的）在所有的T T標(biāo)號中，標(biāo)號中，T T( (v v8 8)=12)=12最小，令最小，令P P( (v v8 8)=12)=12，S S7 7=v v1 1,v,v4 4,v,v3 3,v,v2 2,v,v5 5,v,v7 7, v, v6 6,v,v8 8 ， k k=8=8。 i i=7=7： 這時，僅有這時，僅有T T標(biāo)號的點(diǎn)為標(biāo)號的點(diǎn)為v v9 9，T T（v v9 9）=+=+，算法，算法結(jié)束。結(jié)束。此時，把此時，把P P標(biāo)號和標(biāo)號和值標(biāo)在圖中，如圖值標(biāo)在圖中，如

50、圖8.158.15所示所示圖8.16P(VP(V4 4) )=1=1 (V(V4 4) )=1=1v4v2v8v7v6v5v963623410231262410P(VP(V6 6) )=10=10P(VP(V7 7) )=9=9 (V(V1 1)=0)=0P(VP(V1 1) )=0=0 (V(V6 6) )=5=5 (V(V5 5) )=2=2P(VP(V2 2) )=5=5P(VP(V5 5) )=6=6P(VP(V8 8) )=12=12 (V(V7 7) )=5=5 (V(V2 2) )=3=3 (V(V8 8) )=5=5T(VT(V9 9) )=+=+ (V(V9 9) )=M=M

51、P(VP(V3 3) )=3=3 (V(V3 3) )=1=11最短路：最短路：V V1 1-(V-(V4 4-)V-)V3 3-V-V2 2-V-V5 5-(V-(V6 6-V-V7 7-)V-)V8 8 從圖從圖8.168.16中，不難看出從中，不難看出從v v1 1到到v v8 8的最短路。因?yàn)榈淖疃搪?。因?yàn)椋╲ v8 8）=5=5，故最短路經(jīng)過點(diǎn)，故最短路經(jīng)過點(diǎn)v v5 5有因?yàn)橛幸驗(yàn)椋╲ v5 5）=2=2，故最短路經(jīng)過點(diǎn)，故最短路經(jīng)過點(diǎn)v v2 2。依次類推，。依次類推，（v v2 2）=3=3，（v v3 3）=1=1于是，最短路經(jīng)過點(diǎn)于是，最短路經(jīng)過點(diǎn)v v3 3，v v1 1

52、。這樣，從。這樣，從v v1 1到到v v8 8的最短路是（的最短路是（v v1 1，v v3 3，v v2 2，v v5 5，v v8 8）。同理，可）。同理，可以求出從以求出從v v1 1到任一點(diǎn)到任一點(diǎn)v vi i的最短路，顯然不存在從的最短路，顯然不存在從v v1 1到到v v9 9的最短路。的最短路。 （二）逐次逼近法（二）逐次逼近法適用于網(wǎng)絡(luò)中帶負(fù)權(quán)的邊，求指定點(diǎn) v1 到網(wǎng)絡(luò)中任意點(diǎn)的最短路 基本原理基本原理 如果v1 到vj 的最短路總是沿著該路從v1先到某一點(diǎn)vi ，然后再沿邊(vi , vj)到達(dá)vj ，則v1 到vi的這條路必然也是v1 到v i的最短路。 步驟步驟 若令

53、P1j表示從v1 到vj 的最短路長， P1i為v1 到vi的最短路長，則必有下列方程 用迭代法解這個方程。 開始時令即用v1 到vj 的直接距離做初始解，若v1 到vj 間無邊，則記v1 到vj 的最短路長為+ 。), 2 , 1(1)1(1njlPjj )(min11ijiijlPP 從第二步起，使用迭代公式求 ，當(dāng)進(jìn)行到第t步，若出現(xiàn)則停止， 即為點(diǎn)v1 到各點(diǎn)的最短路長。), 3 , 2(min)1(1)(1nklPPijkiikj )(1kjP), 2 , 1()1(1)(1njPPtjtj ),2 , 1()(1njPtj 遞推公式中的 實(shí)際意義為從v1 到vj 點(diǎn)、至多含有 k-

54、1個中間點(diǎn)的最短路權(quán)，所以，在含有n 個點(diǎn)的圖中，如果不含有總權(quán)小于零的回路，求v1 點(diǎn)到任一點(diǎn)的最短路權(quán)，用上述算法最多經(jīng)過n-1次迭代必定收斂。如果圖中含有總權(quán)小于零的回路，最短路權(quán)沒有下界。)(1kjP例10 （見書本P253），求圖8-34中，V1點(diǎn)到各點(diǎn)的最短路。254-364-3372-1-24解：全部計(jì)算過程用表表示如下： 最短路問題的應(yīng)用設(shè)備更新問題設(shè)備更新問題 某工廠使用一臺設(shè)備，每年年初都要做出決定，如果繼續(xù)使用舊的，要付維修費(fèi)；若購買一臺新設(shè)備，要付購買費(fèi)。制定一個5年的更新計(jì)劃，使總支出最少。已知設(shè)備在各年的購買費(fèi)，及不同機(jī)器役齡時的殘值和維修費(fèi)如下表所示。項(xiàng)目第1年第

55、2年第3年第4年第5年購買費(fèi)1112131414機(jī)器役齡0-11-22-33-44-5維修費(fèi)5681118殘值43210 此問題可用動態(tài)規(guī)劃方法求解。下面介紹用最短路徑此問題可用動態(tài)規(guī)劃方法求解。下面介紹用最短路徑方法求解。方法求解。 令令Vi表示第表示第i年年初，邊（年年初，邊（ Vi， Vj ）表示在第）表示在第i年購買年購買一臺設(shè)備，一直使用到第一臺設(shè)備，一直使用到第j-1年年末。邊（年年末。邊（ Vi， Vj ）上的權(quán)表示在第上的權(quán)表示在第i年購買一臺設(shè)備，一直使用到第年購買一臺設(shè)備，一直使用到第j-1年年末所花出的總費(fèi)用，于是設(shè)備更新問題變?yōu)榍髨D年年末所花出的總費(fèi)用，于是設(shè)備更新問題

56、變?yōu)榍髨D8-35中點(diǎn)中點(diǎn) V1到到 點(diǎn)點(diǎn)V6的最短路。的最短路。121314151559213020192840294122V1V2V3V4V5V6圖圖8-35計(jì)算過程用表表示如下：所以最優(yōu)策所以最優(yōu)策略為在第一略為在第一年和第三年年和第三年年初各購買年初各購買一臺新設(shè)備一臺新設(shè)備為最優(yōu)策略為最優(yōu)策略，總費(fèi)用為，總費(fèi)用為49.121314151559213020192840294122V1V2V3V4V5V6 例例12的分析（見的分析（見P256） （三）（三）FloydFloyd算法算法用于求解任意兩點(diǎn)之間的最短路.算法的基本思想及步驟算法的基本思想及步驟（1 1） 先寫出網(wǎng)絡(luò)的權(quán)矩陣先寫出

57、網(wǎng)絡(luò)的權(quán)矩陣D=(dD=(dijij) )n nn,lij表示表示Vi到到Vj的距離。的距離。(,)ijijlV i V jEd其 他（2）D（k）=( dij(k)dij(k） =mindij(k-1),dil(k-1)+ dlj(k-1)（3） 若若D（k）=D（k-1），），的的 ，則算法，則算法終止。終止。例例13 13 求下圖中任意兩點(diǎn)間的最短路求下圖中任意兩點(diǎn)間的最短路 解解：用：用Floyd算法算法, ,首先寫出其首先寫出其( (對稱的對稱的) )權(quán)矩權(quán)矩陣陣A = (dij )88. . 0 1 2 3 4 5 6 70 1 2 3 4 5 6 70 0 0 2 8 1 0 2

58、 8 1 1 1 2 0 6 1 2 0 6 1 2 2 8 6 0 7 5 1 2 8 6 0 7 5 1 2 3 3 1 7 0 9 1 7 0 9 4 4 1 5 0 3 8 1 5 0 3 85 5 1 3 0 4 6 1 3 0 4 66 6 2 9 4 0 3 2 9 4 0 37 7 8 6 3 0 8 6 3 0D= 用用Floyd算法算法, ,首先寫出首先寫出D D（1 1） 如下如下 0 1 2 3 4 5 6 70 1 2 3 4 5 6 70 0 0 2 8 1 3 9 10 0 2 8 1 3 9 10 1 1 2 0 6 3 1 4 8 9 2 0 6 3 1 4

59、8 92 2 8 6 0 7 4 1 2 5 8 6 0 7 4 1 2 53 3 1 3 7 0 12 8 9 12 1 3 7 0 12 8 9 124 4 3 1 4 12 0 3 7 8 3 1 4 12 0 3 7 85 5 9 4 1 8 3 0 3 6 9 4 1 8 3 0 3 66 6 10 8 2 9 7 3 0 3 10 8 2 9 7 3 0 37 7 9 5 12 8 6 3 0 9 5 12 8 6 3 0D(1)= 0 1 2 3 4 5 6 70 1 2 3 4 5 6 70 0 0 2 7 1 3 6 10 11 0 2 7 1 3 6 10 111 1 2

60、0 5 3 1 4 7 9 2 0 5 3 1 4 7 92 2 7 5 0 7 4 1 2 5 7 5 0 7 4 1 2 53 3 1 3 7 0 5 7 9 12 1 3 7 0 5 7 9 124 4 3 1 4 5 0 3 6 8 3 1 4 5 0 3 6 85 5 6 4 1 7 3 0 3 6 6 4 1 7 3 0 3 66 6 10 7 2 9 6 3 0 3 10 7 2 9 6 3 0 37 7 11 9 5 12 8 6 3 0 11 9 5 12 8 6 3 0D(2)= 求出求出D D（2 2） 如下如下 0 1 2 3 4 5 6 70 1 2 3 4 5 6