1、最優化與最優控制最優化與最優控制例例1 1 火車快速運行問題。設有一列火車從甲地出發，火車快速運行問題。設有一列火車從甲地出發，要求算出容許的控制使其到達乙地的時間最短。要求算出容許的控制使其到達乙地的時間最短?；疖嚨倪\動方程火車的運動方程)(tuxm ( )u tM式中，式中， 是火車的質量，是火車的質量， 是火車的加速度，為使是火車的加速度，為使旅客舒適，其值有限制。旅客舒適，其值有限制。 是產生加速度的控是產生加速度的控制作用（即推力），其值也應有限制，設制作用（即推力），其值也應有限制，設x )(tum一、最優控制問題舉例一、最優控制問題舉例選擇選擇 使使 為最小。為最小。)(tu)(

2、uJ初始條件初始條件00( )x tx0( )0 x t終端條件終端條件ffxtx)(0)(ftx 性能指標性能指標00)(ttdtuJfttf例例2：登月艙軟著陸的最小燃料問題：登月艙軟著陸的最小燃料問題)(u)()()(u)(v)(v)(tktmgtmtttth 運動方程運動方程參數說明：登月艙質量參數說明：登月艙質量m(t)，不含燃料時的質量不含燃料時的質量M，所載燃料，所載燃料質量質量F。高度。高度h(t)，登月時的初，登月時的初始高度始高度h0，初始垂直速度，初始垂直速度v0.發動機推力發動機推力u(t)，重力加速度，重力加速度g一、最優控制問題舉例一、最優控制問題舉例0)(0)(

3、fftvthmax)(0utu )(ftmJ 末端條件末端條件控制約束控制約束性能指標性能指標FMmvvhh )0()0()0(00初始條件初始條件二、最優控制二、最優控制 在生產過程、軍事行動、經濟活動以及人類的其在生產過程、軍事行動、經濟活動以及人類的其它有目的的活動中，常需要對被控系統或被控過程施它有目的的活動中，常需要對被控系統或被控過程施加某種控制作用以使某個性能指標達到最優，這種控加某種控制作用以使某個性能指標達到最優，這種控制作用稱為最優控制。制作用稱為最優控制。二、最優控制二、最優控制 ,),(0ftttttUtXfX其中， 為 維狀態向量， 為 維控制向量， 為 維向量函數，

4、它可以是非線性時變向量函數，也可以是線性定常的向量函數。狀態方程必須精確的知道。( )X tn( )U tm( ),( ),f X t U t tn （1）建立被控系統的狀態方程）建立被控系統的狀態方程二、最優控制二、最優控制 而到達終端的時刻而到達終端的時刻 和狀態和狀態 則因問題而異。則因問題而異。ft()fX tn 一個動態過程對應于一個動態過程對應于 維狀態空間中從一個維狀態空間中從一個狀態到另一個狀態的轉移，也就是狀態空間中的狀態到另一個狀態的轉移，也就是狀態空間中的一條軌線。在最優控制中初態通常是知道的，即一條軌線。在最優控制中初態通常是知道的，即00( )X tX（2）確定狀態方

5、程的邊界條件）確定狀態方程的邊界條件()ffX tX（1-19）例如，在流水線生產過程中，例如，在流水線生產過程中， 是固定的；在飛機是固定的；在飛機快速爬高時，只規定爬高的高度快速爬高時，只規定爬高的高度 ，而，而 是自由的，要求是自由的，要求 越小越好。終端狀態越小越好。終端狀態 一般屬于一個目標集一般屬于一個目標集 ，即，即ft()ffX tXft0ftt( )fX tS當終端狀態是固定的，即當終端狀態是固定的，即 時，則目標集退時，則目標集退化為化為 維狀態空間中的一個點。而當終態滿足某些維狀態空間中的一個點。而當終態滿足某些約束條件，即約束條件，即()ffX tXn這時這時 處在處在

6、 維狀態空間中某個超曲面上。若維狀態空間中某個超曲面上。若終態不受約束，則目標集便擴展到整個終態不受約束，則目標集便擴展到整個 維空間，維空間，或稱終端狀態自由?；蚍Q終端狀態自由。()fX tnn(),0ffG X tt （3）確定控制作用的容許范圍）確定控制作用的容許范圍 ，即，即 是是 維控制空間維控制空間 中的一個集合。例如，控中的一個集合。例如，控制飛機的舵偏角是受限制的，控制電機的電流是制飛機的舵偏角是受限制的，控制電機的電流是受限制的，即有受限制的，即有 。這時控制作用屬于一。這時控制作用屬于一個閉集。當個閉集。當 不受任何限制時，稱它屬于一個不受任何限制時，稱它屬于一個開集。處理

7、這兩類問題的方法是不同的。開集。處理這兩類問題的方法是不同的。 可稱可稱為容許集合，屬于為容許集合，屬于 的控制則稱為容許控制。的控制則稱為容許控制。mmR( )U tM( )U t( )U t （4）選定性能指標）選定性能指標 J 性能指標性能指標 是控制作用是控制作用 的函數，也就是的函數，也就是函數函數 的函數，這種以函數為自變量的函數稱的函數，這種以函數為自變量的函數稱為泛函，所以為泛函，所以 又稱為性能泛函。有的文獻中也又稱為性能泛函。有的文獻中也把性能指標稱為代價函數、目標函數等等。把性能指標稱為代價函數、目標函數等等。J( )U tJ( )U t按一定的方法計算出容許控制按一定的

8、方法計算出容許控制 將它將它施加于用狀態方程描述的系統，使狀態從初態施加于用狀態方程描述的系統，使狀態從初態轉移到目標集轉移到目標集 中的某一個終態中的某一個終態 ，并使性能，并使性能指標達到最大或最小，即達到某種意義下的最優。指標達到最大或最小，即達到某種意義下的最優。( )( )U t U t 0( )X t()fX tS 1、 積分型性能指標 （1）最短時間控制 （2）最少燃料消耗控制 （3）最少能量控制 fttdtttutxJ0),(),( fttfttdtJ00 fttmjjidttuJ01)( fttTdttutuJ0)()(拉格朗日問題拉格朗日問題（2）末值型性能指標）末值型性能

9、指標（3）復合型性能指標）復合型性能指標 二次型性能指標二次型性能指標),(ffttxJ fttffdtttutxttxJ0),(),(),( fttTTTdttutRtutxtQtxtFxtxJ0)()()()()()(21)()(21波爾扎問題波爾扎問題 學科內容：學科內容： 線性系統理論線性系統理論 非線性系統理論非線性系統理論 最優控制理論最優控制理論 最優狀態估計最優狀態估計 自適應控制理論自適應控制理論 系統辨識系統辨識數學工具數學工具：現代數學的內容，包括矩陣理論和泛函分析。：現代數學的內容，包括矩陣理論和泛函分析。著重研究線性系統中狀態的觀測著重研究線性系統中狀態的觀測與控制與

10、控制基本的分析與綜合方法：狀態空基本的分析與綜合方法：狀態空間法間法 使控制系統的性能指標實現最使控制系統的性能指標實現最優化的基本條件與綜合方法優化的基本條件與綜合方法 在系統和環境的信息不完備的情況在系統和環境的信息不完備的情況下改變自身特性來保持良好工作品下改變自身特性來保持良好工作品質的控制方式。質的控制方式。 根據可獲取的量測數據估計根據可獲取的量測數據估計動態系統內部狀態動態系統內部狀態 根據系統輸入輸出時間函根據系統輸入輸出時間函數描述系統模型數描述系統模型 2、發展歷程、發展歷程19401940年維納提出相對于某一個年維納提出相對于某一個性能指標進行最優設計的概念性能指標進行最

11、優設計的概念19501950年米頓納爾首先將這個概年米頓納爾首先將這個概念用于研究繼電器系統過渡過念用于研究繼電器系統過渡過程時間最短問題程時間最短問題19571957年德來培爾研究內燃機消年德來培爾研究內燃機消耗最小問題耗最小問題 20世紀世紀50年代中期，空間技術的要求與推動年代中期，空間技術的要求與推動19531957貝爾曼貝爾曼動態規劃方法動態規劃方法貝爾曼貝爾曼Richard Bellman(19201984)Richard Bellman(19201984)美國數學家，美國全國科學院美國數學家，美國全國科學院院士，動態規劃的創始人。院士，動態規劃的創始人。19571957年出版專著

12、年出版專著動態規劃動態規劃，對控制理論結合數學界有深遠對控制理論結合數學界有深遠影響。影響。19561958年年龐德里亞金龐德里亞金最大（?。┲翟碜畲螅ㄐ。┲翟睚嬏乩飦喗瘕嬏乩飦喗?. . (1908)(1908)蘇聯數學家，極大值原理的創始人蘇聯數學家，極大值原理的創始人1960s，貝爾曼，卡爾曼等將狀態空間法貝爾曼，卡爾曼等將狀態空間法引入控制理論，引入控制理論，提出具有二次型性能指標的線提出具有二次型性能指標的線性狀態反饋律給出最優調節器的概念。性狀態反饋律給出最優調節器的概念。 卡爾曼卡爾曼 R.ER.ERudolf Emil Rudolf Emil Kalman(1930)Kal

13、man(1930)美國數學家和電氣工程美國數學家和電氣工程師。師。19601960年提出著名的年提出著名的卡爾曼濾波器卡爾曼濾波器1、最優化問題的實質 -求取極值 如：營養學問題，確定什么樣的食譜既能滿營養學問題，確定什么樣的食譜既能滿足人們健康所需的要求，又使價格最便宜；足人們健康所需的要求，又使價格最便宜； 在生產計劃中，在一定人力、機器、原材料、在生產計劃中，在一定人力、機器、原材料、資金條件下，如何安排生產，使生產成本達到資金條件下，如何安排生產，使生產成本達到最低最低2、最優化問題的三個基本要素：、最優化問題的三個基本要素： 優化變量、目標函數和約束條件優化變量、目標函數和約束條件一

14、、最優化問題例例1：最大利潤問題：最大利潤問題某工廠生產兩種不同產品某工廠生產兩種不同產品A，B，每種產品都要經過兩個工，每種產品都要經過兩個工藝過程藝過程A1，A2，各產品在各工藝過程所消耗的時間、各，各產品在各工藝過程所消耗的時間、各工藝過程每周可用工時和每件產品的單位利潤如表：工藝過程每周可用工時和每件產品的單位利潤如表：設備設備每件產品的加工時每件產品的加工時間間/h每周可用工時每周可用工時hABA11.5540A22440利潤（元）2005003、最優化問題舉例、最優化問題舉例設二種產品每周計劃產量分別為設二種產品每周計劃產量分別為可獲總利潤為可獲總利潤為f.500200)(max2

15、1tsxxxf 2 , 1, 040424055 . 12121 jxxxxxj2, 1xx優化變量優化變量目標函數目標函數約束條件約束條件特點：目標函數與優化變量都是線性的特點：目標函數與優化變量都是線性的 給定厚度和密度的金屬板設計一個長方體容給定厚度和密度的金屬板設計一個長方體容器，使其體積一定的條件下重量最輕器，使其體積一定的條件下重量最輕321133322211.minxxxVtsxxcxxcxxcJ 約束條件約束條件特點：目標函數與優化變量都是非線性的特點：目標函數與優化變量都是非線性的是金屬板厚度和密度有關的系數是金屬板厚度和密度有關的系數容器的長寬高容器的長寬高321321,x

16、xxccc實際問題所提出的實際問題所提出的最優化問題最優化問題大體有兩類：一類是求大體有兩類：一類是求函數的極值函數的極值，另一類是求，另一類是求泛函的極值泛函的極值。 求函數極值的最優化方法可稱為求函數極值的最優化方法可稱為數學規劃數學規劃，包括，包括線性線性規劃規劃和和非線性規劃非線性規劃，一般處理的是，一般處理的是靜態問題靜態問題。有約束、無約束；有約束、無約束；等式約束，不等式約束等式約束，不等式約束隨機性、確定性隨機性、確定性；解析式模型，圖；解析式模型，圖變量不是時間的函數變量不是時間的函數1、幾個名詞、幾個名詞 （1）可行解可行解-滿足約束條件的一組解稱為可行解，它可滿足約束條件

17、的一組解稱為可行解，它可以有無窮多個。以有無窮多個。 （2）可行解域可行解域-約束條件包含的范圍，即變量滿足約束約束條件包含的范圍，即變量滿足約束條件的可行范圍，由無窮多個可行解組成。條件的可行范圍，由無窮多個可行解組成。（3）最優解最優解-使指標函數為極值的可行解。最優解在可使指標函數為極值的可行解。最優解在可行解域內。行解域內。（4）指標函數等高線指標函數等高線-由指標函數值相等的點構成的直由指標函數值相等的點構成的直線或曲線（對于非線性指標函數時為曲線）。線或曲線（對于非線性指標函數時為曲線）。.500200)(max21tsxxxf 2 , 1, 040424055 . 12121 j

18、xxxxxj（1）最優解不唯一）最優解不唯一0, 015053602106max21212121 xxxxxxxxJ由于指標函數等高由于指標函數等高線與線與AD平行，此平行，此時時AD上所有點均上所有點均為最優值。為最優值。（2）可行解域無界）可行解域無界0, 03312max21212121 xxxxxxxxJ指標函數極大值為指標函數極大值為無窮大，極小值為無窮大，極小值為左頂點左頂點（3）可行解域不存在）可行解域不存在0, 0302103max21212121 xxxxxxxxJ約束條件所確定的約束條件所確定的區域不重合區域不重合3、線性規劃問題的求解、線性規劃問題的求解單純形方法單純形方

19、法-G. B. Dantzig 在在可行域的頂點可行域的頂點中搜索最優點中搜索最優點從可行解域的頂點出發，向鄰近頂點運動，如此繼續，直至從可行解域的頂點出發，向鄰近頂點運動，如此繼續，直至檢查出基本可行解為最優解為止。檢查出基本可行解為最優解為止。線性規劃的基本定理：線性規劃的基本定理：（1）線性規劃問題的可行域是凸集。）線性規劃問題的可行域是凸集。（2）線性規劃問題的最優值一定可行域）線性規劃問題的最優值一定可行域凸集凸集的某個的某個頂點上達到。頂點上達到。S為凸集：為凸集：S為為n維歐式空間中一個點集，對維歐式空間中一個點集，對S中任意兩個不同點，連中任意兩個不同點，連線上的一切點仍屬于線

20、上的一切點仍屬于S。4、Matlab優化工具箱中優化工具箱中 求解線性規劃的函數為求解線性規劃的函數為linprog（）（）例題例題 f=-7;-9;-8; A=4.2,6.1,5.3;0.4,0.7,0.3;1.1,1.9,1.4; b=8300;3700;4100; lb=zeros(3,1); x,fval=linprog(f,A,b,lb);說明：為應用該函數，需將最大值問題變為最小值求解說明：為應用該函數，需將最大值問題變為最小值求解不等式約束不等式約束等式約束等式約束.897)(max321tsxxxxf 3 , 2 , 1, 041004 . 19 . 11 . 137003 .

21、 07 . 04 . 083003 . 51 . 62 . 4321321321 jxxxxxxxxxxj1、目標函數和約束條件至少有一個是非線性。、目標函數和約束條件至少有一個是非線性。常見的非線性規劃常見的非線性規劃-二次型二次型最優性條件最優性條件-局部極小點的一階必要條件局部極小點的一階必要條件設函數設函數 在點在點x處可微，且處可微，且x為局部極小點，則必有為局部極小點，則必有梯度梯度可將求極值問題化為求可將求極值問題化為求x使滿足使滿足AxxxfT )()(xf0)( Xf 0)(0)(1nxxfxxf 一般而言該一般而言該n維方程組是非線性的，難以用維方程組是非線性的，難以用解析

22、法求解，因此一般用數值方法直接求極值。解析法求解，因此一般用數值方法直接求極值。迭代法基本思想：給出極小點的一個初始估計迭代法基本思想：給出極小點的一個初始估計X0，計算一系列，計算一系列Xk（1，2，），希望點列），希望點列Xk的極限的極限X*為為f（x）的極小點。）的極小點。點列獲得方法：最速下降法，牛頓法等點列獲得方法：最速下降法，牛頓法等 0)(0)(1nxxfxxf2、Matlab優化工具箱中，求解無約束非線性規優化工具箱中，求解無約束非線性規劃的函數為劃的函數為fminsearch（）和（）和fminunc()例：求例：求Function f=myfun(x) f=3*x(1)2+

23、2*x(1)*x(2)+x(2)2;X0=1,1;%初始值初始值x,fval=fminunc(myfun,x0);22212123)(minxxxxxf3、有約束非線性規劃、有約束非線性規劃 有約束問題取得的最優解可能是局部最優，并有約束問題取得的最優解可能是局部最優，并且與初始點有關。一般求解有兩類方法：且與初始點有關。一般求解有兩類方法：（1）間接解）間接解 將約束問題轉換為無約束問題，如將約束問題轉換為無約束問題，如拉格朗日乘子法，消元法等拉格朗日乘子法，消元法等（2）直接解）直接解 在可行域內選取各點的目標函數，在可行域內選取各點的目標函數，找到最小點，如隨機試驗法，線性逼近法找到最小

24、點，如隨機試驗法，線性逼近法拉格朗日乘子法拉格朗日乘子法（1）等式約束）等式約束構造拉格朗日函數構造拉格朗日函數2、不等式約束、不等式約束引入松弛因子，約束函數變為引入松弛因子，約束函數變為目標函數為目標函數為. .)(mintsxfLlxhl, 2 , 1, 0)( LlllxhxfxL1)()(),( . .)(mintsxfMmmmmxgxfxL12)()(),(Mmxgm, 2 , 1, 0)(Mmxgmm, 2 , 1, 0)(2 Matlab優化工具箱中，求解有約束最優化的函數為優化工具箱中，求解有約束最優化的函數為fminbnd(), fmincon(), fseminf(),

25、quadprog(), fminimax()例例:求取求取約束條件約束條件初始位置初始位置Function f=myfun(x)F=-x(1)*x(2)*x(3);X0=10;10;10;A=-1,-2,-2;1,2,2;b=0;27;x,fval=fmincon(myfun,x0,A,b)321)(minxxxxf27220321xxxTx101010)0(2722022321321xxxxxx典型問題：典型問題：TSP問題問題，背包問題背包問題，作業調度問題，作業調度問題難以抽象出合適數學解析式的優化問題難以抽象出合適數學解析式的優化問題可采用經驗推理、人工智能、專家系統等方法可采用經驗推

26、理、人工智能、專家系統等方法算法包括禁忌搜索算法、模擬退火算法、遺傳算法、算法包括禁忌搜索算法、模擬退火算法、遺傳算法、蟻群優化算法、神經網絡、拉格朗日松弛算法等蟻群優化算法、神經網絡、拉格朗日松弛算法等TSP問題問題問題說明：設有問題說明：設有n+1個城市，分別用個城市，分別用0，1，2n來表示，來表示，從城市從城市i到城市到城市j的距離為的距離為dij，一個推銷員從城市，一個推銷員從城市0出發，出發，到達其它任一城市一次且僅僅一次，然后回到城市到達其它任一城市一次且僅僅一次，然后回到城市0，如，如何選擇行走路線，使總的路程最短？何選擇行走路線，使總的路程最短？旅行商問題特點：旅行商問題特點

27、：1、實際很多應用問題可轉化為該問題，如物資、實際很多應用問題可轉化為該問題，如物資運輸路線，管道鋪設等；運輸路線，管道鋪設等；2、難于求解，可從事、難于求解，可從事有效求解算法有效求解算法的研究的研究設有設有n種物品，每一種物品數量無限。第種物品，每一種物品數量無限。第i種物品每件種物品每件重量為重量為wi公斤，每件價值公斤，每件價值ci元。現有一只可裝載重元。現有一只可裝載重量為量為W公斤的背包，求各種物品應各取多少件放入公斤的背包，求各種物品應各取多少件放入背包，使背包中物品的價值最高。背包，使背包中物品的價值最高?？梢杂谜麛狄巹澞Ｐ蛠砻枋觥ＴO第可以用整數規劃模型來描述。設第i種物品取種

28、物品取xi件件（i=1,2,n，xi為非負整數為非負整數)，背包中物品的價，背包中物品的價值為值為z，則，則為非負整數為非負整數nnnnnxxxWxwxwxwtsxcxcxcZ,.max2122112211 6、算法復雜性、算法復雜性算法的時間復雜性函數是問題輸入長度的函數，例冒算法的時間復雜性函數是問題輸入長度的函數，例冒泡排序法對個數為泡排序法對個數為n的整數排序，最壞情形的時間的整數排序，最壞情形的時間復雜度為復雜度為222) 1()(2nnnnnf時間復雜度為時間復雜度為)(2nO算法的時間復雜性函數很多情況下為下列函數之一：算法的時間復雜性函數很多情況下為下列函數之一：)(),!()

