-【大學(xué)課件】動(dòng)態(tài)規(guī)劃方法簡(jiǎn)介P88-PPT

1、 動(dòng)態(tài)規(guī)劃方法簡(jiǎn)介 動(dòng)態(tài)規(guī)劃是解決多階段決策過(guò)程最優(yōu)化問(wèn)題的一種方法。由美國(guó)數(shù)學(xué)家貝爾曼（Ballman）等人在20世紀(jì)50年代提出。他們針對(duì)多階段決策問(wèn)題的特點(diǎn)，提出了解決這類(lèi)問(wèn)題的“最優(yōu)化原理”，并成功地解決了生產(chǎn)管理 、 工程技術(shù)等方面的許多實(shí)際問(wèn)題。docin/sundae_meng 動(dòng)態(tài)規(guī)劃是現(xiàn)代企業(yè)管理中的一種重要決策方法，可用于最優(yōu)路徑問(wèn)題、資源分配問(wèn)題、生產(chǎn)計(jì)劃和庫(kù)存問(wèn)題、投資問(wèn)題、裝載問(wèn)題、排序問(wèn)題及生產(chǎn)過(guò)程的最優(yōu)控制等。docin/sundae_meng 一.多階段決策過(guò)程最優(yōu)化 多階段決策過(guò)程是指這樣一類(lèi)特殊的活動(dòng)過(guò)程，他們可以按時(shí)間順序分解成若干相互聯(lián)系的階段，在每個(gè)階

2、段都要做出決策，全部過(guò)程的決策是一個(gè)決策序列，所以多階段決策問(wèn)題也稱(chēng)為序貫決策問(wèn)題。動(dòng)態(tài)規(guī)劃的基本原理docin/sundae_meng12n狀態(tài)決策狀態(tài)決策狀態(tài)狀態(tài)決策圖示 多階段決策問(wèn)題，不論其本身是否與時(shí)間有關(guān)，由于分為階段依次解決，這便具有明顯的時(shí)序性，而在各階段中所采取的決策是隨階段而變動(dòng)的，不同階段采取不同決策，這便是動(dòng)態(tài)的含義.階段往往可以用時(shí)段來(lái)表示，但動(dòng)態(tài)規(guī)劃在一定條件下也可以解決一些與時(shí)間無(wú)關(guān)的靜態(tài)最優(yōu)化問(wèn)題，只要人為地引入“時(shí)段”因素，就可以將其轉(zhuǎn)化為一個(gè)多階段決策問(wèn)題。docin/sundae_meng 動(dòng)態(tài)規(guī)劃是用來(lái)解決多階段決策過(guò)程最優(yōu)化的一種數(shù)量方法。其特點(diǎn)在于，

3、它可以把一個(gè)n 維決策問(wèn)題變換為幾個(gè)一維最優(yōu)化問(wèn)題，從而一個(gè)一個(gè)地去解決。 需指出：動(dòng)態(tài)規(guī)劃是求解某類(lèi)問(wèn)題的一種方法，是考察問(wèn)題的一種途徑，而不是一種算法。必須對(duì)具體問(wèn)題進(jìn)行具體分析，運(yùn)用動(dòng)態(tài)規(guī)劃的原理和方法，建立相應(yīng)的模型，然后再用動(dòng)態(tài)規(guī)劃方法去求解。docin/sundae_meng二、多階段決策問(wèn)題舉例1)工廠(chǎng)生產(chǎn)過(guò)程：由于市場(chǎng)需求是一隨著時(shí)間而變化的因素，因此，為了取得全年最佳經(jīng)濟(jì)效益，就要在全年的生產(chǎn)過(guò)程中，逐月或者逐季度地根據(jù)庫(kù)存和需求情況決定生產(chǎn)計(jì)劃安排。docin/sundae_meng 2)設(shè)備更新問(wèn)題：一般企業(yè)用于生產(chǎn)活動(dòng)的設(shè)備，剛買(mǎi)來(lái)時(shí)故障少，經(jīng)濟(jì)效益高，即使進(jìn)行轉(zhuǎn)讓?zhuān)?/p>

4、理價(jià)值也高，隨著使用年限的增加，就會(huì)逐漸變?yōu)楣收隙?，維修費(fèi)用增加，可正常使用的工時(shí)減少，加工質(zhì)量下降，經(jīng)濟(jì)效益差，并且，使用的年限越長(zhǎng)、處理價(jià)值也越低，自然，如果賣(mài)去舊的買(mǎi)新的，還需要付出更新費(fèi)因此就需要綜合權(quán)衡決定設(shè)備的使用年限，使總的經(jīng)濟(jì)效益最好。docin/sundae_meng3)連續(xù)生產(chǎn)過(guò)程的控制問(wèn)題：一般化工生產(chǎn)過(guò)程中，常包含一系列完成生產(chǎn)過(guò)程的設(shè)備，前一工序設(shè)備的輸出則是后一工序設(shè)備的輸入，因此，應(yīng)該如何根據(jù)各工序的運(yùn)行工況，控制生產(chǎn)過(guò)程中各設(shè)備的輸入和輸出，以使總產(chǎn)量最大。docin/sundae_mengdocin/sundae_meng4)運(yùn)輸網(wǎng)絡(luò)問(wèn)題（最短路問(wèn)題）：如圖1

