1、最優化理論與方法最優化理論與方法 歷史上最早記載下來的最優化問題可追溯到古希歷史上最早記載下來的最優化問題可追溯到古希臘的歐幾里得（臘的歐幾里得（Euclid，公元前，公元前300300年左右），他指出：年左右），他指出：在周長相同的一切矩形中，以正方形的面積為最大。在周長相同的一切矩形中，以正方形的面積為最大。十七、十八世紀十七、十八世紀微積分微積分的建立給出了求函數極值的一的建立給出了求函數極值的一些準則，對最優化的研究提供了某些理論基礎。然而，些準則，對最優化的研究提供了某些理論基礎。然而，在以后的兩個世紀中，最優化技術的進展緩慢，主要在以后的兩個世紀中，最優化技術的進展緩慢，主要考慮了

2、有約束條件的最優化問題，發展了考慮了有約束條件的最優化問題，發展了變分法變分法。 直到上世紀直到上世紀4040年代初，由于軍事上的需要產生了年代初，由于軍事上的需要產生了運籌學運籌學，并使優化技術首先應用于解決戰爭中的實際，并使優化技術首先應用于解決戰爭中的實際問題，例如轟炸機最佳俯沖軌跡的設計等。問題，例如轟炸機最佳俯沖軌跡的設計等。 近十幾年來，最優化方法已陸續用到建筑結構、近十幾年來，最優化方法已陸續用到建筑結構、化工、冶金、鐵路、航天航空、造船、機床、汽車、化工、冶金、鐵路、航天航空、造船、機床、汽車、自動控制系統、電力系統以及電機、電器等工程設計自動控制系統、電力系統以及電機、電器等

3、工程設計領域，并取得了顯著效果。領域，并取得了顯著效果。 50年代末年代末數學規劃方法數學規劃方法被首次用于結構最優化，并被首次用于結構最優化，并成為優化設計中求優方法的理論基礎。數學規劃方法是成為優化設計中求優方法的理論基礎。數學規劃方法是在第二次世界大戰期間發展起來的一個新的數學分支，在第二次世界大戰期間發展起來的一個新的數學分支，線性規劃與非線性規劃是其主要內容。線性規劃與非線性規劃是其主要內容。 大型電子計算機的出現，使最優化方法及其理論蓬大型電子計算機的出現，使最優化方法及其理論蓬勃發展，成為應用數學中的一個重要分支，并在許多科勃發展，成為應用數學中的一個重要分支，并在許多科學技術領

4、域中得到應用。學技術領域中得到應用。 已知：制造一體積為已知：制造一體積為100m3，長度不小于，長度不小于5m，不，不帶上蓋的箱盒，試確定箱盒的長，寬，高，使箱帶上蓋的箱盒，試確定箱盒的長，寬，高，使箱盒用料最省。盒用料最省。x x1 1x x2 2x x3 3例例1.1.箱盒的優化問題箱盒的優化問題分析：分析：（1）箱盒的表面積的表達式；）箱盒的表面積的表達式；（2）優化變量確定：長）優化變量確定：長x1，寬，寬x2，高，高x3 ；（3）優化約束條件：）優化約束條件： （a）體積要求；）體積要求； （b）長度要求；）長度要求；123,x x x122313min2()Sx xx xx x1

5、23123500100 xxxx x x優化變量：優化變量：目標函數：目標函數：約束條件：約束條件：. .st例例2.2.最大產值生產資源分配問題最大產值生產資源分配問題 分析：分析：,ABxxmaxAABBPP xP x0,0CACBEAEBLALBABa xb xCa xb xEa xb xLxx優化變量：優化變量：目標函數：目標函數：約束條件：約束條件：. .st14 旅行推銷商問題旅行推銷商問題(Travelling Salesman Problem,(Travelling Salesman Problem,簡記為簡記為TSP)TSP)，問題的經典提法為，問題的經典提法為: : 有一貨

6、物推銷員要去若干個城市推銷貨物有一貨物推銷員要去若干個城市推銷貨物, , 從城市從城市1 1出發出發, , 經其余各城市一次經其余各城市一次, , 然后回到城市然后回到城市1, 1, 問選問選擇怎樣的行走路線擇怎樣的行走路線, , 才能使總行程最短才能使總行程最短( (各城市間距各城市間距離為已知離為已知) ) 。例3. TSP問題 1.1.優化變量優化變量 一個優化問題可以用一組基本參數的數值來表一個優化問題可以用一組基本參數的數值來表示，在優化過程中進行選擇并最終必須確定的各項示，在優化過程中進行選擇并最終必須確定的各項獨立的基本參數，稱作獨立的基本參數，稱作優化變量優化變量，又叫做，又叫

