《機械優(yōu)化設(shè)計（第7版）》課件 孫靖民 第5章線性規(guī)劃；第6章約束優(yōu)化方法；第7章多目標(biāo)及離散變量優(yōu)化

機械優(yōu)化設(shè)計第五章線性規(guī)劃×第一節(jié)線性規(guī)劃的標(biāo)準形式與基本性質(zhì)§第二節(jié)基本可行解的轉(zhuǎn)換§第三節(jié)單純形方法§

第五章線性規(guī)劃

第四節(jié)單純形法應(yīng)用舉例§第五節(jié)修正單純形法§

目標(biāo)函數(shù)和約束條件都是線性的，像這類約束函數(shù)和目標(biāo)函數(shù)都是為線性函數(shù)的優(yōu)化問題，稱作線性規(guī)劃問題。它的解法在理論和方法上都很成熟，實際應(yīng)用也很廣泛。雖然大多數(shù)工程設(shè)計是非線性的，但是也有采用線性逼近方法求解非線性問題的。此外，線性規(guī)劃方法還常被用作解決非線性問題的子問題的工具，如在可行方向法中可行方向的尋求就是采用線性規(guī)劃方法。當(dāng)然，對于真正的線性優(yōu)化問題，線性規(guī)劃方法就更有用了。

第五章線性規(guī)劃

解：設(shè)生產(chǎn)A、B兩產(chǎn)品分別為x1,x2臺，則該問題的優(yōu)化數(shù)學(xué)模型為：例5-1：某工廠要生產(chǎn)A、B兩種產(chǎn)品，每生產(chǎn)一臺產(chǎn)品A可獲產(chǎn)值2萬元；需占用一車間工作日3天，二車間工作日6天；每生產(chǎn)一臺產(chǎn)品B可獲產(chǎn)值1萬元；需占用一車間工作日5天，二車間工作日2天?，F(xiàn)一車間可用于生產(chǎn)A、B產(chǎn)品的時間15天，二車間可用于生產(chǎn)A、B產(chǎn)品的時間24天。試求出生產(chǎn)組織者安排A、B兩種產(chǎn)品的合理投資產(chǎn)數(shù)，以獲得最大的總產(chǎn)值。§第一節(jié)線性規(guī)劃的標(biāo)準形式與基本性質(zhì)一、線性規(guī)劃實例例5-2：生產(chǎn)甲種產(chǎn)品每件需使用材料9kg、3個工時、4kw電，獲利潤60元。生產(chǎn)乙種產(chǎn)品每件需用材料4kg、10個工時、5kw電，可獲利120元。若每天能供應(yīng)材料360kg，有300個工時，能供200kw電。試確定兩種產(chǎn)品每天的產(chǎn)量，使每天可能獲得的利潤最大？

分析：每天生產(chǎn)的甲、乙兩種產(chǎn)品分別為件（工時約束）（電力約束）（材料約束）(利潤最大)將其化成線性規(guī)劃標(biāo)準形式：求使且滿足例5-3：某廠生產(chǎn)甲、乙兩種產(chǎn)品，已知：①兩種產(chǎn)品分別由兩條生產(chǎn)線生產(chǎn)。第一條生產(chǎn)甲，每天最多生產(chǎn)9件，第二條生產(chǎn)乙，每天最多生產(chǎn)7件；②該廠僅有工人24名，生產(chǎn)甲每件用2工日，生產(chǎn)乙每件用3工日；③產(chǎn)品甲、乙的單件利潤分別為40元和80元。問工廠如何組織生產(chǎn)才能獲得最大利潤？日利潤最大生產(chǎn)能力限制勞動力限制變量非負解:

設(shè)甲、乙兩種產(chǎn)品的日產(chǎn)件數(shù)分別為s.t.建模例1：某公司有鋼材、鋁材、銅材1200t，800t和650t，擬調(diào)往物資緊張的地區(qū)甲、乙、丙。已知甲、乙、丙對上述物資的總需求分別為：900t，800t和1000t。各種物資在各地銷售每噸的獲利如下表所示。試問公司應(yīng)如何安排調(diào)運計劃，才能獲利最大？建立該問題的數(shù)學(xué)模型。鋼材鋁材銅材甲260300400乙210250550丙180400350物資獲利地區(qū)建模例2：某工廠生產(chǎn)A、B、C三種產(chǎn)品，現(xiàn)根據(jù)訂貨合同以及生產(chǎn)狀況制定5月份的生產(chǎn)計劃，已知合同甲為：A產(chǎn)品1000件，單件價格為500元，違約金為100元/件；合同乙為：B產(chǎn)品500件，單件價格為400元，違約金為120元/件；合同丙為：B產(chǎn)品600件，單件價格為420元，違約金為130元/件；C產(chǎn)品600件，單件價格為400元，違約金為90元/件；有關(guān)各產(chǎn)品生產(chǎn)過程所需工時以及原材料的情況見下表。試以利潤為目標(biāo)，建立該工廠的生產(chǎn)計劃線性規(guī)劃模型。工序1工序2工序3原材料1原材料2其他成本產(chǎn)品A/件2323410產(chǎn)品B/件1132310產(chǎn)品C/件2124210總工時或原材料460040006000100008000工時或原材料成本（元）1510102040建模例3：成批生產(chǎn)企業(yè)年度生產(chǎn)計劃的按月分配。在成批生產(chǎn)的機械制造企業(yè)中，不同產(chǎn)品勞動量的結(jié)構(gòu)上可能有很大差別。如：某種產(chǎn)品要求較多的車床加工時間，另一種產(chǎn)品的勞動量可能集中在銑床和其他機床上。因此，企業(yè)在按月分配年度計劃任務(wù)時，應(yīng)考慮到各種設(shè)備的均衡且最大負荷。在年度計劃按月分配時一般要考慮:1）從數(shù)量和品種上保證年度計劃的完成；2）成批的產(chǎn)品盡可能在各個月內(nèi)均衡生產(chǎn)或集中在幾個月內(nèi)生產(chǎn)；3）由于生產(chǎn)技術(shù)準備等方面原因，某些產(chǎn)品要在某個月后才能投產(chǎn)；4）根據(jù)合同要求，某些產(chǎn)品要求在年初交貨；5）批量小的產(chǎn)品盡可能集中在一個月或幾個月內(nèi)生產(chǎn)出來，以便減少各個月的品種數(shù)量等等。如何在滿足上述條件的基礎(chǔ)上，使設(shè)備均衡負荷且最大負荷。線性規(guī)劃數(shù)學(xué)模型的一般形式：求使且滿足說明：1）m=n,唯一解2）m>n,無解3）m<n,無窮解二、線性規(guī)劃的標(biāo)準形式將一般形式的線性規(guī)劃化為標(biāo)準形式的方法x3為松弛變量約束條件為“

”時：約束條件包括兩部分：一是等式約束條件，二是變量的非負要求，它是標(biāo)準形式中出現(xiàn)的唯一不等式形式x3為剩余變量約束條件為“

”時：(2)變量3x1'-3x1"+2x28x1'

-x1"-4x2

14x1',x1",

x2

01、x

0，令x’＝-x。3x1+2x28x1-4x2

14x202、x取值無約束，令x=x'-x"3x1'-3x1"+2x2+x3=8

x1'

-x1"-4x2+x4=14x1',x1",x2,x3,x40例如：x1'

+x211x1'

16x1',x20（3）x兩邊有約束的情況。x1+x25-6

x110x20-6+6x1+6

10+6

令x1'

=x1+6

0

x1'