5、所示的運(yùn)輸網(wǎng)絡(luò)，點(diǎn)間連線(xiàn)上的數(shù)字表示兩地距離(也可是運(yùn)費(fèi)、時(shí)間等)，要求從v1至v10的最短路線(xiàn)。 這種運(yùn)輸網(wǎng)絡(luò)問(wèn)題也是靜態(tài)決策問(wèn)題。但是，按照網(wǎng)絡(luò)中點(diǎn)的分布，可以把它分為4個(gè)階段，而作為多階段決策問(wèn)題來(lái)研究。docin/sundae_meng 以上所舉問(wèn)題的發(fā)展過(guò)程都與時(shí)間因素有關(guān)，階段的劃分常取時(shí)間區(qū)段來(lái)表示，并且各個(gè)階段上的決策往往也與時(shí)間因素有關(guān)，這就使它具有了“動(dòng)態(tài)”的含義，所以把處理這類(lèi)動(dòng)態(tài)問(wèn)題的方法稱(chēng)為動(dòng)態(tài)規(guī)劃方法。不過(guò)，實(shí)際中尚有許多不包含時(shí)間因素的一類(lèi)“靜態(tài)”決策問(wèn)題，就其本質(zhì)而言是一次決策問(wèn)題，是非動(dòng)態(tài)決策問(wèn)題，但是也可以人為地引入階段的概念當(dāng)作多階段決策問(wèn)題，應(yīng)用動(dòng)態(tài)規(guī)劃

6、方法加以解決。docin/sundae_meng 三、動(dòng)態(tài)規(guī)劃方法導(dǎo)引 例1：為了說(shuō)明動(dòng)態(tài)規(guī)劃的基本思想方法和特點(diǎn)，下面以圖1所示為例討論的求最短路問(wèn)題的方法。 第一種方法稱(chēng)做全枚舉法或窮舉法。它的基本思想是列舉出所有可能發(fā)生的方案和結(jié)果，再對(duì)它們一一進(jìn)行比較，求出最優(yōu)方案。這里從v1到v10的路程可以分為4個(gè)階段。第一段的走法有三種，第二三兩段的走法各有兩種，第四段的走法僅一種，因此共有322112條可能的路線(xiàn)，分別算出各條路線(xiàn)的距離，最后進(jìn)行比較，可知最優(yōu)路線(xiàn)是v1 v3 v7 v9 v10 ,最短距離是18docin/sundae_meng 顯然，當(dāng)組成交通網(wǎng)絡(luò)的節(jié)點(diǎn)很多時(shí)，用窮舉法求最

7、優(yōu)路線(xiàn)的計(jì)算工作量將會(huì)十分龐大，而且其中包含著許多重復(fù)計(jì)算 第二種方法即所謂“局部最優(yōu)路徑”法，是說(shuō)某人從k出發(fā)，他并不顧及全線(xiàn)是否最短，只是選擇當(dāng)前最短途徑，“逢近便走”，錯(cuò)誤地以為局部最優(yōu)會(huì)致整體最優(yōu)，在這種想法指導(dǎo)下，所取決策必是v1 v3 v5 v8 v10 ，全程長(zhǎng)度是20；顯然，這種方法的結(jié)果常是錯(cuò)誤的docin/sundae_meng 第三種方法是動(dòng)態(tài)規(guī)劃方法。動(dòng)態(tài)規(guī)劃方法尋求該最短路問(wèn)題的基本思想是，首先將問(wèn)題劃分為4個(gè)階段，每次的選擇總是綜合后繼過(guò)程的一并最優(yōu)進(jìn)行考慮，在各段所有可能狀態(tài)的最優(yōu)后繼過(guò)程都已求得的情況下，全程的最優(yōu)路線(xiàn)便也隨之得到。 為了找出所有可能狀態(tài)的最優(yōu)后

8、繼過(guò)程，動(dòng)態(tài)規(guī)劃方法總是從過(guò)程的最后階段開(kāi)始考慮，然后逆著實(shí)際過(guò)程發(fā)展的順序，逐段向前遞推計(jì)算直至始點(diǎn)。docin/sundae_meng 具體說(shuō)，此問(wèn)題先從v10開(kāi)始，因?yàn)関10是終點(diǎn)。再無(wú)后繼過(guò)程，故可以接著考慮第4階段上所有可能狀態(tài)v8 ,v9的最優(yōu)后續(xù)過(guò)程因?yàn)閺膙8 ,v9 到v10的路線(xiàn)是唯一的，所以v8 ,v9 的最優(yōu)決策和最優(yōu)后繼過(guò)程就是到v10 ，它們的最短距離分別是5和3。 接著考慮階段3上可能的狀態(tài)v5 ,v6 , v7 , 到v10的最優(yōu)決策和最優(yōu)后繼過(guò)程在狀態(tài)V5上，雖然到v8是8，到v9是9，但是綜合考慮后繼過(guò)程整體最優(yōu)，取最優(yōu)決策是到v9,最優(yōu)后繼過(guò)程是v5v9 v