7、做決策變量決策變量。 最優化的數學模型是描述實際優化問題目標函數、最優化的數學模型是描述實際優化問題目標函數、變量關系、有關約束條件和意圖的數學表達式，它變量關系、有關約束條件和意圖的數學表達式，它反映了物理現象各主要因素的內在聯系，是進行最反映了物理現象各主要因素的內在聯系，是進行最優化的基礎。優化的基礎。 優化變量的全體實際上是一組變量，可用一個列優化變量的全體實際上是一組變量，可用一個列向量表示。優化變量的數目稱為優化問題的維數，如向量表示。優化變量的數目稱為優化問題的維數，如n個優化變量，則稱為個優化變量，則稱為n維優化問題維優化問題。 1212 ,Tnnxxx xxxx圖1 優化變量

8、所組成的優化空間優化變量所組成的優化空間（a a）二維問題）二維問題 （b b）三維問題）三維問題 只有兩個優化變量的二維優化問題可用圖（只有兩個優化變量的二維優化問題可用圖（a a）所示的平面直角坐標表示；有三個優化變量的三維所示的平面直角坐標表示；有三個優化變量的三維問題可用圖（問題可用圖（b b）所表示的空間直角坐標表示。）所表示的空間直角坐標表示。 優化問題的維數表征優化的自由度，優化變量愈優化問題的維數表征優化的自由度，優化變量愈多，則問題的自由度愈大、可供選擇的方案愈多，但多，則問題的自由度愈大、可供選擇的方案愈多，但難度亦愈大、求解亦愈復雜。難度亦愈大、求解亦愈復雜。 小型優化問

9、題：小型優化問題：一般含有一般含有2 21010個優化變量；個優化變量； 中型中型優化優化問題：問題：10105050個個優化優化變量；變量； 大型大型優化優化問題：問題：5050個以上的個以上的優化優化變量。變量。 如何選定優化變量如何選定優化變量？ 任何一項產品，是眾多變量標志結構尺寸的綜合體。變量任何一項產品，是眾多變量標志結構尺寸的綜合體。變量越多，可以淋漓盡致地描述產品結構，但會增加建模的難度和越多，可以淋漓盡致地描述產品結構，但會增加建模的難度和造成優化規模過大。所以確定優化變量時應注意以下幾點：造成優化規模過大。所以確定優化變量時應注意以下幾點： （1 1）抓主要，舍次要。抓主要

10、，舍次要。 對產品性能和結構影響大的參數可取為優化變量，影響小對產品性能和結構影響大的參數可取為優化變量，影響小的可先根據經驗取為試探性的常量，有的甚至可以不考慮。的可先根據經驗取為試探性的常量，有的甚至可以不考慮。（2 2）根據要解決問題的特殊性來選擇優化變量。根據要解決問題的特殊性來選擇優化變量。 約束條件約束條件 優化問題中有些是工程上所不能接受的，在優化優化問題中有些是工程上所不能接受的，在優化中對優化變量取值有一些限制條件，這些限制條件稱中對優化變量取值有一些限制條件，這些限制條件稱作作約束條件約束條件，簡稱，簡稱約束約束。 約束又可按其數學表達形式分成等式約束和約束又可按其數學表達

11、形式分成等式約束和不等式約束兩種類型：不等式約束兩種類型：(1)(1)等式約束等式約束(2)(2)不等式約束不等式約束( )0hx( )0gx目標函數目標函數 在優化過程中，通過優化變量的不斷向在優化過程中，通過優化變量的不斷向f(X)值改善的方向自值改善的方向自動調整，最后求得動調整，最后求得f(X)值最好或最滿意的值最好或最滿意的X值。在構造目標函值。在構造目標函數時，目標函數的最優值可能是最大值，也可能是最小值。在數時，目標函數的最優值可能是最大值，也可能是最小值。在機械設計中，可作為參考目標函數的有：機械設計中，可作為參考目標函數的有： 體積最小、重量最輕、效率最高、承載能力最大、結構

12、體積最小、重量最輕、效率最高、承載能力最大、結構運動精度最高、振幅或噪聲最小、成本最低、耗能最小、動運動精度最高、振幅或噪聲最小、成本最低、耗能最小、動負荷最小等等。負荷最小等等。 12()()nf Xf xxx， ， ， 為了對優化進行定量評價，必須構造包含優化變量的評價為了對優化進行定量評價，必須構造包含優化變量的評價函數，它是優化的目標，稱為函數，它是優化的目標，稱為目標函數目標函數，以，以f(X)表示。表示。 在優化問題中，可以只有一個目標函數，稱為在優化問題中，可以只有一個目標函數，稱為單目單目標函數標函數。當在同一設計中要提出多個目標函數時，這種。當在同一設計中要提出多個目標函數時