16(4)右端常數(shù)右端項b＜0時，只需將等式或不等式兩端同乘(一1)，則等式右端項必大于零。三、線性規(guī)劃的基本性質(zhì)圖5.1線性規(guī)劃的幾何意義圖5.1線性規(guī)劃的幾何意義通過頂點Ｃ的直線滿足上述條件，故點Ｃ是該問題的最優(yōu)解。序號123456變量值x10005415/4x20312003/4x3150-45030x424180-600圖5.1中對應(yīng)的頂點ODEBAC可行域可行解：同時滿足所有約束條件的任何一個解x=[x1,x2,…,xn]T。例：多邊形OACD域中任意一個解?；究尚薪猓喝绻窘膺€滿足非負條件xj≥0(j=1,2,…,n),則稱之為基本可行解（既是基本解，又是可行解）。例：表5-1中列出的4個解(或圖6.1對應(yīng)的4個頂點A、C、D、O)。基本解：令線性規(guī)劃標(biāo)準形式中任意(n-m)個變量等于零，若剩余的m個變量構(gòu)成的m個線性方程有唯一解，則稱由此得到的n個變量的解為基本解。例：表5-1中列出的６個解(或圖6.1對應(yīng)的６個頂點A、B、C、D、E、O)。基、基向量、基變量與非基變量基：在系數(shù)矩陣A中，選擇m列線性無關(guān)向量構(gòu)成m×m階非奇異子矩陣B,則稱B為線性規(guī)劃的一個基?；蛄浚航M成基B的列向量pj(j=1,2,…,m)?；兞浚号c基向量對應(yīng)的變量xj(j=1,2,…,m)。用xB表示。非基變量：除基變量外的其余(n-m)個變量。用xN表示。最優(yōu)解：使目標(biāo)函數(shù)達到最小值的基本可行解。例：圖5.1中的點C為最優(yōu)解，對應(yīng)的目標(biāo)函數(shù)值為-33/4.基變量和非基變量是相對于基而言的。線性規(guī)劃問題的以上幾個解的關(guān)系，可用下圖來描述：基本解共10個,每個基本解中有n-m＝2變量取零值?；究尚薪?個線性規(guī)劃的兩個重要性質(zhì)線性規(guī)劃可行解的集合構(gòu)成一個凸集，且這個凸集是凸多面體，它的每一個頂點對應(yīng)于一個基本可行解，即頂點與基本可行解相當(dāng)。線性規(guī)劃的最優(yōu)解如果存在，必然在凸集的某個頂點（即某個基本可行解）上達到。圖5.2線性規(guī)劃解的特殊情形因此，線性規(guī)劃的最優(yōu)解不必在可行域整個區(qū)域內(nèi)搜索，只要在它的有限個基本可行解（頂點）中去尋找即可。

但是，在實際的線性規(guī)劃問題中，其變量的個數(shù)n和約束方程的個數(shù)m都是很大的，其基本可行解的數(shù)目非常多，即使采用計算機也難以實現(xiàn)；同時，僅僅考察基本可行解，也不能確定問題何時有無界解。故沒有必要找出所有的基本可行解以求得最優(yōu)解，而是采用一定的方法如單純形法來解決這個問題。一、從一個基本解轉(zhuǎn)到另一個基本解把約束條件展開：§第二節(jié)基本可行解的轉(zhuǎn)換采用高斯-約當(dāng)法(Gauss-Jordan)進行消元：此過程稱作對變量xk進行轉(zhuǎn)軸運算，xk稱為轉(zhuǎn)軸變量，alk稱為轉(zhuǎn)軸元素。選取另一變量作為轉(zhuǎn)軸變量進行第二次轉(zhuǎn)軸運算，并反復(fù)此過程，我們將得到：這一方程組稱為正則方程組（高斯-亞當(dāng)消元過程）。從而得到一組基本解(基本解中所有基本變量的全體稱為基)：基本變量如果此時繼續(xù)對上述形式的方程組進行附加的一次轉(zhuǎn)軸運算，例如選取作（(t>m)為轉(zhuǎn)軸元素，此時xt進入基，

xs出基。這樣就完成了從一個基本解到另一個基本解的轉(zhuǎn)換解：用a11,

a22作為軸元素進行兩次轉(zhuǎn)軸運算：例：給定如下方程組，試進行基本解的轉(zhuǎn)換運算。得到一組基本解：

x1=-12

x2=-20

x3=x4=x5=0用a25作為軸元素進行第三次轉(zhuǎn)軸運算：又得到一組基本可行解：

x1=3

x5=5

x2=x3=x4=0此時x5進入基，x2出基。二、從一個基本可行解轉(zhuǎn)到另一個基本可行解當(dāng)已經(jīng)得到一組基本可行解，若要求把xk選進基本變量，并使下一組基本解是可行解的話，則在第k列要選取不為任何負值的元素作為轉(zhuǎn)軸元素alk作為轉(zhuǎn)軸元素進行轉(zhuǎn)軸運算：方程組第一行發(fā)生的變化：alk作為軸元素，xk選進基本變量后，xk的取值由零變成了一個正值，則原來各基本變量的取值變?yōu)?

若是基本可行解,應(yīng)該保證各差值最小者為零:決定了離基變量為xi若想用xk取代xl成為可行解中的基本變量，就應(yīng)該選所對應(yīng)的行成為轉(zhuǎn)軸行，即所選取的行要滿足條件:規(guī)則例：基本可行解：

x1=3

x5=5

x2=x3=x4=0基本變量x1、x5

基本可行解的轉(zhuǎn)換：

1）x2、x4系數(shù)全部為負，只能選取x3所在的第3列為轉(zhuǎn)軸行

2）,由于，則取第一行為轉(zhuǎn)軸行,

于是取a'13=2為轉(zhuǎn)軸元素，使x3取代x1成為基本變量。經(jīng)轉(zhuǎn)軸運算得：得基本可行解：

結(jié)論：可把松馳變量作為初始基本可行解中的一部分基本變量。三、初始基本可行解的求法原始約束條件:引入松馳變量:可得一組基本可行解：一、單純形法的基本思想從一個初始基本可行解X0出發(fā)，尋找目標(biāo)函數(shù)有較大下降的一個新的基本可行解X1,代替原來的基本可行解X0，如此完成一次迭代。隨后作出判斷，如果未達到最優(yōu)解，則繼續(xù)迭代下去。因為基本可行解的數(shù)目有限，所以經(jīng)過有限次迭代一定能達到最優(yōu)解。§第三節(jié)單純形方法采用單純形法求解線性規(guī)劃問題，主要應(yīng)解決以下三個問題：（1）如何確定初始基本可行解；（2）如何由一個基本可行解迭代出另一個基本可行解，同時保證目標(biāo)函數(shù)的下降性；（3）如何判斷一個基本可行解是否為最優(yōu)解。二.最優(yōu)解規(guī)則對應(yīng)一組基本可行解：前m個變量組成基本可行解的基本變量相應(yīng)的目標(biāo)函數(shù)值為:經(jīng)過轉(zhuǎn)軸運算得到另一組基本可行解為:其中：進基變量xk出基變量xs對應(yīng)的目標(biāo)函數(shù)為:由于要求∴結(jié)論:一旦所有的,即可停止轉(zhuǎn)軸運算,對應(yīng)的可行解就是最優(yōu)解。r是對線性規(guī)劃問題的解進行最優(yōu)性檢驗的標(biāo)志，稱之為檢驗數(shù)?！摺嗑唧w計算時應(yīng)選取:由于有可能同時有幾組都為負值最速變化規(guī)則1）最速變化規(guī)則決定進基的非基本變量結(jié)論：2）規(guī)則決定了出基的基本變量3）若對基本可行解X，所有檢驗數(shù)rk≥0，則X為最優(yōu)解。例5-3某建筑單位擬蓋一批二人、三人和四人的宿舍單元，要確定每一種宿舍單元的數(shù)目，以獲得最大利潤。其限制條件如下：1）預(yù)算不能超過9000千元。2）宿舍單元總數(shù)不得少于350套。3）每類宿舍單元的百分比為：二人的不超過總數(shù)的20%，三人的不超過總數(shù)的60%，四人的不超過總數(shù)的40%（百分比總和超過100，這是上限）。4）建造價格為：二人的宿舍單元是20千元，三人的宿舍單元是25千元，四人的宿舍單元是30千元。5）凈利潤為：二人的宿舍單元是2千元，三人的宿舍單元是3千元，四人的宿舍單元是4千元。解：略§第四節(jié)單純形法應(yīng)用舉例修正單純形法的迭代過程如下：§第五節(jié)修正單純形法（1）根據(jù)問題的需要，加入松弛變量或人工變量，寫出初始基方陣E，求E-1和基本解（2）計算和，對應(yīng)于非基本變量計算相應(yīng)的。若所有（對極小化問題），則x為最優(yōu)解；否則轉(zhuǎn)至步驟（3）。（3）選取進入新的基方陣的，找出，計算。若所有，則無解；否則轉(zhuǎn)至步驟（4）。修正單純形法的迭代過程如下：§第五節(jié)修正單純形法（4）計算，選取離開基方陣的，形成新的基方陣，轉(zhuǎn)至步驟（5）。（5）計算新的矩陣的逆矩陣和。每迭代一次，就構(gòu)成一個新的逆矩陣。然后轉(zhuǎn)至步驟（1）重復(fù)計算，直到求得最優(yōu)解和相應(yīng)的目標(biāo)函數(shù)值（極小值或極大值）。END?機械優(yōu)化設(shè)計第六章約束優(yōu)化方法×6.1概述6.2隨機方向法

