【大學(xué)競賽】數(shù)學(xué)建模輔導(dǎo) 優(yōu)化(p88)

1、整理課件 動態(tài)規(guī)劃方法簡介動態(tài)規(guī)劃方法簡介 整理課件整理課件整理課件12n狀態(tài)狀態(tài)決策決策狀態(tài)狀態(tài)決策決策狀態(tài)狀態(tài)狀態(tài)狀態(tài)決策決策圖示圖示 整理課件 動態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)動態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種數(shù)量方法。其特點在于，它可以把一化的一種數(shù)量方法。其特點在于，它可以把一個個n 維決策問題變換為幾個一維最優(yōu)化問題，從維決策問題變換為幾個一維最優(yōu)化問題，從而一個一個地去解決。而一個一個地去解決。 需指出：動態(tài)規(guī)劃是求解某類問題的一種需指出：動態(tài)規(guī)劃是求解某類問題的一種方法，方法，是考察問題的一種途徑是考察問題的一種途徑，而不是一種算，而不是一種算法。必須對具體問題進(jìn)

2、行具體分析，運用動態(tài)法。必須對具體問題進(jìn)行具體分析，運用動態(tài)規(guī)劃的原理和方法，建立相應(yīng)的模型，然后再規(guī)劃的原理和方法，建立相應(yīng)的模型，然后再用動態(tài)規(guī)劃方法去求解。用動態(tài)規(guī)劃方法去求解。整理課件二、多階段決策問題舉例二、多階段決策問題舉例1)工廠生產(chǎn)過程工廠生產(chǎn)過程：由于市場需求是一隨著時間而：由于市場需求是一隨著時間而變化的因素，因此，為了取得全年最佳經(jīng)濟(jì)效益，變化的因素，因此，為了取得全年最佳經(jīng)濟(jì)效益，就要在全年的生產(chǎn)過程中，逐月或者逐季度地根就要在全年的生產(chǎn)過程中，逐月或者逐季度地根據(jù)庫存和需求情況決定生產(chǎn)計劃安排。據(jù)庫存和需求情況決定生產(chǎn)計劃安排。整理課件 2)2)設(shè)備更新問題設(shè)備更新問

3、題：一般企業(yè)用于生產(chǎn)一般企業(yè)用于生產(chǎn)活動的設(shè)備，剛買來時故障少，經(jīng)濟(jì)效益活動的設(shè)備，剛買來時故障少，經(jīng)濟(jì)效益高，即使進(jìn)行轉(zhuǎn)讓，處理價值也高，隨著高，即使進(jìn)行轉(zhuǎn)讓，處理價值也高，隨著使用年限的增加，就會逐漸變?yōu)楣收隙?，使用年限的增加，就會逐漸變?yōu)楣收隙?，維修費用增加，可正常使用的工時減少，維修費用增加，可正常使用的工時減少，加工質(zhì)量下降，經(jīng)濟(jì)效益差，并且，使用加工質(zhì)量下降，經(jīng)濟(jì)效益差，并且，使用的年限越長、處理價值也越低，自然，如的年限越長、處理價值也越低，自然，如果賣去舊的買新的，還需要付出更新果賣去舊的買新的，還需要付出更新費因此就需要綜合權(quán)衡決定設(shè)備的使用費因此就需要綜合權(quán)衡決定設(shè)備的使用

4、年限，使總的經(jīng)濟(jì)效益最好。年限，使總的經(jīng)濟(jì)效益最好。整理課件3) 3)連續(xù)生產(chǎn)過程的控制問題連續(xù)生產(chǎn)過程的控制問題：一般化工一般化工生產(chǎn)過程中，常包含一系列完成生產(chǎn)生產(chǎn)過程中，常包含一系列完成生產(chǎn)過程的設(shè)備，前一工序設(shè)備的輸出則過程的設(shè)備，前一工序設(shè)備的輸出則是后一工序設(shè)備的輸入，因此，應(yīng)該是后一工序設(shè)備的輸入，因此，應(yīng)該如何根據(jù)各工序的運行工況，控制生如何根據(jù)各工序的運行工況，控制生產(chǎn)過程中各設(shè)備的輸入和輸出，以使產(chǎn)過程中各設(shè)備的輸入和輸出，以使總產(chǎn)量最大?？偖a(chǎn)量最大。整理課件整理課件4)4)運輸網(wǎng)絡(luò)問題（最短路問題）運輸網(wǎng)絡(luò)問題（最短路問題）：如圖如圖1所示的運輸網(wǎng)絡(luò)，點間連線上的數(shù)字表所

5、示的運輸網(wǎng)絡(luò)，點間連線上的數(shù)字表示兩地距離示兩地距離(也可是運費、時間等也可是運費、時間等)，要，要求從求從v1至至v10的最短路線。的最短路線。 這種運輸網(wǎng)絡(luò)問題也是靜態(tài)決策問題。這種運輸網(wǎng)絡(luò)問題也是靜態(tài)決策問題。但是，按照網(wǎng)絡(luò)中點的分布，可以把它但是，按照網(wǎng)絡(luò)中點的分布，可以把它分為分為4個階段，而作為多階段決策問題個階段，而作為多階段決策問題來研究。來研究。整理課件 以上所舉問題的發(fā)展過程都與時間因以上所舉問題的發(fā)展過程都與時間因素有關(guān)，階段的劃分常取時間區(qū)段來表示，素有關(guān)，階段的劃分常取時間區(qū)段來表示，并且各個階段上的決策往往也與時間因素并且各個階段上的決策往往也與時間因素有關(guān)，這就使

6、它具有了有關(guān)，這就使它具有了“動態(tài)動態(tài)”的含義，的含義，所以把處理這類動態(tài)問題的方法稱為動態(tài)所以把處理這類動態(tài)問題的方法稱為動態(tài)規(guī)劃方法。不過，實際中尚有許多不包含規(guī)劃方法。不過，實際中尚有許多不包含時間因素的一類時間因素的一類“靜態(tài)靜態(tài)”決策問題，就其決策問題，就其本質(zhì)而言是一次決策問題，是非動態(tài)決策本質(zhì)而言是一次決策問題，是非動態(tài)決策問題，但是也可以人為地引入階段的概念問題，但是也可以人為地引入階段的概念當(dāng)作多階段決策問題，應(yīng)用動態(tài)規(guī)劃方法當(dāng)作多階段決策問題，應(yīng)用動態(tài)規(guī)劃方法加以解決。加以解決。整理課件 三、動態(tài)規(guī)劃方法導(dǎo)引三、動態(tài)規(guī)劃方法導(dǎo)引 例例1 1：為了說明動態(tài)規(guī)劃的基本思想方法和