9、10 ，最短距離是12同理，狀態(tài)v6的最優(yōu)決策是至v8 ；v7的最優(yōu)決策是到v9 。docin/sundae_meng 同樣，當(dāng)階段3上所有可能狀態(tài)的最優(yōu)后繼過(guò)程都已求得后，便可以開(kāi)始考慮階段2上所有可能狀態(tài)的最優(yōu)決策和最優(yōu)后繼過(guò)程，如v2的最優(yōu)決策是到v5,最優(yōu)路線(xiàn)是v2v5v9v10 ，最短距離是15依此類(lèi)推，最后可以得到從初始狀態(tài)v1的最優(yōu)決策是到v3最優(yōu)路線(xiàn)是v1v3v7v9v10 ，全程的最短距離是18。圖51中粗實(shí)線(xiàn)表示各點(diǎn)到v10的最優(yōu)路線(xiàn)，每點(diǎn)上方括號(hào)內(nèi)的數(shù)字表示該點(diǎn)到終點(diǎn)的最短路距離。docin/sundae_meng 綜上所述可見(jiàn)，全枚舉法雖可找出最優(yōu)方案，但不是個(gè)好算法，

10、局部最優(yōu)法則完全是個(gè)錯(cuò)誤方法，只有動(dòng)態(tài)規(guī)劃方法屬較科學(xué)有效的算法。它的基本思想是，把一個(gè)比較復(fù)雜的問(wèn)題分解為一系列同類(lèi)型的更易求解的子問(wèn)題，便于應(yīng)用計(jì)算機(jī)。整個(gè)求解過(guò)程分為兩個(gè)階段，先按整體最優(yōu)的思想逆序地求出各個(gè)子問(wèn)題中所有可能狀態(tài)的最優(yōu)決策與最優(yōu)路線(xiàn)值，然后再順序地求出整個(gè)問(wèn)題的最優(yōu)策略和最優(yōu)路線(xiàn)。計(jì)算過(guò)程中，系統(tǒng)地刪去了所有中間非最優(yōu)的方案組合，從而使計(jì)算工作量比窮舉法大為減少。docin/sundae_meng四、動(dòng)態(tài)規(guī)劃的基本概念與基本方程 使用動(dòng)態(tài)規(guī)劃方法解決多階段決策問(wèn)題，首先要將實(shí)際問(wèn)題寫(xiě)成動(dòng)態(tài)規(guī)劃模型，同時(shí)也為了今后敘述和討論方便，這里需要對(duì)動(dòng)態(tài)規(guī)劃的下述一些基本術(shù)語(yǔ)進(jìn)一步加

11、以說(shuō)明和定義： docin/sundae_meng (一) 階段 為了便于求解和表示決策及過(guò)程的發(fā)展順序，而把所給問(wèn)題恰當(dāng)?shù)貏澐譃槿舾蓚€(gè)相互聯(lián)系又有區(qū)別的子問(wèn)題，稱(chēng)之為多段決策問(wèn)題的階段。一個(gè)階段，就是需要作出一個(gè)決策的子問(wèn)題，通常，階段是按決策進(jìn)行的時(shí)間或空間上先后順序劃分的。用以描述階段的變量叫作階段變量，一般以k表示階段變量階段數(shù)等于多段決策過(guò)程從開(kāi)始到結(jié)束所需作出決策的數(shù)目，圖1所示的最短路問(wèn)題就是一個(gè)四階段決策過(guò)程， 。docin/sundae_meng （二）狀態(tài) 1.狀態(tài)與狀態(tài)變量。用以描述事物(或系統(tǒng))在某特定的時(shí)間與空間域中所處位置及運(yùn)動(dòng)特征的量，稱(chēng)為狀態(tài)。反映狀態(tài)變化的量叫

12、做狀態(tài)變量。狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息。按照過(guò)程進(jìn)行的先后，每個(gè)階段的狀態(tài)可分為初始狀態(tài)和終止?fàn)顟B(tài)，或稱(chēng)輸入狀態(tài)和輸出狀態(tài)，階段k的初始狀態(tài)記作sk，終止?fàn)顟B(tài)記為sk+1。但為了清楚起見(jiàn)，通常定義階段的狀態(tài)即指其初始狀態(tài)。狀態(tài)應(yīng)描述過(guò)程特征;能直接或間接觀(guān)測(cè);具有無(wú)后效性. 某階段的狀態(tài)給定后，則過(guò)程未來(lái)發(fā)展不受該階段以前各階段狀態(tài)的影響docin/sundae_meng 2可能狀態(tài)集 一般狀態(tài)變量的取值有一定的范圍或允許集合，稱(chēng)為可能狀態(tài)集，或可達(dá)狀態(tài)集。通?？赡軤顟B(tài)集用相應(yīng)階段狀態(tài)sk的大寫(xiě)字母Sk表示，skSk，可能狀態(tài)集可以是一離散取值的集合，也可以為一

