最優(yōu)化方法.doc

最優(yōu)化方法最優(yōu)化方法（也稱(chēng)做運(yùn)籌學(xué)方法）是近幾十年形成的，它主要運(yùn)用數(shù)學(xué)方法研究各種系統(tǒng)的優(yōu)化途徑及方案，為決策者提供科學(xué)決策的依據(jù)。基本定義最優(yōu)化方法（也稱(chēng)做運(yùn)籌學(xué)方法）是近幾十年形成的，它主要運(yùn)用數(shù)學(xué)方法研究各種系統(tǒng)的優(yōu)化途徑及方案，為決策者提供科學(xué)決策的依據(jù)。最優(yōu)化方法的主要研究對(duì)象是各種有組織系統(tǒng)的管理問(wèn)題及其生產(chǎn)經(jīng)營(yíng)活動(dòng)。最優(yōu)化方法的目的在于針對(duì)所研究的系統(tǒng)，求得一個(gè)合理運(yùn)用人力、物力和財(cái)力的最佳方案，發(fā)揮和提高系統(tǒng)的效能及效益，最終達(dá)到系統(tǒng)的最優(yōu)目標(biāo)。實(shí)踐表明，隨著科學(xué)技術(shù)的日益進(jìn)步和生產(chǎn)經(jīng)營(yíng)的日益發(fā)展，最優(yōu)化方法已成為現(xiàn)代管理科學(xué)的重要理論基礎(chǔ)和不可缺少的方法，被人們廣泛地應(yīng)用到公共管理、經(jīng)濟(jì)管理、工程建設(shè)、國(guó)防等各個(gè)領(lǐng)域，發(fā)揮著越來(lái)越重要的作用。本章將介紹最優(yōu)化方法的研究對(duì)象、特點(diǎn)，以及最優(yōu)化方法模型的建立和模型的分析、求解、應(yīng)用。主要是線性規(guī)劃問(wèn)題的模型、求解（線性規(guī)劃問(wèn)題的單純形解法）及其應(yīng)用運(yùn)輸問(wèn)題；以及動(dòng)態(tài)規(guī)劃的模型、求解、應(yīng)用資源分配問(wèn)題。最優(yōu)化方法1.微分學(xué)中求極值2.無(wú)約束最優(yōu)化問(wèn)題3.常用微分公式4.凸集與凸函數(shù)5.等式約束最優(yōu)化問(wèn)題6.不等式約束最優(yōu)化問(wèn)題7.變分學(xué)中求極值詳細(xì)資料數(shù)學(xué)意義為了達(dá)到最優(yōu)化目的所提出的各種求解方法。從數(shù)學(xué)意義上說(shuō)，最優(yōu)化方法是一種求極值的方法，即在一組約束為等式或不等式的條件下，使系統(tǒng)的目標(biāo)函數(shù)達(dá)到極值，即最大值或最小值。從經(jīng)濟(jì)意義上說(shuō)，是在一定的人力、物力和財(cái)力資源條件下，使經(jīng)濟(jì)效果達(dá)到最大（如產(chǎn)值、利潤(rùn)），或者在完成規(guī)定的生產(chǎn)或經(jīng)濟(jì)任務(wù)下，使投入的人力、物力和財(cái)力等資源為最少。發(fā)展簡(jiǎn)史公元前 500年古希臘在討論建筑美學(xué)中就已發(fā)現(xiàn)了長(zhǎng)方形長(zhǎng)與寬的最佳比例為1. 黃金分割比618,稱(chēng)為黃金分割比。其倒數(shù)至今在優(yōu)選法中仍得到廣泛應(yīng)用。在微積分出現(xiàn)以前，已有許多學(xué)者開(kāi)始研究用數(shù)學(xué)方法解決最優(yōu)化問(wèn)題。例如阿基米德證明：給定周長(zhǎng)，圓所包圍的面積為最大。這就是歐洲古代城堡幾乎都建成圓形的原因。但是最優(yōu)化方法真正形成為科學(xué)方法則在17世紀(jì)以后。17世紀(jì)，I.牛頓和G.W.萊布尼茨在他們所創(chuàng)建的微積分中，提出求解具有多個(gè)自變量的實(shí)值函數(shù)的最大值和最小值的方法。以后又進(jìn)一步討論具有未知函數(shù)的函數(shù)極值，從而形成變分法。這一時(shí)期的最優(yōu)化方法可以稱(chēng)為古典最優(yōu)化方法。第二次世界大戰(zhàn)前后，由于軍事上的需要和科學(xué)技術(shù)和生產(chǎn)的迅速發(fā)展，許多實(shí)際的最優(yōu)化問(wèn)題已經(jīng)無(wú)法用古典方法來(lái)解決，這就促進(jìn)了近代最優(yōu)化方法的產(chǎn)生。近代最優(yōu)化方法的形成和發(fā)展過(guò)程中最重要的事件有： 以蘇聯(lián).康托羅維奇和美國(guó)G.B.丹齊克為代表的線性規(guī)劃；以美國(guó)庫(kù)恩和塔克爾為代表的非線性規(guī)劃；以美國(guó)R.貝爾曼為代表的動(dòng)態(tài)規(guī)劃；以蘇聯(lián).龐特里亞金為代表的極大值原理等。這些方法后來(lái)都形成體系，成為近代很活躍的學(xué)科，對(duì)促進(jìn)運(yùn)籌學(xué)、管理科學(xué)、控制論和系統(tǒng)工程等學(xué)科的發(fā)展起了重要作用。工作步驟用最優(yōu)化方法解決實(shí)際問(wèn)題，一般可經(jīng)過(guò)下列步驟：提出最優(yōu)化問(wèn)題，收集有關(guān)數(shù)據(jù)和資料；建立最優(yōu)化問(wèn)題的數(shù)學(xué)模型,確定變量,列出目標(biāo)函數(shù)和約束條件；分析模型，選擇合適的最優(yōu)化方法；求解，一般通過(guò)編制程序，用計(jì)算機(jī)求最優(yōu)解；最優(yōu)解的檢驗(yàn)和實(shí)施。上述 5個(gè)步驟中的工作相互支持和相互制約，在實(shí)踐中常常是反復(fù)交叉進(jìn)行。模型的基本要素最優(yōu)化模型一般包括變量、約束條件和目標(biāo)函數(shù)三要素:變量:指最優(yōu)化問(wèn)題中待確定的某些量。變量可用x=(x1，x2,xn)T表示。約束條件:指在求最優(yōu)解時(shí)對(duì)變量的某些限制,包括技術(shù)上的約束、資源上的約束和時(shí)間上的約束等。列出的約束條件越接近實(shí)際系統(tǒng)，則所求得的系統(tǒng)最優(yōu)解也就越接近實(shí)際最優(yōu)解。約束條件可用 gi(x)0表示i=1,2，m，m 表示約束條件數(shù)；或xR(R表示可行集合)。目標(biāo)函數(shù)：最優(yōu)化有一定的評(píng)價(jià)標(biāo)準(zhǔn)。目標(biāo)函數(shù)就是這種標(biāo)準(zhǔn)的數(shù)學(xué)描述，一般可用f(x)來(lái)表示，即f(x)=f(x1，x2,xn)。要求目標(biāo)函數(shù)為最大時(shí)可寫(xiě)成；要求最小時(shí)則可寫(xiě)成。目標(biāo)函數(shù)可以是系統(tǒng)功能的函數(shù)或費(fèi)用的函數(shù)。它必須在滿(mǎn)足規(guī)定的約束條件下達(dá)到最大或最小。 問(wèn)題的分類(lèi) 最優(yōu)化問(wèn)題根據(jù)其中的變量、約束、目標(biāo)、問(wèn)題性質(zhì)、時(shí)間因素和函數(shù)關(guān)系等不同情況，可分成多種類(lèi)型（見(jiàn)表）。最優(yōu)化方法最優(yōu)化方法不同類(lèi)型的最優(yōu)化問(wèn)題可以有不同的最優(yōu)化方法，即使同一類(lèi)型的問(wèn)題也可有多種最優(yōu)化方法。反之,某些最優(yōu)化方法可適用于不同類(lèi)型的模型。最優(yōu)化問(wèn)題的求解方法一般可以分成解析法、直接法、數(shù)值計(jì)算法和其他方法。解析法：這種方法只適用于目標(biāo)函數(shù)和約束條件有明顯的解析表達(dá)式的情況。求解方法是：先求出最優(yōu)的必要條件，得到一組方程或不等式，再求解這組方程或不等式，一般是用求導(dǎo)數(shù)的方法或變分法求出必要條件，通過(guò)必要條件將問(wèn)題簡(jiǎn)化，因此也稱(chēng)間接法。直接法：當(dāng)目標(biāo)函數(shù)較為復(fù)雜或者不能用變量顯函數(shù)描述時(shí)，無(wú)法用解析法求必要條件。此時(shí)可采用直接搜索的方法經(jīng)過(guò)若干次迭代搜索到最優(yōu)點(diǎn)。這種方法常常根據(jù)經(jīng)驗(yàn)或通過(guò)試驗(yàn)得到所需結(jié)果。對(duì)于一維搜索(單變量極值問(wèn)題)，主要用消去法或多項(xiàng)式插值法；對(duì)于多維搜索問(wèn)題(多變量極值問(wèn)題)主要應(yīng)用爬山法。數(shù)值計(jì)算法：這種方法也是一種直接法。它以梯度法為基礎(chǔ)，所以是一種解析與數(shù)值計(jì)算相結(jié)合的方法。其他方法：如網(wǎng)絡(luò)最優(yōu)化方法等(見(jiàn)網(wǎng)絡(luò)理論)。解析性質(zhì)根據(jù)函數(shù)的解析性質(zhì)，還可以對(duì)各種方法作進(jìn)一步分類(lèi)。例如，如果目標(biāo)函數(shù)和約束條件都是線性的，就形成線性規(guī)劃。線性規(guī)劃有專(zhuān)門(mén)的解法，諸如單純形法、解乘數(shù)法、橢球法和卡馬卡法等。當(dāng)目標(biāo)或約束中有一非線性函數(shù)時(shí),就形成非線性規(guī)劃。當(dāng)目標(biāo)是二次的,而約束是線性時(shí)，則稱(chēng)為二次規(guī)劃。二次規(guī)劃的理論和方法都較成熟。如果目標(biāo)函數(shù)具有一些函數(shù)的平方和的形式，則有專(zhuān)門(mén)求解平方和問(wèn)題的優(yōu)化方法。目標(biāo)函數(shù)具有多項(xiàng)式形式時(shí)，可形成一類(lèi)幾何規(guī)劃。最優(yōu)解的概念最優(yōu)化問(wèn)題的解一般稱(chēng)為最優(yōu)解。如果只考察約束集合中某一局部范圍內(nèi)的優(yōu)劣情況，則解稱(chēng)為局部最優(yōu)解。如果是考察整個(gè)約束集合中的情況，則解稱(chēng)為總體最優(yōu)解。對(duì)于不同優(yōu)化問(wèn)題，最優(yōu)解有不同的含意，因而還有專(zhuān)用的名稱(chēng)。例如，在對(duì)策論和數(shù)理經(jīng)濟(jì)模型中稱(chēng)為平衡解；在控制問(wèn)題中稱(chēng)為最優(yōu)控制或極值控制；在多目標(biāo)決策問(wèn)題中稱(chēng)為非劣解（又稱(chēng)帕雷托最優(yōu)解或有效解）。在解決實(shí)際問(wèn)題時(shí)情況錯(cuò)綜復(fù)雜，有時(shí)這種理想的最優(yōu)解不易求得，或者需要付出較大的代價(jià)，因而對(duì)解只要求能滿(mǎn)足一定限度范圍內(nèi)的條件,不一定過(guò)分強(qiáng)調(diào)最優(yōu)。50年代初,在運(yùn)籌學(xué)發(fā)展的早期就有人提出次優(yōu)化的概念及其相應(yīng)的次優(yōu)解。提出這些概念的背景是：最優(yōu)化模型的建立本身就只是一種近似，因?yàn)閷?shí)際問(wèn)題中存在的某些因素，尤其是一些非定量因素很難在一個(gè)模型中全部加以考慮。另一方面，還缺乏一些求解較為復(fù)雜模型的有效方法。1961年H.A.西蒙進(jìn)一步提出滿(mǎn)意解的概念，即只要決策者對(duì)解滿(mǎn)意即可。最優(yōu)化方法的應(yīng)用最優(yōu)化一般可以分為最優(yōu)設(shè)計(jì)、最優(yōu)計(jì)劃、最優(yōu)管理和最優(yōu)控制等四個(gè)方面。最優(yōu)設(shè)計(jì):世界各國(guó)工程技術(shù)界,尤其是飛機(jī)、造船、機(jī)械、建筑等部門(mén)都已廣泛應(yīng)用最優(yōu)化方法于設(shè)計(jì)中，從各種設(shè)計(jì)參數(shù)的優(yōu)選到最佳結(jié)構(gòu)形狀的選取等，結(jié)合有限元方法已使許多設(shè)計(jì)優(yōu)化問(wèn)題得到解決。一個(gè)新的發(fā)展動(dòng)向是最優(yōu)設(shè)計(jì)和計(jì)算機(jī)輔助設(shè)計(jì)相結(jié)合。電子線路的最優(yōu)設(shè)計(jì)是另一個(gè)應(yīng)用最優(yōu)化方法的重要領(lǐng)域。配方配比的優(yōu)選方面在化工、橡膠、塑料等工業(yè)部門(mén)都得到成功的應(yīng)用,并向計(jì)算機(jī)輔助搜索最佳配方、配比方向發(fā)展(見(jiàn)優(yōu)選法)。最優(yōu)計(jì)劃:現(xiàn)代國(guó)民經(jīng)濟(jì)或部門(mén)經(jīng)濟(jì)的計(jì)劃，直至企業(yè)的發(fā)展規(guī)劃和年度生產(chǎn)計(jì)劃，尤其是農(nóng)業(yè)規(guī)劃、種植計(jì)劃、能源規(guī)劃和其他資源、環(huán)境和生態(tài)規(guī)劃的制訂,都已開(kāi)始應(yīng)用最優(yōu)化方法。一個(gè)重要的發(fā)展趨勢(shì)是幫助領(lǐng)導(dǎo)部門(mén)進(jìn)行各種優(yōu)化決策。最優(yōu)管理：一般在日常生產(chǎn)計(jì)劃的制訂、調(diào)度和運(yùn)行中都可應(yīng)用最優(yōu)化方法。隨著管理信息系統(tǒng)和決策支持系統(tǒng)的建立和使用，使最優(yōu)管理得到迅速的發(fā)展。最優(yōu)控制：主要用于對(duì)各種控制系統(tǒng)的優(yōu)化。例如，導(dǎo)彈系統(tǒng)的最優(yōu)控制，能保證用最少燃料完成飛行任務(wù),用最短時(shí)間達(dá)到目標(biāo);再如飛機(jī)、船舶、電力系統(tǒng)等的最優(yōu)控制，化工、冶金等工廠的最佳工況的控制。計(jì)算機(jī)接口裝置不斷完善和優(yōu)化方法的進(jìn)一步發(fā)展，還為計(jì)算機(jī)在線生產(chǎn)控制創(chuàng)造了有利條件。最優(yōu)控制的對(duì)象也將從對(duì)機(jī)械、電氣、化工等硬系統(tǒng)的控制轉(zhuǎn)向?qū)ι鷳B(tài)、環(huán)境以至社會(huì)經(jīng)濟(jì)系統(tǒng)的控制。內(nèi)容簡(jiǎn)介最優(yōu)化方法介紹最優(yōu)化模型的理論與計(jì)算方法，其中理論包括對(duì)偶理論、非線性規(guī)劃的最優(yōu)性理論、非線性半定規(guī)劃的最優(yōu)性理論、非線性二階錐優(yōu)化的最優(yōu)性理論；計(jì)算方法包括無(wú)約束優(yōu)化的線搜索方法、線性規(guī)劃的單純形方法和內(nèi)點(diǎn)方法、非線性規(guī)劃的序列二次規(guī)劃方法、非線性規(guī)劃的增廣Lagrange方法、非線性半定規(guī)劃的增廣Lagrange方法、非線性二階錐優(yōu)化的增廣Lagrange方法以及整數(shù)規(guī)劃的Lagrange松弛方法。最優(yōu)化方法注重知識(shí)的準(zhǔn)確性、系統(tǒng)性和算法論述的完整性，是學(xué)習(xí)最優(yōu)化方法的一本入門(mén)書(shū)。最優(yōu)化方法可用作高等院校數(shù)學(xué)系高年級(jí)本科生和管理專(zhuān)業(yè)研究生的教材，也可作為相關(guān)工程技術(shù)人員的參考用書(shū)。圖書(shū)目錄前言第1章 變分分析的相關(guān)素材1.1 凸分析素材1.1.1 凸集合1.1.2 凸函數(shù)的閉包1.1.3 共軛函數(shù)1.1.4 次可微性1.2 集值映射的極限1.3 方向?qū)?shù)1.4 集合的切錐與二階切集1.4.1 集合的切錐1.4.2 二階切集1.4.3 函數(shù)水平集的切錐與二階切集1.4.4 負(fù)卦限錐的切錐與二階切集1.5 有限維系統(tǒng)的穩(wěn)定性1.5.1線性系統(tǒng)1.5.2 集合約束的線性系統(tǒng)1.5.3 集合約束的非線性系統(tǒng)第2章 無(wú)約束優(yōu)化2.1 引言2.2 線搜索方法2.2.1 線搜索原則2.2.2 下降方法的收斂性2.3 最速下降方法2.3.1 最速下降方法的全局收斂性2.3.2 最速下降方法的收斂速度2.4 Newton法2.4.1 經(jīng)典N(xiāo)ewton法2.4.2 帶線搜索的：Newton法2.4.3 自協(xié)調(diào)函數(shù)的Newton法2.5 擬Newton法2.5.1 擬Newton方程和著名的擬Newton公式2.5.2 擬Newton法求解凸二次規(guī)劃2.5.3 Dixon定理2.5.4 DFP方法的收斂性2.5.5 BFGS方法的收斂性2.5.6 限制Broyden類(lèi)方法的收斂性2.6 共軛梯度方法2.6.1 共軛方向2.6.2 共軛梯度方法求解二次規(guī)劃2.6.3 求解無(wú)約束優(yōu)化問(wèn)題的FR方法2.7 信賴(lài)域方法2.7.1 信賴(lài)域基本算法2.7.2 Cauchy點(diǎn)與模型下降2.7.3 信賴(lài)域算法的收斂性第3章 線性規(guī)劃3.1 線性規(guī)劃問(wèn)題及其性質(zhì)3.2 單純形法3.3 Bland原則3.4 線性規(guī)劃的對(duì)偶定理3.5 對(duì)偶單純形方法3.6 線性規(guī)劃的Karmakar內(nèi)點(diǎn)法3.6.1 解析中心與勢(shì)函數(shù)3.6.2 線性規(guī)劃的勢(shì)函數(shù)3.6.3 線性規(guī)劃的中心路徑3.6.4 線性規(guī)劃的Karmarkar算法第4章 對(duì)偶理論4.1 共軛對(duì)偶性4.2 Lagrange對(duì)偶性4.3 對(duì)偶理論的應(yīng)用第5章 最優(yōu)性條件5.1 一階最優(yōu)性條件5.2 廣義Lagrange乘子5.3 二階最優(yōu)性條件第6章 增廣Lagrange函數(shù)方法6.1 懲罰與障礙函數(shù)方法6.1.1 懲罰函數(shù)方法6.1.2 經(jīng)典障礙函數(shù)方法6.2 增廣Lagran