工程優(yōu)化 第1章

1、工 程 優(yōu) 化 方 法任課教師：盧楠聯(lián)系方式：mathlunan最優(yōu)化技術與數(shù)學模型是工程類研究生應掌握的數(shù)學基礎課，是從事相應學科理論研究的前提。工程中許多實際問題都可以抽象為數(shù)學建模問題，數(shù)學模型其中包括最優(yōu)化模型。了解最優(yōu)化技術的基本原理、相關算法是分析問題、解決問題的一種技能，同時也是寫出高水平學術論文的關鍵素材。最優(yōu)化技術與數(shù)學模型所包括的知識點很多，選取了一些實用的方法。為什么要學習工程優(yōu)化 從工程應用的角度出發(fā)，注重工程優(yōu)化的基本思想和方法的闡述。 內(nèi)容主要包括線性規(guī)劃、非線性規(guī)劃、約束優(yōu)化、無約束優(yōu)化等，并對如何建立數(shù)學模型、如何選擇優(yōu)化方法和提高優(yōu)化效率作了適當?shù)慕榻B。課程簡

2、介 講授工程優(yōu)化的基本理論和方法，要求通過本課程的學習，具有應用工程優(yōu)化方法解決實際問題的技能，并為以后的學習和工作打好基礎。課程任務第一章 緒論第二章 基本概念和理論基礎第三章 線性規(guī)劃第四章 最優(yōu)化搜索算法結構與一維搜索第五章 無約束最優(yōu)化方法第六章 約束最優(yōu)化方法具體內(nèi)容最優(yōu)化計算方法陳開周編，西電出版社最優(yōu)化理論與方法袁亞湘等編，科學出版社最優(yōu)化理論與算法陳寶林編，清華大學出版社數(shù)學規(guī)劃講義馬仲蓄等編，人大出版社實用線性規(guī)劃D.M希梅爾布勞著無約束最優(yōu)化計算方法鄧乃楊等編教材及主要參考書目本課程授課方式與考核學科總成績平時成績（20）課堂考勤（50）平時作業(yè)（50）期末成績（80）講授

3、為主，結合習題作業(yè)第一章 緒論什么是最優(yōu)化最優(yōu)化問題的數(shù)學模型與分類最優(yōu)化問題舉例1 什么是最優(yōu)化 最優(yōu)化是一個重要的數(shù)學分支，是一門應用廣泛、實用性很強的學科。簡單地說,最優(yōu)化就是從所有可能的方案中選擇最合理的一種以達到最優(yōu)目標的學科。 達到最優(yōu)目標的方案稱為最優(yōu)方案。 搜索最優(yōu)方案的方法稱為最優(yōu)化方法。 這種方法的數(shù)學理論稱為最優(yōu)化理論。最優(yōu)化問題的兩大要素可能的方案追求的目標后者是前者的函數(shù).如果第一要素與時間無關就稱為靜態(tài)最優(yōu)化問題，否則稱為動態(tài)最優(yōu)化問題。本課程主要討論靜態(tài)最優(yōu)化問題。最優(yōu)化就是從所有可能的方案中選擇最合理的一種以達到最優(yōu)目標的學科公元前500年，古希臘在討論建筑美學

4、中就已發(fā)現(xiàn)了長方形長與寬的最佳比例為1.618,稱為黃金分割比。其倒數(shù)至今在優(yōu)選法中仍得到廣泛應用。在微積分出現(xiàn)以前，已有許多學者開始研究用數(shù)學方法解決最優(yōu)化問題。阿基米德證明：給定周長，圓所包圍的面積為最大。這就是歐洲古代城堡幾乎都建成圓形的原因。但是最優(yōu)化方法真正形成為科學方法則在17世紀以后。 歷史與現(xiàn)狀歷史與現(xiàn)狀17 世紀，Newton & Leibniz 提出了函數(shù)的極值問題；后來出現(xiàn)了Lagrange乘數(shù)法；1847年，Cauchy研究了函數(shù)值沿什么方向下降最快的問題，提出了最速下降法；1939年，蘇聯(lián)數(shù)學家提出解決下料問題和運輸問題這兩種線性規(guī)劃問題的求解方法；1947年，Dan

