最優(yōu)化計算方法(工程優(yōu)化) 第1章

1、工工 程程 優(yōu)優(yōu) 化化 方方 法法任課教師：楊國平任課教師：楊國平 數(shù)學與統(tǒng)計學院數(shù)學與統(tǒng)計學院聯(lián)系方式：聯(lián)系方式： 最優(yōu)化技術與數(shù)學模型是工程類研究生應掌握的數(shù)學基礎最優(yōu)化技術與數(shù)學模型是工程類研究生應掌握的數(shù)學基礎課，是從事相應學科理論研究的前提。課，是從事相應學科理論研究的前提。 工程中許多實際問題都可以抽象為數(shù)學建模問題，數(shù)學模工程中許多實際問題都可以抽象為數(shù)學建模問題，數(shù)學模型包括最優(yōu)化模型。型包括最優(yōu)化模型。 了解最優(yōu)化技術的基本原理、相關算法是分析問題、解了解最優(yōu)化技術的基本原理、相關算法是分析問題、解決問題的一種技能，同時也是寫出高水平學術論文的關鍵決問題的一種技能，同時也是寫

2、出高水平學術論文的關鍵素材。素材。 最優(yōu)化技術與數(shù)學模型所包括的知識點很多，選取了一些最優(yōu)化技術與數(shù)學模型所包括的知識點很多，選取了一些實用的方法。實用的方法。 從工程應用的角度出發(fā)，注重工程優(yōu)化的基本思想和從工程應用的角度出發(fā)，注重工程優(yōu)化的基本思想和方法的闡述。方法的闡述。 內容主要包括內容主要包括: : 線性規(guī)劃、非線性規(guī)劃、約束優(yōu)化、無約束優(yōu)化等，線性規(guī)劃、非線性規(guī)劃、約束優(yōu)化、無約束優(yōu)化等， 并對如何建立數(shù)學模型、如何選擇優(yōu)化方法和提高優(yōu)并對如何建立數(shù)學模型、如何選擇優(yōu)化方法和提高優(yōu)化效率作了適當?shù)慕榻B?；首髁诉m當?shù)慕榻B。 講授工程優(yōu)化的基本理論和方法，要求通過本課程的學習，講授

3、工程優(yōu)化的基本理論和方法，要求通過本課程的學習，具有應用工程優(yōu)化方法解決實際問題的技能，并為以后的學具有應用工程優(yōu)化方法解決實際問題的技能，并為以后的學習和工作打好基礎。習和工作打好基礎。 第一章第一章 緒論緒論 第二章第二章 基本概念和理論基礎基本概念和理論基礎 第三章第三章 線性規(guī)劃線性規(guī)劃 第四章第四章 最優(yōu)化搜索算法結構與一維搜索最優(yōu)化搜索算法結構與一維搜索 第五章第五章 無約束最優(yōu)化方法無約束最優(yōu)化方法 第六章第六章 約束最優(yōu)化方法約束最優(yōu)化方法最優(yōu)化計算方法最優(yōu)化計算方法陳開周編，西電出版社陳開周編，西電出版社最優(yōu)化理論與方法最優(yōu)化理論與方法袁亞湘等編，科學出版社袁亞湘等編，科學出

4、版社最優(yōu)化理論與算法最優(yōu)化理論與算法陳寶林編，清華大學出版社陳寶林編，清華大學出版社數(shù)學規(guī)劃講義數(shù)學規(guī)劃講義馬仲蓄等編，人大出版社馬仲蓄等編，人大出版社實用線性規(guī)劃實用線性規(guī)劃D.MD.M希梅爾布勞著希梅爾布勞著無約束最優(yōu)化計算方法無約束最優(yōu)化計算方法鄧乃楊等編鄧乃楊等編學科總成績學科總成績平時成績平時成績（=20=80=80）講授為主，結合習題作業(yè)講授為主，結合習題作業(yè)作業(yè)以章為單位，本章結束后交作業(yè)，部分作業(yè)會在課堂上講評作業(yè)以章為單位，本章結束后交作業(yè)，部分作業(yè)會在課堂上講評 什么是最優(yōu)化什么是最優(yōu)化 最優(yōu)化問題的數(shù)學模型與分類最優(yōu)化問題的數(shù)學模型與分類 最優(yōu)化問題舉例最優(yōu)化問題舉例 最

