【文章內(nèi)容簡介】 后，如果目標(biāo)函數(shù)是二次型函數(shù)，則必然可收斂到極小點。采用這種方法構(gòu)成共扼方向，要用到函數(shù)的海賽矩陣，因此計算復(fù)雜，對A的要求也高，在實用上是存在困難的?，F(xiàn)在我們對以上公式作一些適當(dāng)?shù)暮喕?，得到求βk1，的公式如下：此廣中不合海賽矩陣A，因而免去了許多煩鎖的計算，而且不用擔(dān)心A的正定及非奇異問題,對初始點的選擇也就無任何限制了。共扼梯度法的計算步驟及迭代公式如下(1)任選初始點Xo，則：如此可構(gòu)造n個共扼方向s0，sl，s2，…，sn。(3)對于每個迭代點及每個共扼方向，求a*，使：(4)按收斂判斷準(zhǔn)則判斷Xk+1，是否為極小點，若是，則可以停機(jī)，輸出結(jié)果；若不是，則應(yīng)繼續(xù)進(jìn)行，直到滿足精度要求，求出極小值點為止。對于n維二次函數(shù)，只用迭代n次，一定可以收斂到極小值點。若為非二次函數(shù)，則在迭代n次，得到x。點后，不一定就是極小值點。若經(jīng)過判斷不是，就應(yīng)令x0xn，k0重新構(gòu)造n個共扼方向，重復(fù)以上迭代過程。第七節(jié) 變尺度法變尺度法也是共扼方向法的一種。由于它避免了計算二階導(dǎo)數(shù)短陣及其求逆運算，同時又具有較好的收斂性，對于計算高維的非線性問題還具有較好的穩(wěn)定性，因此是求最優(yōu)化問題的最有效方法之一。變尺度法的種類很多，這里我們只介紹其中最重要的兩種方法，DFP法和BFGS陽法。一、基本原理在尺度空間中，如果有—H為n x n階對稱正定矩陣，則定義：為x的非歐氏范數(shù)，也稱X的尺度。梯度法迭代公式為：阻尼牛頓法迭代公式為：梯度法和阻尼牛頓法的迭代公式可以統(tǒng)一寫成如下形式：Ak為變尺度矩陣(也稱近似矩陣)。Ak的構(gòu)成應(yīng)保證算法具有下降性、收斂性和計算的方便性。為此，必須做到以下四點：(1) 希望算法具有下降性，即滿足：(2)為使算法具有二次收斂性，必須保證每次迭代的搜索方向Sk是關(guān)于H(xk)相互共扼的。(3)為計算方便，我們希望變尺度矩陣具有以下的遞推形式：(4) Ak必須滿足擬牛頓條件。二、DFP變尺度法根據(jù)擬牛頓條件推出校正矩陣的計算公式為：用此公式算出Ek后，即可按：求出變尺度矩陣 Ak+1，并由此產(chǎn)生一個新的搜索方向：然后可按一般步驟求得下一輪迭代點。三、DFP變尺度法的計算步驟及算例根據(jù)以上分析，DFP變尺度法的計算步驟如下：(1) 給定起始點Xo．精度ε，并令初始近似矩陣：(2) 計算vF(Xk )，并構(gòu)造搜索方向：(3) 過Xk點沿Sk進(jìn)行一維搜索，求得ak*，則可得：(4)檢驗迭代是否已滿足精度要求，即若：則可停止迭代，最優(yōu)點即為：否則，繼續(xù)執(zhí)行下一步。(5)計算：(6)若在迭代了n次后仍達(dá)不到精度要求，為了加快收斂速度可重取Ak＝I：，再進(jìn)行選代循環(huán)。也就是說，若A＝n，則令A(yù)k＝I，再轉(zhuǎn)到第二步，否則可進(jìn)行下一步，(7)k＝k+1．轉(zhuǎn)到第二步。四、BFGS變尺度法DFP方法對于高維問題，由于收斂快，效果好，普遍被認(rèn)為是目前求解無約束最優(yōu)化問題最好的方法之一。但是它也存在數(shù)值穩(wěn)定性方面不夠理想的問題，對一維搜索的精度也要求較高。在70年代韌，又有人提出了另一種方法，稱為BFGS變尺度法，實際上，是對DFP方法的一種改進(jìn)的方法。所改進(jìn)之處是校正矩陣的計算：其余和DFP方法完全一樣，計算校正矩陣復(fù)雜了，但對一維搜索的精度要求不高。第八節(jié) 坐標(biāo)輪換法直接解法。它們適用于以下場合：(1)目標(biāo)函數(shù)的導(dǎo)數(shù)很難求得它的解析式。(2)目標(biāo)函數(shù)本身不是一個解析式或無法用解析式表達(dá)，例如目標(biāo)函數(shù)是一個二階常微分方程的解．而不是一個解析式；(3)對于維數(shù)不多的優(yōu)化設(shè)計問題，持別對于帶有離散變量的維數(shù)不多的問 題，有時用直接法較簡便。一、坐標(biāo)輪換法的基本思想坐標(biāo)輪換法的基本思想是把多維優(yōu)化問題轉(zhuǎn)化為一系列一維優(yōu)化問題。二、算例三、坐標(biāo)輪換法的討論第四章 線性規(guī)劃工程中的最優(yōu)化設(shè)計問題絕大多數(shù)都是有約束的。有約束的最優(yōu)化設(shè)計問題可以分為兩類廣是目標(biāo)函數(shù)相約束函數(shù)均為線性函數(shù)，稱線性規(guī)劃問題；另一類是目標(biāo)函數(shù)和約束函數(shù)中至少有一個函數(shù)是非線性的，稱為非線性規(guī)劃問題。工程優(yōu)化設(shè)計多屬于后者。然而非線性規(guī)劃有時也可以用線性規(guī)劃在逐次逼近來求解，同時在生產(chǎn)管理領(lǐng)域內(nèi)(如制訂生產(chǎn)規(guī)劃、工藝方案等)也常常會遇到許多線性規(guī)劃問題，因此線性規(guī)劃在員優(yōu)化設(shè)計方法中仍占有雖要地位。第一節(jié) 線性規(guī)劃的數(shù)學(xué)模型一、引 例例1若有某水泥制品廠生產(chǎn)A、B兩種混合料。按照工廠的生產(chǎn)能力，每小時可生產(chǎn)A料14t，或B料7t。從運輸眨離來講．每小時能運A科7t或B料12t。按工廠的運輸能力，不論何種混合料，每小時只能運出物料8t已知生產(chǎn)4料所創(chuàng)造的經(jīng)濟(jì)價值為5元／t，B科為10元／t,試問該廠每小時能創(chuàng)造的最大經(jīng)濟(jì)價值為多少?這時每小時生產(chǎn)的A、B料各為多少?設(shè)計變量：目標(biāo)函數(shù)：約束條件：二、線性規(guī)劃的數(shù)學(xué)模型為了得到線性規(guī)劃的數(shù)學(xué)模型，我們可以把上述引例的數(shù)學(xué)描述改寫為：并滿足：改寫后的數(shù)學(xué)表達(dá)式就是引例中線性規(guī)劃問題的數(shù)學(xué)模型。由此也就可以寫出線性規(guī)劃數(shù)學(xué)模型的一般形式：并滿足：線性規(guī)劃的數(shù)學(xué)模型也可用矩陣的形式更簡潔地寫為：并滿足：第二節(jié) 線性規(guī)劃的基本原理1． 可行解滿足非負(fù)約束條件的約束方程的任何一個解都是可行解。2． 基本解若設(shè)計變量數(shù)為n．約束方程數(shù)為m，使n—m個變量值等于0，聯(lián)立解約束方程組所得到曲解稱為基本解。3． 基本可行解滿足非負(fù)條件的基本解稱基本可行解?；究尚薪饧仁腔窘?，也是可行解。4． 基本變量及基底為得到基本解而使之不等于零的諸變量稱為基本變量?；咀兞康慕M合稱基底。5． 最優(yōu)解及最優(yōu)基本解目標(biāo)函數(shù)為最優(yōu)的可行解稱最優(yōu)解。目標(biāo)函數(shù)為最優(yōu)的基本可行解稱最優(yōu)基本解。第三節(jié) 單純形法一、單純形法原理首先找到一個基本可行解，作為迭代的初始頂點。然后從這個頂點移到另一個頂點，并判斷該頂點是否是員憂解，若是，則迭代結(jié)束，否則再移到另一個新頂點，再判斷，直到找到最優(yōu)點為止。這里關(guān)留要解決三個問題： (1)初始頂點(初始的基本可行解)如何確定?(2)怎樣使最優(yōu)搜索從一個頂點移到另一個頂點?(3)如何判斷所找到的頂點是不是最優(yōu)解?首先讓我們來解決第一個問題。我們?nèi)杂蒙鲜鲆齺碚f明。寫成向量形式：令x1和x2為0，得初始可行基本解：在求得初始基本可行解之后，我們就可以進(jìn)一步去求新的基本可行解，以實現(xiàn)從一個頂點轉(zhuǎn)移到另一個頂點。根據(jù)上述基變量所對應(yīng)的列向量所具有的特征，我們可以通過變換約束方程的系數(shù)和常數(shù)項，使一個非基本變量(X1或X2)和一個基本變量(XXX5)替換，從而找到新的基本可行解，即新的頂點。已知初始基本可行解所對應(yīng)的增廣矩陣為：既然是把X2，作為基本變量替換X3。增廣矩陣變成：得新基本可行解：可以證明在這里X2只能和第1個(即第1行)的基本變量X1（k）＝X3替換，而不能和其他基變量替換。綜上所述，我們可以把求新頂點的方法歸納如下：若己知具有m個線性獨立約束方程和n個變量的線性規(guī)劃的某個基本可行解(某個頂點)為：若想把非基本變量XQ去替換某個基本變量而進(jìn)入基底必須按參數(shù)λl確定替換對象Xl(k)。新的頂點(即新的基本可行解)所對應(yīng)的基本變量可用如下公式計算：這時，增廣矩陣中的各個系數(shù)，應(yīng)按如下公式進(jìn)行相應(yīng)的變化：以上我們解決了怎樣從一個頂點轉(zhuǎn)移到另一個頂點。根據(jù)線性規(guī)劃的基本原理可知，最優(yōu)點必在可行區(qū)的頂點之中．因此每當(dāng)找到一個新的頂點，就需要判斷該頂點是不是最優(yōu)點。怎樣判斷一個頂點是否是優(yōu)點呢，若線性規(guī)劃問題為：初始的基本可行解：通過轉(zhuǎn)變新的基本解：這時目標(biāo)函數(shù)為：則說明任何一個新的可行解，其目標(biāo)函數(shù)值都比原來的大(至少是相等)。所以原來的解x(k)(當(dāng)k＝0)時為初始基本可行解)就是最優(yōu)解。且對某些i有a(k)iQ0，則說明x(k)不是最優(yōu)解，必須進(jìn)行頂點的轉(zhuǎn)移，也就是求新的基本可行解。用前面介紹過的方法，我們可以找到新的基本可行解：且對所有i有a(k)iQ0，則無最優(yōu)解。二、單純形方法的計爵步驟及框圖 將約束條件變換成等式，形成m階n維的線性規(guī)劃問題，求得起始基本可行解。 對系數(shù)陣的每一列計算檢驗數(shù)：對于初始基本可行解k=0。若每一列的檢驗數(shù)全部大于等于零．則x(k)即為最優(yōu)解，迭代結(jié)束。若某個檢驗數(shù)小于零且全部元素a(k)iQ0，則此問題無最優(yōu)解。若某個檢驗數(shù)小于零且對于某些I有a(k)iQ0，則選定Q列所對應(yīng)的變量xQ作為替換的非基本變量，求新的基本可行解。再計算每一列的檢驗數(shù)，再判斷，如此迭代直至找到最優(yōu)解。第四節(jié) 人造基變量如果某線性規(guī)劃的約束條件為如下形式：加入松弛變量后變?yōu)椋嚎梢姴荒芰⒓吹玫揭粋€起始基本可行解。為了解決這個問題，我們可設(shè)法人工構(gòu)造一個基本可行解(稱人造基)作為已知的初始基本可行解。怎樣來構(gòu)成人造基呢? 若有n維m階的線性規(guī)劃問題：現(xiàn)轉(zhuǎn)而求另一個線性規(guī)劃問題：從而可找到起始基本可行解：轉(zhuǎn)換后的線性規(guī)劃問題的最優(yōu)解：如果人造基變量始終不能從基底中替換出來，則說明原問題無最優(yōu)解。第五章 非線性規(guī)劃如果目標(biāo)函數(shù)和約束函數(shù)中至少有一個是非線性函數(shù)，那么這類優(yōu)化設(shè)計問題就稱為非線性規(guī)劃問題。第一節(jié) SUMT方法(罰函數(shù)方法)一、 SUMT方法的原理SUMT方法即序列無約束極小化方法，亦稱罰函數(shù)法。它的基本思想是將原來的目標(biāo)函數(shù)相約束函數(shù)按一定的方式構(gòu)成一個新的函數(shù)。在這個新函數(shù)中，既包含目標(biāo)函數(shù)，又包臺全部約束條件及其一個可以變化的乘子。當(dāng)這個乘子按一定的方式改變時，就得到了一個新函數(shù)序列。顯然，求每一個新函數(shù)的最優(yōu)解都是一個無約束優(yōu)化問題。這樣我們就把一個有約束的優(yōu)化問題轉(zhuǎn)化為一系列的無約束優(yōu)化問題。求解無約束優(yōu)化問題的最優(yōu)解可用第三章所介紹方法進(jìn)行。所得到的最優(yōu)解序列將逐步逼近原問題的最優(yōu)解。通過上面引例的分析，可以得到這樣一個啟示，約束非線性規(guī)劃問題可以通過構(gòu)造新目標(biāo)函數(shù)序列，用無約束優(yōu)化方法求解其極小點，并逐次逼近原問題的最優(yōu)點。即有約束的優(yōu)化設(shè)計問題可以轉(zhuǎn)化成一系列無約束極小化問題進(jìn)行求解。在這里，關(guān)鍵是如何構(gòu)造這個新的目標(biāo)函數(shù)。對于上述內(nèi)點法所構(gòu)造的新目標(biāo)函數(shù)，它具有如下重要特征：當(dāng)在可行區(qū)內(nèi)某一點離開約束邊界較遠(yuǎn)時，其對應(yīng)的函數(shù)值是不很大的，而一旦某一點臨近約束邊界，其對應(yīng)的函數(shù)值就會陡然增大o這樣就可以保證在進(jìn)行無約束極小化時使每次找到的新點始終在可行區(qū)內(nèi)，而不會進(jìn)入非可行區(qū)。因此這種函數(shù)就好像有個“圍墻”一樣，阻止最優(yōu)搜索進(jìn)入非可行區(qū)．故有圍墻函數(shù)之稱，所引入的乘子rk常稱為障礙因子。根據(jù)這一特點，內(nèi)點法每次用無約束最優(yōu)化方法求極小點時，其初始點必須是可行區(qū)的內(nèi)點，而每次選定一個rk所找到的極小點也必然是內(nèi)點，即內(nèi)點法始終是在可行區(qū)的內(nèi)部進(jìn)行最優(yōu)搜索。所以新目標(biāo)函數(shù)是圍墻函數(shù)的SUMT方法，又稱為別SUMT內(nèi)點法。現(xiàn)在我們采用另一種方法對引例構(gòu)造新目標(biāo)函數(shù)：由于是從非可行區(qū)通過求一系列的無約束極小點逐步逼近F(X)的最優(yōu)點，故稱此法為SUMT外點法。外點法的函數(shù)是一個懲罰函數(shù)，當(dāng)不滿足約束條件時，其中的懲罰項將起作用。這就是用外點法構(gòu)造的新目標(biāo)函數(shù)的重要特點。綜上所述，SUMT方法的基本原理可小結(jié)如下：二、 內(nèi)點法例題及框圖構(gòu)造圍墻函數(shù)：rk＝r＝1，用無約束最優(yōu)化方法求圍墻函數(shù)由φ(