7、為了說明動態(tài)規(guī)劃的基本思想方法和特點，下面以圖特點，下面以圖1 1所示為例討論的求最短路問題所示為例討論的求最短路問題的方法。的方法。 第一種方法稱做第一種方法稱做全枚舉法全枚舉法或或窮舉法窮舉法。它的。它的基本思想是列舉出所有可能發(fā)生的方案和結(jié)果，基本思想是列舉出所有可能發(fā)生的方案和結(jié)果，再對它們一一進(jìn)行比較，求出最優(yōu)方案。這里再對它們一一進(jìn)行比較，求出最優(yōu)方案。這里從從v v1 1到到v v1010的路程可以分為的路程可以分為4 4個階段。第一段的走個階段。第一段的走法有三種，第二三兩段的走法各有兩種，第四法有三種，第二三兩段的走法各有兩種，第四段的走法僅一種，因此共有段的走法僅一種，因此

8、共有3 32 22 21 11212條條可能的路線，分別算出各條路線的距離，最后可能的路線，分別算出各條路線的距離，最后進(jìn)行比較，可知最優(yōu)路線是進(jìn)行比較，可知最優(yōu)路線是v v1 1 v v3 3 v v7 7 v v9 9 v v10 10 , ,最短距離是最短距離是1818整理課件 顯然，當(dāng)組成交通網(wǎng)絡(luò)的節(jié)點很多顯然，當(dāng)組成交通網(wǎng)絡(luò)的節(jié)點很多時，用窮舉法求最優(yōu)路線的計算工作量時，用窮舉法求最優(yōu)路線的計算工作量將會十分龐大，而且其中包含著許多重將會十分龐大，而且其中包含著許多重復(fù)計算復(fù)計算 第二種方法即所謂第二種方法即所謂“局部最優(yōu)路徑局部最優(yōu)路徑”法，是說某人從法，是說某人從k k出發(fā)，他并

9、不顧及全線出發(fā)，他并不顧及全線是否最短，只是選擇當(dāng)前最短途徑，是否最短，只是選擇當(dāng)前最短途徑，“逢近便走逢近便走”，錯誤地以為局部最優(yōu)會，錯誤地以為局部最優(yōu)會致整體最優(yōu)，在這種想法指導(dǎo)下，所取致整體最優(yōu)，在這種想法指導(dǎo)下，所取決策必是決策必是v1 v3 v5 v8 v10 v1 v3 v5 v8 v10 ，全程長度是全程長度是2020；顯然，這種方法的結(jié)果；顯然，這種方法的結(jié)果常是錯誤的常是錯誤的整理課件 第三種方法是第三種方法是動態(tài)規(guī)劃方法動態(tài)規(guī)劃方法。動態(tài)規(guī)。動態(tài)規(guī)劃方法尋求該最短路問題的基本思想是，劃方法尋求該最短路問題的基本思想是，首先將問題劃分為首先將問題劃分為4 4個階段，個階段，

10、每次的選擇總每次的選擇總是綜合后繼過程的一并最優(yōu)進(jìn)行考慮是綜合后繼過程的一并最優(yōu)進(jìn)行考慮，在，在各段所有可能狀態(tài)的最優(yōu)后繼過程都已求各段所有可能狀態(tài)的最優(yōu)后繼過程都已求得的情況下，全程的最優(yōu)路線便也隨之得得的情況下，全程的最優(yōu)路線便也隨之得到。到。 為了找出所有可能狀態(tài)的最優(yōu)后繼過為了找出所有可能狀態(tài)的最優(yōu)后繼過程，動態(tài)規(guī)劃方法總是從過程的最后階段程，動態(tài)規(guī)劃方法總是從過程的最后階段開始考慮，然后逆著實際過程發(fā)展的順序，開始考慮，然后逆著實際過程發(fā)展的順序，逐段向前遞推計算直至始點。逐段向前遞推計算直至始點。整理課件 具體說，此問題先從具體說，此問題先從v v1010開始，因為開始，因為v v

11、1010是終是終點。再無后繼過程，故可以接著考慮第點。再無后繼過程，故可以接著考慮第4 4階段上階段上所有可能狀態(tài)所有可能狀態(tài)v v8 8 , ,v v9 9的最優(yōu)后續(xù)過程因為從的最優(yōu)后續(xù)過程因為從v v8 8 , ,v v9 9 到到v v1010的路線是唯一的，所以的路線是唯一的，所以v v8 8 , ,v v9 9 的最的最優(yōu)決策和最優(yōu)后繼過程就是到優(yōu)決策和最優(yōu)后繼過程就是到v v1010 ，它們的最短，它們的最短距離分別是距離分別是5 5和和3 3。 接著考慮階段接著考慮階段3 3上可能的狀態(tài)上可能的狀態(tài)v v5 5 , ,v v6 6 , , v v7 7 , , 到到v v1010

12、的最優(yōu)決策和最優(yōu)后繼過程在狀態(tài)的最優(yōu)決策和最優(yōu)后繼過程在狀態(tài)V V5 5上，上，雖然到雖然到v v8 8是是8 8，到，到v v9 9是是9 9，但是綜合考慮后繼過程，但是綜合考慮后繼過程整體最優(yōu)，取最優(yōu)決策是到整體最優(yōu)，取最優(yōu)決策是到v v9 9, ,最優(yōu)后繼過程是最優(yōu)后繼過程是v v5 5v v9 9 v v10 10 ，最短距離是，最短距離是1212同理，狀態(tài)同理，狀態(tài)v v6 6的的最優(yōu)決策是至最優(yōu)決策是至v v8 8 ；v v7 7的最優(yōu)決策是到的最優(yōu)決策是到v v9 9 。整理課件 同樣，當(dāng)階段同樣，當(dāng)階段3 3上所有可能狀態(tài)的最上所有可能狀態(tài)的最優(yōu)后繼過程都已求得后，便可以開始考

13、慮優(yōu)后繼過程都已求得后，便可以開始考慮階段階段2 2上所有可能狀態(tài)的最優(yōu)決策和最優(yōu)上所有可能狀態(tài)的最優(yōu)決策和最優(yōu)后繼過程，如后繼過程，如v v2 2的最優(yōu)決策是到的最優(yōu)決策是到v v5 5, ,最優(yōu)路最優(yōu)路線是線是v v2 2v v5 5v v9 9v v10 10 ，最短距離是，最短距離是1515依依此類推，最后可以得到從初始狀態(tài)此類推，最后可以得到從初始狀態(tài)v v1 1的最的最優(yōu) 決 策 是 到優(yōu) 決 策 是 到v v3 3最 優(yōu) 路 線 是最 優(yōu) 路 線 是v v1 1v v3 3v v7 7v v9 9v v10 10 ，全程的最短距離是，全程的最短距離是1818。圖。圖5151中粗實