5、優(yōu)化是一個重要的數(shù)學分支，是一門應用廣泛、實最優(yōu)化是一個重要的數(shù)學分支，是一門應用廣泛、實用性很強的學科。簡單地說用性很強的學科。簡單地說, ,最優(yōu)化就是從所有可能的方最優(yōu)化就是從所有可能的方案中選擇最合理的一種以達到最優(yōu)目標的學科。案中選擇最合理的一種以達到最優(yōu)目標的學科。 達到最優(yōu)目標的方案稱為最優(yōu)方案。達到最優(yōu)目標的方案稱為最優(yōu)方案。 搜索最優(yōu)方案的方法稱為最優(yōu)化方法。搜索最優(yōu)方案的方法稱為最優(yōu)化方法。 這種方法的數(shù)學理論稱為最優(yōu)化理論。這種方法的數(shù)學理論稱為最優(yōu)化理論。n可能的方案可能的方案n追求的目標追求的目標后者是前者的函數(shù)后者是前者的函數(shù). .如果第一要素與時間無關就稱為靜態(tài)最優(yōu)

6、化問題，否則如果第一要素與時間無關就稱為靜態(tài)最優(yōu)化問題，否則稱為動態(tài)最優(yōu)化問題。稱為動態(tài)最優(yōu)化問題。本課程主要討論靜態(tài)最優(yōu)化問題。本課程主要討論靜態(tài)最優(yōu)化問題。最優(yōu)化就是從所有可能的方最優(yōu)化就是從所有可能的方案中選擇最合理的一種以達案中選擇最合理的一種以達到最優(yōu)目標的學科到最優(yōu)目標的學科 公元前公元前500500年，古希臘在討論建筑美學中就已發(fā)現(xiàn)了長方年，古希臘在討論建筑美學中就已發(fā)現(xiàn)了長方形長與寬的最佳比例為形長與寬的最佳比例為1.618,1.618,稱為黃金分割比。其倒數(shù)稱為黃金分割比。其倒數(shù)至今在優(yōu)選法中仍得到廣泛應用。至今在優(yōu)選法中仍得到廣泛應用。 在微積分出現(xiàn)以前，已有許多學者開始研

7、究用數(shù)學方法在微積分出現(xiàn)以前，已有許多學者開始研究用數(shù)學方法解決最優(yōu)化問題。阿基米德證明：給定周長，圓所包圍解決最優(yōu)化問題。阿基米德證明：給定周長，圓所包圍的面積為最大。這就是歐洲古代城堡幾乎都建成圓形的的面積為最大。這就是歐洲古代城堡幾乎都建成圓形的原因。但是最優(yōu)化方法真正形成為科學方法則在原因。但是最優(yōu)化方法真正形成為科學方法則在1717世紀世紀以后。以后。 17 世紀，世紀，Newton & Leibniz 提出了函數(shù)的極值問題；后提出了函數(shù)的極值問題；后來出現(xiàn)了來出現(xiàn)了Lagrange乘數(shù)法；乘數(shù)法； 1847年，年，Cauchy研究了函數(shù)值沿什么方向下降最快的問研究了函數(shù)值沿

8、什么方向下降最快的問題，提出了最速下降法；題，提出了最速下降法； 1939年，蘇聯(lián)數(shù)學家提出解決下料問題和運輸問題這兩種年，蘇聯(lián)數(shù)學家提出解決下料問題和運輸問題這兩種線性規(guī)劃問題的求解方法；線性規(guī)劃問題的求解方法； 1947年，年，Dantzig 提出解線性規(guī)劃問題的單純形法，被稱提出解線性規(guī)劃問題的單純形法，被稱為為“20世紀最偉大的創(chuàng)作之一世紀最偉大的創(chuàng)作之一”； 1948年，年，F(xiàn)ritz John 提出最優(yōu)性條件；提出最優(yōu)性條件； 1951年，年，Kuhn和和Tucher 提出最優(yōu)性條件，完成了非線性規(guī)提出最優(yōu)性條件，完成了非線性規(guī)劃的基礎工作；劃的基礎工作； 近幾十年來，最優(yōu)化理論和