13、連續(xù)的取值區(qū)間在圖1所示的最短路問(wèn)題中，第一階段狀態(tài)為v1，狀態(tài)變量s1的狀態(tài)集合S1=v1；第二階段則有三個(gè)狀態(tài)：v2 ,v3 ,v4 ,狀態(tài)變量s2的狀態(tài)集合S2=v2 ,v3 ,v4 ；第三階段也有三個(gè)狀態(tài):v5 ,v6 ,v7 ，狀態(tài)變量s3的狀態(tài)集合S3=v5 ,v6 ,v7 ；第四階段則有二個(gè)狀態(tài)： v8 ,v9 , 狀態(tài)變量s4的狀態(tài)集合S4=v8 ,v9 ；docin/sundae_meng （三）決策 所謂決策，就是確定系統(tǒng)過(guò)程發(fā)展的方案。決策的實(shí)質(zhì)是關(guān)于狀態(tài)的選擇，是決策者從給定階段狀態(tài)出發(fā)對(duì)下一階段狀態(tài)作出的選擇。 用以描述決策變化的量稱(chēng)之決策變量，和狀態(tài)變量一樣，決策變

14、量可以用一個(gè)數(shù)，一組數(shù)或一向量來(lái)描述，也可以是狀態(tài)變量的函數(shù)，記以u(píng)k= uk(sk)，表示于階段k狀態(tài)sk時(shí)的決策變量。 決策變量的取值往往也有一定的允許范圍，稱(chēng)之允許決策集合。決策變量uk(sk)的允許決策集用Uk(sk)表示, uk(sk) Uk(sk)允許決策集合實(shí)際是決策的約束條件。docin/sundae_meng （四）狀態(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)過(guò)去的狀態(tài)s1,s2, ,sk-1及其決

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

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

17、 不僅跟當(dāng)前狀態(tài)sk有關(guān)，還跟該子過(guò)程策略pk,n(sk)有關(guān)，表示為:docin/sundae_meng 適于用動(dòng)態(tài)規(guī)劃求解的問(wèn)題的過(guò)程指標(biāo)函數(shù)（即目標(biāo)函數(shù)），必須具有關(guān)于階段指標(biāo)的可分離形式對(duì)于部子過(guò)程的指標(biāo)函數(shù)可以表示為： (2)多階段決策問(wèn)題中，常見(jiàn)的目標(biāo)函數(shù)形式之一是取各階段效應(yīng)之和的形式，即:docin/sundae_meng (七) 最優(yōu)解 用fk(sk)表示第k子過(guò)程指標(biāo)函數(shù)在狀態(tài)sk下的最優(yōu)值,即 相應(yīng)的子策略稱(chēng)為sk狀態(tài)下的最優(yōu)子策略，記為pk,n*(sk) ；而構(gòu)成該子策賂的各段決策稱(chēng)為該過(guò)程上的最優(yōu)決策，記為 ；有 docin/sundae_meng 最優(yōu)化原理 （貝爾

18、曼最優(yōu)化原理） 作為一個(gè)全過(guò)程的最優(yōu)策略具有這樣的性質(zhì)：對(duì)于最優(yōu)策略過(guò)程中的任意狀態(tài)而言，無(wú)論其過(guò)去的狀態(tài)和決策如何，余下的諸決策必構(gòu)成一個(gè)最優(yōu)子策略。該原理的具體解釋是，若某一全過(guò)程最優(yōu)策略為： 則對(duì)上述策略中所隱含的任一狀態(tài)而言， 第k子過(guò)程上對(duì)應(yīng)于該狀態(tài)的最優(yōu)策略必然 包含在上述全過(guò)程最優(yōu)策略p1*中，即為(八) 動(dòng)態(tài)規(guī)劃的最優(yōu)性原理docin/sundae_meng(九)動(dòng)態(tài)規(guī)劃的基本方程 基于上述原理，提出了一種逆序遞推法；該法的關(guān)鍵在于給出一種遞推關(guān)系。一般把這種遞推關(guān)系稱(chēng)為動(dòng)態(tài)規(guī)劃的函數(shù)基本方程。 當(dāng)過(guò)程指標(biāo)函數(shù)為下列“和”的形式時(shí)，相應(yīng)的函數(shù)基本方程為docin/sundae_