14、線表示各點到中粗實線表示各點到v v1010的最優(yōu)的最優(yōu)路線，每點上方括號內(nèi)的數(shù)字表示該點到路線，每點上方括號內(nèi)的數(shù)字表示該點到終點的最短路距離。終點的最短路距離。整理課件 綜上所述可見，全枚舉法雖可找出最優(yōu)方案，綜上所述可見，全枚舉法雖可找出最優(yōu)方案，但不是個好算法，局部最優(yōu)法則完全是個錯誤方但不是個好算法，局部最優(yōu)法則完全是個錯誤方法，只有法，只有動態(tài)規(guī)劃方法屬較科學(xué)有效的算法動態(tài)規(guī)劃方法屬較科學(xué)有效的算法。它。它的基本思想是，的基本思想是，把一個比較復(fù)雜的問題分解為一把一個比較復(fù)雜的問題分解為一系列同類型的更易求解的子問題系列同類型的更易求解的子問題，便于應(yīng)用計算，便于應(yīng)用計算機(jī)。整個求

15、解過程分為兩個階段，機(jī)。整個求解過程分為兩個階段，先按整體最優(yōu)先按整體最優(yōu)的思想逆序地求出各個子問題中所有可能狀態(tài)的的思想逆序地求出各個子問題中所有可能狀態(tài)的最優(yōu)決策與最優(yōu)路線值，然后再順序地求出整個最優(yōu)決策與最優(yōu)路線值，然后再順序地求出整個問題的最優(yōu)策略和最優(yōu)路線。問題的最優(yōu)策略和最優(yōu)路線。計算過程中，系統(tǒng)計算過程中，系統(tǒng)地刪去了所有中間非最優(yōu)的方案組合，從而使計地刪去了所有中間非最優(yōu)的方案組合，從而使計算工作量比窮舉法大為減少。算工作量比窮舉法大為減少。整理課件四、動態(tài)規(guī)劃的基本概念與基本方程四、動態(tài)規(guī)劃的基本概念與基本方程 使用動態(tài)規(guī)劃方法解決多階段決策使用動態(tài)規(guī)劃方法解決多階段決策問題

16、，首先要將實際問題寫成動態(tài)規(guī)劃問題，首先要將實際問題寫成動態(tài)規(guī)劃模型，同時也為了今后敘述和討論方便，模型，同時也為了今后敘述和討論方便，這里需要對動態(tài)規(guī)劃的下述一些基本術(shù)這里需要對動態(tài)規(guī)劃的下述一些基本術(shù)語進(jìn)一步加以說明和定義語進(jìn)一步加以說明和定義： 整理課件 (一) 階段 為了便于求解和表示決策及過程的發(fā)展順序，而把所給問題恰當(dāng)?shù)貏澐譃槿舾蓚€相互聯(lián)系又有區(qū)別的子問題，稱之為多段決策問題的階段。一個階段，就是需要作出一個決策的子問題，通常，階段是按決策進(jìn)行的時間或空間上先后順序劃分的。用以描述階段的變量叫作階段變量，一般以k表示階段變量階段數(shù)等于多段決策過程從開始到結(jié)束所需作出決策的數(shù)目，圖1

17、所示的最短路問題就是一個四階段決策過程， 。1,2,3,4k 整理課件 （二）狀態(tài)二）狀態(tài) 1.狀態(tài)與狀態(tài)變量。用以描述事物用以描述事物( (或或系統(tǒng)系統(tǒng)) )在某特定的時間與空間域中所處位置在某特定的時間與空間域中所處位置及運動特征的量，稱為狀態(tài)及運動特征的量，稱為狀態(tài)。反映狀態(tài)變化的量叫做狀態(tài)變量。狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息。按照過程進(jìn)行的先后，每個階段的狀態(tài)可分為初始狀態(tài)和終止?fàn)顟B(tài)，或稱輸入狀態(tài)和輸出狀態(tài)，階段階段k k的初始狀態(tài)記作的初始狀態(tài)記作s sk k，終止?fàn)?，終止?fàn)顟B(tài)記為態(tài)記為s sk+1k+1。但為了清楚起見，通常定義階段的狀態(tài)即指其初始狀態(tài)。

18、狀態(tài)應(yīng)描述過程特征狀態(tài)應(yīng)描述過程特征; ;能直接或間接觀測能直接或間接觀測; ;具有無后效性具有無后效性. . 某階段的狀態(tài)給定后，則過程未來發(fā)展不受該階段以前各階段狀態(tài)的影響某階段的狀態(tài)給定后，則過程未來發(fā)展不受該階段以前各階段狀態(tài)的影響整理課件 2可能狀態(tài)集 一般狀態(tài)變量的取值有一定的范圍或允許集合，稱為可能狀態(tài)集，或可達(dá)狀態(tài)集。通常可能狀態(tài)集用相應(yīng)階段狀態(tài)sk的大寫字母Sk表示，skSk，可能狀態(tài)集可以是一離散取值的集合，也可以為一連續(xù)的取值區(qū)間在圖1所示的最短路問題中，第一階段狀態(tài)為v1，狀態(tài)變量s1的狀態(tài)集合S1=v1；第二階段則有三個狀態(tài)：v2 , v3 , v4 , 狀 態(tài) 變

19、量s2的 狀 態(tài) 集 合S2=v2 ,v3 ,v4 ；第三階段也有三個狀態(tài):v5 ,v6 ,v7 ，狀態(tài)變量s3的狀態(tài)集合S3=v5 ,v6 ,v7 ；第四階段則有二個狀態(tài)： v8 ,v9 , 狀態(tài)變量s4的狀態(tài)集合S4=v8 ,v9 ；整理課件 （三）決策三）決策 所謂決策，就是確定系統(tǒng)過程發(fā)展的方案。決策的實質(zhì)是關(guān)于狀態(tài)的選擇，是決策者從給定階段狀態(tài)出發(fā)對下一階段狀態(tài)作出的選擇。 用以描述決策變化的量稱之決策變量，和狀態(tài)變量一樣，決策變量可以用一個數(shù)，一組數(shù)或一向量來描述，也可以是狀態(tài)變量的函數(shù)，記以u uk k= = u uk k( (s sk k) )，表示于階段k狀態(tài)sk時的決策變量

