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

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

2、數(shù)量分別為400、600和500，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺時數(shù)和加工費用如下表.問怎樣分配車床的加工任務，才能既滿足加工工件的要求，又使加工費用最低？ 單位工件所需加工臺時數(shù) 單位工件的加工費用 車床類 型 工件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 引例引例解解 設在甲車床上加工工件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 目標函數(shù)和所有的約束條件都是設計變量目標函數(shù)和所有的約束條件都是設計變量的線性函數(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= ，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 若沒有等式約束: , 則令Aeq= , beq= . 2其中X0表示初始點 beqXAeq4. 命令：x,fval=linprog()返回最優(yōu)解及處的目標函數(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)結果結果:x = 0.0000 600.0000 0.0000 400.0000 0.0000 500.0000fval =1.3800e+004 即在甲機床上加工600個工件2,在乙機床上加工400個工件1、500個工件3，可在滿足條件的情況下使總加工費最小為13800. 投資的收益和風險投資的收益和風險二、基本假設和符號規(guī)定二、基本假設和符號規(guī)定三、模型的建立與分析三、模型的建立與分析1.總體風險用所投資的Si中最大的一個風險來衡量,即max qixi|i=1，2,n4. 模型簡

8、化：四、模型四、模型1 1的求解的求解 由于a是任意給定的風險度，到底怎樣給定沒有一個準則，不同的投資者有不同的風險度.我們從a=0開始，以步長a=0.001進行循環(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）計算結果：計算結果：五、五、 結果分析結果分析返 回4 4.在a=0.006附近有一個轉折點，在這一點左邊，風險增加很少時，利潤增長 很快.在這一點右邊，風險增加很大時，利潤增長很緩慢，所以對于風險和 收益沒有特殊偏好的投資者來說，應該選擇曲線的拐點作為最優(yōu)投資組合， 大約是a*=0.6%，Q*=20% ，所對應投資方案為: 風險度 收益 x0 x1 x2 x3 x4 0.00

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

11、 目目 標標 規(guī)規(guī) 劃劃一、多一、多 目標目標 規(guī)規(guī) 劃劃 及及 其其 解解 多目標規(guī)劃包含有三大要素：多目標規(guī)劃包含有三大要素： 目標、方案和決策者目標、方案和決策者 多目標規(guī)劃中的方案即為決策變量，也稱為多目標問題的多目標規(guī)劃中的方案即為決策變量，也稱為多目標問題的解。備選方案即決策問題的可行解。在多目標決策中，有解。備選方案即決策問題的可行解。在多目標決策中，有些問題的方案是有限的，有些問題的方案是無限的。方案些問題的方案是有限的，有些問題的方案是無限的。方案有其特征或特性，稱之為屬性。有其特征或特性，稱之為屬性。例題例題 某工廠在一個計劃期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，某工廠在一個計劃期內(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)值都最大，且造成的污染最?。考准滓乙屹Y源限量資源限量資源資源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解：問題的多目標模型如下解：問題的多目標模型如下0,300103200542404923)(max(600400)(max12070)(max21212121213212211xxxxxxxxxxXfxxXfxxXf對于此模型的三個目標，工對于此模型的三個目標，工廠確定利潤最大為主要目標。廠確定利潤最大為主要目標。另兩個目標則通過預測預先另兩個目標則通過預測預先給定的希望達到的目標值轉給定的希望達到的目標值

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

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

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

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

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

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

20、)(. .)(max1pkXfmjXhniXgtsXfkkji例題例題 某工廠在一個計劃期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，某工廠在一個計劃期內(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解：問題的多目標模型如下解：問題的多目標模型如下0,300103200542404923)(max(600400)(max12070)(max21212121213212211xxxxxxxxxxXfxxXfxxXf對于此模型的三個目標，工對于此模型的三個目標，工廠確定利潤

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

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

24、XhXgtsXfXUjipiii則多目標問題化為如下的單目標問題則多目標問題化為如下的單目標問題例如，某公司計劃購進一批新卡車，可供選擇的卡車有例如，某公司計劃購進一批新卡車，可供選擇的卡車有如下如下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種型號的種型號的卡車分別關于目標屬性的指標值卡車分別關于目標屬性的指標值fi

25、jij如下表所示。如下表所示。fijf1f2f3f4f5f6A12.01500455一般一般高高A22.527003.665低低一般一般A32.020004.245高高很高很高A42.21800450很高很高一般一般首先對不同度量單位和不同數(shù)量級的指標值進行標準首先對不同度量單位和不同數(shù)量級的指標值進行標準化處理。先將定性指標定量化：化處理。先將定性指標定量化：變換后的指標值矩陣為：變換后的指標值矩陣為：aijf1f2f3f4f5f6A1116750.53450.5A2100100110011A3142.25100167100A440.625.756725.751001設權系數(shù)向量為設權系數(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法）法） 這是一種交互方法，其求解過程通過分析者與決策這是一種交互方法，其求解過程通過分析者與決策者之間的對話逐步進行，故稱步驟法。者之間的對話逐步進行，故稱步驟法。 步驟法的基本思想是，首先需要求出原多目標問題步驟法的基本思想是，首先需要求出原多目標問題的一組理想解的一組理

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

28、*21*21*11211*121pipppppiiiiipipifzzzXzfzzXzzzfXffffX例題：例題：某公司考慮生產(chǎn)兩種光電太陽能電池：產(chǎn)品甲和某公司考慮生產(chǎn)兩種光電太陽能電池：產(chǎn)品甲和產(chǎn)品乙。這種生產(chǎn)過程會在空氣中引起放射性污染。因產(chǎn)品乙。這種生產(chǎn)過程會在空氣中引起放射性污染。因此，公司經(jīng)理有兩個目標：極大化利潤與極小化總的放此，公司經(jīng)理有兩個目標：極大化利潤與極小化總的放射性污染。已知在一個生產(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個個單位單位. .由于機器能力由于機器能力( (小時小時) )、裝配能力（人時）和可用、裝配能力（人時）和可用的原材料（單位）的限制，約束條件是的原材料（單位）的限制，約束條件是)(725)(42 . 02 . 0)(825. 05 . 0212121原材料裝配能力機器能力xxxxxx)(725)(42 . 02 . 0)(825. 05 . 05 . 1)(,3)()(),()(max21212121221121原材料裝配能力機器能力xxxxxxxxXfxxXfXfXfXFT目標有兩個目標有兩個:

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

31、 0(1*2fX由此由此, ,構造支付表構造支付表Xf1*f2*(7,13)(0,0)460-23.50由此計算兩個目標與理由此計算兩個目標與理想值偏離的權重：想值偏離的權重：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進行下一

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

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

34、在這里我們主要討論線性目標規(guī)劃問題。線性目標規(guī)劃問題。一、線性目標規(guī)劃模型的建立一、線性目標規(guī)劃模型的建立 例例1 1：某一個企業(yè)利用某種原材料和現(xiàn)有設備可生某一個企業(yè)利用某種原材料和現(xiàn)有設備可生產(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個單位，需要占用個單位，需要占用的設備分別為的設備分別為1 1臺時和臺時和2 2臺時；原材料擁有量為臺時；原材料擁有量為1111個個單位；可利用的設備總臺時為

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

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

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

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

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

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

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

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

43、tion f=fun(X);f=F(X);標準型為： 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，否則轉入（，否則轉入（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 標號改變?yōu)闃颂柛淖優(yōu)镻 P 標號標號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，轉入（轉入（1 1）；否則結束。）；否則結束。這時，對每一個這時，對每一個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到各個點的最短路，到各個點的最短路，此時此時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標號中，標號中，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標號中，標號中，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標號中，標號中，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標號中，標號中，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的點，因此轉的點，因此轉入（入（3 3）。）。3 3）在所有的）在所有的T T標號中，標號中，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標號的點為標號的點為v v9 9，T T（v v9 9）=+=+，算法，算法結束。結束。此時，把此時，把P P標號和標號和值標在圖中，如圖值標在圖中，如

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的最短路。因為的最短路。因為（v v8 8）=5=5，故最短路經(jīng)過點，故最短路經(jīng)過點v v5 5有因為有因為（v v5 5）=2=2，故最短路經(jīng)過點，故最短路經(jīng)過點v v2 2。依次類推，。依次類推，（v v2 2）=3=3，（v v3 3）=1=1于是，最短路經(jīng)過點于是，最短路經(jīng)過點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到任一點到任一點v vi i的最短路，顯然不存在從的最短路，顯然不存在從v v1 1到到v v9 9的最短路。的最短路。 （二）逐次逼近法（二）逐次逼近法適用于網(wǎng)絡中帶負權的邊，求指定點 v1 到網(wǎng)絡中任意點的最短路 基本原理基本原理 如果v1 到vj 的最短路總是沿著該路從v1先到某一點vi ，然后再沿邊(vi , vj)到達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 從第二步起，使用迭代公式求 ，當進行到第t步，若出現(xiàn)則停止， 即為點v1 到各點的最短路長。), 3 , 2(min)1(1)(1nklPPijkiikj )(1kjP), 2 , 1()1(1)(1njPPtjtj ),2 , 1()(1njPtj 遞推公式中的 實際意義為從v1 到vj 點、至多含有 k-

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

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

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

57、網(wǎng)絡的權矩陣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 求下圖中任意兩點間的最短路求下圖中任意兩點間的最短路 解解：用：用Floyd算法算法, ,首先寫出其首先寫出其( (對稱的對稱的) )權矩權矩陣陣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