19、meng（三）、建立動(dòng)態(tài)規(guī)劃模型的步驟 1、劃分階段劃分階段是運(yùn)用動(dòng)態(tài)規(guī)劃求解多階段決策問(wèn)題的第一步，在確定多階段特性后，按時(shí)間或空間先后順序，將過(guò)程劃分為若干相互聯(lián)系的階段。對(duì)于靜態(tài)問(wèn)題要人為地賦予“時(shí)間”概念，以便劃分階段。 2、正確選擇狀態(tài)變量選擇變量既要能確切描述過(guò)程演變又要滿(mǎn)足無(wú)后效性，而且各階段狀態(tài)變量的取值能夠確定。一般地，狀態(tài)變量的選擇是從過(guò)程演變的特點(diǎn)中尋找。 3、確定決策變量及允許決策集合通常選擇所求解問(wèn)題的關(guān)鍵變量作為決策變量，同時(shí)要給出決策變量的取值范圍，即確定允許決策集合。docin/sundae_meng 4、確定狀態(tài)轉(zhuǎn)移方程根據(jù)k 階段狀態(tài)變量和決策變量，寫(xiě)出k+

20、1階段狀態(tài)變量，狀態(tài)轉(zhuǎn)移方程應(yīng)當(dāng)具有遞推關(guān)系。 5、確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)，建立動(dòng)態(tài)規(guī)劃基本方程 階段指標(biāo)函數(shù)是指第k 階段的收益，最優(yōu)指標(biāo)函數(shù)是指從第k 階段狀態(tài)出發(fā)到第n 階段末所獲得收益的最優(yōu)值，最后寫(xiě)出動(dòng)態(tài)規(guī)劃基本方程。 以上五步是建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型的一般步驟。由于動(dòng)態(tài)規(guī)劃模型與線(xiàn)性規(guī)劃模型不同，動(dòng)態(tài)規(guī)劃模型沒(méi)有統(tǒng)一的模式，建模時(shí)必須根據(jù)具體問(wèn)題具體分析，只有通過(guò)不斷實(shí)踐總結(jié)，才能較好掌握建模方法與技巧。 docin/sundae_meng例一、從A 地到D 地要鋪設(shè)一條煤氣管道,其中需經(jīng)過(guò)兩級(jí)中間站，兩點(diǎn)之間的連線(xiàn)上的數(shù)字表示距離，如圖所示。問(wèn)應(yīng)該選擇什么路線(xiàn)，使總距離最短

21、？ AB1B2C1C2C3D24333321114五、建模舉例：最短路徑問(wèn)題docin/sundae_meng 解：整個(gè)計(jì)算過(guò)程分三個(gè)階段，從最后一個(gè)階段開(kāi)始。 第一階段（C D）： C 有三條路線(xiàn)到終點(diǎn)D 。 AB1B2C1C2C3D24333321114DC1C2C3顯然有 f1 (C1 ) = 1 ； f1(C2 ) = 3 ； f1 (C3 ) = 4 docin/sundae_meng 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

22、4 = min 6 = 4 5第二階段（B C）： B 到C 有六條路線(xiàn)。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線(xiàn)為B1C1 D)docin/sundae_meng 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(最短路線(xiàn)為B2C1 D)docin/sundae_meng第三階段（ A B ）： A 到B 有

23、二條路線(xiàn)。 f3(A)1 = d(A, B1 ) 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 )(最短路線(xiàn)為AB1C1 D)AB1B2C1C2C3D24333321114DC1C2C3B1B2Adocin/sundae_mengAB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路線(xiàn)為 AB1C1 D 路長(zhǎng)為 6docin/sundae_mengSETS:CITIES/1.7/:F;ROADS(CITI

24、ES,CITIES)/1, 2 1, 32, 4 2, 5 2, 63, 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程序docin/sundae_meng Feasible solution found. Total solver iterations: 0 Variable Value F( 1) 6.00000

25、0 F( 2) 4.000000 F( 3) 3.000000 F( 4) 1.000000 F( 5) 3.000000 F( 6) 4.000000 F( 7) 0.000000 D( 1, 2) 2.000000 D( 1, 3) 4.000000 D( 2, 4) 3.000000 D( 2, 5) 3.000000 D( 2, 6) 1.000000 D( 3, 4) 2.000000 D( 3, 5) 3.000000 D( 3, 6) 1.000000 D( 4, 7) 1.000000 D( 5, 7) 3.000000 D( 6, 7) 4.000000 Row Slack

26、or Surplus 1 0.000000 2 0.000000 3 0.000000 4 0.000000 5 0.000000 6 0.000000 7 0.000000運(yùn)行結(jié)果docin/sundae_meng練習(xí)1：AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664最優(yōu)路線(xiàn)為：A B1 C2 D1 E2 F2 G 路長(zhǎng)18求從A到G的最短路徑3docin/sundae_meng 有資金4萬(wàn)元，投資A、B、C三個(gè)項(xiàng)目，每個(gè)項(xiàng)目的投資效益與投入該項(xiàng)目的資金有關(guān)。三個(gè)項(xiàng)目A、B、C的投資效益（萬(wàn)噸）和投入資金（萬(wàn)元）關(guān)系見(jiàn)下