20、。 決策變量的取值往往也有一定的允許范圍，稱之允許決策集合。決策變量uk(sk)的允許決策集用U Uk k( (s sk k) )表示, u uk k( (s sk k) U) Uk k( (s sk k) )允許決策集合實際是決策的約束條件。整理課件 （四）狀態(tài)轉(zhuǎn)移方程（四）狀態(tài)轉(zhuǎn)移方程 系統(tǒng)在階段k處于狀態(tài)sk，執(zhí)行決策uk(sk)的結(jié)果是系統(tǒng)狀態(tài)的轉(zhuǎn)移，即系統(tǒng)由階段k的初始狀態(tài)sk轉(zhuǎn)移到終止?fàn)顟B(tài)sk+1，系統(tǒng)由階段k到階段k+1的狀態(tài)轉(zhuǎn)移完全由階段k的狀態(tài)sk和決策uk(sk)所確定，與系統(tǒng)過去的狀態(tài)s1,s2, ,sk-1及其決策u1(s1), u2(s2)uk-1(sk-1)無關(guān)。系

21、統(tǒng)狀態(tài)的這種轉(zhuǎn)移，用數(shù)學(xué)公式描述即有：)(,(1kkkkksusTs(1)整理課件 （五）、策略（五）、策略 策略(Policy)也叫決策序列策略有全過程策略和k部子策略之分，全過程策略是指具有n個階段的全部過程，由依次進(jìn)行的n個階段決策構(gòu)成 的 決 策 序 列 ， 簡 稱 策 略 ， 表 示 為p1,nu1,u2,un。從k階段到第n階段，依次進(jìn)行的階段決策構(gòu)成的決策序列稱為k部子策略,表示為pk,nuk,uk+1,un ，顯然當(dāng)k=1時的k部子策略就是全過程策略。 在實際問題中，由于在各個階段可供選擇的決策有許多個，因此，它們的不同組合就構(gòu)成了許多可供選擇的決策序列(策略)，由它們組成的集

22、合，稱之允許策略集合，記作P1,n ，從允許策略集中，找出具有最優(yōu)效果的策略稱為最優(yōu)策略。整理課件 (六) 指標(biāo)函數(shù) 用來衡量策略或子策略或決策的效果的某種數(shù)量指標(biāo)，就稱為指標(biāo)函數(shù)。它是定義在全過程或各子過程或各階段上的確定數(shù)量函數(shù)。對不同問題，指標(biāo)函數(shù)可以是諸如費用、成本、產(chǎn)值、利潤、產(chǎn)量、耗量、距離、時間、效用，等等。例如：圖1的指標(biāo)就是運費。整理課件 (1)(1)階段指標(biāo)函數(shù)（也稱階段效應(yīng)）。階段指標(biāo)函數(shù)（也稱階段效應(yīng)）。用用v vk k( (s sk k,u,uk k) )表示第表示第k k段處于段處于s sk k狀態(tài)且所作決策為狀態(tài)且所作決策為u uk k( (s sk k) )時的

23、指標(biāo)，則它就是第時的指標(biāo)，則它就是第k k段指標(biāo)函數(shù)段指標(biāo)函數(shù)。 (2)(2)過程指標(biāo)函數(shù)（也稱目標(biāo)函數(shù)）。過程指標(biāo)函數(shù)（也稱目標(biāo)函數(shù)）。 不僅跟當(dāng)前狀態(tài)不僅跟當(dāng)前狀態(tài)s sk k有關(guān)，還跟該子過程策略有關(guān)，還跟該子過程策略p pk,nk,n( (s sk k) )有關(guān)，表示為有關(guān)，表示為: :,()k nk nkVps整理課件 適于用動態(tài)規(guī)劃求解的問題的過程指標(biāo)函數(shù)適于用動態(tài)規(guī)劃求解的問題的過程指標(biāo)函數(shù)（即目標(biāo)函數(shù)），必須具有關(guān)于階段指標(biāo)的可分（即目標(biāo)函數(shù)），必須具有關(guān)于階段指標(biāo)的可分離形式對于部子過程的指標(biāo)函數(shù)可以表示為：離形式對于部子過程的指標(biāo)函數(shù)可以表示為： ,1,1,1()(,()k

24、 nk nkkkkknknkVpss u Vps (2),11 ,1 ,1()(,)(,)(,)(,)()nknknkiiiiknkkkiiiikkkkknknkVpsvsuvsuvsuvsuVps 整理課件 ( (七七) ) 最優(yōu)解最優(yōu)解 用用f fk k( (s sk k) )表示第表示第k k子過程指標(biāo)函數(shù)在狀態(tài)子過程指標(biāo)函數(shù)在狀態(tài)s sk k下的最下的最優(yōu)值優(yōu)值, ,即即 相應(yīng)的子策略稱為相應(yīng)的子策略稱為s sk k狀態(tài)下的最優(yōu)子策略，記狀態(tài)下的最優(yōu)子策略，記為為p pk,nk,n* *( (s sk k) ) ；而構(gòu)成該子策賂的各段決策稱為該；而構(gòu)成該子策賂的各段決策稱為該過程上的最

25、優(yōu)決策，記為過程上的最優(yōu)決策，記為 ；有有 ,()()()(*(),1,2,k nk nkkkk nk nkk nk nkpPsfsoptVpsVpskn )(,),(),(11nnkkkksususu ,1,1,2,k nkknpuuukn 整理課件 最優(yōu)化原理最優(yōu)化原理 （貝爾曼最優(yōu)化原理）（貝爾曼最優(yōu)化原理） 作為一個全過程的最優(yōu)策略具有這樣的性質(zhì)：作為一個全過程的最優(yōu)策略具有這樣的性質(zhì)：對于最優(yōu)策略過程中的任意狀態(tài)而言，無論其過去對于最優(yōu)策略過程中的任意狀態(tài)而言，無論其過去的狀態(tài)和決策如何，余下的諸決策必構(gòu)成一個最優(yōu)的狀態(tài)和決策如何，余下的諸決策必構(gòu)成一個最優(yōu)子策略。子策略。該原理的具

26、體解釋是，若某一全過程最優(yōu)該原理的具體解釋是，若某一全過程最優(yōu)策略為策略為：1,11122( )( ),(),(),()nkknnpsu su su su s 則對上述策略中所隱含的任一狀態(tài)而言，則對上述策略中所隱含的任一狀態(tài)而言， 第第k k子過程上對應(yīng)于該狀態(tài)的最優(yōu)策略必然子過程上對應(yīng)于該狀態(tài)的最優(yōu)策略必然 包含在上述全過程最優(yōu)策略包含在上述全過程最優(yōu)策略p p1 1* *中，即為中，即為,11()(),(),()k nkkkkknnpsususus ( (八八) ) 動態(tài)規(guī)劃的最優(yōu)性原理動態(tài)規(guī)劃的最優(yōu)性原理整理課件1111()()0() ( ,)(),1,2,1kkknnkkkkkkku

27、Dsfsf soptv s ufskn n 整理課件（三）、建立動態(tài)規(guī)劃模型的步驟（三）、建立動態(tài)規(guī)劃模型的步驟 1 1、劃分階段、劃分階段劃分階段是運用動態(tài)規(guī)劃求解多階段決策問題的第一劃分階段是運用動態(tài)規(guī)劃求解多階段決策問題的第一步，在確定多階段特性后，按時間或空間先后順序，步，在確定多階段特性后，按時間或空間先后順序，將過程劃分為若干相互聯(lián)系的階段。對于靜態(tài)問題要將過程劃分為若干相互聯(lián)系的階段。對于靜態(tài)問題要人為地賦予人為地賦予“時間時間”概念，以便劃分階段。概念，以便劃分階段。 2 2、正確選擇狀態(tài)變量、正確選擇狀態(tài)變量選擇變量既要能確切描述過程演變又要滿足無后效性，選擇變量既要能確切描

28、述過程演變又要滿足無后效性，而且各階段狀態(tài)變量的取值能夠確定。一般地，狀態(tài)而且各階段狀態(tài)變量的取值能夠確定。一般地，狀態(tài)變量的選擇是從過程演變的特點中尋找。變量的選擇是從過程演變的特點中尋找。 3 3、確定決策變量及允許決策集合、確定決策變量及允許決策集合通常選擇所求解問題的關(guān)鍵變量作為決策變量，同時通常選擇所求解問題的關(guān)鍵變量作為決策變量，同時要給出決策變量的取值范圍，即確定允許決策集合。要給出決策變量的取值范圍，即確定允許決策集合。整理課件 4 4、確定狀態(tài)轉(zhuǎn)移方程、確定狀態(tài)轉(zhuǎn)移方程根據(jù)根據(jù)k 階段狀態(tài)變量和決策變量，寫出階段狀態(tài)變量和決策變量，寫出k+1階段狀態(tài)變階段狀態(tài)變量，狀態(tài)轉(zhuǎn)移方

29、程應(yīng)當(dāng)具有遞推關(guān)系。量，狀態(tài)轉(zhuǎn)移方程應(yīng)當(dāng)具有遞推關(guān)系。 5 5、確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)，建立動態(tài)規(guī)、確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)，建立動態(tài)規(guī)劃基本方程劃基本方程 階段指標(biāo)函數(shù)是指第階段指標(biāo)函數(shù)是指第k 階段的收益，最優(yōu)指標(biāo)函數(shù)階段的收益，最優(yōu)指標(biāo)函數(shù)是指從第是指從第k 階段狀態(tài)出發(fā)到第階段狀態(tài)出發(fā)到第n 階段末所獲得收益的最階段末所獲得收益的最優(yōu)值，最后寫出動態(tài)規(guī)劃基本方程。優(yōu)值，最后寫出動態(tài)規(guī)劃基本方程。 以上五步是建立動態(tài)規(guī)劃數(shù)學(xué)模型的一般步驟。由于以上五步是建立動態(tài)規(guī)劃數(shù)學(xué)模型的一般步驟。由于動態(tài)規(guī)劃模型與線性規(guī)劃模型不同，動態(tài)規(guī)劃模型沒有統(tǒng)動態(tài)規(guī)劃模型與線性規(guī)劃模型不同，動態(tài)

30、規(guī)劃模型沒有統(tǒng)一的模式，建模時必須根據(jù)具體問題具體分析，只有通過一的模式，建模時必須根據(jù)具體問題具體分析，只有通過不斷實踐總結(jié)，才能較好掌握建模方法與技巧。不斷實踐總結(jié)，才能較好掌握建模方法與技巧。 整理課件例一、從例一、從A 地到地到D 地要鋪設(shè)一條煤氣管道地要鋪設(shè)一條煤氣管道,其中需經(jīng)過其中需經(jīng)過兩級中間站，兩點之間的連線上的數(shù)字表示距離，如兩級中間站，兩點之間的連線上的數(shù)字表示距離，如圖所示。問應(yīng)該選擇什么路線，使總距離最短？圖所示。問應(yīng)該選擇什么路線，使總距離最短？ AB1B2C1C2C3D24333321114五、建模舉例：最短路徑問題五、建模舉例：最短路徑問題整理課件 解：整個計算

31、過程分三個階段，從最后一個階段開始。解：整個計算過程分三個階段，從最后一個階段開始。 第一階段（第一階段（C D）：）： C 有三條路線到終點有三條路線到終點D 。 AB1B2C1C2C3D24333321114DC1C2C3顯然有顯然有 f1 (C1 ) = 1 ； f1(C2 ) = 3 ； f1 (C3 ) = 4 整理課件 d( B1,C1 ) + f1 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f1 (C2 ) = min 3+3 d( B1,C3 ) + f1 (C3 ) 1+4 4 = min 6 = 4 5第二階段（第二階段（B C）：）：

32、B 到到C 有六條路線。有六條路線。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為最短路線為B1C1 D)整理課件 d( B2,C1 ) + f1 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f1 (C2 ) = min 3+3 d( B2,C3 ) + f1 (C3 ) 1+4 3 = min 6 = 3 5AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為最短路線為B2C1 D)整理課件第三階段（第三階段（ A B ）：）： A 到到B 有二條路線。有二條路線。 f3(A)1 = d(A, B

33、1 ) f2 ( B1 ) 246 f3 (A)2 = d(A, B2 ) f2 ( B2 ) 437 f3 (A) = min = min6,7=6d(A, B1 ) f2 ( B1 )d(A, B2 ) f2 ( B2 )(最短路線為最短路線為AB1C1 D)AB1B2C1C2C3D24333321114DC1C2C3B1B2A整理課件AB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路線為最短路線為 AB1C1 D 路長為路長為 6整理課件SETS:CITIES/1.7/:F;ROADS(CITIES,CITIES)/1, 2 1, 32, 4 2, 5 2, 6