6.3復(fù)合形方法

6.4可行方向法

6.5懲罰函數(shù)法

6.6增廣乘子法

6.11遺傳算法簡述6.10結(jié)構(gòu)優(yōu)化法簡述

6.9二次規(guī)劃法

6.8廣義簡約梯度法

6.7非線性規(guī)劃問題的線性化解法—線性逼近法

機械優(yōu)化設(shè)計中的問題，大多數(shù)屬于約束優(yōu)化設(shè)計問題，其數(shù)學(xué)模型為§第一節(jié)

概述§第一節(jié)

概述

直接解法：隨機方向搜索法、復(fù)合形法、可行方向法

間接解法：內(nèi)點懲罰函數(shù)法、外點懲罰函數(shù)法、混合懲罰函數(shù)法一.有約束問題解法分類：二.直接解法的基本思想：

合理選擇初始點，確定搜索方向，在可行域中尋優(yōu)，經(jīng)過若干次迭代，收斂至最優(yōu)點。

xk+1=xk+αkdkdk::

可行搜索方向。即設(shè)計點沿該方向作微量移動時,目標(biāo)函數(shù)值將下降,且不會超出可行域直接解法通常適用于僅含不等式約束的問題§第一節(jié)

概述特點：①由于求解過程在可行域內(nèi)進行；無論迭代計算何時終止,都可以獲得一個比初始點好的設(shè)計點;②若可行域是凸集，目標(biāo)函數(shù)是定義在凸集上的凸函數(shù)，則收斂到全局最優(yōu)點；否則，結(jié)果與初始點有關(guān)。凸可行域非凸可行域§第一節(jié)

概述原理：將有約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題來解決。方法：以原目標(biāo)函數(shù)和加權(quán)的約束函數(shù)共同構(gòu)成一個新的

目標(biāo)函數(shù)Φ(x,r1,r2)，成為無約束優(yōu)化問題。通

過不斷調(diào)整加權(quán)因子，產(chǎn)生一系列Φ函數(shù)的極小點

序列x(k)*(r1(k),r2(k))k=0,1,2…，逐漸收斂到原目標(biāo)

函數(shù)的約束最優(yōu)解。其中：新目標(biāo)函數(shù)：三.間接解法的基本思想：

懲罰因子：r1,r2§第二節(jié)隨機方向法一.基本思想：隨機產(chǎn)生初始點，隨機產(chǎn)生若干個搜索方向dk，并從中選擇一個能使目標(biāo)函數(shù)值下降最快的方向作為可行搜索方向進行搜索。確保：①新迭代點在可行域中②目標(biāo)函數(shù)值的下降性。x(0)x(L)x(1)x*二.初始點的選擇

隨機方向法的初始點x0必須是一個可行點，既滿足全部

不等式約束條件。初始點可以通過隨機選擇的方法產(chǎn)生。1）輸入設(shè)計變量的下限值和上限值，即2）在區(qū)間（0，1）內(nèi)產(chǎn)生n個偽隨機數(shù)3）計算隨機點x的各分量4）判別隨機點x是否可行，若隨機點可行，用x0←x

為初始點；若非可行點，轉(zhuǎn)到步驟2）重新產(chǎn)生隨

機點，直到可行為止?！斓诙?jié)隨機方向法三.可行搜索方向的產(chǎn)生從k個隨機方向中，選取一個較好的方向。1）在(-1,1)區(qū)間內(nèi)產(chǎn)生偽隨機數(shù)，得隨機單位向量2)取一試驗步長a0，按下式計算k個隨機點§第二節(jié)隨機方向法3）檢驗k個隨機點是否為可行點，除去非可行點，計算余下的可行點的目標(biāo)函數(shù)值，比較其大小，選出目標(biāo)

函數(shù)最小的點xL

。4)比較xL

和x0兩點的目標(biāo)函數(shù)值:①若f(xL)<f(x0)，則取xL

和x0連線方向為可行搜索方向；

②若f(xL)≥f(x0)，則縮小步長α0

，轉(zhuǎn)步驟1）重新計算，

直至f(xL)<f(x0)為止。③α0

縮小到很小仍然找不到一個xL，使f(xL)<f(x0),則

說明x0是一個局部極小點，更換初始點轉(zhuǎn)步驟1）?！斓诙?jié)隨機方向法產(chǎn)生可行搜索方向的條件為：則可行搜索方向為：四、搜索步長的確定步長由加速步長法確定：τ為步長加速系數(shù)，一般取1.3§第二節(jié)隨機方向法五.計算步驟1)選擇一個可行的初始點x0;2)產(chǎn)生k個n維隨機單位向量ej(j=1,2,…,k);3)取試驗步長

0，計算出k個隨機點xj;4)在k個隨機點中，找出可行的的隨機點xL,產(chǎn)生可行搜索方向d=xL

x0.5)從初始點x0出發(fā)，沿可行搜索方向d以步長

進行迭代計算，直到搜索到一個滿足全部約束條件，且目標(biāo)函數(shù)值不再下降的新點x。6)若收斂條件滿足，停止迭代。否則，令x0

x轉(zhuǎn)步驟2例6-1求下列約束優(yōu)化問題的最優(yōu)解

解：用隨機方向法程序，在計算機上運行，迭代13次，求得約束最優(yōu)解：x*=[0.00273.0]T,f(x*)=3

迭代次數(shù)設(shè)計變量x1設(shè)計變量x1目標(biāo)函數(shù)值0-2.02.06.01-0.01681.1171.1964-0.0331.0241.0257-0.1140.7170.73010-0.077-2.998-2.99713-0.002-3.0-3.0一.單純形法：基本思想：以一個目標(biāo)函數(shù)值較小的新點，代替原單純形中目標(biāo)函數(shù)值最大的頂點，組成新的單純形，不斷地迭代，逐漸逼近最優(yōu)點。

二維空間中映射法比較單純形x(1)x(2)x(3)的頂點，f(x(1))>f(x(2))>f(x(3)),

x(1)為最壞點，稱為x(H)，通過映射得到新點x(R)，x(R)＝x(S)＋a(x(S)-x(H))以x(R)來代替x(H)，組成新的單純形x(R)x(2)x(3)。其中f(x(R))<f(x(H));