9、算法發(fā)展十分迅速，應用也越近幾十年來，最優(yōu)化理論和算法發(fā)展十分迅速，應用也越來越廣泛，已成為一個相當龐大的研究領域；來越廣泛，已成為一個相當龐大的研究領域； 狹義上主要指非線性規(guī)劃問題的相關內容；狹義上主要指非線性規(guī)劃問題的相關內容； 廣義上則涵蓋：線性規(guī)劃、非線性規(guī)劃、動態(tài)規(guī)劃、整數(shù)廣義上則涵蓋：線性規(guī)劃、非線性規(guī)劃、動態(tài)規(guī)劃、整數(shù)規(guī)劃、幾何規(guī)劃、多目標規(guī)劃、隨機規(guī)劃甚至還包括變分、規(guī)劃、幾何規(guī)劃、多目標規(guī)劃、隨機規(guī)劃甚至還包括變分、最優(yōu)控制等等。最優(yōu)控制等等。l由實際生產(chǎn)或科技問題形成最優(yōu)化的數(shù)學模型由實際生產(chǎn)或科技問題形成最優(yōu)化的數(shù)學模型. .l對所形成的最優(yōu)化數(shù)學模型進行數(shù)學加工和求解

10、。對所形成的最優(yōu)化數(shù)學模型進行數(shù)學加工和求解。對于第二方面的工作，目前已有一些較系統(tǒng)成熟的資料對于第二方面的工作，目前已有一些較系統(tǒng)成熟的資料第一方面工作即如何由實際問題抽象出數(shù)學模型，目前很少有系第一方面工作即如何由實際問題抽象出數(shù)學模型，目前很少有系統(tǒng)的資料，而這一工作在應用最優(yōu)化技術解決實際問題時是十分統(tǒng)的資料，而這一工作在應用最優(yōu)化技術解決實際問題時是十分關鍵的。關鍵的。 因此，我們在學習本課程時要盡可能了解如何因此，我們在學習本課程時要盡可能了解如何由實際問題形成最優(yōu)化的數(shù)學模型。由實際問題形成最優(yōu)化的數(shù)學模型。數(shù)學模型數(shù)學模型: : 對現(xiàn)實事物或問題的數(shù)學抽象或描述對現(xiàn)實事物或問題

11、的數(shù)學抽象或描述。 過于簡單的數(shù)學模型所得到的結果可能不符合實際情過于簡單的數(shù)學模型所得到的結果可能不符合實際情況；而過于詳細復雜的模型又給分析計算帶來困難。況；而過于詳細復雜的模型又給分析計算帶來困難。 具體建立怎樣的數(shù)學模型需要豐富的經(jīng)驗和熟練的技具體建立怎樣的數(shù)學模型需要豐富的經(jīng)驗和熟練的技巧。巧。 建立數(shù)學模型時要盡可能簡單，而且要能完整地描建立數(shù)學模型時要盡可能簡單，而且要能完整地描述所研究的系統(tǒng)。述所研究的系統(tǒng)。 一般的模型簡化工作包括以下幾類：一般的模型簡化工作包括以下幾類： （1）將離散變量轉化為連續(xù)變量。）將離散變量轉化為連續(xù)變量。 （2）將非線性函數(shù)線性化。）將非線性函數(shù)線

12、性化。 （3）刪除一些非主要約束條件。）刪除一些非主要約束條件。 在建立了問題的數(shù)學模型之后，通常也必須對模在建立了問題的數(shù)學模型之后，通常也必須對模型進行必要的數(shù)學簡化以便于分析、計算。型進行必要的數(shù)學簡化以便于分析、計算。其中：其中： 為決策變量為決策變量 為已知參數(shù)為已知參數(shù) 為隨機因素為隨機因素 為（一般或廣義）函數(shù)為（一般或廣義）函數(shù) min,. .,( , )0,1,2,ijklijkfxys tgxylm 在在 的約束下求決的約束下求決策變量策變量x，使函數(shù)，使函數(shù) 達到極達到極小小min；若求極大；若求極大max，相當于一個，相當于一個min（-f）。）。ixjyk,lf g