34、3, 4 3, 5 3, 6 4, 7 5, 7 6, 7/:D;ENDSETS DATA:D=2 4 3 3 1 2 3 1 1 3 4;ENDDATAF(SIZE(CITIES)=0;FOR(CITIES(i)|i#LT#SIZE(CITIES):F(i)=MIN(ROADS(i,j):D(i,j)+F(j);ENDlINGO程序整理課件 Feasible solution found. Total solver iterations: 0 Variable Value Row Slack or Surplus運行結(jié)果運行結(jié)果整理課件練習(xí)練習(xí)1：AB1B2C1C2C3C4D1D2D3E1E

35、2E3F1F2G53136876368533842221333525664最優(yōu)路線為：最優(yōu)路線為：A B1 C2 D1 E2 F2 G 路長路長18求從求從A到到G的最短路徑的最短路徑3整理課件 有資金有資金4 4萬元，投資萬元，投資A A、B B、C C三個項目，每個項目的投資效三個項目，每個項目的投資效益與投入該項目的資金有關(guān)。三個項目益與投入該項目的資金有關(guān)。三個項目A A、B B、C C的投資效益的投資效益（萬噸）和投入資金（萬元）關(guān)系見下表（萬噸）和投入資金（萬元）關(guān)系見下表：求對三個項目的最優(yōu)投資分配，使總投資效益最大。求對三個項目的最優(yōu)投資分配，使總投資效益最大。練習(xí)練習(xí)2 2整

36、理課件w階段k：每投資一個項目作為一個階段；w狀態(tài)變量xk：投資第k個項目前的資金數(shù)；w決策變量dk：第k個項目的投資；w決策允許集合：0dkxkw狀態(tài)轉(zhuǎn)移方程：xk+1=xk-dkw階段指標(biāo)：vk(xk ,dk)見表中所示；w遞推方程：fk(xk)=maxvk(xk ,dk)+fk+1(xk+1)w終端條件：f4(x4)=0整理課件k=4，f4(x4)=0k=3，0d3x3，x4=x3-d3整理課件k=2，0d2x2，x3=x2-d2整理課件k=1，0d1x1，x2=x1-d1整理課件無約束最優(yōu)化問題無約束最優(yōu)化問題標(biāo)準(zhǔn)形式：標(biāo)準(zhǔn)形式：RmaxnXfXRmin nXfX例：選址問題 某市燃?xì)?/p>

37、公司計劃要建一個煤氣供應(yīng)站，該站要向城市中某市燃?xì)夤居媱澮ㄒ粋€煤氣供應(yīng)站，該站要向城市中有固定位置的有固定位置的m m 個用戶供貨個用戶供貨. .對于選定的坐標(biāo)系而言，已知對于選定的坐標(biāo)系而言，已知第第i i 個用戶的位置為個用戶的位置為如果只考慮直線距離，如何確定這個煤氣站的位置，才能如果只考慮直線距離，如何確定這個煤氣站的位置，才能使總的運輸距離最短使總的運輸距離最短？整理課件解：設(shè)煤氣站的位置為解：設(shè)煤氣站的位置為則第則第i 個用戶到個用戶到該站的直線距離為該站的直線距離為故故 m 個用戶到該站的總距離為個用戶到該站的總距離為故選址問題可以歸結(jié)為求變量故選址問題可以歸結(jié)為求變量使得使