13、，這種問題稱為問題稱為多目標函數多目標函數的最優化問題。在一般的最優化問的最優化問題。在一般的最優化問題中，多目標函數的情況較多。目標函數愈多，建模的題中，多目標函數的情況較多。目標函數愈多，建模的綜合效果愈好，但問題的求解亦愈復雜。綜合效果愈好，但問題的求解亦愈復雜。 在實際工程問題中，常常會遇到在多目標函數的在實際工程問題中，常常會遇到在多目標函數的某些目標之間存在矛盾的情況，這就要求建模者正確某些目標之間存在矛盾的情況，這就要求建模者正確處理各目標函數之間的關系。處理各目標函數之間的關系。 滿足約束條件滿足約束條件 ：12min()(),. .()01,2,()01,2,nnjkf Xf

14、 xxxXRst gXjmh Xkl， ， ，12 ,TnnXx xxR()minf X ()0(1,2, )kh Xkl()0(1,2,)jgXjm求優化變量向量求優化變量向量使目標函數使目標函數 對于復雜的問題，要建立能反映客觀工程實際的、完善的對于復雜的問題，要建立能反映客觀工程實際的、完善的數學模型往往會遇到很多困難，有時甚至比求解更為復雜。數學模型往往會遇到很多困難，有時甚至比求解更為復雜。這時要抓住關鍵因素，適當忽略不重要的成分，使問題合理這時要抓住關鍵因素，適當忽略不重要的成分，使問題合理簡化，以易于列出數學模型，這樣不僅可節省時間，有時也簡化，以易于列出數學模型，這樣不僅可節省

15、時間，有時也會改善優化結果。會改善優化結果。 最優化問題的目標函數通常為求目標函數的最小值。若最優化問題的目標函數通常為求目標函數的最小值。若目標函數的最優點為可行域中的最大值時，則可看成是求目標函數的最優點為可行域中的最大值時，則可看成是求-f（X）的最小值，因為）的最小值，因為min-f（X）與）與max f（X）是等價的。是等價的。最優化問題的分類最優化問題的分類1 1：按有無約束條件分：按有無約束條件分無約束最優化問題無約束最優化問題：（：（Non-restrict Optimization）：）： 可行域：可行域： 無約束最優化問題的數學模型：無約束最優化問題的數學模型： 無約束問題

16、是在空間無約束問題是在空間 上尋求使得目標函數上尋求使得目標函數 達到極小或最小的點達到極小或最小的點 。 nRD )(minxf)(xfnR*x約束最優化問題約束最優化問題（Restrict Optimization）：）： 約束最優化問題是在約束集合（約束最優化問題是在約束集合（Restrict Collection）上尋求使得目標函數上尋求使得目標函數 達到極小或最小的點達到極小或最小的點 。 lkxhmjxgtsxfkj, 2 , 1, 0)(, 2 , 1, 0)(. .)(minlkxhmjxgxDkj, 2 , 1, 0)(, 2 , 1, 0)(|)(xf*x最優化問題的分類最

17、優化問題的分類2 2：按約束條件的形式分類：按約束條件的形式分類：l 等式約束優化問題；等式約束優化問題；l 不等式約束優化問題；不等式約束優化問題；l 混合優化問題；混合優化問題；最優化問題的分類最優化問題的分類3 3：按目標函數和約束條件是否非線性分類：按目標函數和約束條件是否非線性分類：l 線性規劃（線性規劃（Linear Programming）l 非線性規劃非線性規劃（Nonlinear Programming）l 二次規劃二次規劃: :目標函數 為二次函數的 線性規劃問題。 )(xf1 1）根據問題要求，應用專業范圍內的現行理論和經驗等，對）根據問題要求，應用專業范圍內的現行理論和

18、經驗等，對優化對象進行分析，并盡可能反映該專業范圍內的現代技術進優化對象進行分析，并盡可能反映該專業范圍內的現代技術進步的成果。步的成果。2 2）對諸參數進行分析，以確定問題的原始參數、優化常數和）對諸參數進行分析，以確定問題的原始參數、優化常數和優化變量。優化變量。3 3）根據問題要求，確定并構造目標函數和相應的約束條件，）根據問題要求，確定并構造目標函數和相應的約束條件，有時要構造多目標函數。有時要構造多目標函數。 4 4）必要時對數學模型進行規范化，以消除諸組成項間由于）必要時對數學模型進行規范化，以消除諸組成項間由于量綱不同等原因導致的數量懸殊的影響。量綱不同等原因導致的數量懸殊的影響。 以最低成本確定滿足所需營養的最優混合飼料。設每天需以最低成本確定滿足所需營養的最優混合飼料。設每天需要混合飼料的批量為要混合飼料的批量為100100磅，這份飼料必須含：至少磅，這份飼料必須含：至少0.8%0.8%而不而不超過超過1.2%1.2%的鈣的鈣; ;至少至少22%22%的蛋白質的蛋白質; ;至多至多5%5%的粗纖維。假定主要的粗纖維。假定主要配料包括石灰石、谷物、大豆粉。這些配料的主要營養成分為：配料包括石灰石、谷物、大豆粉。這些配料的主要營養成分為：12