13、,( , )0lijkgxy ,ijkfxy 決策變量是由數(shù)學模型的解確定的未知數(shù)。參數(shù)表示決策變量是由數(shù)學模型的解確定的未知數(shù)。參數(shù)表示系統(tǒng)的控制變量，有確定性的也有隨機性的。系統(tǒng)的控制變量，有確定性的也有隨機性的。 由于現(xiàn)實系統(tǒng)的客觀物質條件限制，模型必須包括把由于現(xiàn)實系統(tǒng)的客觀物質條件限制，模型必須包括把決策變量限制在它們可行值之內的約束條件，而這通常是決策變量限制在它們可行值之內的約束條件，而這通常是用約束的數(shù)學函數(shù)形式來表示的。用約束的數(shù)學函數(shù)形式來表示的。 其作為系統(tǒng)決策變量的一個數(shù)學函數(shù)來衡量系統(tǒng)的效其作為系統(tǒng)決策變量的一個數(shù)學函數(shù)來衡量系統(tǒng)的效率，即系統(tǒng)追求的目標。率，即系統(tǒng)追

14、求的目標。l 無約束最優(yōu)化問題無約束最優(yōu)化問題l 約束最優(yōu)化問題約束最優(yōu)化問題 等式約束優(yōu)化問題等式約束優(yōu)化問題 不等式約束優(yōu)化問題不等式約束優(yōu)化問題 minnx Rfx min. .0nx Rifxs t hx min. .01,2,nx Rifxs tgxim 標準形式標準形式1）2） -00iigxgx 0-00iiihxhxhx 一般的約束優(yōu)化問題一般的約束優(yōu)化問題 min. .0,1,2,nx Rifxs tgxim l 線性規(guī)劃：目標函數(shù)、約束條件都是線性的線性規(guī)劃：目標函數(shù)、約束條件都是線性的l 非線性規(guī)劃：目標函數(shù)、約束條件中的函數(shù)不全是線性非線性規(guī)劃：目標函數(shù)、約束條件中的函

15、數(shù)不全是線性 的。的。l 二次規(guī)劃：目標函數(shù)為二次函數(shù)，約束條件中的函數(shù)為線二次規(guī)劃：目標函數(shù)為二次函數(shù)，約束條件中的函數(shù)為線 性的。性的。l 動態(tài)與靜態(tài)動態(tài)與靜態(tài)l 隨機與確定隨機與確定l 單目標與多目標單目標與多目標l 解析方法解析方法: :利用函數(shù)的分析性質去構造迭代公式，使之收斂利用函數(shù)的分析性質去構造迭代公式，使之收斂 到極值點。到極值點。l 直接方法：按一定的數(shù)學原理，用盡量少的計算量，直接比直接方法：按一定的數(shù)學原理，用盡量少的計算量，直接比 較函數(shù)值的大小。較函數(shù)值的大小。1) 1) 提出問題：目標、約束、決策變量、參數(shù)提出問題：目標、約束、決策變量、參數(shù)2) 2) 建立模型：

16、變量、參數(shù)、目標之間的關系表示建立模型：變量、參數(shù)、目標之間的關系表示3) 3) 模型求解：數(shù)學方法及其他方法模型求解：數(shù)學方法及其他方法4) 4) 解的檢驗：制定檢驗準則、討論與現(xiàn)實的一致性解的檢驗：制定檢驗準則、討論與現(xiàn)實的一致性5) 5) 靈敏性分析：參數(shù)擾動對解的影響情況靈敏性分析：參數(shù)擾動對解的影響情況6) 6) 解的實施：回到實踐中解的實施：回到實踐中7) 7) 后評估：考察問題是否得到完滿解決后評估：考察問題是否得到完滿解決 最優(yōu)化在物質運輸、自動控制、機械設計、采礦冶金、經(jīng)最優(yōu)化在物質運輸、自動控制、機械設計、采礦冶金、經(jīng)濟管理等科學技術各領域中有廣泛應用。下面舉幾個簡單的實濟