5、tzig 提出解線性規(guī)劃問題的單純形法，被稱為“20世紀最偉大的創(chuàng)作之一”；1948年，F(xiàn)ritz John 提出最優(yōu)性條件；1951年，Kuhn和Tucher 提出最優(yōu)性條件，完成了非線性規(guī)劃的基礎工作；近幾十年來，最優(yōu)化理論和算法發(fā)展十分迅速，應用也越來越廣泛，已成為一個相當龐大的研究領域；狹義上主要指非線性規(guī)劃問題的相關內(nèi)容；廣義上則涵蓋：線性規(guī)劃、非線性規(guī)劃、動態(tài)規(guī)劃、整數(shù)規(guī)劃、幾何規(guī)劃、多目標規(guī)劃、隨機規(guī)劃甚至還包括變分、最優(yōu)控制等等。歷史與現(xiàn)狀 最優(yōu)化的研究一般被分成兩個方面：由實際生產(chǎn)或科技問題形成最優(yōu)化的數(shù)學模型.對所形成的最優(yōu)化數(shù)學模型進行數(shù)學加工和求解。對于第二方面的工作，

6、目前已有一些較系統(tǒng)成熟的資料第一方面工作即如何由實際問題抽象出數(shù)學模型，目前很少有系統(tǒng)的資料，而這一工作在應用最優(yōu)化技術解決實際問題時是十分關鍵的。 因此，我們在學習本課程時要盡可能了解如何由實際問題形成最優(yōu)化的數(shù)學模型。數(shù)學模型: 對現(xiàn)實事物或問題的數(shù)學抽象或描述。 過于簡單的數(shù)學模型所得到的結果可能不符合實際情況；而過于詳細復雜的模型又給分析計算帶來困難。 具體建立怎樣的數(shù)學模型需要豐富的經(jīng)驗和熟練的技巧。 2 最優(yōu)化問題的數(shù)學模型與分類 建立數(shù)學模型時要盡可能簡單，而且要能完整地描述所研究的系統(tǒng)。數(shù)學模型的建立 一般的模型簡化工作包括以下幾類： （1）將離散變量轉(zhuǎn)化為連續(xù)變量。 （2）將

7、非線性函數(shù)線性化。 （3）刪除一些非主要約束條件。 數(shù)學模型的建立 在建立了問題的數(shù)學模型之后，通常也必須對模型進行必要的數(shù)學簡化以便于分析、計算。優(yōu)化模型的一般形式其中： 為決策變量 為已知參數(shù) 為隨機因素 為（一般或廣義）函數(shù)在 的約束下求決策變量 ，使函數(shù) 達到極小min；若求極大max，相當于一個min（-f）。建立最優(yōu)化問題數(shù)學模型的三要素： 決策變量和參數(shù) 決策變量是由數(shù)學模型的解確定的未知數(shù)。參數(shù)表示系統(tǒng)的控制變量，有確定性的也有隨機性的。 約束或限制條件 由于現(xiàn)實系統(tǒng)的客觀物質(zhì)條件限制，模型必須包括把決策變量限制在它們可行值之內(nèi)的約束條件，而這通常是用約束的數(shù)學函數(shù)形式來表示的

8、。 目標函數(shù) 其作為系統(tǒng)決策變量的一個數(shù)學函數(shù)來衡量系統(tǒng)的效率，即系統(tǒng)追求的目標。根據(jù)問題的不同特點分類無約束最優(yōu)化問題約束最優(yōu)化問題 等式約束優(yōu)化問題不等式約束優(yōu)化問題優(yōu)化模型的分類標準形式1）2） 一般的約束優(yōu)化問題優(yōu)化模型的分類根據(jù)函數(shù)類型分類線性規(guī)劃：目標函數(shù)、約束條件都是線性的二次規(guī)劃：目標函數(shù)為二次函數(shù)，約束條件 中的函數(shù)為線性的。非線性規(guī)劃：目標函數(shù)不是一次或者二次的， 或約束條件中的函數(shù)不全是線 性的。根據(jù)函數(shù)性質(zhì)分類動態(tài)與靜態(tài)隨機與確定單目標與多目標優(yōu)化模型的分類解法的分類解析方法:利用函數(shù)的分析性質(zhì)去構造迭代 公式，使之收斂到極值點。直接方法：按一定的數(shù)學原理，用盡量少的

9、計算量，直接比較函數(shù)值的大小。優(yōu)化模型的分類最優(yōu)化方法解決問題的工作步驟1 ）提出問題：目標、約束、決策變量、參數(shù)2 ）建立模型：變量、參數(shù)、目標之間的關系表示3 ）模型求解：數(shù)學方法及其他方法4 ）解的檢驗：制定檢驗準則、討論與現(xiàn)實的一致性5 ）靈敏性分析：參數(shù)擾動對解的影響情況6 ）解的實施：回到實踐中7 ）后評估：考察問題是否得到完滿解決3 最優(yōu)化問題舉例 最優(yōu)化在物質(zhì)運輸、自動控制、機械設計、采礦冶金、經(jīng)濟管理等科學技術各領域中有廣泛應用。下面舉幾個簡單的實例。 例1. 把半徑為1的實心金屬球熔化后，鑄成一個實心圓柱體，問圓柱體取什么尺寸才能使它的表面積最??？ 解：決定圓柱體表面積大小