a>1；稱為映射因子；X(1)=X(H)X(2)X(3)X(S)X(R)=X(4)X(5)X(6)定義：在n維空間中，由n+1個點組成的圖形稱單純形。X*除x(H)外，其它頂點的幾何中心§第三節(jié)復(fù)合形法二.復(fù)合形法：定義：在n維空間中，由k≥n+1個點組成的多面體稱為復(fù)合形?；舅枷耄?/p>

以一個較好的新點，代替原復(fù)合形中的最壞點，組成新的復(fù)合形，以不斷的迭代，使新復(fù)合形逐漸逼近最優(yōu)點。說明：

單純形是無約束優(yōu)化方法，復(fù)合形用于約束優(yōu)化的方法。因為頂點數(shù)較多，所以比單純形更靈活易變。復(fù)合形只能解決不等式約束問題。因為迭代過程始終在可行域內(nèi)進行，運行結(jié)果可靠。三.迭代方法：1.映射法：

例：二維空間中，k=4，復(fù)合形是四面體x(1)x(2)x(3)x(4)，計算得：f(x(1))<f(x(2))<f(x(3))<f(x(4)),確定最壞點x(H)=x(4)，次壞點x(G)=x(3)，最好點x(L)=x(1)。x(S)為除x(H)以外，各點的幾何中心。映射迭代公式：x(R)=x(S)+α(x(S)-x(H))搜索方向：沿x(H)→x(S)的方向。步長因子（映射系數(shù)）α：α>1，建議先取1.3。若求得的x(R)在可行域內(nèi)，且f(x(R))<f(x(H))，則以x(R)代替x(H)組成新復(fù)合形，再進行下輪迭代。●X(S)X(R)X(H)變形法一

——擴張：若f(x(R))<f(x(L))，則可沿此方向擴張取若f(x(E))<f(x(L))，則擴張成功，以x(E)代替x(H)組成新復(fù)合形若f(x(E))>f(x(L))，則擴張失敗，以x(R)代替x(H)組成新復(fù)合形●X(S)X(R)X(H)X(E)變形法二

——收縮：若在映射法中f(x(R))>f(x(H)),則以a＝0.5a重復(fù)采用映射法若直至a<10-5仍不成功，考慮采用收縮法

取

若f(x(K))<f(x(H)),則成功，以x(K)代替x(H)組成新復(fù)合形?！馲(S)X(R)X(H)X(K)4.變形法三

——壓縮：如采用上述方法均無效，還可以將復(fù)合形各頂點向最好點

x(L)靠攏，即采用壓縮的方法改變復(fù)合形的形狀。

取

X(L)四.初始復(fù)合形的形成：人工選擇初始復(fù)合形2.隨機產(chǎn)生初始復(fù)合形：

①先在可行域內(nèi)確定一個初始頂點；②確定xi的上下界：ai、bi；③產(chǎn)生區(qū)間[0,1]中的k-1組偽隨機數(shù)ri(j)；④產(chǎn)生k-1個頂點，xi(j)=αi+ri(j)

(bi-ai)⑤檢查k-1個頂點的可行性，若有q個頂點滿足約束，求q個頂點的幾何中心：

⑥以x(q+1)=x(t)+α(x(q+1)-x(t)),a=0.5將不滿足約束的頂點移向可行域若可行域是非凸集，可能失敗，需減小上、下界再進行。步驟：

1.形成初始復(fù)合形

2.計算各頂點的函數(shù)值,找到最壞點x(H)

、次壞點x(G)和最好點x(L)

3.計算除最壞點外，其余頂點的形心:

檢查形心是否在可行域內(nèi)

4.則可行域為非凸集，取ai＝min[ai

(L),

ai(S)],

bi＝max[ai

(L),

ai(S)]作為上下界；計算xi(j)=αi+ri(j)(bi-ai)，重新構(gòu)成復(fù)合形，轉(zhuǎn)步驟2

5.計算映射點：

x(R)=x(S)+a(x(S)-x(H))

檢查是否在可行域內(nèi)是，a=1.3,轉(zhuǎn)步驟5否，轉(zhuǎn)步驟4是，轉(zhuǎn)步驟6否，a=0.5a,重新計算反射點6.計算f(x(R))，若

7.若a>

:

檢查終止準則

若f(x(R))<f(x(H))，以x(R)代替x(H)重構(gòu)復(fù)合形后轉(zhuǎn)步驟2f(x(R))≥f(x(H))，轉(zhuǎn)步驟7是，則a=0.5a，轉(zhuǎn)步驟5否，則調(diào)用收縮法或壓縮法，重構(gòu)復(fù)合形后轉(zhuǎn)步驟2是，則迭代結(jié)束，以此復(fù)合形的x(L)為x＊否，則以重構(gòu)的復(fù)合形轉(zhuǎn)步驟2六.方法評價：

計算簡單，不必求導(dǎo)，占內(nèi)存??；隨著維數(shù)的增加，效率大大下降；不能解含等式約束的問題；建議：①初始α取1.3。②n+1≤k≤2n，當(dāng)n≤5時，k取值接近2n；當(dāng)n>5時，k取值可小些。一.基本思想：在可行域內(nèi)選擇一個初始點x(0)，確定了一個可行方向和適當(dāng)?shù)牟介L后，按照下式進行迭代計算：

x(k+1)=x(k)+ad通過不斷的調(diào)整可行方向，使迭代點逐步逼近約束最優(yōu)點。§第四節(jié)可行方向法二.搜索策略：

根據(jù)目標(biāo)函數(shù)和約束函數(shù)的不同性態(tài)，選擇不同的搜索策略。

①邊界反彈法：第一次搜索為負梯度方向，終止于邊

界。以后各次搜索方向均為適用可行方向，以最大

步長從一個邊界反彈到另一個邊界，直至滿足收斂

條件。x(1)x(2)x(3)x*x(0)§第四節(jié)可行方向法

②最優(yōu)步長法：第一次搜索為負梯度方向，終止于邊

界。第二次搜索沿適用可行方向作一維搜索以最優(yōu)

步長因子求得最優(yōu)點。反復(fù)以上兩步，直至得到最

優(yōu)點x*。x(1)x(2)x(3)x*x(0)§第四節(jié)可行方向法

③貼邊搜索法：第一次搜索為負梯度方向，終止于邊界。以后各次搜索貼邊（約束面）進行。若適時約束面是線性約束，每次搜索到約束面的交集時，移至另一個約束面，經(jīng)過有限的幾步就可以收斂到最優(yōu)點。x(1)x(2)x*x(0)§第四節(jié)可行方向法

若約束面是非線性時，從x(k)點沿切線（面）方向d(k)

搜索，會進入非可行域。容差帶δ：

建立約束面的容差帶+δ，從x(k)

出發(fā)，沿d(k)方向搜索到d(k)方向與g(x)+δ=0的交點x’后，再沿適時約束的負梯度方向返回約束面的x(k+1)點。x(k)x(k+1)g(x)g(x)+

δx’-▽g(x)d(k)§第四節(jié)可行方向法調(diào)整步長因子α1

：

x(k+1)=x’-a1▽g(x’)將g(x)在x’點泰勒展開，取一階近似式：

g(x)≈g(x’)+[▽g(x’)]T(x-x’)進而得到：

g(x(k+1))≈g(x’)+[▽g(x’)]T[-a1▽g(x’)]為了讓x(k+1)到達約束面，令g(x(k+1))=0得:§第四節(jié)可行方向法三.可行方向的確定可行方向應(yīng)該滿足設(shè)計點可行及目標(biāo)函數(shù)值下降兩個條件

①可行條件:

[▽gj(xk)]T

dk≤0

j=1,2,…J(起作用約束的個數(shù))▽g(xk)dk▽g1(xk)▽g2(xk)dk§第四節(jié)可行方向法三.可行方向的確定

②目標(biāo)函數(shù)值下降條件:

[▽f(xk)]T

dk<0

▽f(xk)dk§第四節(jié)可行方向法三.可行方向的確定[▽gj(xk)]T