27、表：求對(duì)三個(gè)項(xiàng)目的最優(yōu)投資分配，使總投資效益最大。練習(xí)2docin/sundae_meng階段k：每投資一個(gè)項(xiàng)目作為一個(gè)階段；狀態(tài)變量xk：投資第k個(gè)項(xiàng)目前的資金數(shù)；決策變量dk：第k個(gè)項(xiàng)目的投資；決策允許集合：0dkxk狀態(tài)轉(zhuǎn)移方程：xk+1=xk-dk階段指標(biāo)：vk(xk ,dk)見(jiàn)表中所示；遞推方程：fk(xk)=maxvk(xk ,dk)+fk+1(xk+1)終端條件：f4(x4)=0docin/sundae_mengk=4，f4(x4)=0k=3，0d3x3，x4=x3-d3docin/sundae_mengk=2，0d2x2，x3=x2-d2docin/sundae_mengk=1

28、，0d1x1，x2=x1-d1docin/sundae_meng無(wú)約束最優(yōu)化問(wèn)題標(biāo)準(zhǔn)形式：例：選址問(wèn)題 某市燃?xì)夤居?jì)劃要建一個(gè)煤氣供應(yīng)站，該站要向城市中有固定位置的m 個(gè)用戶(hù)供貨.對(duì)于選定的坐標(biāo)系而言，已知第i 個(gè)用戶(hù)的位置為如果只考慮直線(xiàn)距離，如何確定這個(gè)煤氣站的位置，才能使總的運(yùn)輸距離最短？docin/sundae_meng解：設(shè)煤氣站的位置為則第i 個(gè)用戶(hù)到該站的直線(xiàn)距離為故 m 個(gè)用戶(hù)到該站的總距離為故選址問(wèn)題可以歸結(jié)為求變量使得docin/sundae_meng無(wú)約束優(yōu)化問(wèn)題的解法1.如果可微，則利用 求其駐點(diǎn)，然后利用充分條件判別這些駐點(diǎn)是否是極值點(diǎn)。.2. 搜索算法（迭代算法）

29、基本思想：首先給定目標(biāo)函數(shù) 的極小點(diǎn)的一個(gè)初始估計(jì)點(diǎn) 然后按照一定的規(guī)則產(chǎn)生一個(gè)點(diǎn)列 ，希望這種點(diǎn)列的極限是的一個(gè)極小點(diǎn) .需要給定初始點(diǎn)docin/sundae_meng常見(jiàn)的算法： 梯度法（最速下降法）2. 牛頓法 3.共軛梯度法用MATLAB優(yōu)化工具箱求解無(wú)約束最優(yōu)化計(jì)算機(jī)實(shí)現(xiàn) 前面我們介紹了Matlab 工具箱中函數(shù)用linprog解線(xiàn)性規(guī)劃的方法，Matlab優(yōu)化工具箱還提供了一般無(wú)約束優(yōu)化與約束優(yōu)化的求解問(wèn)題，下面介紹Matlab優(yōu)化工具箱的主要函數(shù)。docin/sundae_mengMATLAB優(yōu)化工具箱簡(jiǎn)介1.MATLAB求解優(yōu)化問(wèn)題的主要函數(shù)docin/sundae_meng

30、2.優(yōu)化函數(shù)的輸入變量 使用優(yōu)化函數(shù)或優(yōu)化工具箱中其他優(yōu)化函數(shù)時(shí), 輸入變量見(jiàn)下表:docin/sundae_meng3.優(yōu)化函數(shù)的輸出變量見(jiàn)下表:docin/sundae_meng3.優(yōu)化函數(shù)的輸出變量見(jiàn)下表:docin/sundae_meng4控制參數(shù)選項(xiàng)的設(shè)置 (3) MaxIter: 允許進(jìn)行迭代的最大次數(shù),取值為正整數(shù).選項(xiàng)中常用的幾個(gè)參數(shù)的名稱(chēng)、含義、取值如下: (1)陳列: 顯示水平.取值為off時(shí),不顯示輸出; 取值為iter時(shí),顯示每次迭代的信息;取值為final時(shí),顯示最終結(jié)果.默認(rèn)值為final.(2)MaxFunEvals: 允許進(jìn)行函數(shù)評(píng)價(jià)的最大次數(shù),取值為正整數(shù).d

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

32、數(shù)取默認(rèn)值.(3) options=optimset(oldops, param1,value1,param2,value2,.) 創(chuàng)建名稱(chēng)為oldops的參數(shù)的拷貝,用指定的參數(shù)值修改oldops中相應(yīng)的參數(shù).返回docin/sundae_meng用MATLAB解無(wú)約束優(yōu)化問(wèn)題 其中等式（3）、（4）、（5）的右邊可選用（1）或（2）的等式右邊. 函數(shù)fminbnd的算法基于黃金分割法和二次插值法，它要求目標(biāo)函數(shù)必須是連續(xù)函數(shù)，并可能只給出局部最優(yōu)解. 常用格式如下：（1）x= fminbnd (fun,x1,x2)（2）x= fminbnd (fun,x1,x2 ，options)（3）x