10、有兩個決策變量：圓柱體底面半徑r、高h。 問題的約束條件是所鑄圓柱體重量與球重相等。即 即：問題追求的目標是圓柱體表面積最小。即 min 則得原問題的數(shù)學模型： 利用在高等數(shù)學中所學的Lagrange乘子法可求解本問題分別對r, h,求偏導數(shù),并令其等于零.有:所以，圓柱體的表面積為：例2:多參數(shù)曲線擬合問題 已知兩個物理量x和y之間的依賴關系為: 其中 為待定參數(shù),為確定這些參數(shù), 對x.y測得m個實驗點:試將確定參數(shù)的問題表示成最優(yōu)化問題.解:很顯然對參數(shù) 和 任意給定的一組數(shù)值,就由上式確定了 y關于x的一個函數(shù)關系式,在幾何上它對應一條曲線,這條曲線不一定通過那m個測量點,而要產(chǎn)生“偏

11、差”.將測量點沿垂線方向到曲線的距離的平方和作為這種“偏差”的度量.即顯然偏差S越小,曲線就擬合得越好,說明參數(shù)值就選擇得越好，從而我們的問題就轉(zhuǎn)化為5維無約束最優(yōu)化問題。即：例3：有一旅行團從 出發(fā)要遍游城市 ，已知從 到 的旅費為 ，問應如何安排行程使總費用最??？模型：變量是否從i第個城市到第j個城市約束每個城市只能到達一次、離開一次 目標總費用最小線性函數(shù)又稱一次函數(shù)，一般表達式為y=cTx+bx=0或1等價與x(x-1)=0,顯然不是線性函數(shù) 例4：靠近某河流有兩個化工廠，流經(jīng)第一化工廠的河流流量為每天500萬m3，在兩個工廠之間有一條流量為200萬m3的支流。兩化工廠每天排放某種有害

12、物質(zhì)的工業(yè)污水分別為2萬m3和1.4萬m3。從第一化工廠排出的工業(yè)污水流到第二化工廠以前，有20%可以自然凈化。環(huán)保要求河流中工業(yè)污水含量不能大于0.2%。兩化工廠處理工業(yè)污水的成本分別為1000元/萬m3和800元/萬m3?，F(xiàn)在要問在滿足環(huán)保要求的條件下，每廠各應處理多少工業(yè)污水，使這兩個工廠處理工業(yè)污水的費用最小.工廠1工廠2200萬m3500萬m3變量：x1、x2分別代表工廠1和工廠2處理污水的數(shù)量(萬m3)。則目標函數(shù)：min z=1000 x1+800 x2約束條件：第一段河流（工廠1工廠2之間）： (2x1)/500 0.2%第二段河流： 0.8(2x1) +(1.4x2)/700

13、0.2%此外有： x12； x21.4化簡有： min z=1000 x1+800 x2 x1 1 0.8x1 + x2 1.6 x1 2 x2 1.4 x1、x2 0配料每磅配料中的營養(yǎng)含量鈣蛋白質(zhì)纖維每磅成本（元）石灰石谷物大豆粉0.380 0.00 0.000.001 0.09 0.020.002 0.50 0.08 0.0164 0.0463 0.1250例5：（混合飼料配合）以最低成本確定滿足動物所需營養(yǎng)的最優(yōu)混合飼料。設每天需要混合飼料的批量為100磅，這份飼料必須含：至少0.8%而不超過1.2%的鈣;至少22%的蛋白質(zhì);至多5%的粗纖維。假定主要配料包括石灰石、谷物、大豆粉。這些配料的主要營養(yǎng)成分為： 解:根據(jù)前面介紹的建模要素得出此問題的數(shù)學模型如下:設 是生產(chǎn)100磅混合飼料所須的石灰石、谷物、大豆粉的量（磅）。 可行集：定義1: 若 使得 ，恒有 稱 為問題（p）的最優(yōu)解或者全局極小點。4 最優(yōu)解與極值點 定義2:若 ，使得 ， 恒有 ，稱 為問題（p）的嚴格全局 極小點。定義3:若 ， 使得 ，恒有 稱 為問題（p）的局部極小點。定義4:若 ， ，恒有 稱 為問題（p）的嚴格局部極小點。嚴格局部極小點嚴格全局極小點局部極小點 嚴格全局極小點 全局極小點 非嚴格全局極小點極小點 嚴格局部極小點 局部極小點 非嚴格