dk≤0

保證在可行域內(nèi)[▽f(xk)]T

dk<0

保證目標(biāo)函數(shù)值下降

可行方向§第四節(jié)可行方向法①優(yōu)選方向法四.可行方向產(chǎn)生方法式中：d為求解變量，▽gj(xk)]T

、[▽f(xk)]T為定值，可用線性規(guī)劃方法求解§第四節(jié)可行方向法②梯度投影法：可行方向:

其中:p為投影算子J-起作用的約束個數(shù)§第四節(jié)可行方向法①取最優(yōu)步長五.步長的確定若x(k+1)為可行點，a＊作為本次迭代步長

x(k+1)=x(k)+a＊da＊dx(k+1)

§第四節(jié)可行方向法②取最大步長aM五.步長的確定a＊daMdx(k+1)

x(k+1)=x(k)+a＊d§第四節(jié)可行方向法收斂條件2）設(shè)計點xk滿足庫恩-塔克條件1）設(shè)計點xk及約束允差滿足例用可行方向法求約束優(yōu)化問題的約束最優(yōu)解。Minf(x1,x2)=x12+2x22-10x1-x1x2-4x2+60s.t.g1(x)=x10

g2(x)=x20g3(x)=x160g4(x)=x280g5(x)=x1+x2110解：取初始點x0=[01]T，為約束邊界g1(x)=0上的一點。第一次迭代用優(yōu)選方向法確定可行方向。首先計算x0點的目標(biāo)函數(shù)f(x0)和約束函數(shù)g1(x0)的梯度為在可行下降扇形區(qū)內(nèi)尋找最優(yōu)方向，需求解一個以可行方向d=[d1d2]T為設(shè)計變量的線性規(guī)劃問題，其數(shù)學(xué)模型為：最優(yōu)方向是d*=[0.9840.179]T，它是目標(biāo)函數(shù)等值線（直線束）和約束函數(shù)d12+d22=1（半徑為1的圓）的切點。第一次迭代的可行方向為d0=d*。第一次迭代的可行方向為d0=d*。若步長取

0=6.098，則

可見第一次迭代點x1

在約束邊界g3(x1)=0上。

第二次迭代用梯度投影法來確定可行方向。迭代點x1的目標(biāo)函數(shù)負梯度-

f(x1)=[0.0925.818]T，不滿足方向的可行條件?，F(xiàn)將f(x1)投影到約束邊界g3(x)=0上，

計算投影算子P本次迭代的可行方向為顯然，d1為沿約束邊界g3(x)=0的方向。若取1=2.909，則本次迭代點即為該問題的約束最優(yōu)點x*則得約束最優(yōu)解

將有約束的優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題來求解。前提：一是不能破壞約束問題的約束條件，二是使它歸結(jié)到原約束問題的同一最優(yōu)解上去。

構(gòu)成一個新的目標(biāo)函數(shù)：§第五節(jié)

懲罰函數(shù)法懲罰項懲罰因子懲罰函數(shù)從而保證懲罰項必須具有以下極限性質(zhì)：根據(jù)懲罰項的不同構(gòu)成形式，懲罰函數(shù)法又可分為內(nèi)點懲罰函數(shù)法、外點懲罰函數(shù)法和混合懲罰函數(shù)法§第五節(jié)

懲罰函數(shù)法一.內(nèi)點懲罰函數(shù)法基本思想內(nèi)點法將新目標(biāo)函數(shù)Φ(x,r)構(gòu)筑在可行域D內(nèi)，隨著懲罰因子r(k)的不斷遞減，生成一系列新目標(biāo)函數(shù)Φ(xk,

r(k))，在可行域內(nèi)逐步迭代，產(chǎn)生的極值點xk*(r(k))序列從可行域內(nèi)部趨向原目標(biāo)函數(shù)的約束最優(yōu)點x*。例：min.f(x)=x

s.t.g(x)=1-x≤0X1*X2*X*2.懲罰函數(shù)的形式

①

②其中：懲罰（加權(quán)）因子

降低系數(shù)c：0<c<1當(dāng)x在可行域內(nèi)遠離約束邊界時：當(dāng)x由可行城內(nèi)靠近約束邊界時：障礙項3.幾個參數(shù)的選擇懲罰因子初始值r(0)

的選擇：

過大、過小均不好，建議考慮選擇r(0)=1或者：2.降低系數(shù)c的選擇：c的典型值為0.1～0.7。3.初始點x(0)

的選擇：要求：①在可行域內(nèi)；②不要離約束邊界太近。方法：①人工估算，需要校核可行性；②計算機隨機產(chǎn)生，也需校核可行性。

③搜索方法：

任意給出一個初始點；判斷其可行性，若違反了S個約束，求出不滿足約束中的最大值：

應(yīng)用優(yōu)化方法減少違反約束：

以求得的設(shè)計點作為新初始點，繼續(xù)其判斷可行性，若仍有不滿足的約束，則重復(fù)上述過程，直至初始點可行。④

判斷是否收斂：4.步驟：①選取合適的初始點x(0)

，以及r(0)、c、計算精度ε1、ε2

，令k=0；

②

構(gòu)造懲罰（新目標(biāo)）函數(shù)；③調(diào)用無約束優(yōu)化方法，求新目標(biāo)函數(shù)的最優(yōu)解xk*和

Φ(xk,r(k))；若均滿足，停止迭代，有約束優(yōu)化問題的最優(yōu)點為x*=xk*；若有一個準則不滿足，則令并轉(zhuǎn)入第3步，繼續(xù)計算。例：用內(nèi)點法求下列問題的最優(yōu)解：構(gòu)造懲罰函數(shù)112二.外點懲罰函數(shù)法1.基本原理外點法將新目標(biāo)函數(shù)Φ(x,r)構(gòu)筑在可行域D外，隨著懲罰因子r(k)的不斷遞增，生成一系列新目標(biāo)函數(shù)Φ(xk,r(k))，在可行域外逐步迭代，產(chǎn)生的極值點xk*(r(k))序列從可行域外部趨向原目標(biāo)函數(shù)的約束最優(yōu)點x*。新目標(biāo)函數(shù)：例：求下述約束優(yōu)化問題的最優(yōu)點。

min.f(X)=x

x∈R1s.tg(X)=1-x≤0懲罰函數(shù)可取為2)懲罰因子1)當(dāng)設(shè)計點在可行域內(nèi)時,懲罰項為0,不懲罰;當(dāng)設(shè)計點在可行域外

時,懲罰項大于0,有懲罰作用.外點法可以用來求解含不等式和等式約束的優(yōu)化問題。衰減項3.幾個參數(shù)的選擇①r(0)

的選擇:r(0)

過大，會使懲罰函數(shù)的等值線變形或偏心，求極

值困難。r(0)

過小，迭代次數(shù)太多。r(0)

＝1或者②x(0)

的選擇：基本上可以在可行域內(nèi)外，任意選擇。③遞增系數(shù)c的選擇：通常選擇5～10，可根據(jù)具體題目，進行試算調(diào)整。內(nèi)點法特點：

（1）初始點必須為嚴格的可行點

（2）不適于具有等式約束的數(shù)學(xué)模型

（3）迭代過程中各個點均為可行設(shè)計方案

（4）一般收斂較慢

（5）初始懲罰因子要選擇得當(dāng)

（6）懲罰因子為遞減，遞減率c有0<c<1

外點法特點：

（1）初始點可以任選

（2）對等式約束和不等式約束均可適用

（3）僅最優(yōu)解為可行設(shè)計方案

（4）一般收斂較快

（5）初始罰因子要選擇得當(dāng)

（6）罰因子為遞增，遞增率c有c>1三.