17、管理等科學技術各領域中有廣泛應用。下面舉幾個簡單的實例。例。 把半徑為把半徑為1的實心金屬球熔化后，鑄成一個實心圓柱體，的實心金屬球熔化后，鑄成一個實心圓柱體，問圓柱體取什么尺寸才能使它的表面積最??？問圓柱體取什么尺寸才能使它的表面積最小？決定圓柱體表面積大小有兩個決策變量：圓柱體底面半決定圓柱體表面積大小有兩個決策變量：圓柱體底面半徑徑r、高、高h。 問題的約束條件是所鑄圓柱體重量與球重相等。即問題的約束條件是所鑄圓柱體重量與球重相等。即 2343rhR 1. 0.R為金屬比重 即：即：問題追求的目標問題追求的目標是圓柱體表面積最小，即是圓柱體表面積最小，即 min 則得原問題的數(shù)學模型：則

18、得原問題的數(shù)學模型： 利用在高等數(shù)學中所學的利用在高等數(shù)學中所學的Lagrange乘子法可求解本問題乘子法可求解本問題分別對分別對r, h,求偏導數(shù)求偏導數(shù),并令其等于零并令其等于零.有有:0342hr24,3r h 222rhr 22min 224. .03rhrs tr h 224,223L r hrhrr h 所以，圓柱體的表面積為：所以，圓柱體的表面積為：222420202403LhrrhrLrrhrhLr h 32 / 3r 322 / 3h 23263S 多參數(shù)曲線擬合問題多參數(shù)曲線擬合問題 已知兩個物理量已知兩個物理量x和和y之間的依賴關系為之間的依賴關系為: 其中其中 為待定參

19、數(shù)為待定參數(shù), 為確定這些參數(shù)為確定這些參數(shù), 對對x,y測得測得m個實驗點個實驗點:試將確定參數(shù)的問題表示成最優(yōu)化問題。試將確定參數(shù)的問題表示成最優(yōu)化問題。214351ln 1expayaxaaa 12345,aaaaa 1,12,2,mmx yx yxy很顯然對參數(shù)很顯然對參數(shù) 任意給定的一組數(shù)值任意給定的一組數(shù)值,就由上式確就由上式確定了定了 y關于關于x的一個函數(shù)關系式的一個函數(shù)關系式,在幾何上它對應一條曲線在幾何上它對應一條曲線,這條曲線這條曲線不一定通過那不一定通過那m個測量點個測量點,而要產(chǎn)生而要產(chǎn)生“偏差偏差”.xy12345,aaaaa22114351ln 1 expmiii

20、aSyaxaaa 顯然偏差顯然偏差S越小越小,曲線就擬合得越好曲線就擬合得越好,說明參數(shù)值就選擇得越好，說明參數(shù)值就選擇得越好，從而我們的問題就轉化為從而我們的問題就轉化為5維無約束最優(yōu)化問題。即：維無約束最優(yōu)化問題。即：將測量點沿垂線方向到曲線的距離的將測量點沿垂線方向到曲線的距離的平方和作為這種平方和作為這種“偏差偏差”的度量的度量. 即即2211435min1ln 1 expmiiiayaxaaa 有一旅行團從有一旅行團從 出發(fā)要遍游城市出發(fā)要遍游城市 ，已知從已知從 到到 的旅費為的旅費為 ，問應如何安排行程使總，問應如何安排行程使總費用最小？費用最?。?v12,.,nv vvjviv

21、ijcl變量變量是否從是否從i第個城市到第第個城市到第j個城市個城市l(wèi)約束約束每個城市只能到達一次、離開一次每個城市只能到達一次、離開一次1,0;ijx 001;0,1,. ,1;0,1,.nnijijjixinxjnl目標目標總費用最小總費用最小00nnijijijc x 0000min1;1,2,.,. .1;1,2,.,1,0,1,2,., ,1,2,.,nnijijijnijjnijiijc xxins txjnxin jn 線性函數(shù)又稱一次函數(shù)，線性函數(shù)又稱一次函數(shù)，一般表達式為一般表達式為y=cTx+bx=0或或1等價與等價與x(x-1)=0,顯然不是線性函數(shù)顯然不是線性函數(shù)靠近某