38、得整理課件無約束優(yōu)化問題的解法無約束優(yōu)化問題的解法可微，則利用可微，則利用 求其駐點，然后利用充分條件判別這些駐點是否求其駐點，然后利用充分條件判別這些駐點是否是極值點。是極值點。.2. 搜索算法（迭代算法）搜索算法（迭代算法）基本思想基本思想：首先給定目標(biāo)函數(shù)首先給定目標(biāo)函數(shù) 的極小點的一個初始的極小點的一個初始估計點估計點 然后按照一定的規(guī)則產(chǎn)生一個點列然后按照一定的規(guī)則產(chǎn)生一個點列 ，希望，希望這種點列的極限是的一個極小點這種點列的極限是的一個極小點 .需要給定初始點需要給定初始點整理課件常見的算法常見的算法： 梯度法（最速下降法）梯度法（最速下降法）用用MATLABMATLAB優(yōu)化工具

39、箱求解無約束最優(yōu)化優(yōu)化工具箱求解無約束最優(yōu)化計算機(jī)實現(xiàn)計算機(jī)實現(xiàn) 前面我們介紹了前面我們介紹了Matlab 工具箱中函數(shù)用工具箱中函數(shù)用linprog解線性規(guī)劃的解線性規(guī)劃的方法，方法，Matlab優(yōu)化工具箱還提供了一般無約束優(yōu)化與約束優(yōu)化優(yōu)化工具箱還提供了一般無約束優(yōu)化與約束優(yōu)化的求解問題，下面介紹的求解問題，下面介紹Matlab優(yōu)化工具箱的主要函數(shù)。優(yōu)化工具箱的主要函數(shù)。整理課件MATLAB優(yōu)化工具箱簡介優(yōu)化工具箱簡介1.1.MATLAB求解優(yōu)化問題的主要函數(shù)求解優(yōu)化問題的主要函數(shù)整理課件 使用優(yōu)化函數(shù)或優(yōu)化工具箱中其他優(yōu)化函數(shù)時使用優(yōu)化函數(shù)或優(yōu)化工具箱中其他優(yōu)化函數(shù)時, , 輸入變量見下

40、表輸入變量見下表:整理課件3.3.優(yōu)化函數(shù)的輸出變量見下表優(yōu)化函數(shù)的輸出變量見下表: :整理課件3.3.優(yōu)化函數(shù)的輸出變量見下表優(yōu)化函數(shù)的輸出變量見下表: :整理課件4 4控制參數(shù)選項的設(shè)置控制參數(shù)選項的設(shè)置 (3) MaxIterMaxIter: 允許進(jìn)行迭代的最大次數(shù),取值為正整數(shù).選項中常用的幾個參數(shù)的名稱、含義、取值如下選項中常用的幾個參數(shù)的名稱、含義、取值如下: :off時,不顯示輸出; 取值為iter時,顯示每次迭代的信息;取值為finalfinal.(2)MaxFunEvals: 允許進(jìn)行函數(shù)評價的最大次數(shù),取值為正整數(shù).整理課件例：opts=optimset(Display,

41、iter, TolFun,1e-8) 該語句創(chuàng)建一個稱為選擇的優(yōu)化選項結(jié)構(gòu),其中顯示參數(shù)設(shè)為iter, TolFun參數(shù)設(shè)為1e-8. 控制參數(shù)選項可以通過函數(shù)控制參數(shù)選項可以通過函數(shù)optimsetoptimset創(chuàng)建或修改創(chuàng)建或修改. .命令的命令的格式如下：格式如下：(1) options=optimset(optimfun) 創(chuàng)建一個含有所有參數(shù)名,并與優(yōu)化函數(shù)optimfun相關(guān)的默認(rèn)值的選項結(jié)構(gòu).（2）options=optimset(param1,value1,param2,value2,.) 創(chuàng)建一個名稱為選項的優(yōu)化選項參數(shù),其中指定的參數(shù)具有指定值,所有未指定的參數(shù)取默認(rèn)值.