混合懲罰函數(shù)法1.基本思想采用內(nèi)點法和外點法相結(jié)合的混合懲罰函數(shù)法，以發(fā)揮內(nèi)點法和外點法的特點，處理既有等式約束，又有不等式約束的優(yōu)化設(shè)計問題。2.懲罰函數(shù)的形式一般既包括障礙項，也包括衰減項。懲罰函數(shù)法優(yōu)點：原理簡單，算法易行，適應(yīng)范圍廣，可利用無約束最優(yōu)化方法資源。缺點：（1）初始懲罰因子r(0)取值不當(dāng)可導(dǎo)致懲罰函數(shù)變得病態(tài)，

使無約束優(yōu)化計算困難。（2）理論上講，只有懲罰因子r

(k)

0（內(nèi)點法）或

r(k)

趨于無窮（外點法）時，算法才收斂，因此序

列迭代過程收斂速度慢。增廣乘子法外點懲罰函數(shù)＋拉格朗日函數(shù)

計算過程穩(wěn)定，計算效率超過懲罰函數(shù)法拉格朗日函數(shù)一、拉格朗日乘子法（升維法）§第六節(jié)

增廣乘子法l+n個方程l+n個未知變量具有相同的最優(yōu)解X*例:用拉格朗日乘子法求下列問題的最優(yōu)解解構(gòu)造拉格朗日函數(shù)令▽L=0,得到求解得：構(gòu)造拉格朗日函數(shù)構(gòu)造外點懲罰函數(shù)二.等式約束的增廣乘子法

采用拉格朗日乘子法時求解有難度,而罰函數(shù)法當(dāng)?shù)c接近邊界時函數(shù)常有病態(tài),此法的思路是把兩者結(jié)合起來。其增廣拉格朗日函數(shù)為:等式約束增廣乘子法不論r(k)取何值，增廣乘子函數(shù)與原函數(shù)具有相同的約束極值點X*，與拉格朗日函數(shù)有相同的拉格朗日乘子向量。等式約束增廣乘子法等式約束增廣乘子法增廣乘子法中的乘子迭代等式約束增廣乘子法參數(shù)選取沒有其它信息情況下，初始乘子向量

增廣乘子函數(shù)和外點懲罰函數(shù)形式相同；從第二次迭代開始，乘子向量按式子進行校正。懲罰因子初始值r(0)按照外點法取。從第二次迭代開始，懲罰因子按下式遞增：懲罰因子遞增系數(shù)，C=10判別數(shù)，通常取0.25等式約束增廣乘子法計算步驟：

選取設(shè)計變量的初始點x0，懲罰因子初值r0，增長系數(shù)β，判別數(shù)δ，收斂精度ε，乘子向量λp0=0

(p=1,2,…l),迭代次數(shù)k=0；構(gòu)造增廣乘子函數(shù)M(x,λ,r)，并用無約束方法求

min

M(x,λ,r)，得無約束最優(yōu)解xk=x*(λk,rk)計算校正乘子向量如果，迭代終止，約束最優(yōu)解為x*=xk，λ*=λk+1;否則轉(zhuǎn)步驟6計算懲罰因子再令k=k+1，轉(zhuǎn)步驟2例:用拉格朗日乘子法求下列問題的最優(yōu)解解構(gòu)造增廣乘子函數(shù)確定初始參數(shù)：

C＝2,

λ0=0,

r0=0.1，利用解析法求min

M(X,λ,r)，令▽M(X,λ,r)＝0，可得最優(yōu)解：

krkλkxk10.10(0.0714,0,2142)20.20.0714(0.1507,0.4523)30.40.1507(0.2118,0.6355)40.80.2118(0.3409,0.7227)51.60.2409(0.2487,0.7463)63.20.2487(0.2499,0.7497)76.40.2499(0.2499,0.7499)迭代6次得到最優(yōu)解,迭代結(jié)果如下:精確解:

X*=[0.25,0.75],