22、河流有兩個化工廠，流經(jīng)第一化工廠的河流流靠近某河流有兩個化工廠，流經(jīng)第一化工廠的河流流量為每天量為每天500萬萬m3，在兩個工廠之間有一條流量為，在兩個工廠之間有一條流量為200萬萬m3的支流。兩化工廠每天排放某種有害物質的工業(yè)污水的支流。兩化工廠每天排放某種有害物質的工業(yè)污水分別為分別為2萬萬m3和和1.4萬萬m3。從第一化工廠排出的工業(yè)污水流。從第一化工廠排出的工業(yè)污水流到第二化工廠以前，有到第二化工廠以前，有20%可以自然凈化。環(huán)保要求河流可以自然凈化。環(huán)保要求河流中工業(yè)污水含量不能大于中工業(yè)污水含量不能大于0.2%。兩化工廠處理工業(yè)污水。兩化工廠處理工業(yè)污水的成本分別為的成本分別為10

23、00元元/萬萬m3和和800元元/萬萬m3?，F(xiàn)在要問在滿?，F(xiàn)在要問在滿足環(huán)保要求的條件下，每廠各應處理多少工業(yè)污水，使這足環(huán)保要求的條件下，每廠各應處理多少工業(yè)污水，使這兩個工廠處理工業(yè)污水的費用最小兩個工廠處理工業(yè)污水的費用最小.工廠工廠1工廠工廠2200萬萬m3500萬萬m3 變量變量：x1、x2-分別代表工廠分別代表工廠1和工廠和工廠2處理污水的數(shù)量處理污水的數(shù)量(萬萬m3)則目標函數(shù)：則目標函數(shù)：min z=1000 x1+800 x2約束條件：約束條件：化簡有：化簡有：第一段河流（工廠第一段河流（工廠1-工廠工廠2之間）：之間）：(2-x1)/500 0.2%第二段河流：第二段河流：

24、 0.8(2-x1) +(1.4-x2)/7000.2%此外有：此外有： x12； x21.4 min z=1000 x1+800 x2 s.t. x1 1 0.8x1 + x2 1.6 x1 2 x2 1.4 x1、x2 0配料配料每磅配料中的營養(yǎng)含量每磅配料中的營養(yǎng)含量鈣鈣蛋白質蛋白質纖維纖維每磅成本（元）每磅成本（元）石灰石石灰石谷物谷物大豆粉大豆粉0.380 0.00 0.000.001 0.09 0.020.002 0.50 0.08 0.0164 0.0463 0.1250（混合飼料配合）以最低成本確定滿足動物所需營養(yǎng)的（混合飼料配合）以最低成本確定滿足動物所需營養(yǎng)的最優(yōu)混合飼料。

25、設每天需要混合飼料的批量為最優(yōu)混合飼料。設每天需要混合飼料的批量為100磅，這份飼磅，這份飼料必須含：至少料必須含：至少0.8%而不超過而不超過1.2%的鈣的鈣;至少至少22%的蛋白質的蛋白質;至多至多5%的粗纖維。假定主要配料包括石灰石、谷物、大豆粉。的粗纖維。假定主要配料包括石灰石、谷物、大豆粉。這些配料的主要營養(yǎng)成分為：這些配料的主要營養(yǎng)成分為： 根據(jù)前面介紹的建模要素得出此問題的數(shù)學模型如下根據(jù)前面介紹的建模要素得出此問題的數(shù)學模型如下:設設 是生產(chǎn)是生產(chǎn)100磅混合飼料所須的石灰石、谷物、大豆粉磅混合飼料所須的石灰石、谷物、大豆粉的量（磅），的量（磅），123,x xx1231231231232323123min0.01640.04630.1250. .1000.3800.0010.0020.012 1000.3800.0010.0020.008 1000.090.500.22 1000.020.080.05 1000,0,0Zxxxs txxxxxxxxxxxxxxxx 若若 ,使得使得 恒恒 有有 稱稱 為問題為問題(P)的的最優(yōu)解或者全局極小最優(yōu)解或者全局極小 點點。 0,1,