42、(3) options=optimset(oldops, param1,value1,param2,value2,.) 創(chuàng)建名稱為oldops的參數(shù)的拷貝,用指定的參數(shù)值修改oldops中相應(yīng)的參數(shù).返回整理課件用用MATLAB解無約束優(yōu)化問題解無約束優(yōu)化問題 其中等式（其中等式（3 3）、（）、（4 4）、（）、（5 5）的右邊可選用（）的右邊可選用（1 1）或（）或（2 2）的等式右邊的等式右邊. . 函數(shù)函數(shù)fminbndfminbnd的算法基于黃金分割法和二次插值法，它要求的算法基于黃金分割法和二次插值法，它要求目標(biāo)函數(shù)必須是連續(xù)函數(shù)，并可能只給出局部最優(yōu)解目標(biāo)函數(shù)必須是連續(xù)函數(shù)，并可

43、能只給出局部最優(yōu)解. . 常用格式如下：常用格式如下：（1）x= fminbnd (fun,x1,x2)（2）x= fminbnd (fun,x1,x2 ，options)（3）x，fval= fminbnd（）（4）x，fval，exitflag= fminbnd（）（5）x，fval，exitflag，output= fminbnd（）整理課件MATLAB(wliti1) 主程序為主程序為wliti1.m: f=2*exp(-x).*sin(x); fplot(f,0,8); %作圖語句作圖語句 xmin,ymin=fminbnd (f, 0,8) f1=-2*exp(-x).*sin (

44、x); xmax,ymax=fminbnd (f1, 0,8)整理課件例例2 2 有邊長為有邊長為3 3m的正方形鐵板，在四個角剪去相等的正方形以的正方形鐵板，在四個角剪去相等的正方形以制成方形無蓋水槽，問如何剪法使水槽的容積最大？制成方形無蓋水槽，問如何剪法使水槽的容積最大？解解先編寫先編寫M文件如下文件如下: : function f=fun0(x) f=-(3-2*x).2*x;主程序為主程序為wliti2.m: x,fval=fminbnd(fun0,0,1.5); xmax=x fmax=-fval運算結(jié)果為運算結(jié)果為: xmax = 0.5000, = 0.5000,fmaxm時水

45、槽的容積最大時水槽的容積最大, ,最大最大容積為容積為2 2m3. .MATLAB(wliti2)整理課件 命令格式為命令格式為: :（1）x= fminunc（fun,X0 ）；或x=fminsearch（fun,X0 ）（2）x= fminunc（fun,X0 ，options）； 或x=fminsearch（fun,X0 ，options）（3）x，fval= fminunc（.）； 或x，fval= fminsearch（.）（4）x，fval，exitflag= fminunc（.）； 或x，fval，exitflag= fminsearch（5）x，fval，exitflag，ou

46、tput= fminunc（.）； 或x，fval，exitflag，output= fminsearch（.） 2.多元函數(shù)無約束優(yōu)化問題多元函數(shù)無約束優(yōu)化問題標(biāo)準(zhǔn)型為：標(biāo)準(zhǔn)型為：min()F X整理課件3 fminunc為中型優(yōu)化算法的步長一維搜索提供了兩種算法，由選項中參數(shù)LineSearchType控制： LineSearchType=quadcubic (缺省值)，混合的二次和三次多項式插值； LineSearchType=cubicpoly，三次多項式插使用使用fminunc和和 fminsearch可能會得到局部最優(yōu)解可能會得到局部最優(yōu)解. .說明說明: :fminsearch是

47、用單純形法尋優(yōu)是用單純形法尋優(yōu).fminunc算法見以下幾點說明：算法見以下幾點說明：1 fminunc為無約束優(yōu)化提供了大型優(yōu)化和中型優(yōu)化算法.由選項中的參數(shù)LargeScale控制：LargeScale=on (默認(rèn)值默認(rèn)值),使用大型算法使用大型算法LargeScale=off (默認(rèn)值默認(rèn)值),使用中型算法使用中型算法2 fminunc為中型優(yōu)化算法的搜索方向提供了4種算法，由 選項中的參數(shù)選項中的參數(shù)HessUpdate控制：控制： HessUpdate=bfgs（默認(rèn)值），擬牛頓法的（默認(rèn)值），擬牛頓法的BFGS公式；公式；HessUpdate=dfp，擬牛頓法的，擬牛頓法的DFP

48、公式；公式；HessUpdate=steepdesc，最速下降法，最速下降法整理課件例例3 3 minMATLAB(wliti3)M文件文件: :function f = fun1 (x)f = exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1); M文件如下文件如下: : x0 = -1, 1; x=fminunc(fun1,x0); y=fun1(x) 3. 3.運行結(jié)果運行結(jié)果: : 12212122( )(42421) exf xxxx xx整理課件非線性規(guī)劃非線性規(guī)劃 返回返回整理課件 定義定義 如果目標(biāo)函數(shù)或約束條件中至少有一個是非線性函

49、數(shù),則最優(yōu)化問題就叫做非線性規(guī)劃問題非線性規(guī)劃問題非現(xiàn)性規(guī)劃的基本概念非現(xiàn)性規(guī)劃的基本概念 一般形式一般形式: （1） 其中 ， 是定義在 R Rn 上的實值函數(shù)，簡記: Xfmin jihgf, 其它情況其它情況: 求目標(biāo)函數(shù)的最大值，或約束條件小于等于零兩種情況，都可通過取其相反數(shù)化為上述一般形式1nj1ni1nR :h ,R :g ,R :RRRfnTnRxxxX,21 .,.,2 , 1 0 m;1,2,., 0. . ljXhiXgtsji整理課件 定義定義1 1 把滿足問題（1）中條件的解 稱為可行解可行解（或可行（或可行點點），），所有可行點的集合稱為可行集可行集（或（或可行域可