f(X*)=0.125不等式約束增廣乘子法用于求解不等式約束優(yōu)化問題。引入松弛變量Z＝[z1,

z2

,

…,

zm]T,并且令則不等式約束優(yōu)化問題轉(zhuǎn)化為等式優(yōu)化問題不等式約束增廣乘子法構(gòu)造增廣乘子函數(shù)由于引入松弛變量Z，使原有的n維極值問題擴充為n+m維問題，計算工作量和求解難度增大，可簡化。不等式約束增廣乘子法同時具有等式和不等式約束的增廣乘子法第七節(jié)非線性規(guī)劃問題的線性化解法——線性逼近法一、序列線性規(guī)劃法這個方法的基本思想：在某個近似解處將約束函數(shù)和目標(biāo)函數(shù)進行泰勒展開，只保留一次項，從而將非線性規(guī)劃問題變成線性規(guī)劃問題。求解此線性規(guī)劃，并將其最優(yōu)解作為原來問題新的近似解，再展開成新的線性規(guī)劃問題，再求解。如此重復(fù)下去，一直到相鄰兩次最優(yōu)解足夠接近時為止。缺點：序列線性規(guī)劃法收斂較慢，且最后的近似解不滿足非線性約束，有時還會出現(xiàn)不收斂的情況。為了獲得較好的收斂性而采用一些改進的方法，如割平面法、小步梯度法等。第七節(jié)非線性規(guī)劃問題的線性化解法——線性逼近法二、割平面法割平面法主要用于不等式約束的非線性規(guī)劃問題。若問題是凸規(guī)劃問題，則這種方法將收斂于問題的最優(yōu)解。對于非凸規(guī)劃問題，某些約束的線性近似可能把原問題可行域切掉一些，可能最優(yōu)點恰好就在這些被切去的區(qū)域里。因為這種方法實際上是用線性近似約束把原問題可行域切掉一部分，所以稱為“割平面法”。第七節(jié)非線性規(guī)劃問題的線性化解法——線性逼近法三、小步梯度法線性逼近法求解是指按下面的迭代公式對設(shè)計點進行修改，從而獲得新的設(shè)計點的方法。當(dāng)把上式寫成而是一個小數(shù)值時，可把此式作為一個約束列入原問題中去求解。當(dāng)用梯度法求解時，這種方法就是用一個小數(shù)值限制各尋優(yōu)方向步長的方法，可稱為小步梯度法。只有當(dāng)是可行解時，此法收斂較快，否則過程收斂較慢。第七節(jié)非線性規(guī)劃問題的線性化解法——線性逼近法四、非線性規(guī)劃法對于燈飾和不等式約束的給線性規(guī)劃問題，有一種解法是把最速下降法（梯度法）和線性規(guī)劃法結(jié)合起來求解。它的解法步驟如下：第一步，當(dāng)是不可行點時，用最速下降法把它拉到滿足約束集內(nèi)。此時的函數(shù)形式取為：第二步，再用線性規(guī)劃法。每次線性規(guī)劃階段移步后，要進行一次判別，看是否滿足此法的使用效果好于前兩種方法。第七節(jié)非線性規(guī)劃問題的線性化解法——線性逼近法四、非線性規(guī)劃法對于線性規(guī)劃問題，也可以通過泰勒級數(shù)展開的方法把約束取成線性的，目標(biāo)函數(shù)取成二次函數(shù)。這種約束為線性而目標(biāo)函數(shù)是二次函數(shù)的最優(yōu)問題。有多種求解二次規(guī)劃問題的方法，其中一種實際上可以看成是線性規(guī)劃問題中單純形法的推廣。因此，用這樣的處理辦法來解決非線性規(guī)劃問題可以稱為二次規(guī)劃問題的線性規(guī)劃解法。第八節(jié)廣義簡約梯度法廣義簡約梯度法也稱GRG法。它是簡約梯度法推廣到求解具有非線性約束的優(yōu)化問題的一種方法。這種方法是目前求解一般非線性優(yōu)化問題的最有效的算法之一。一、簡約梯度法簡約梯度法僅用來求解具有線性等式約束的優(yōu)化問題。算法的基本思想是設(shè)法處理約束函數(shù)，將原問題轉(zhuǎn)化成僅具有變量邊界約束的優(yōu)化問題，然后求解。第八節(jié)廣義簡約梯度法二、廣義簡約梯度法廣義簡約梯度法可以用來求解具有非線性等式約束和變量界限約束的優(yōu)化問題，其數(shù)學(xué)模型為式中的為變量的下界和上界值。第八節(jié)廣義簡約梯度法三、不等式約束函數(shù)的處理和換基問題1.不等式簡約梯度法求解的處理方法用廣義簡約梯度法求解具有不等式約束函數(shù)的優(yōu)化問題時，需引進新變量，將不等式約束函數(shù)轉(zhuǎn)化成等式約束函數(shù)，即將該問題轉(zhuǎn)化成與式（6-107）相同的形式，然后按前述方法求解。第八節(jié)廣義簡約梯度法三、不等式約束函數(shù)的處理和換基問題2.基變量的選擇和換基問題按廣義簡約梯度法原理，首先應(yīng)將涉及變量分成基變量和非基變量，對于只具有等式函數(shù)的問題，應(yīng)在n設(shè)計變量中選擇m個變量作為基變量，對于具有不等式約束函數(shù)的問題，應(yīng)在n+l個變量中選擇m+l個變量作為基變量（l為松弛變量數(shù)），其余的變量為非基變量。為了使基變量的變化盡量少，應(yīng)選擇遠離其邊界的變量為基變量。同時，為了保證基矩陣非奇異及求逆計算的穩(wěn)定，要求基矩陣的主元不能太小以及同列中的其他元素與主元之比不能太大。在迭代過程中，若某一基變量等于0，或等于邊界值時，應(yīng)換基變量，即選擇一非基變量來代替該基變量。第九節(jié)二次規(guī)劃法二次規(guī)劃法的基本原理是將元問題轉(zhuǎn)化為一系列二次規(guī)劃的子問題。求解子問題，得到本次迭代的搜索方向，沿搜索方向?qū)?yōu)，最終逼近問題的最優(yōu)點，因此，這種方法又稱為序列二次規(guī)劃法。另外，算法是利用擬牛頓法（變尺度法）來近似構(gòu)造海塞矩陣，以建立二次規(guī)劃子問題，故又可稱為約束變尺度法，這種方法被認為是目前最先進的非線性規(guī)劃計算方法。第九節(jié)二次規(guī)劃法二次規(guī)劃法的迭代步驟如下：1.給定初始值，令（單位矩陣）。2.計算原問題的函數(shù)值、梯度值，構(gòu)造二次規(guī)劃子問題。3.求解二次規(guī)劃子問題，確定新的乘子矢量和搜索方向。4.沿進行一維搜索，確定步長，得到新的近似極小點。5.若滿足收斂精度則停止計算，否則轉(zhuǎn)至下步。6.采用擬牛頓公式（如BFGS公式）對進行修正，得到，返回步驟2.第十節(jié)結(jié)構(gòu)優(yōu)化簡述在工程結(jié)構(gòu)設(shè)計中，通常要在保證性能約束條件下，滿足結(jié)構(gòu)體積盡量小以減輕重量或節(jié)約材料。在進行結(jié)構(gòu)設(shè)計時，性能約束一般是取結(jié)構(gòu)固有頻率禁區(qū)約束、振型約束、結(jié)構(gòu)變形或許用應(yīng)力約束。以準則法思想為基礎(chǔ)的優(yōu)化準則法，對于結(jié)構(gòu)優(yōu)化來說，它是一種收斂速度快、求解目標(biāo)函數(shù)和約束函數(shù)次數(shù)少的一種方法。準則法思想是由“滿應(yīng)力設(shè)計”和“同步失效準則”原則，且主要是針對桁架結(jié)構(gòu)的最輕設(shè)計發(fā)展起來的。第十節(jié)結(jié)構(gòu)優(yōu)化簡述一、準則方程二、迭代乘子C三、優(yōu)化準則法和數(shù)學(xué)規(guī)劃法的相似性質(zhì)四、形狀優(yōu)化和拓撲布局優(yōu)化五、小結(jié)第十節(jié)結(jié)構(gòu)優(yōu)化簡述一、準則方程任何一個設(shè)計方案是否是最優(yōu)的基本檢驗方法就是看它是否滿足K-T條件。優(yōu)化問題的準則方程是由所討論的優(yōu)化問題的最優(yōu)解應(yīng)滿足K-T條件推導(dǎo)出來的。這時的迭代公式用來尋求滿足K-T條件的極小值點（設(shè)計點）。第十節(jié)結(jié)構(gòu)優(yōu)化簡述二、迭代乘子C考慮到結(jié)構(gòu)性能約束函數(shù)常是隱含設(shè)計變量的非線性方程，對式（6-127）的準則方程的求解可采用線性迭代的方法。這種求解從某個初始設(shè)計變量開始，按迭代公式反復(fù)進行線性迭代，直到求出滿足準則方的設(shè)計變量。這種優(yōu)化準則就具有數(shù)學(xué)規(guī)劃法的性質(zhì)，是準則思想和數(shù)學(xué)規(guī)劃的結(jié)合，故稱為優(yōu)化準則法。第十節(jié)結(jié)構(gòu)優(yōu)化簡述三、優(yōu)化準則法和數(shù)學(xué)規(guī)劃法的相似性質(zhì)雖然在滿應(yīng)力設(shè)計的一類準則設(shè)計中，不考慮目標(biāo)函數(shù)值，因而其解不是最優(yōu)解。這反映了它和數(shù)學(xué)規(guī)劃法的不同，這是它的特點。但是，在優(yōu)化準則法中，由于準則方程是目標(biāo)函數(shù)梯度換和諸約束梯度的線性組合，所以已經(jīng)失去了原來的滿應(yīng)力類設(shè)計與目標(biāo)函數(shù)無關(guān)的特點，而具有數(shù)學(xué)規(guī)劃法的性質(zhì)。它實際上已經(jīng)把準則法和數(shù)學(xué)規(guī)劃法結(jié)合起來了。第十節(jié)結(jié)構(gòu)優(yōu)化簡述四、形狀優(yōu)化和拓撲布局優(yōu)化一種以極大值原理為基礎(chǔ)——把優(yōu)化問題表示為泛函極值形式的求解結(jié)構(gòu)形式的理論和方法的應(yīng)用，實現(xiàn)了從有限維的參數(shù)優(yōu)化向無限維的形狀優(yōu)化和拓撲及布局優(yōu)化的跨越。這種無限維的優(yōu)化方法是一種連續(xù)型的分析方法，它是基于結(jié)構(gòu)的彈性力學(xué)模型和泛函極值的求解方法。連續(xù)體的形狀和拓撲及布局優(yōu)化設(shè)計需要建立研究對象的幾何和分析模型，這既涉及用相應(yīng)的優(yōu)化設(shè)計變量對邊界形狀和布局進行有效的描述，也需要處理與有限元分析相關(guān)的敏度分析和網(wǎng)絡(luò)生成等問題。第十節(jié)結(jié)構(gòu)優(yōu)化簡述五、小結(jié)求解非線性規(guī)劃問題可概括為如下三種迭代格式：1）（搜索格式）2）（替代格式）3）（收斂格式）前兩種屬于數(shù)學(xué)規(guī)劃類方法，后一種屬于優(yōu)化準則方法。第十節(jié)結(jié)構(gòu)優(yōu)化簡述五、小結(jié)總得策略：一是在可行域內(nèi)直接搜索最優(yōu)設(shè)計點；二是把非線性問題轉(zhuǎn)化為線性問題，采用線性規(guī)劃方法求解；三是把約束問題轉(zhuǎn)化為無約束問題，采用無約束方法求解。具體方法是：1）直接方法——以約束條件為界面，形成一個解的可行域，在可行域范圍內(nèi)直接采用無約束優(yōu)化方法求解。2）線性逼近法——把非線性函數(shù)在現(xiàn)行點線性化，采用較成熟的線性規(guī)劃方法。3）簡接方法——先把約束問題轉(zhuǎn)化為無約束問題，再采用無約束優(yōu)化方法求解。這種方法可以分為兩類，即降維方法和升維方法。Powell法、梯度法隨機方向法、復(fù)合形法、懲罰函數(shù)法常規(guī)優(yōu)化算法啟發(fā)式算法(現(xiàn)代優(yōu)化計算方法)