33、，fval= fminbnd（）（4）x，fval，exitflag= fminbnd（）（5）x，fval，exitflag，output= fminbnd（）docin/sundae_mengMATLAB(wliti1) 主程序?yàn)閣liti1.m: f=2*exp(-x).*sin(x); fplot(f,0,8); %作圖語(yǔ)句 xmin,ymin=fminbnd (f, 0,8) f1=-2*exp(-x).*sin (x); xmax,ymax=fminbnd (f1, 0,8)docin/sundae_meng例2 有邊長(zhǎng)為3m的正方形鐵板，在四個(gè)角剪去相等的正方形以制成方形無(wú)蓋水槽

34、，問(wèn)如何剪法使水槽的容積最大？解先編寫(xiě)M文件fun0.m如下: function f=fun0(x) f=-(3-2*x).2*x;主程序?yàn)閣liti2.m: x,fval=fminbnd(fun0,0,1.5); xmax=x fmax=-fval運(yùn)算結(jié)果為: xmax = 0.5000,fmax =2.0000.即剪掉的正方形的邊長(zhǎng)為0.5m時(shí)水槽的容積最大,最大容積為2m3.MATLAB(wliti2)docin/sundae_meng 命令格式為:（1）x= fminunc（fun,X0 ）；或x=fminsearch（fun,X0 ）（2）x= fminunc（fun,X0 ，opt

35、ions）； 或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，output= fminunc（.）； 或x，fval，exitflag，output= fminsearch（.） 2.多元函數(shù)無(wú)約束優(yōu)化問(wèn)題標(biāo)準(zhǔn)型為：mindocin/sundae_meng3 fminunc為中型優(yōu)化算法的步長(zhǎng)一維搜索提供了兩種算法，由選項(xiàng)中參數(shù)LineS

36、earchType控制： LineSearchType=quadcubic (缺省值)，混合的二次和三次多項(xiàng)式插值； LineSearchType=cubicpoly，三次多項(xiàng)式插使用fminunc和 fminsearch可能會(huì)得到局部最優(yōu)解.說(shuō)明:fminsearch是用單純形法尋優(yōu).fminunc算法見(jiàn)以下幾點(diǎn)說(shuō)明：1 fminunc為無(wú)約束優(yōu)化提供了大型優(yōu)化和中型優(yōu)化算法.由選項(xiàng)中的參數(shù)LargeScale控制：LargeScale=on (默認(rèn)值),使用大型算法LargeScale=off (默認(rèn)值),使用中型算法2 fminunc為中型優(yōu)化算法的搜索方向提供了4種算法，由 選項(xiàng)中的參

37、數(shù)HessUpdate控制： HessUpdate=bfgs（默認(rèn)值），擬牛頓法的BFGS公式；HessUpdate=dfp，擬牛頓法的DFP公式；HessUpdate=steepdesc，最速下降法docin/sundae_meng例3 minMATLAB(wliti3) 1.編寫(xiě)M文件 fun1.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); 2.輸入M文件wliti3.m如下: x0 = -1, 1; x=fminunc(fun1,x0); y=fun1(x) 3.運(yùn)行結(jié)果: x= 0

38、.5000 -1.0000 y = 1.3029e-10docin/sundae_meng*非線(xiàn)性規(guī)劃的基本解法非線(xiàn)性規(guī)劃的基本概念非線(xiàn)性規(guī)劃 返回docin/sundae_meng 定義 如果目標(biāo)函數(shù)或約束條件中至少有一個(gè)是非線(xiàn)性函數(shù),則最優(yōu)化問(wèn)題就叫做非線(xiàn)性規(guī)劃問(wèn)題非現(xiàn)性規(guī)劃的基本概念 一般形式: （1） 其中 ， 是定義在 Rn 上的實(shí)值函數(shù)，簡(jiǎn)記: 其它情況: 求目標(biāo)函數(shù)的最大值，或約束條件小于等于零兩種情況，都可通過(guò)取其相反數(shù)化為上述一般形式1nj1ni1nR :h ,R :g ,R :RRRf()nTnRxxxX=,21L()()=.,.,2,1 0 m;1,2,., 0. ljX