50、行域）記為D即 問題(1)可簡記為 XfDXmin定義定義2 2 對于問題(1),設(shè) ,若存在 ,使得對一切 ,且 ,都有 ,則稱X*是f(X)在D上的局部極小值點局部極小值點（局部最優(yōu)解局部最優(yōu)解）特別地,當(dāng) 時，若 ,則稱X*是f(X)在D上的嚴(yán)格局部極小值點嚴(yán)格局部極小值點（嚴(yán)格局部最嚴(yán)格局部最優(yōu)解優(yōu)解）DX *0DX *XX*XX XfXf* XfXf*定義定義3 3 對于問題(1),設(shè) ,若對任意的 ,都有則稱X*是f(X)在D上的全局極小值點全局極小值點（全局最優(yōu)解全局最優(yōu)解）特別地,當(dāng) 時，若 ,則稱X*是f(X)在D上的嚴(yán)格全局極小值嚴(yán)格全局極小值點點（嚴(yán)格全局最優(yōu)解嚴(yán)格全局最

51、優(yōu)解）DX *DX *XX XfXf* 返回返回)(nRX njiRXXhXg XD , 0, 0| ,Xf Xf *整理課件非線性規(guī)劃的基本解法非線性規(guī)劃的基本解法 返回返回整理課件MATLAB 優(yōu)化工具箱解非線性規(guī)劃優(yōu)化工具箱解非線性規(guī)劃整理課件 用MATLAB軟件求解,其輸入格式輸入格式如下: 1x=quadprog(H,C,A,b); 2x=quadprog(H,C,A,b,Aeq,beq); 3x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB); 4x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0); 5x=quadprog(H,C,

52、A,b,Aeq,beq,VLB,VUB,X0,options); 6x,fval=quaprog(); 7x,fval,exitflag=quaprog(); 8x,fval,exitflag,output=quaprog();1二次規(guī)劃二次規(guī)劃整理課件例例1 1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t. x1+x22 -x1+2x22 x10, x20 MATLAB（youh1）1寫成標(biāo)準(zhǔn)形式寫成標(biāo)準(zhǔn)形式： 2輸入命令輸入命令： H=1 -1; -1 2; c=-2 ;-6;A=2 -2; -2 4;b=2;2; Aeq=;beq=; VLB=0;0

53、;VUB=; x,z=quadprog(H,c,A,b,Aeq,beq,VLB,VUB)3運算結(jié)果運算結(jié)果為： T111222 2 -221min( , )2 462xxzx xxx 1212 1 121 2200 xxxxs.t.整理課件 1 首先建立M文件fun.m,用來定義目標(biāo)函數(shù)F（X）:function f=fun(X);f=F(X);2一般非線性規(guī)劃一般非線性規(guī)劃 其中X為n維變元向量，G(X)與Ceq(X)均為非線性函數(shù)組成的向量，其他變量的含義與線性規(guī)劃、二次規(guī)劃中相同用MATLAB求解上述問題，基本步驟分三步：整理課件3 建立主程序.求解非線性規(guī)劃的函數(shù)是fmincon,命令

54、的基本格式如下： (1) x=fmincon(fun,X0,A,b) (2) x=fmincon(fun,X0,A,b,Aeq,beq) (3) x=fmincon(fun,X0,A,b, Aeq,beq,VLB,VUB) (4) x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon)(5)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon,options) (6) x,fval= fmincon() (7) x,fval,exitflag= fmincon() (8)x,fval,exitflag,output= fm

55、incon()輸出極值點M文件迭代的初值參數(shù)說明變量上下限整理課件注意：注意：1 fmincon函數(shù)提供了大型優(yōu)化算法和中型優(yōu)化算法默認(rèn)時: 若在fun函數(shù)中提供了梯度（options參數(shù)的GradObj設(shè)置為on），并且只有上下界存在或只有等式約束，fmincon函數(shù)將選擇大型算法當(dāng)既有等式約束又有梯度約束時，使用中型算法2 fmincon函數(shù)的中型算法使用的是序列二次規(guī)劃法在每一步迭代中求解二次規(guī)劃子問題，并用BFGS法更新拉格朗日Hesse矩陣3 fmincon函數(shù)可能會給出局部最優(yōu)解，這與初值X0的選取有關(guān)整理課件1寫成標(biāo)準(zhǔn)形式寫成標(biāo)準(zhǔn)形式： s.t. 00546322121xxxx2

56、100 xx22212121212minxxxxf22212121212minxxxxf 2x1+3x2 6 s.t. x1+4x2 5 x1,x2 0例例2整理課件2先建立先建立M-文件文件 fun3m: function f=fun3(x); f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)2MATLAB(youh2)3再建立主程序youh2m： x0=1;1; A=2 3 ;1 4; b=6;5; Aeq=;beq=; VLB=0;0; VUB=; x,fval=fmincon(fun3,x0,A,b,Aeq,beq,VLB,VUB)4運算結(jié)果為：運算結(jié)果為：

57、x = 07647 10588 fval = -20294整理課件1 1先建立先建立M文件文件fun4m定義目標(biāo)函數(shù)定義目標(biāo)函數(shù): function f=fun4(x); f=exp(x(1) *(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);12212122( )e (42421)xf xxxx xx x1+x2=0 s.t. 1.5+x1x2 - x1 - x2 0 -x1x2 10 0例例3 2再建立再建立M文件文件myconm定義非線性約束：定義非線性約束： function g,ceq=mycon(x) g=x(1)+x(2);15+x(1)*x(2)-

58、x(1)-x(2); -x(1)*x(2)-10;整理課件3主程序主程序youh3m為為:x0=-1;1;A=;b=;Aeq=1 1;beq=0;vlb=;vub=;x,fval=fmincon(fun4,x0,A,b,Aeq,beq,vlb, vub,mycon)MATLAB(youh3)4 運算結(jié)果為運算結(jié)果為： x = -12250 12250 fval = 18951整理課件 例4 12221122221212 min2s.t. 250 70 05, 010fXxxgXxxgXxxxx 1先建立先建立M文件文件funm定義目標(biāo)函數(shù)定義目標(biāo)函數(shù): function f=fun(x); f=-2*x(1)-x(2);2再建立再建立M文件文件mycon2m定義非線性約束：定義非線性約束：function g,ceq=mycon2(x)g=x(1)2+x(2)2-25;x(1)2-x(2)2-7;整理課件3 主程序主程序fxxm為為: x0=3;25; VLB=0 0;VUB=5 10; x,fval,exitflag,output =fmincon(fun,x0, VLB,VUB,mycon2)MATLAB(fxx(fun)整理課件4 運算結(jié)果為運算結(jié)果為: x = 40000 30000fval =-110000exitfla