29、,(),2(),(),log(),(),(loglog2nnnnOnnnOOnOnnOnOnO以上按時間復雜度增大排列以上按時間復雜度增大排列存在某個以輸入長度存在某個以輸入長度n為變量的多項式函數為變量的多項式函數p(n)，使時，使時間復雜性函數為間復雜性函數為O（p(n)）,稱為多項式時間算法，如稱為多項式時間算法，如)5(),10(),(836nOnOnO算法的復雜度算法的復雜度 是指數函數，是無望求解的是指數函數，是無望求解的 NP問題問題圖中曲線圖中曲線y=y(x)y=y(x)如何選取，才如何選取，才能在滿足邊界弧長為定值的條件能在滿足邊界弧長為定值的條件下，使該圖形的面積實現最大下

30、，使該圖形的面積實現最大 20)()(dxxyyJyx020)2()0(,)()(1 yyCxyxyy面積面積其中其中 dxy2021弧長約束弧長約束7、泛函最優問題、泛函最優問題如圖所示，在重力作用下，物體由如圖所示，在重力作用下，物體由(0,0)(0,0)點點至至(x1,y1)(x1,y1)點，路徑點，路徑y=y(x)y=y(x)如何可使所用時如何可使所用時間為最短？間為最短？(0,0)xy(x,y)(x1,y1)設設t時刻物體速度為時刻物體速度為v，則，則)(221)(122xgyvmvxmgydxdtydtdsv (0,0)xy(x,y)(x1,y1)xxyT)( 102)(21minminxyydxxgyyT該問題即求取該問題即求取函數關系函數關系 102222)(21)(21)(221)(1xdxxgyyTdxxgyydtxgyvmvxmgydxdtydtdsv則則 空間實際上就是一個集合，且該集合中的元素之間具有空間實際上就是一個集合，且該集合中的元素之間具有某些特定的聯系和性質。某些特定的聯系和性質。1、線性空間、線性空間 在非空集合在非空集合X中規定了元素的加法和數乘線性運算，加法中規定了元素的加法和數乘線性