39、hiXgtsjidocin/sundae_meng 定義1 把滿(mǎn)足問(wèn)題（1）中條件的解 稱(chēng)為可行解（或可行點(diǎn)），所有可行點(diǎn)的集合稱(chēng)為可行集（或可行域）記為D即 問(wèn)題(1)可簡(jiǎn)記為 定義2 對(duì)于問(wèn)題(1),設(shè) ,若存在 ,使得對(duì)一切 ,且 ,都有 ,則稱(chēng)X*是f(X)在D上的局部極小值點(diǎn)（局部最優(yōu)解）特別地,當(dāng) 時(shí)，若 ,則稱(chēng)X*是f(X)在D上的嚴(yán)格局部極小值點(diǎn)（嚴(yán)格局部最優(yōu)解）定義3 對(duì)于問(wèn)題(1),設(shè) ,若對(duì)任意的 ,都有則稱(chēng)X*是f(X)在D上的全局極小值點(diǎn)（全局最優(yōu)解）特別地,當(dāng) 時(shí)，若 ,則稱(chēng)X*是f(X)在D上的嚴(yán)格全局極小值點(diǎn)（嚴(yán)格全局最優(yōu)解） 返回)(nRX()()njiRXX

40、hXg XD = =,0,0|()(),Xf Xf *docin/sundae_meng非線(xiàn)性規(guī)劃的基本解法SUTM外點(diǎn)法SUTM內(nèi)點(diǎn)法（障礙罰函數(shù)法）1 罰函數(shù)法2 近似規(guī)劃法 返回docin/sundae_mengMATLAB 優(yōu)化工具箱解非線(xiàn)性規(guī)劃docin/sundae_meng 用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); 5

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

42、q=; VLB=0;0;VUB=; x,z=quadprog(H,c,A,b,Aeq,beq,VLB,VUB)3運(yùn)算結(jié)果為： x =3 2 z = -15.5s.t.docin/sundae_meng 1 首先建立M文件fun.m,用來(lái)定義目標(biāo)函數(shù)F（X）:function f=fun(X);f=F(X);2一般非線(xiàn)性規(guī)劃 其中X為n維變?cè)蛄?，G(X)與Ceq(X)均為非線(xiàn)性函數(shù)組成的向量，其他變量的含義與線(xiàn)性規(guī)劃、二次規(guī)劃中相同用MATLAB求解上述問(wèn)題，基本步驟分三步：docin/sundae_meng3 建立主程序.求解非線(xiàn)性規(guī)劃的函數(shù)是fmincon,命令的基本格式如下： (1) x

43、=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= fmincon()輸出極值點(diǎn)M文

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

45、. x1+4x2 5 x1,x2 0例2docin/sundae_meng2先建立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運(yùn)算結(jié)果為： x = 07647 10588 fval = -20294docin/sundae_meng1先建立M文件fun4

46、m定義目標(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); x1+x2=0 s.t. 1.5+x1x2 - x1 - x2 0 -x1x2 10 0例3 2再建立M文件myconm定義非線(xiàn)性約束： function g,ceq=mycon(x) g=x(1)+x(2);15+x(1)*x(2)-x(1)-x(2); -x(1)*x(2)-10;docin/sundae_meng3主程序youh3m為:x0=-1;1;A=;b=;Aeq=1 1;beq=0;vlb=;vub=;x,fval=fm

47、incon(fun4,x0,A,b,Aeq,beq,vlb, vub,mycon)MATLAB(youh3)4 運(yùn)算結(jié)果為： x = -12250 12250 fval = 18951docin/sundae_meng 例4 1先建立M文件funm定義目標(biāo)函數(shù): function f=fun(x); f=-2*x(1)-x(2);2再建立M文件mycon2m定義非線(xiàn)性約束：function g,ceq=mycon2(x)g=x(1)2+x(2)2-25;x(1)2-x(2)2-7;docin/sundae_meng3 主程序fxxm為: x0=3;25; VLB=0 0;VUB=5 10; x

48、,fval,exitflag,output =fmincon(fun,x0, VLB,VUB,mycon2)MATLAB(fxx(fun)docin/sundae_meng4 運(yùn)算結(jié)果為: x = 40000 30000fval =-110000exitflag = 1output = iterations: 4 funcCount: 17 stepsize: 1 algorithm: 1x44 char firstorderopt: cgiterations: 返回docin/sundae_meng應(yīng)用實(shí)例： 供應(yīng)與選址 某公司有6個(gè)建筑工地要開(kāi)工，每個(gè)工地的位置（用平面坐標(biāo)系a，b表示，距離單位：km）及水泥日用量d(t)由下表給出目前有兩個(gè)臨時(shí)料場(chǎng)位于A(yíng)(5,1)，B(2,7)，日儲(chǔ)量各有20t假設(shè)從料場(chǎng)到工地之間均有直線(xiàn)道路相連 （1）試制定每天的供應(yīng)計(jì)劃，即從A，B兩料場(chǎng)分別向各工地運(yùn)送多少水泥，可使總的噸千米數(shù)最小 （2）為了進(jìn)一步減少?lài)嵡讛?shù)，打算舍棄兩個(gè)臨時(shí)料場(chǎng)，改建兩個(gè)新的，日儲(chǔ)量各為20t，問(wèn)應(yīng)建在何處，節(jié)省的噸千米數(shù)有多大？docin/sundae