適于求解高非線性、多約束、多極值問題遺傳算法（Geneticalgorithms）神經(jīng)網(wǎng)絡(luò)優(yōu)化算法（Neuralnetworksoptimization）混合優(yōu)化算法（Hybridoptimization）§第十一節(jié)

遺傳算法簡述一.背景：生物進化基本循環(huán)圖

依據(jù)生物進化論的“適者生存”規(guī)律而提出：§第十一節(jié)

遺傳算法簡述

遺傳算法的主要生物進化特征體現(xiàn)在：（1）進化發(fā)生在解的編碼（染色體）上。（2）自然選擇規(guī)律決定優(yōu)秀的染色體產(chǎn)生超過平均數(shù)的后代。遺傳算法通過優(yōu)化目標(biāo)構(gòu)造適應(yīng)函數(shù)以達到好的染色體超過平均數(shù)的后代。（3）染色體結(jié)合時，雙親的遺傳基因結(jié)合使得子女保持父母的特征。（4）當(dāng)染色體結(jié)合后，隨機變異會造成子代與父代不同。§第十一節(jié)

遺傳算法簡述二.基本思想：

遺傳算法在求解優(yōu)化問題時首先對求解空間的各個解進行編碼。在尋優(yōu)過程中，通過對染色體

進行結(jié)合（選擇、交配和變異），不斷產(chǎn)生新的解，進而根據(jù)適應(yīng)函數(shù)在新解中選擇部分染色體繼續(xù)進行結(jié)合，直至最終找到最好的解。§第十一節(jié)

遺傳算法簡述

例用遺傳算法求minf(x1,x2)=x1+x2

，當(dāng)x1和x2為整數(shù)時的整數(shù)解，且解：若用4位二進制編碼表示一個設(shè)計變量xi，則一個解(x1,x2)需用8位二進制編碼表示：一個解（個體的染色體）適應(yīng)函數(shù)f(x1,x2)N1：1011001114N2：1101111027N3：1000110121N4：0110010111N4：01100101交配N1：10110011N4：01100101交配N3：10001101N1’：01110111=14N2’：10100001=11N3’：01000101=9N4’：10101101=23遺傳算法4個組成部分：編碼和解碼、適應(yīng)函數(shù)、遺傳算子和控制參數(shù)若以這4個個體為群體，按求解的要求，適應(yīng)函數(shù)值小的染色體的生存概率較大，則能競爭上的是N1、N3和N4點，其交配方式如下：通過分別交換基因，實現(xiàn)了交配，得到了4個新個體N1’、N2’、N3’和N4’。若對某個個體（例如N2’）進行基因變異（1→0），可得N2”:00100001(=3)三.算法的基本步驟：S.1選擇優(yōu)化問題求解的一種編碼；S.2隨機產(chǎn)生N個染色體的初始群體{pop(k),k=0}；S.3對群體中的每個染色體popi(k)計算適應(yīng)函數(shù)

fi=fitness(popi(k))S.4若滿足終止規(guī)則，則轉(zhuǎn)向S.9，否則計算概率S.5以概率pi從pop

(k)中隨機選一些染色體構(gòu)成一個新群體（其中可以重復(fù)選pop

(k)中的元素）

newpop(k+1)={popi(k),i=1,2,···,N}§第十一節(jié)

遺傳算法簡述三.算法的基本步驟：S.6通過交配，按交配概率pc得到一個有N個染色體的交配群體crosspop(k+1)；S.7以一個較小的變異概率pm，使得一個染色體的基因發(fā)生變異，形成變異群體mutpop(k+1)；S.8令k=k+1和popi(k)=mutpop(k+1)，返回S.3；S.9終止計算，輸出最優(yōu)結(jié)果?！斓谑还?jié)

遺傳算法簡述四.算法實現(xiàn)的幾個技術(shù)問題——編碼和解碼編碼——由設(shè)計空間向編碼空間的映射。將設(shè)計解用字符串表示的過程。編碼的選擇是影響算法性能和效率的重要因素。解碼——由編碼空間向設(shè)計空間的映射?！斓谑还?jié)

遺傳算法簡述幾種常見的編碼方式四.算法實現(xiàn)的幾個技術(shù)問題——編碼和解碼

編碼方式示例說明二進制編碼染色體中的基因值只能是二值符號集｛0，1｝中一個實數(shù)編碼染色體的基因值是設(shè)計變量的真實值符號編碼每一位基因只能有代碼含義，無數(shù)值含義序列編碼例如在旅行商問題中，此編碼表示按順序”1→3→5→7→9→2→4→6→8→1”依次訪問各個城市110100115.806.702.183.56ABCDEF13579246§第十一節(jié)

遺傳算法簡述對于求極大化的目標(biāo)函數(shù)（max

f(x)），可通過下面轉(zhuǎn)換建立與fitness(x)的映射關(guān)系:四.算法實現(xiàn)的幾個技術(shù)問題——適應(yīng)函數(shù)fitness(x)

對于求極小化的目標(biāo)函數(shù)（min

f(x)），可通過下面轉(zhuǎn)換建立與fitness(x)的映射關(guān)系:Cmin和Cmax為可調(diào)參數(shù)，所取的值應(yīng)使適應(yīng)函數(shù)fitness(x)恒大于0。適應(yīng)函數(shù)——用于對個體進行評價，即反映個體對環(huán)境適應(yīng)能力。是優(yōu)化進程發(fā)展的依據(jù)。其值必須大于等于零§第十一節(jié)

遺傳算法簡述群體規(guī)模N——是影響算法性能和效率的因素之一。規(guī)模太小，不能提供足夠多的采樣點；規(guī)模太大，計算量大，耗時長。通常取N介于n（編碼長度）和2n之間，或依據(jù)經(jīng)驗在范圍內(nèi)取值。四.算法實現(xiàn)的幾個技術(shù)問題——算法參數(shù)

交配概率pc

——用于控制交配操作的頻率，通常取0.4~0.9之間。概率太大，種群更新過快，會使高適應(yīng)函數(shù)值的個體過快被破壞；概率太小，交配操作很少進行，搜索速度慢，耗時長。變異概率pm

——加大種群多樣性的重要因素，通常取0.001~0.1之間。概率太大，則使遺傳算法退化成隨機搜索算法；概率太小，產(chǎn)生新個體的機會太小。§第十一節(jié)

遺傳算法簡述復(fù)制、交配、變異四.算法實現(xiàn)的幾個技術(shù)問題——遺傳算子

復(fù)制(選擇)

—選擇用于繁殖后代的雙親。體現(xiàn)“適者生存”，適應(yīng)度高，生存概率大。依據(jù)選擇概率pi=fi/Σfi進行。交配(交叉)

—兩個相互配對的染色體（雙親）按某種方式相互交換其部分基因而生成兩個新的個體?！斓谑还?jié)

遺傳算法簡述四.算法實現(xiàn)的幾個技術(shù)問題——遺傳算子

雙親A100100交配B010010后代A’100010B’010100雙親A1011001

交配B0010110后代A’1010101B’0011010一點交配（二進制）：多點交配（二進制）：§第十一節(jié)

遺傳算法簡述四.算法實現(xiàn)的幾個技術(shù)問題——遺傳算子

0101010變異0101110變異

—在交配之后進行。將個體染色體編碼字符中的某些基因用其他等位基因