最優(yōu)化及最優(yōu)化方法講稿課件

最優(yōu)化及最優(yōu)化方法講稿最優(yōu)化及最優(yōu)化方法講稿最優(yōu)化方法的研究對象及應(yīng)用

最優(yōu)化方法的主要研究對象是各種有組織系統(tǒng)的管理問題及其生產(chǎn)經(jīng)營活動(dòng)。最優(yōu)化方法的目的在于針對所研究的系統(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)營的日益發(fā)展，最優(yōu)化方法已成為現(xiàn)代管理科學(xué)的重要理論基礎(chǔ)和不可缺少的方法，被人們廣泛地應(yīng)用到空間技術(shù)、軍事科學(xué)、電子工程、通訊工程、自動(dòng)控制、系統(tǒng)識(shí)別、資源分配、計(jì)算數(shù)學(xué)、公共管理、經(jīng)濟(jì)管理等各個(gè)領(lǐng)域，發(fā)揮著越來越重要的作用。最優(yōu)化方法的研究對象及應(yīng)用最優(yōu)化方法的主要研

最優(yōu)化方法的具體應(yīng)用舉例

最優(yōu)化一般可以分為最優(yōu)設(shè)計(jì)、最優(yōu)計(jì)劃、最優(yōu)管理和最優(yōu)控制等四個(gè)方面。①最優(yōu)設(shè)計(jì):世界各國工程技術(shù)界,尤其是飛機(jī)、造船、機(jī)械、建筑等部門都已廣泛應(yīng)用最優(yōu)化方法于設(shè)計(jì)中，從各種設(shè)計(jì)參數(shù)的優(yōu)選到最佳結(jié)構(gòu)形狀的選取等，結(jié)合有限元方法已使許多設(shè)計(jì)優(yōu)化問題得到解決。一個(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è)部門都得到成功的應(yīng)用,并向計(jì)算機(jī)輔助搜索最佳配方、配比方向發(fā)展(見優(yōu)選法)。

最優(yōu)化方法的具體應(yīng)用舉例最優(yōu)化一般可

最優(yōu)化方法的具體應(yīng)用舉例

②最優(yōu)計(jì)劃:現(xiàn)代國民經(jīng)濟(jì)或部門經(jīng)濟(jì)的計(jì)劃，直至企業(yè)的發(fā)展規(guī)劃和年度生產(chǎn)計(jì)劃，尤其是農(nóng)業(yè)規(guī)劃、種植計(jì)劃、能源規(guī)劃和其他資源、環(huán)境和生態(tài)規(guī)劃的制訂,都已開始應(yīng)用最優(yōu)化方法。一個(gè)重要的發(fā)展趨勢是幫助領(lǐng)導(dǎo)部門進(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)化方法的具體應(yīng)用舉例②最優(yōu)計(jì)劃:現(xiàn)代國民經(jīng)濟(jì)或

最優(yōu)化方法的具體應(yīng)用舉例

④最優(yōu)控制：主要用于對各種控制系統(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)控制的對象也將從對機(jī)械、電氣、化工等硬系統(tǒng)的控制轉(zhuǎn)向?qū)ι鷳B(tài)、環(huán)境以至社會(huì)經(jīng)濟(jì)系統(tǒng)的控制。

最優(yōu)化方法的具體應(yīng)用舉例④最優(yōu)控制：主要用于對各種控最優(yōu)化的發(fā)展簡史

最優(yōu)化是一個(gè)古老的課題。長期以來，人們對最優(yōu)化問題進(jìn)行著探討和研究。

公元前500年古希臘在討論建筑美學(xué)中就已發(fā)現(xiàn)了長方形長與寬的最佳比例為1.618,稱為黃金分割比。其倒數(shù)至今在優(yōu)選法中仍得到廣泛應(yīng)用。在微積分出現(xiàn)以前，已有許多學(xué)者開始研究用數(shù)學(xué)方法解決最優(yōu)化問題。例如阿基米德證明：給定周長，圓所包圍的面積為最大。這就是歐洲古代城堡幾乎都建成圓形的原因。

最優(yōu)化的發(fā)展簡史最優(yōu)化是一個(gè)古老的課題。長期以最優(yōu)化的發(fā)展簡史

但是最優(yōu)化方法真正形成為科學(xué)方法則在17世紀(jì)以后。

17世紀(jì)，I.牛頓和G.W.萊布尼茨在他們所創(chuàng)建的微積分中，提出求解具有多個(gè)自變量的實(shí)值函數(shù)的最大值和最小值的方法，后來又出現(xiàn)Lagrange乘數(shù)法。以后又進(jìn)一步討論具有未知函數(shù)的函數(shù)極值，從而形成變分法。這一時(shí)期的最優(yōu)化方法可以稱為古典最優(yōu)化方法。最優(yōu)化的發(fā)展簡史但是最優(yōu)化方法真正形成為科學(xué)最優(yōu)化的發(fā)展簡史

第二次世界大戰(zhàn)前后，由于軍事上的需要和科學(xué)技術(shù)和生產(chǎn)的迅速發(fā)展，許多實(shí)際的最優(yōu)化問題已經(jīng)無法用古典方法來解決，這就促進(jìn)了近代最優(yōu)化方法的產(chǎn)生。

近代最優(yōu)化方法的形成和發(fā)展過程中最重要的事件有：

1847年法國數(shù)學(xué)家Cauchy研究了函數(shù)值沿什么方向下降最快的問題，提出最速下降法。

1939年前蘇聯(lián)數(shù)學(xué)家Л.B.Канторович提出了解決下料問題和運(yùn)輸問題這兩種線性規(guī)劃問題的求解方法。最優(yōu)化的發(fā)展簡史第二次世界大戰(zhàn)前后，由于軍事上的最優(yōu)化的發(fā)展簡史

以蘇聯(lián)Л.В.康托羅維奇和美國G.B.丹齊克為代表的線性規(guī)劃；以美國庫恩和塔克爾為代表的非線性規(guī)劃；以美國R.貝爾曼為代表的動(dòng)態(tài)規(guī)劃；以蘇聯(lián)Л.С.龐特里亞金為代表的極大值原理等。這些方法后來都形成體系，成為近代很活躍的學(xué)科，對促進(jìn)運(yùn)籌學(xué)、管理科學(xué)、控制論和系統(tǒng)工程等學(xué)科的發(fā)展起了重要作用。

最優(yōu)化的發(fā)展簡史最優(yōu)化方法的內(nèi)容

最優(yōu)化方法包括的內(nèi)容很廣泛，如線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、幾何規(guī)劃、動(dòng)態(tài)規(guī)劃、隨機(jī)規(guī)劃、多目標(biāo)規(guī)劃、組合優(yōu)化(在給定有限集的所有具備某些條件的子集中，按某種目標(biāo)找出一個(gè)最優(yōu)子集的一類數(shù)學(xué)規(guī)劃)等等。

最優(yōu)化方法的內(nèi)容最優(yōu)化方法包括的內(nèi)容很廣泛，如線性幾何規(guī)劃非線性規(guī)劃的一個(gè)分支。是最有效的最優(yōu)化的方法之一。幾何規(guī)劃最初是由數(shù)學(xué)家R.J.達(dá)芬和E.L.彼得森及C.M.查納等人于1961年在研究工程費(fèi)用極小化問題基礎(chǔ)上提出的，直到1967年《幾何規(guī)劃》一書出版后才正式定名。幾何規(guī)劃的數(shù)學(xué)基礎(chǔ)是G.H.哈代的平均理論。由于幾何平均不等式的關(guān)鍵性作用，幾何規(guī)劃由此得名。幾何規(guī)劃的目標(biāo)函數(shù)和約束條件均由廣義多項(xiàng)式構(gòu)成，這是一類特殊的非線性規(guī)劃，利用其對偶原理，可以把高度非線性問題的求解轉(zhuǎn)化為具有線性約束的優(yōu)化問題求解，使計(jì)算大為簡化。幾何規(guī)劃理論研究和算法軟件開發(fā)、發(fā)展都很快，并且在化工、機(jī)械、土木、電氣、核工程等部門的工程優(yōu)化設(shè)計(jì)和企業(yè)管理、資源分配、環(huán)境保護(hù)以及技術(shù)經(jīng)濟(jì)分析等方面都得到廣泛應(yīng)用。幾何規(guī)劃非線性規(guī)劃的一個(gè)分支。是最有效的最優(yōu)化的方法之一。幾整數(shù)規(guī)劃整數(shù)規(guī)劃是指一類要求問題中的全部或一部分變量為整數(shù)的數(shù)學(xué)規(guī)劃。是近三十年來發(fā)展起來的、規(guī)劃論的一個(gè)分支.整數(shù)規(guī)劃問題是要求決策變量取整數(shù)值的線性規(guī)劃或非線性規(guī)劃問題。一般認(rèn)為非線性的整數(shù)規(guī)劃可分成線性部分和整數(shù)部分，因此常常把整數(shù)規(guī)劃作為線性規(guī)劃的特殊部分。在線性規(guī)劃問題中，有些最優(yōu)解可能是分?jǐn)?shù)或小數(shù)，但對于某些具體問題，常要求解答必須是整數(shù)。例如，所求解是機(jī)器的臺(tái)數(shù)，工作的人數(shù)或裝貨的車數(shù)等。為了滿足整數(shù)的要求，初看起來似乎只要把已得的非整數(shù)解舍入化整就可以了。實(shí)際上化整后的數(shù)不見得是可行解和最優(yōu)解，所以應(yīng)該有特殊的方法來求解整數(shù)規(guī)劃。整數(shù)規(guī)劃整數(shù)規(guī)劃是指一類要求問題中的全部或一部分變量為整數(shù)的

在整數(shù)規(guī)劃中，如果所有變量都限制為整數(shù)，則稱為純整數(shù)規(guī)劃；如果僅一部分變量限制為整數(shù)，則稱為混合整數(shù)規(guī)劃。整數(shù)規(guī)劃的一種特殊情形是0-1規(guī)劃，它的變數(shù)僅限于0或1。整數(shù)規(guī)劃是從1958年由R.E.戈莫里提出割平面法之后形成獨(dú)立分支的，30多年來發(fā)展出很多方法解決各種問題。解整數(shù)規(guī)劃最典型的做法是逐步生成一個(gè)相關(guān)的問題，稱它是原問題的衍生問題。對每個(gè)衍生問題又伴隨一個(gè)比它更易于求解的松弛問題（衍生問題稱為松弛問題的源問題）。通過松弛問題的解來確定它的源問題的歸宿，即源問題應(yīng)被舍棄，還是再生成一個(gè)或多個(gè)它本身的衍生問題來替代它。隨即，再選擇一個(gè)尚未被舍棄的在整數(shù)規(guī)劃中，如果所有變量都限制為整數(shù)，則稱為純整數(shù)規(guī)

或替代的原問題的衍生問題，重復(fù)以上步驟直至不再剩有未解決的衍生問題為止。目前比較成功又流行的方法是分枝定界法和割平面法，它們都是在上述框架下形成的。

0—1規(guī)劃在整數(shù)規(guī)劃中占有重要地位，一方面因?yàn)樵S多實(shí)際問題，例如指派問題、選地問題、送貨問題都可歸結(jié)為此類規(guī)劃，另一方面任何有界變量的整數(shù)規(guī)劃都與0—1規(guī)劃等價(jià)，用0—1規(guī)劃方法還可以把多種非線性規(guī)劃問題表示成整數(shù)規(guī)劃問題，所以不少人致力于這個(gè)方向的研究。求解0—1規(guī)劃的常用方法是分枝定界法，對各種特殊問題還有一些特殊方法，例如求解指派問題用匈牙利方法就比較方便。

或替代的原問題的衍生問題，重復(fù)以上步驟直至不再剩有未解組合最優(yōu)化

在給定有限集的所有具備某些條件的子集中，按某種目標(biāo)找出一個(gè)最優(yōu)子集的一類數(shù)學(xué)規(guī)劃。又稱組合規(guī)劃。從最廣泛的意義上說，組合規(guī)劃與整數(shù)規(guī)劃這兩者的領(lǐng)域是一致的，都是指在有限個(gè)可供選擇的方案的組成集合中，選擇使目標(biāo)函數(shù)達(dá)到極值的最優(yōu)子集。組合最優(yōu)化發(fā)展的初期，研究一些比較實(shí)用的基本上屬于網(wǎng)絡(luò)極值方面的問題，如廣播網(wǎng)的設(shè)計(jì)、開關(guān)電路設(shè)計(jì)、航船運(yùn)輸路線的計(jì)劃、工作指派、貨物裝箱方案等。自從擬陣概念進(jìn)入圖論領(lǐng)域之后，對擬陣中的一些理論問題的研究成為組合規(guī)劃研究的新課題，并得到應(yīng)用?，F(xiàn)在應(yīng)用的主要方面仍是網(wǎng)絡(luò)上的最優(yōu)化問題，如最短路問題、最大（?。┲螛鋯栴}、最優(yōu)邊無關(guān)集問題、最小截集問題、推銷員問題等。組合最優(yōu)化在給定有限集的所有具備某些條件的子集中，按某種目整數(shù)規(guī)劃與組合最優(yōu)化的關(guān)系

整數(shù)規(guī)劃與組合最優(yōu)化從廣泛的意義上說，兩者的領(lǐng)域是一致的，都是在有限個(gè)可供選擇的方案中，尋找滿足一定標(biāo)準(zhǔn)的最好方案。有許多典型的問題反映整數(shù)規(guī)劃的廣泛背景。例如，背袋（或裝載）問題、固定費(fèi)用問題、和睦探險(xiǎn)隊(duì)問題（組合學(xué)的對集問題）、有效探險(xiǎn)隊(duì)問題（組合學(xué)的覆蓋問題）、送貨問題等。因此整數(shù)規(guī)劃的應(yīng)用范圍也是極其廣泛的。它不僅在工業(yè)和工程設(shè)計(jì)和科學(xué)研究方面有許多應(yīng)用，而且在計(jì)算機(jī)設(shè)計(jì)、系統(tǒng)可靠性、編碼和經(jīng)濟(jì)分析等方面也有新的應(yīng)用。整數(shù)規(guī)劃與組合最優(yōu)化的關(guān)系整數(shù)規(guī)劃與組合最優(yōu)化從廣泛的意義隨機(jī)規(guī)劃

隨機(jī)規(guī)劃是對含有隨機(jī)變量的優(yōu)化問題建模的有效的工具并已有一個(gè)世紀(jì)的歷史。第一種隨機(jī)規(guī)劃是美國經(jīng)濟(jì)學(xué)家丹澤1955年提出的，康托羅維奇在這方面的貢獻(xiàn)，不在于這個(gè)新方法本身，而在于把它應(yīng)用于制定最優(yōu)計(jì)劃。是廣泛使用的期望值模型，即在期望約束條件下，使得期望收益達(dá)到最大或期望損失達(dá)到最小的優(yōu)化方法。第二種是由查納斯（A.Charnes）和庫伯(W.W.Cooper）于1959年提出的機(jī)會(huì)約束規(guī)劃，是在一定的概率意義下達(dá)到最優(yōu)的理論。第三種即是劉寶碇教授于1997年提出的相關(guān)機(jī)會(huì)規(guī)劃，是一種使事件的機(jī)會(huì)在隨機(jī)環(huán)境下達(dá)到最優(yōu)的理論。它與期望值模型和機(jī)會(huì)約束規(guī)劃一起構(gòu)成了隨機(jī)規(guī)劃的三個(gè)分支。隨機(jī)規(guī)劃隨機(jī)規(guī)劃是對含有隨機(jī)變量的優(yōu)化問題建模的隨機(jī)規(guī)劃是處理數(shù)據(jù)帶有隨機(jī)性的一類數(shù)學(xué)規(guī)劃，它與確定性數(shù)學(xué)規(guī)劃最大的不同在于其系數(shù)中引進(jìn)了隨機(jī)變量，這使得隨機(jī)規(guī)劃比起確定性數(shù)學(xué)規(guī)劃更適合于實(shí)際問題。在管理科學(xué)、運(yùn)籌學(xué)、經(jīng)濟(jì)學(xué)、最優(yōu)控制等領(lǐng)域，隨機(jī)規(guī)劃有著廣泛的應(yīng)用。隨機(jī)規(guī)劃的求解方法

隨機(jī)規(guī)劃的求解方法大致分兩種。第一種是轉(zhuǎn)化法，即將隨機(jī)規(guī)劃轉(zhuǎn)化成各自的確定性等價(jià)類，然后利用已有的確定性規(guī)劃的求解方法解之；另一種是逼近方法，利用隨機(jī)模擬技術(shù)，通過一定的遺傳算法程序，得到隨機(jī)規(guī)劃問題的近似最優(yōu)解和目標(biāo)函數(shù)的近似最優(yōu)值。隨機(jī)規(guī)劃是處理數(shù)據(jù)帶有隨機(jī)性的一類數(shù)學(xué)規(guī)劃，它與確定性數(shù)學(xué)規(guī)講授內(nèi)容教材：最優(yōu)化方法及應(yīng)用案例.緒論.線性規(guī)劃.非線性規(guī)劃.動(dòng)態(tài)規(guī)劃.多目標(biāo)優(yōu)化及其應(yīng)用

講授內(nèi)容教材：最優(yōu)化方法及應(yīng)用案例預(yù)備知識(shí)和學(xué)習(xí)要求學(xué)習(xí)該課程的需要具備的基本知識(shí)

高等數(shù)學(xué)線性代數(shù)學(xué)習(xí)該課程的要求

態(tài)度決定一切

正確理解基本概念和原理掌握最優(yōu)化方法的思想能夠運(yùn)用最優(yōu)化方法分析解決實(shí)際問題預(yù)備知識(shí)和學(xué)習(xí)要求學(xué)習(xí)該課程的需要具備的基本知識(shí)最優(yōu)化問題的數(shù)學(xué)模型一般形式最優(yōu)化問題（目標(biāo)函數(shù)）（不等式約束）（等式約束）其中最優(yōu)化問題的數(shù)學(xué)模型一般形式最優(yōu)化問題（目標(biāo)函數(shù)）（不等式約最優(yōu)化問題分類

經(jīng)典優(yōu)化問題（靜態(tài)優(yōu)化問題）和現(xiàn)代優(yōu)化問題（動(dòng)態(tài)優(yōu)化問題）

1、經(jīng)典優(yōu)化問題（靜態(tài)優(yōu)化問題）

根據(jù)數(shù)學(xué)模型中有無約束函數(shù)分為有約束的最優(yōu)化問題和無約束的最優(yōu)化問題；

根據(jù)目標(biāo)函數(shù)和約束函數(shù)的函數(shù)類型分類：線性最優(yōu)化問題(整數(shù)規(guī)劃、０－１規(guī)劃)、非線性最優(yōu)化問題、二次規(guī)劃、多目標(biāo)規(guī)劃。

2、現(xiàn)代優(yōu)化問題（動(dòng)態(tài)優(yōu)化問題）

動(dòng)態(tài)規(guī)劃與最優(yōu)控制問題組合優(yōu)化問題最優(yōu)化問題分類經(jīng)典優(yōu)化問題（靜態(tài)優(yōu)化問題）和現(xiàn)代優(yōu)化問題最優(yōu)解的相關(guān)定義定義１.1可行解滿足約束條(1.2)和(1.3)的x稱為可行解，也稱為可行點(diǎn)或容許點(diǎn)。定義１.2可行域全體可行解構(gòu)成的集合稱為可行域，也稱為容許集，記為D,即：最優(yōu)解的相關(guān)定義定義１.1可行解滿足約束條(1.2)和(定義１.3整體(全局）最優(yōu)解對于一切則稱恒有為最優(yōu)化問題的整體(全局）最優(yōu)解。若恒有則稱為最優(yōu)化問題的嚴(yán)格整體（全局）最優(yōu)解。定義１.3整體(全局）最優(yōu)解對于一切則稱恒有為最優(yōu)化問題的定義１.4局部最優(yōu)解若：

存在的某鄰域使得對于一切恒有則稱為最優(yōu)化問題的局部最優(yōu)解。其中同樣有：嚴(yán)格局部最優(yōu)解。定義１.4局部最優(yōu)解若：存在的某鄰域使得對于一切恒有則而局部最優(yōu)解不一定是整體最優(yōu)解。顯然，整體最優(yōu)解一定是局部最優(yōu)解，注意：求解最優(yōu)化問題，實(shí)際上是求可行域

D上的整體最優(yōu)解。但是，在一般情況下，整體最優(yōu)解是很難求出的，往往只能求出局部最優(yōu)解。而局部最優(yōu)解不一定是整體最優(yōu)解。顯然，整體最優(yōu)解一定是局定義１.5范數(shù)：

在維向量空間中，定義實(shí)函數(shù)使其滿足以下三個(gè)條件：（１）對任意有在當(dāng)且僅當(dāng)時(shí)（２）對任意及實(shí)數(shù)有（３）對任意有則稱函數(shù)為上的向量范數(shù)。定義１.5范數(shù)：在維向量空間中，定義實(shí)函數(shù)使其滿足以下三兩類比較常見的范數(shù)P-范數(shù)：其中最常用的是2-范數(shù)，即：范數(shù)：兩類比較常見的范數(shù)P-范數(shù)：其中最常用的是2-范數(shù)，即：范數(shù)最優(yōu)化方法概述

求解的一種算法，通常是指一種產(chǎn)生點(diǎn)列的程序。常表現(xiàn)為的一種映射F，它常常滿足以下兩點(diǎn)要求：（1）;（2）

式（1）實(shí)際上常表現(xiàn)為。因此通常構(gòu)造映射F的關(guān)鍵就在于設(shè)計(jì)一種能從出發(fā)，確定方向與步長的方法，要求滿足式（2）并使整個(gè)序列（或子列）具有收斂性。最優(yōu)化方法概述求解的一種算法迭代算法

選取一個(gè)初始可行點(diǎn)

由這個(gè)初始可行點(diǎn)出發(fā)，依次產(chǎn)生一個(gè)可行點(diǎn)列：

恰好是問題的一個(gè)最優(yōu)解，或者該點(diǎn)列收斂到問題的一個(gè)最優(yōu)解。迭代算法選取一個(gè)初始可行點(diǎn)可行點(diǎn)列的產(chǎn)生在處求得一個(gè)方向（可行下降方向）在射線上求一點(diǎn)：使得其中稱為步長?？尚悬c(diǎn)列的產(chǎn)生在處求得一個(gè)方向（可行下降方向）在射線上求一點(diǎn)下降方向定義1.6下降方向：在點(diǎn)處，對于方向若存在實(shí)數(shù)使得任意的有：成立，則稱為函數(shù)在點(diǎn)處的一個(gè)下降方向。下降方向定義1.6下降方向：在點(diǎn)處，對于方向若存在實(shí)數(shù)使得任當(dāng)具有連續(xù)的一階偏導(dǎo)數(shù)，令由Taylor公式：當(dāng)時(shí)，有所以（充分小時(shí)）是在處的一個(gè)下降方向。通常稱滿足：的方向?yàn)樵谔幍南陆捣较?。?dāng)具有連續(xù)的一階偏導(dǎo)數(shù)，令由Taylor公式：當(dāng)時(shí)，有所以（可行方向定義1.7可行方向：已知區(qū)域?qū)τ谙蛄咳舸嬖趯?shí)數(shù)使得任意的有：則稱為點(diǎn)處關(guān)于區(qū)域的可行方向。下降方向關(guān)于區(qū)域可行，則稱為可行下降方向?？尚蟹较蚨x1.7可行方向：已知區(qū)域?qū)τ谙蛄咳舸嬖趯?shí)數(shù)使得任最優(yōu)化問題的算法的一般迭代格式給定初始點(diǎn)令（１）確定處的可行下降方向（２）確定步長使得：（３）令（４）若滿足某種終止準(zhǔn)則，則停止；否則令轉(zhuǎn)（１）最優(yōu)化問題的算法的一般迭代格式給定初始點(diǎn)令（１）確定處的可行收斂性

如果一個(gè)算法只有當(dāng)初始點(diǎn)充分接近最優(yōu)解時(shí)，產(chǎn)生的點(diǎn)列才收斂，則稱該算法為具有局部收斂的算法。

如果對任意的初始點(diǎn)，由算法產(chǎn)生的點(diǎn)列都收斂，則稱該算法為具有全局收斂的算法。

具有全局收斂性的算法才有實(shí)用意義。但對算法的局部收斂性分析，在理論上是重要的，因?yàn)樗侨质諗啃苑治龅幕A(chǔ)。收斂性如果一個(gè)算法只有當(dāng)初始點(diǎn)充分接近最優(yōu)解時(shí)，產(chǎn)生收斂速度定義1.8設(shè)序列收斂于而且若則稱序列為線性收斂的，稱為收斂比；若則稱序列為超線性收斂的。收斂速度定義1.8設(shè)序列收斂于而且若則稱序列為線性收斂的，稱收斂速度定義1.9設(shè)序列收斂于若對則稱序列為有：階收斂的。特別當(dāng)：時(shí)稱為二階收斂的。收斂速度定義1.9設(shè)序列收斂于若對則稱序列為有：階收斂的。特終止準(zhǔn)則對于一種算法，應(yīng)該有某種終止準(zhǔn)則，當(dāng)某次迭代滿足終止準(zhǔn)則時(shí)，就停止迭代。常用的終止準(zhǔn)則有：（1）或或（３）其中是預(yù)先給定的。（2）終止準(zhǔn)則對于一種算法，應(yīng)該有某種終止準(zhǔn)則，當(dāng)某次迭代滿足終止最優(yōu)化模型的建立建立數(shù)學(xué)模型：在對實(shí)際問題深入研究的基礎(chǔ)上，利用有關(guān)數(shù)學(xué)的知識(shí)和概念，對自然規(guī)律的真實(shí)描述（數(shù)學(xué)描述）或模擬。實(shí)例分析1、生產(chǎn)計(jì)劃問題資源分配問題

書第4-5頁例第195頁資源分配問題就是將數(shù)量一定的一種或若干種資源（例如原材料、資金、設(shè)備、設(shè)施、勞力等），恰當(dāng)?shù)胤峙浣o若干使用者或地區(qū)，從而使目標(biāo)函數(shù)最優(yōu)。線性規(guī)劃模型最優(yōu)化模型的建立建立數(shù)學(xué)模型：在對實(shí)際問題深入研究的基礎(chǔ)上，2、食譜問題

設(shè)市場上可買到種不同的食品，第種食品的單位售價(jià)為。每種食品含有種基本營養(yǎng)成分，第種食品每一個(gè)單位含有第種營養(yǎng)成分為。又設(shè)每人每天對第種營養(yǎng)成分的需要量不少于。試確定在保證營養(yǎng)要求條件下的最經(jīng)濟(jì)食譜。線性規(guī)劃模型2、食譜問題線性規(guī)劃模型3、選址問題（類似的問題P89)

某城市要建設(shè)一個(gè)煤氣供應(yīng)中心，該中心向城市中個(gè)用戶（用戶位置固定）提供輸送煤氣服務(wù)。對于給定的坐標(biāo)系而言，已知第個(gè)用戶位置的坐標(biāo)為。如果輸送管道不受道路影響（即只考慮直線距離），問如何確定該中心的位置，才能使總的輸送管道最短，同時(shí)中心到第個(gè)用戶的距離必須介于和之間。非線性規(guī)劃模型3、選址問題（類似的問題P89)非線性規(guī)劃模型4、最短路問題(圖論極值問題）或最優(yōu)管道鋪設(shè)問題(類似問題166頁)動(dòng)態(tài)規(guī)劃模型4、最短路問題(圖論極值問題）動(dòng)態(tài)規(guī)劃模型線性規(guī)劃1、線性規(guī)劃模型的建立2、線性規(guī)劃模型的尋優(yōu)線性規(guī)劃1、線性規(guī)劃模型的建立線性規(guī)劃模型的建立建立優(yōu)化模型的三大要素（1）確定決策變量（2）確定目標(biāo)（決策準(zhǔn)則）（3）確定約束條件實(shí)例分析

（1）生產(chǎn)計(jì)劃資源分配問題線性規(guī)劃模型的建立建立優(yōu)化模型的三大要素例2.1某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，需要消耗R1、R2、和R3三種資源（例如鋼材、煤炭或設(shè)備臺(tái)時(shí)等），已知每件產(chǎn)品對這三種資源的消耗、這三種資源可供使用的量及每單位產(chǎn)品可獲得的利潤如表2.1所示。問應(yīng)如何安排生產(chǎn)計(jì)劃，使得既能充分利用現(xiàn)有資源，又使總利潤最大？試建立問題的數(shù)學(xué)模型。(P10-11)

單件產(chǎn)品消耗資源

甲乙可供使用資源量R1R2R3522315170100150單件利潤1018表2-1例2.1某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，需（2）原材料的合理利用問題（P11-12）（2）原材料的合理利用問題（P11-12）（3）0-1背包問題(P12)背包問題(P13)（3）0-1背包問題(P12)背包問題(P13(4)運(yùn)輸問題

(4)運(yùn)輸問題(5)分派（指派）問題

(5)分派（指派）問題線性的特點(diǎn)比例性可加性線性的特點(diǎn)比例性共同的特征每一個(gè)線性規(guī)劃問題都用一組決策變量表示某一方案，這組決策變量的值就代表一個(gè)具體方案。一般這些變量取值是非負(fù)且連續(xù)的；(2)要有各種資源和使用有關(guān)資源的技術(shù)數(shù)據(jù),創(chuàng)造新價(jià)值的數(shù)據(jù)；共同的特征每一個(gè)線性規(guī)劃問題都用一組決策變量共同的特征（繼續(xù)）(3)存在可以量化的約束條件，這些約束條件可以用一組線性等式或線性不等式來表示；(4)要有一個(gè)達(dá)到目標(biāo)的要求，它可用決策變量的線性函數(shù)(稱為目標(biāo)函數(shù))來表示。按問題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。共同的特征（繼續(xù)）(3)存在可以量化的約束條件，這些約束它們的對應(yīng)關(guān)系可用表格表示：它們的對應(yīng)關(guān)系可用表格表示：線性規(guī)劃的一般模型形式線性規(guī)劃的一般模型形式

線性規(guī)劃模型的標(biāo)準(zhǔn)形式

線性規(guī)劃模型的標(biāo)準(zhǔn)形式線性規(guī)劃模型的幾種表示形式線性規(guī)劃模型的幾種表示形式向量表示式向量表示式矩陣表示式矩陣表示式如何變換為標(biāo)準(zhǔn)形(1)當(dāng)目標(biāo)函數(shù)為求極（最）大值時(shí),即，這時(shí)只需令，即轉(zhuǎn)化為。這就同標(biāo)準(zhǔn)形的目標(biāo)函數(shù)的形式一致了。(2)約束方程為不等式。這里有兩種情況：一種是約束方程為“≤”不等式，則可在“≤”不等式的左端加入非負(fù)松弛變量，把原“≤”不等式變?yōu)榈仁?；另一種是約束方程為“≥”不等式，則可在“≥”不等式的左端減去一個(gè)非負(fù)剩余變量(也可稱松弛變量)，把不等式約束條件變?yōu)榈仁郊s束條件。如何變換為標(biāo)準(zhǔn)形(1)當(dāng)目標(biāo)函數(shù)為求極（最）大值時(shí),即如何變換為標(biāo)準(zhǔn)型(續(xù)）（3）當(dāng)約束條件的右端常數(shù)項(xiàng)時(shí)，只需將等式或不等式兩端同乘以即可。（4）當(dāng)決策變量的取值約束為時(shí)，令，則有。（5）當(dāng)決策變量的取值無任何約束時(shí)，令，則由表示的不受任何取值的約束。

如何變換為標(biāo)準(zhǔn)型(續(xù)）（3）當(dāng)約束條件的右端常數(shù)項(xiàng)線性規(guī)劃的分類

線性規(guī)劃一般線性規(guī)劃

特殊線性規(guī)劃

整數(shù)規(guī)劃

運(yùn)輸問題

純整數(shù)規(guī)劃混合整數(shù)規(guī)劃

0-1規(guī)劃

指派問題的線性規(guī)劃

線性規(guī)劃的分類線一般線性規(guī)劃特殊線整數(shù)規(guī)劃運(yùn)輸問題純解的相關(guān)概念

基本概念

定義2.1在線性規(guī)劃問題中，凡是滿足其全部約束條件（包括變量取值約束）的一組決策變量的取值稱作該線性規(guī)劃問題的可行解。定義2.2線性規(guī)劃問題中，可行解的集合稱為該問題的可行域。定義2.3在線性規(guī)劃問題的可行域中，使目標(biāo)函數(shù)值達(dá)到最優(yōu)（最大或最?。┑目尚薪夥Q為該問題的最優(yōu)解。相應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)值。

解的相關(guān)概念基本概念凸集定義1設(shè)集合若對于任意兩點(diǎn)及實(shí)數(shù)都有：則稱集合為凸集．注：常見的凸集：空集，整個(gè)歐氏空間超平面：半空間：凸集定義1設(shè)集合若對于任意兩點(diǎn)及實(shí)數(shù)都有：則稱集合為凸集．注例1：證明超球?yàn)橥辜C明：設(shè)為超球中的任意兩點(diǎn)，則有：即點(diǎn)屬于超球所以超球?yàn)橥辜?：證明超球?yàn)橥辜C明：設(shè)為超球中的任意兩點(diǎn)，則有：即點(diǎn)凸集的性質(zhì)（１）有限個(gè)（可以改成無限）凸集的交集為凸集．（２）設(shè)是凸集，是一實(shí)數(shù)，則下面的集合是凸集：（３）設(shè)是凸集，則的和集是凸集凸集的性質(zhì)（１）有限個(gè)（可以改成無限）凸集的交集為凸集．（２注：和集和并集有很大的區(qū)別，凸集的并集未必是凸集，而凸集的和集是凸集．例：表示軸上的點(diǎn)．表示軸上的點(diǎn)．則表示兩個(gè)軸的所有點(diǎn)，它不是凸集；而凸集．注：和集和并集有很大的區(qū)別，凸集的并集未必是凸集，而凸集的和推論：設(shè)是凸集，則也是凸集，其中是實(shí)數(shù)．定義2:設(shè)實(shí)數(shù)則稱為的凸組合．注：凸集中任意有限個(gè)點(diǎn)的凸組合仍然在該凸集中．推論：設(shè)是凸集，則也是凸集，其中是實(shí)數(shù)．定義2:設(shè)實(shí)數(shù)則極點(diǎn)（頂點(diǎn)）定義1設(shè)為凸集，若中不存在兩個(gè)相異的點(diǎn)及某一實(shí)數(shù)使得則稱為的極點(diǎn)．例：則上的點(diǎn)均為極點(diǎn)．極點(diǎn)（頂點(diǎn)）定義1設(shè)為凸集，若中不存在兩個(gè)相異的點(diǎn)及某一實(shí)數(shù)證：設(shè)若存在及使得則：不等式要取等號(hào)，必須且容易證明根據(jù)定義可知為極點(diǎn)．證：設(shè)若存在及使得則：不等式要取等號(hào)，必須且容易證明根據(jù)定義與算法有關(guān)的概念無窮多解圖解法中，此情況出現(xiàn)在目標(biāo)函數(shù)等值直線向優(yōu)化方向平移時(shí)，最后與可行域邊界的一條邊重合，此時(shí)，除該直線段的兩個(gè)端點(diǎn)（即可行域的兩個(gè)頂點(diǎn)）外，直線段上所有點(diǎn)的目標(biāo)函數(shù)值都達(dá)到最優(yōu)。無界解圖解法中，此情況出現(xiàn)在可行域?yàn)闊o界區(qū)域，且目標(biāo)函數(shù)等值直線向優(yōu)化方向平移時(shí)，始終無法脫離可行域。發(fā)生這種情況往往是建模時(shí)遺漏了某些約束條件所至。無解當(dāng)可行域?yàn)榭占瘯r(shí)，問題不存在可行解。發(fā)生此情況是因?yàn)槟Ｐ椭谐霈F(xiàn)了相互矛盾的約束條件。

圖解法中解的概念與算法有關(guān)的概念無窮多解圖解法中，此情況出現(xiàn)在目標(biāo)函數(shù)等與算法有關(guān)的概念可行解、最優(yōu)解基、基向量、基變量基解、基可行解可行基與單純形法有關(guān)的解概念與算法有關(guān)的概念可行解、最優(yōu)解與單純形法有關(guān)的解概念可行解、最優(yōu)解滿足約束條件(1-2)，(1-3)式的解稱為線性規(guī)劃問題的可行解，其中使目標(biāo)函數(shù)達(dá)到最小值的可行解稱為最優(yōu)解?？尚薪?、最優(yōu)解滿足約束條件(1-2)，(1-3)式的解基、基向量、基變量基、基向量、基變量基解、基可行解

基解：滿足約束方程組（1-2）且非基變量為0的解。基可行解：滿足非負(fù)條件（1-3）的基解.

基可行解的非零分量的數(shù)目也不大于m，并且都是非負(fù)的。

基解、基可行解基解：滿足約束方程組（1-2）且非基變量可行基

對應(yīng)于基可行解的基，稱為可行基。約束方程組(1-2)具有基解的數(shù)目最多是個(gè)。一般基可行解的數(shù)目要小于基解的數(shù)目。以上提到的幾種解的概念，它們之間的關(guān)系可用圖6表明。另外還要說明一點(diǎn)，基解中的非零分量的個(gè)數(shù)小于m個(gè)時(shí)，該基解是退化解。在以下討論時(shí)，假設(shè)不出現(xiàn)退化的情況。以上給出了線性規(guī)劃問題的解的概念和定義，它們將有助于用來分析線性規(guī)劃問題的求解過程。

可行基對應(yīng)于基可行解的基，稱為可行基。可行解、基解、基可行解之間的關(guān)系圖6可行解、基解、基可行解之間的關(guān)系圖6與算法有關(guān)的概念與內(nèi)點(diǎn)法有關(guān)的解概念與算法有關(guān)的概念與內(nèi)點(diǎn)法有關(guān)的解概念與算法有關(guān)的概念與其他算法有關(guān)的解概念與算法有關(guān)的概念與其他算法有關(guān)的解概念與算法有關(guān)的概念與其他算法有關(guān)的解概念與算法有關(guān)的概念與其他算法有關(guān)的解概念線性規(guī)劃的尋優(yōu)方法圖解法單純形方法內(nèi)點(diǎn)法計(jì)算機(jī)求解分支定界法隱枚舉法表上作業(yè)法匈牙利法只有二個(gè)變量的線性規(guī)劃問題一般LP特殊LP整數(shù)線性規(guī)劃問題0-1規(guī)劃問題平衡運(yùn)輸問題指派問題重要的方法線性規(guī)劃的尋優(yōu)方法圖解法只有二個(gè)變量的線性規(guī)劃問題一般LP特

圖解法

對于只有兩個(gè)變量的線性規(guī)劃問題，可以采用在平面上作圖的方法求解，稱為圖解法。例1

用圖解法求解

因存在，所以必須在直角坐標(biāo)的第1象限內(nèi)作圖，求解。圖解法對于只有兩個(gè)變量的線性規(guī)劃問題，可以采（1）在平面直角坐標(biāo)系上畫出可行域（1）在平面直角坐標(biāo)系上畫出可行域

(2)畫出目標(biāo)函數(shù)等值線，并沿其法線方向平移等值線，以求得最優(yōu)解。目標(biāo)值在（4，2）點(diǎn)，達(dá)到最大值14目標(biāo)函數(shù)圖1(2)畫出目標(biāo)函數(shù)等值線，并沿其法線方向平移等值線，以最優(yōu)化及最優(yōu)化方法講稿課件可能出現(xiàn)的幾種情況（1）無窮多最優(yōu)解(多重最優(yōu)解)目標(biāo)函數(shù)maxz=2x1+4x2

圖3可能出現(xiàn)的幾種情況（1）無窮多最優(yōu)解(多重最優(yōu)解)目標(biāo)函數(shù)

（2）無界解圖4

（2）無界解圖4

（3）無可行解

當(dāng)存在矛盾的約束條件時(shí)，為無可行域。如果在例1的數(shù)學(xué)模型中增加一個(gè)約束條件:該問題的可行域?yàn)榭占?，即無可行解，

（3）無可行解當(dāng)存在矛盾的約束條件時(shí)，為

不存在可行域增加的約束條件圖5不存在可行域增加的約束條件圖5小結(jié)（1）線性規(guī)劃問題的模型特征（2）通過圖解法了解如何求解線性規(guī)劃問題（3）為求解高維線性規(guī)劃問題，必須建立的概念小結(jié)（1）線性規(guī)劃問題的模型特征線性規(guī)劃的單純形方法線性規(guī)劃問題的幾個(gè)定理單純形法的原理初始基可行解的確定線性規(guī)劃的單純形方法線性規(guī)劃問題的幾個(gè)定理線性規(guī)劃問題的幾個(gè)定理定理1若線性規(guī)劃問題存在可行解，則問題的可行域是凸集。定理2線性規(guī)劃問題的基可行解對應(yīng)線性規(guī)劃問題可行域（凸集）的頂點(diǎn)（極點(diǎn)）。定理3若線性規(guī)劃問題有最優(yōu)解，則一定存在一個(gè)基可行解是最優(yōu)解。結(jié)論：求解線性規(guī)劃問題歸結(jié)為找最優(yōu)基可行解，即在其可行域（凸集）的頂點(diǎn)（極點(diǎn)）中找使目標(biāo)函數(shù)最小的頂點(diǎn)（極點(diǎn)）。線性規(guī)劃問題的幾個(gè)定理定理1若線性規(guī)劃問題存在可行解，則問單純形法的原理單純形方法的基本思想

從一個(gè)基可行解出發(fā)，求一個(gè)使目標(biāo)函數(shù)值有所改善的基可行解；通過不斷改進(jìn)基可行解，力圖達(dá)到最優(yōu)基可行解。它主要通過基可行解的轉(zhuǎn)換完成?；尚薪獾霓D(zhuǎn)換

考慮矩陣形式的標(biāo)準(zhǔn)形問題：式中單純形法的原理單純形方法的基本思想最優(yōu)化及最優(yōu)化方法講稿課件最優(yōu)化及最優(yōu)化方法講稿課件最優(yōu)化及最優(yōu)化方法講稿課件最優(yōu)化及最優(yōu)化方法講稿課件最優(yōu)化及最優(yōu)化方法講稿課件最優(yōu)性檢驗(yàn)和解的判別最優(yōu)性檢驗(yàn)和解的判別單純形方法的計(jì)算步驟步驟1找一個(gè)初始基可行解（常用大M法和兩階法找）。步驟2解步驟3求單純形乘子，解單純形方法的計(jì)算步驟步驟1找一個(gè)初始基可行解（常用大M法和最優(yōu)化及最優(yōu)化方法講稿課件使用表格形式的單純形方法使用表格形式的單純形方法使用表格形式的單純形方法

用單純形法解下列問題：

使用表格形式的單純形方法用單純形法解下列問題：初始基可行解的確定大M法基本思想：在約束中增加人工變量，同時(shí)改變目標(biāo)函數(shù)，加上罰項(xiàng)，其中是很大的正數(shù)，這樣，在極小化目標(biāo)函數(shù)的過程中，由于大的存在，將使人工變量離基。考慮線性規(guī)劃問題初始基可行解的確定大M法大M法

引進(jìn)人工變量，研究下列問題：用單純形法求解線性規(guī)劃問題(1-14)，獲得其解，它與（1-13）的解的關(guān)系如下：大M法引進(jìn)人工變量，研究下列問題：大M法達(dá)到問題（1-14）的最優(yōu)解，且，這時(shí)得到的為問題（1-13）的最優(yōu)解。達(dá)到問題（1-14）的最優(yōu)解，且，這時(shí)問題（1-13）無可行解。問題（1-14）不存在有限最優(yōu)值，在單純形表中，，這時(shí)問題（1-13）無界。問題（1-14）不存在有限最優(yōu)值，在單純形表中，，這時(shí)問題（1-13）無可行解。大M法達(dá)到問題（1-14）的最優(yōu)解，且，這時(shí)得到大M法用大M法求解下列問題：大M法用大M法求解下列問題：兩個(gè)階段法基本思想：在約束中增加人工變量，以構(gòu)造一個(gè)單位矩陣。對添加了人工變量的線性規(guī)劃問題分兩個(gè)階段計(jì)算。第一階段是用單純形方法消去人工變量（如果可能的話），即把人工變量都變成非基變量，求出原來問題的一個(gè)基本可行解。消去人工變量的一種方法是解下列第一階段問題：兩個(gè)階段法基本思想：在約束中增加人工變量，以構(gòu)造一個(gè)兩個(gè)階段法

求解（1-16），設(shè)得到的最優(yōu)基本可行解是，此時(shí)必有下列三種情形之一：這時(shí)（1-13）無可行解。的分量都是非基變量，這時(shí)的基變量都是原來的變量，又知

是（1-16）的基可行解，因此是（1-13）的一個(gè)基可行解。

兩個(gè)階段法求解（1-16），設(shè)得到的最優(yōu)基本可行解是兩個(gè)階段法

的某些分量是基變量，這時(shí)可用主元消去法，把原來變量中的某些非基變量引進(jìn)基，替換出基變量中的人工變量，再開始兩階段法的第二階段。應(yīng)該指出，為替換出人工變量而采用的主元消去法，在主元的選擇上，并不要求遵守單純形法確定離進(jìn)基變量的規(guī)則。兩階段法的第二階段，就是從得到的基可行解出發(fā)，用單純形方法求（1-13）的最優(yōu)解。即在問題（1-16）中去掉人工變量，以第一階段最后的基變量為初始基變量開始迭代。操作上可直接在第一階段的最終單純形表基礎(chǔ)上進(jìn)行，只需在表中除去人工變量列、恢復(fù)目標(biāo)價(jià)值向量為原問題之前的狀況即可。兩個(gè)階段法的某些分量是基變兩個(gè)階段法用兩階段法求解下列問題：兩個(gè)階段法用兩階段法求解下列問題：內(nèi)點(diǎn)法

卡瑪卡（Karmarkar）算法--投影尺度法

在大型問題的應(yīng)用中，顯示出能與單純形法競爭的潛力

不能直接用于通常形式的線性規(guī)劃問題

原仿射尺度法(改進(jìn)的內(nèi)點(diǎn)法)

可以直接求解標(biāo)準(zhǔn)形式的線性規(guī)劃問題

內(nèi)點(diǎn)法卡瑪卡（Karmarkar）算法--投影尺度法理論依據(jù)

定理2.5

在仿射尺度變換下，的正卦限中的點(diǎn)仍變?yōu)檎韵拗械狞c(diǎn)，但其分量值發(fā)生變化。特別地，的像點(diǎn)為。定理2.6

設(shè)為行滿秩矩陣，則向量在的零空間上的正交投影為理論依據(jù)定理2.5在仿射尺度變換基本思想

先找出一個(gè)內(nèi)點(diǎn)可行解；從該點(diǎn)出發(fā)，在可行域的內(nèi)部尋求一個(gè)使目標(biāo)函數(shù)值下降的可行方向，沿該方向移動(dòng)到一個(gè)新的內(nèi)點(diǎn)可行解；如此逐步移動(dòng)，當(dāng)移動(dòng)到與最優(yōu)解充分接近時(shí)，迭代停止。基本思想先找出一個(gè)內(nèi)點(diǎn)可行解；從該點(diǎn)出發(fā)，計(jì)算步驟及框圖計(jì)算步驟

（P41-42）

關(guān)鍵的問題是：對于任一迭代點(diǎn)，如何求得一個(gè)適當(dāng)?shù)囊苿?dòng)方向，使是一個(gè)改進(jìn)的內(nèi)點(diǎn)可行解。

利用仿射尺度變換的逆變換

定理2.5-2.6，可找到：

,

計(jì)算步驟及框圖計(jì)算步驟（P41-42）計(jì)

算

框

圖P42

計(jì)

算

框

圖P42例題及初始內(nèi)點(diǎn)可行解的確定

例2.10

用原仿射尺度算法求解如下問題（P43-44)初始內(nèi)點(diǎn)可行解的確定（P44）

方法：類似于單純形方法的大M法。例題及初始內(nèi)點(diǎn)可行解的確定例2.10用原仿射尺度算法求解線性規(guī)劃問題的計(jì)算機(jī)求解

現(xiàn)在已經(jīng)出現(xiàn)了很多能夠求解線性規(guī)劃問題的計(jì)算機(jī)軟件產(chǎn)品，如Lindo,Lingo或Matlab等。下面以Matlab6.x為背景，介紹如何在Matlab中求解線性規(guī)劃。將模型轉(zhuǎn)換成如下“標(biāo)準(zhǔn)形式”：

線性規(guī)劃問題的計(jì)算機(jī)求解現(xiàn)在已經(jīng)出現(xiàn)了很多能線性規(guī)劃問題的計(jì)算機(jī)求解

在上述標(biāo)準(zhǔn)形式中，目標(biāo)函數(shù)求極小，約束條件嚴(yán)格地分為三類：不等式約束且取“

”不等號(hào)、等式約束及變量取值范圍約束。其中

線性規(guī)劃問題的計(jì)算機(jī)求解在上述標(biāo)準(zhǔn)形式中，目標(biāo)函線性規(guī)劃問題的計(jì)算機(jī)求解

調(diào)用時(shí)需注意以下幾點(diǎn)：（1）Matlab提供了一種機(jī)制，允許調(diào)用某個(gè)函數(shù)時(shí)提供的參數(shù)個(gè)數(shù)少于定義該函數(shù)時(shí)所定義的參數(shù)個(gè)數(shù)。因此，在調(diào)用函數(shù)linprog傳遞參數(shù)時(shí)必須按語法指定的順序?qū)?yīng)傳遞，若缺少某些參數(shù)，除非其位于參數(shù)表的尾部，否則調(diào)用時(shí)必須以空數(shù)組“[]”形式占位。（2）若問題的模型為目標(biāo)函數(shù)求最（極）大，須先將目標(biāo)函數(shù)轉(zhuǎn)換為最（極）小。（3）代碼中所使用的標(biāo)點(diǎn)分隔符，如逗號(hào)、分號(hào)、括號(hào)等，必須是半角字符。線性規(guī)劃問題的計(jì)算機(jī)求解調(diào)用時(shí)需注意以下幾點(diǎn)：線性規(guī)劃問題的計(jì)算機(jī)求解寫出下列問題的Matlab調(diào)用代碼：線性規(guī)劃問題的計(jì)算機(jī)求解寫出下列問題的Matlab調(diào)用代碼：最優(yōu)化及最優(yōu)化方法講稿課件分支定界法與隱枚舉法

解決的問題各是什么？理論依據(jù)Discuss基本思想計(jì)算步驟及框圖計(jì)算中的說明計(jì)算機(jī)求解的異同？講P62例2.13

練P907（1）分支定界法與隱枚舉法解決的問題各是什么？分支定界法的計(jì)算框圖分支定界法的計(jì)算框圖隱枚舉法的計(jì)算框圖隱枚舉法的計(jì)算框圖表上作業(yè)法與匈牙利法

解決的問題各是什么？理論依據(jù)Discuss基本思想計(jì)算步驟及框圖計(jì)算中的說明

表上作業(yè)法是單純形法在求解運(yùn)輸問題時(shí)的一種簡化方法，其實(shí)質(zhì)是單純形法。結(jié)合算法步驟講P63例2.14和P67例2.15.表上作業(yè)法與匈牙利法解決的問題各是什么？表上作業(yè)法的計(jì)算框圖表上作業(yè)法的計(jì)算框圖匈牙利法的計(jì)算框圖匈牙利法的計(jì)算框圖第三專題非線性優(yōu)化問題1、非線性優(yōu)化模型的建立2、非線性優(yōu)化模型的尋優(yōu)第三專題非線性優(yōu)化問題1、非線性優(yōu)化模型的建立非線性優(yōu)化模型的建立確定決策變量確定目標(biāo)（決策準(zhǔn)則）確定約束條件非線性優(yōu)化模型的建立確定決策變量實(shí)例分析（1）投資決策問題（P88)（2）曲線擬合問題在實(shí)驗(yàn)數(shù)據(jù)處理或統(tǒng)計(jì)資料分析中，常常遇到這樣的問題：如何利用有關(guān)變量的實(shí)驗(yàn)數(shù)據(jù)（資料）去確定這些變量間的函數(shù)關(guān)系。例如，已知某物體的溫度與時(shí)間之間有如下形式的經(jīng)驗(yàn)函數(shù)關(guān)系：其中是待定參數(shù)。通過測試獲得n組溫度與時(shí)間之間的實(shí)驗(yàn)數(shù)據(jù)，試確定參數(shù)使理論曲線盡可能地與n個(gè)測試點(diǎn)擬合。

實(shí)例分析（1）投資決策問題（P88)非線性規(guī)劃問題的共同特征

都是求一個(gè)目標(biāo)函數(shù)在一組約束條件下的極值問題。在目標(biāo)函數(shù)或約束條件中，至少有一個(gè)是變量的非線性函數(shù)。非線性規(guī)劃問題的共同特征都是求一個(gè)目標(biāo)函數(shù)在一組約束條件下非線性規(guī)劃問題一般形式：向量形式：非線性規(guī)劃問題一般形式：非線性優(yōu)化問題的尋優(yōu)相關(guān)概念及理論一維最優(yōu)化方法多維無約束最優(yōu)化方法多維有約束最優(yōu)化方法非線性優(yōu)化問題的尋優(yōu)相關(guān)概念及理論非線性規(guī)劃的相關(guān)概念及理論一階導(dǎo)數(shù)、二階導(dǎo)數(shù)和n元函數(shù)的Taylor公式非線性規(guī)劃的相關(guān)概念及理論一階導(dǎo)數(shù)、二階導(dǎo)數(shù)和n元函數(shù)的Ta最優(yōu)化及最優(yōu)化方法講稿課件最優(yōu)化及最優(yōu)化方法講稿課件定義4設(shè)函數(shù)定義在凸集上，若對任意的及任意的都有：則稱函數(shù)為凸集上的凸函數(shù)．定義5嚴(yán)格凸函數(shù)注：將上述定義中的不等式反向，可以得到凹函數(shù)的定義．凸函數(shù)定義4設(shè)函數(shù)定義在凸集上，若對任意的及任意的都有：則稱函數(shù)為例1：設(shè)試證明在上是嚴(yán)格凸函數(shù)．證明:設(shè)且都有：因此在上是嚴(yán)格凸函數(shù)．例1：設(shè)試證明在上是嚴(yán)格凸函數(shù)．證明:設(shè)且都有：因此在上是嚴(yán)例2：試證線性函數(shù)是證明:設(shè)上的凸函數(shù)．則所以是凸函數(shù)．類似可以證明是凹函數(shù)．例2：試證線性函數(shù)是證明:設(shè)上的凸函數(shù)．則所以是凸函數(shù)．類似凸函數(shù)的幾何性質(zhì)對一元函數(shù)在幾何上表示連接的線段．表示在點(diǎn)處的函數(shù)值．所以一元凸函數(shù)表示連接函數(shù)圖形上任意兩點(diǎn)的線段總是位于曲線弧的上方．凸函數(shù)的幾何性質(zhì)對一元函數(shù)在幾何上表示連接的線段．表示在點(diǎn)處最優(yōu)化及最優(yōu)化方法講稿課件凸函數(shù)的性質(zhì)（１）設(shè)（２）設(shè)函數(shù)，是凸集上的凸函數(shù)，實(shí)數(shù)則也是上的凸函數(shù)．是凸集上的凸實(shí)數(shù)則也是上的凸函數(shù)．（３）設(shè)是凸集上的凸函數(shù)，是實(shí)數(shù)，則水平集是凸集．凸函數(shù)的性質(zhì)（１）設(shè)（２）設(shè)函數(shù)，是凸集上的凸函數(shù)，實(shí)數(shù)則也下面的圖形給出了凸函數(shù)的等值線的圖形，可以看出水平集是凸集下面的圖形給出了凸函數(shù)的等值線的圖形，可以看出水平集是凸集凸函數(shù)的判定定理1設(shè)上，令則:(1)是定義在凸集是凸集上的凸函數(shù)的充要條件是對任意的一元函數(shù)為上的凸函數(shù).(2)設(shè)若在上為嚴(yán)格凸函數(shù)，則在上為嚴(yán)格凸函數(shù)．凸函數(shù)的判定定理1設(shè)上，令則:(1)是定義在凸集是凸集上的凸該定理的幾何意義是：凸函數(shù)上任意兩點(diǎn)之間的部分是一段向下凸的?。摱ɡ淼膸缀我饬x是：凸函數(shù)上任意兩點(diǎn)之間的部分是一段向下凸的一階條件定理2.1設(shè)在凸集上可微，則：在上為凸函數(shù)的充要條件是對任意的都有：定理2.2嚴(yán)格凸函數(shù)(充要條件)一階條件定理2.1設(shè)在凸集上可微，則：在上為凸函數(shù)的充要條件二階條件定理3設(shè)在開凸集內(nèi)二階可微，則(1)是內(nèi)的凸函數(shù)的充要條件為，在內(nèi)任一點(diǎn)處，的海色矩陣半正定,其中：二階條件定理3設(shè)在開凸集內(nèi)二階可微，則(1)是內(nèi)的凸函數(shù)的充二階條件定理3設(shè)在開凸集內(nèi)(2)若在內(nèi)正定,則在內(nèi)二階可微，則是嚴(yán)格凸函數(shù)．注:反之不成立．例：顯然是嚴(yán)格凸的，但在點(diǎn)處不是正定的二階條件定理3設(shè)在開凸集內(nèi)(2)若在內(nèi)正定,則在內(nèi)二階可微，凸規(guī)劃定義6設(shè)為凸集，為上的凸函數(shù)，則稱規(guī)劃問題為凸規(guī)劃問題．定理4(1)凸規(guī)劃問題的任一局部極小點(diǎn)是整體極小點(diǎn)，全體極小點(diǎn)組成凸集．(2)若是凸集上的嚴(yán)格凸函數(shù)，且凸規(guī)劃問題整體極小點(diǎn)存在，則整體極小點(diǎn)是唯一的．凸規(guī)劃定義6設(shè)為凸集，為上的凸函數(shù)，則稱規(guī)劃問題為凸規(guī)劃問題非線性規(guī)劃的最優(yōu)性條件

最優(yōu)性條件：是指非線性規(guī)劃模型的最優(yōu)解所要滿足的必要和充分條件。無約束最優(yōu)性條件

約束最優(yōu)性條件

非線性規(guī)劃的最優(yōu)性條件最優(yōu)性條件：是指非線性規(guī)無約束最優(yōu)性條件無約束最優(yōu)性條件一（單）元函數(shù)的最優(yōu)性條件（１）若（２）為的局部極小點(diǎn)，則若則為的嚴(yán)格局部極小點(diǎn)；若（３）為的局部極小點(diǎn)，則：一（單）元函數(shù)的最優(yōu)性條件（１）若（２）為的局部極小點(diǎn)，則若多元函數(shù)的一階必要條件（P106-107)定理1:若為的局部極小點(diǎn)，且在內(nèi)一階連續(xù)可導(dǎo)，則注:(1)僅僅是必要條件，而非充分條件．(2)滿足的點(diǎn)稱為駐點(diǎn)．駐點(diǎn)分為：極小點(diǎn)，極大點(diǎn)，鞍點(diǎn)．多元函數(shù)的一階必要條件（P106-107)定理1:若為的局部多元函數(shù)的二階充分條件定理2:若在內(nèi)二階連續(xù)可導(dǎo)，且正定,則為嚴(yán)格局部極小點(diǎn)．注:如果負(fù)定,則為嚴(yán)格局部極大點(diǎn)．多元函數(shù)的二階充分條件定理2:若在內(nèi)二階連續(xù)可導(dǎo)，二階必要條件和充要條件定理3:若為的局部極小點(diǎn)，且在內(nèi)二階連續(xù)可導(dǎo)，則半正定．定理4:設(shè)在上是凸函數(shù)且有一階連續(xù)偏導(dǎo)數(shù)，則為的整體極小點(diǎn)的充要條件是二階必要條件和充要條件定理3:若為的局部極小點(diǎn)，且在內(nèi)二階連例1：利用極值條件解下列問題：解：令即：得到駐點(diǎn)：例1：利用極值條件解下列問題：解：令即：得到駐點(diǎn)：函數(shù)的海色陣：由此，在點(diǎn)處的海色陣依次為：函數(shù)的海色陣：由此，在點(diǎn)處的海色陣依次為：由于矩陣不定，則不是極小點(diǎn)．負(fù)定，則不是極小點(diǎn)，實(shí)際上它是極大點(diǎn)．正定，則是局部極小點(diǎn)．由于矩陣不定，則不是極小點(diǎn)．負(fù)定，則不是極小點(diǎn)，實(shí)際上它是極約束最優(yōu)性條件(p133-p136)約束最優(yōu)性條件(p133-p136)定義1:有效約束：若(*)中的一個(gè)可行點(diǎn)使得某個(gè)不等式約束變成等式，即則稱為關(guān)于的有效(積極）約束．非有效約束：若對則稱為關(guān)于的非有效(無效）約束．有效集：定義2:錐：的子集，如果它關(guān)于正的數(shù)乘運(yùn)算是封閉的．如果錐也是凸集，則稱為凸錐．凸錐關(guān)于加法和正的數(shù)乘運(yùn)算是封閉的．定義1:有效約束：若(*)中的一個(gè)可行點(diǎn)使得某個(gè)不等式約束變一階必要條件定理3.5:(Kuhn-Tucker一階必要條件)(1951)設(shè)在（K-T條件）一階必要條件定理3.5:(Kuhn-Tucker一階必要條件一階必要條件定理1‘:(Kuhn-Tucker一階必要條件)（互補(bǔ)松弛條件）一階必要條件定理1‘:(Kuhn-Tucker一階必要條件)最優(yōu)化及最優(yōu)化方法講稿課件例2：驗(yàn)證是否滿足Kuhn-Tucker條件：試驗(yàn)證最優(yōu)點(diǎn)為KT點(diǎn)．例2：驗(yàn)證是否滿足Kuhn-Tucker條件：試驗(yàn)證最優(yōu)解：令所以即：所以：是KT點(diǎn)．解：令所以即：所以：是KT點(diǎn)．Lagrange函數(shù)及K-T條件Lagrange函數(shù)及K-T條件在一定凸性下的最優(yōu)性的充分條件在一定凸性下的最優(yōu)性的充分條件一維最優(yōu)化方法（線性搜索方法）已知并且求出了處的可行下降方向從出發(fā)，沿方向求目標(biāo)函數(shù)的最優(yōu)解，或者選取使得：問題描述即一維最優(yōu)化方法（線性搜索方法）已知并且求出了處的可行下降方向設(shè)其最優(yōu)解為（叫精確步長因子），所以線性搜索是求解一元函數(shù)的最優(yōu)化問題（也叫一維最優(yōu)化問題）。我們來求解：于是得到一個(gè)新點(diǎn)：設(shè)其最優(yōu)解為（叫精確步長因子），所以線性搜索是求解一元函數(shù)的一般地，線性搜索算法分成兩個(gè)階段：第一階段確定包含理想的步長因子（或問題最優(yōu)解）的搜索區(qū)間；第二階段采用某種分割技術(shù)或插值方法縮小這個(gè)區(qū)間。搜索區(qū)間：一般地，線性搜索算法分成兩個(gè)階段：第一階段確定包含理想的步長搜索區(qū)間求取方法

進(jìn)退法：一種簡單的確定初始搜索區(qū)間方法.基本思想：是從一點(diǎn)出發(fā)，按一定步長，試圖確定出函數(shù)值呈現(xiàn)“高-低-高”的三點(diǎn)，即

這里。具體地說，就是給出初始點(diǎn)，初始步長，若，則下一步從新點(diǎn)出發(fā)，加大步長，再向前搜索，直到目標(biāo)函數(shù)上升為止。搜索區(qū)間求取方法進(jìn)退法：一種簡單的確定初始搜索區(qū)間方法.

若，則下一步仍以為出發(fā)點(diǎn)，沿反方向同樣搜索，直到目標(biāo)函數(shù)上升就停止。這樣便得到一個(gè)搜索區(qū)間。這種方法叫進(jìn)退法。計(jì)算步驟：見P96計(jì)算框圖:見P97若最優(yōu)化及最優(yōu)化方法講稿課件黃金分割法（0.618法）基本思想：它通過對試探點(diǎn)的函數(shù)值進(jìn)行比較，使得包含極小點(diǎn)的區(qū)間不斷縮短，當(dāng)區(qū)間長度小到精度范圍之內(nèi)時(shí)，可以粗略地認(rèn)為區(qū)間上各點(diǎn)的函數(shù)值均接近于極小值。黃金分割法（0.618法）基本思想：設(shè)在上為下單峰函數(shù)，即有唯一的極小點(diǎn)在左邊嚴(yán)格下降，在右邊嚴(yán)格上升。在內(nèi)任取若則若則單峰函數(shù)：黃金分割法設(shè)在上為下單峰函數(shù)，即有唯一的極小點(diǎn)在左邊嚴(yán)格下降，在右邊嚴(yán)黃金分割法若第一次選取的試點(diǎn)為則下一步保留的區(qū)間為或兩者的機(jī)會(huì)是均等的．因此我們選取試點(diǎn)時(shí)希望設(shè)則另外，我們希望如果縮小的區(qū)間包含原來的試點(diǎn)，則該試點(diǎn)在下一步被利用．若保留的區(qū)黃金分割法若第一次選取的試點(diǎn)為則下一步保留的區(qū)間為或兩者的機(jī)我們希望原來的間為前一次的試點(diǎn)在這個(gè)區(qū)間內(nèi)．在縮小的區(qū)間內(nèi)成為新的我們根據(jù)這條件來計(jì)算計(jì)算的公式為：因此我們希望：即：我們希望原來的間為前一次的試點(diǎn)在這個(gè)區(qū)間內(nèi)．在縮小的區(qū)間內(nèi)成化簡得：若保留區(qū)間為我們得到的結(jié)果是一致的．該方法稱為黃金分割法，實(shí)際計(jì)算?。核渣S金分割法又稱為0.618法．黃金分割法每次縮小區(qū)間的比例是一致的，每次將區(qū)間長度縮小到原來的0.618倍．化簡得：若保留區(qū)間為我們得到的結(jié)果是一致的．該方法稱為黃金分

黃金分割法的算法步驟Step1給定以及令Step2Step3轉(zhuǎn)Step２.令轉(zhuǎn)Step３.若則停；否則轉(zhuǎn)Step４.Step4若則轉(zhuǎn)Step3.黃金分割法的算法步驟Step1給定以及令Step2Step黃金分割法的算法步驟Step5若則轉(zhuǎn)Step3.若則轉(zhuǎn)Step3.黃金分割法的算法步驟Step5若則轉(zhuǎn)Step3.若則轉(zhuǎn)Ste例1（黃金分割法）用黃金分割法求函數(shù)在區(qū)間上的極小點(diǎn)。要求最終區(qū)間長度不大于原始區(qū)間長度的0.08倍．解：函數(shù)在區(qū)間上為下單峰函數(shù)，例1（黃金分割法）用黃金分割法求函數(shù)在區(qū)間上的極小點(diǎn)。要求最第一次迭代：縮短后區(qū)間為第二次迭代：縮短后區(qū)間為第一次迭代：縮短后區(qū)間為第二次迭代：縮短后區(qū)間為迭代次數(shù)０0.5281.4721.7512.695否１-0.0560.5282.0591.751否２0.5280.8881.7511.901否３0.3050.5281.7881.751否４0.5280.6651.7511.777否５0.4430.5281.7531.751否６0.5280.5801.7511.757是迭代０0.5281.4721.7512.695否１-0.05Fibonacci法為了盡快得到結(jié)果，希望區(qū)間縮小的盡量小。

如果在區(qū)間只有一個(gè)試點(diǎn)，我們無法將區(qū)間縮小。如果知道兩個(gè)試點(diǎn)根據(jù)的大小關(guān)系，可以得到縮小的區(qū)間或者

它與0.618法的主要區(qū)別之一在于：搜索區(qū)間長度的縮短率不是采用0.618，而是采用Fibonacci數(shù)。

Fibonacci法為了盡快得到結(jié)果，希望區(qū)間縮小的盡量小。下面我們考慮任給一個(gè)另外一種思維方式為，的單峰區(qū)間如果給定試點(diǎn)的個(gè)數(shù)如何使最后確定最優(yōu)值的區(qū)間盡量的小。按什么方式取點(diǎn)，求次函數(shù)值之后，可最多將多長的原始區(qū)間長度縮小為設(shè)為試點(diǎn)個(gè)數(shù)為最終區(qū)間長度為時(shí)、原始區(qū)間的最大可能長度。的包含下面我們考慮任給一個(gè)另外一種思維方式為，的單峰區(qū)間如果給定試設(shè)最初兩個(gè)試點(diǎn)為和若極小點(diǎn)在內(nèi)，至多還有個(gè)試點(diǎn)，則若極小點(diǎn)在內(nèi)，包括在內(nèi)可以有個(gè)試點(diǎn)，則因此，如果我們采取合適的技巧，可以使得：另外，顯然，設(shè)最初兩個(gè)試點(diǎn)為和若極小點(diǎn)在內(nèi)，至多還有個(gè)試點(diǎn)，則若極小點(diǎn)在從而滿足差分方程：此為Fibonacci數(shù)列，一般寫為：從而滿足差分方程：此為Fibonacci數(shù)列，一般寫為：若原始區(qū)間為要求最終區(qū)間長度則由此可確定區(qū)間縮短之后與之前的比依次為：確定之后，最初兩個(gè)試點(diǎn)分別為：關(guān)于對稱由于

若原始區(qū)間為要求最終區(qū)間長度則由此可確定區(qū)間縮短之后與之前的上述過程完成了依次迭代，新區(qū)間仍記為若已經(jīng)進(jìn)行了次迭代，第次迭代時(shí)，還有個(gè)試點(diǎn)（包括已經(jīng)計(jì)算過的函數(shù)值的一個(gè)）注意：（２）若在一定的誤差范圍內(nèi)，則認(rèn)為在內(nèi)。（１）最后的兩個(gè)試點(diǎn)的選取方式：上述過程完成了依次迭代，新區(qū)間仍記為若已經(jīng)進(jìn)行了次迭代，第次例3.1（Fibonacci法）用Fibonacci法求函數(shù)在區(qū)間上的極小點(diǎn)。要求最終區(qū)間長度不大于原始區(qū)間長度的0.08倍．解：函數(shù)在區(qū)間上為下單峰函數(shù)，由可知應(yīng)?。禙ibonacci算法與0.618法幾乎完全相同。例3.1（Fibonacci法）用Fibonacci法求函數(shù)第一次迭代：縮短后區(qū)間為第一次迭代：縮短后區(qū)間為第二次迭代：縮短后區(qū)間為第二次迭代：縮短后區(qū)間為第三次迭代：縮短后區(qū)間為第四次迭代：縮短后區(qū)間為第三次迭代：縮短后區(qū)間為第四次迭代：縮短后區(qū)間為第五次迭代：取最優(yōu)解第五次迭代：取最優(yōu)解Fibonacci方法評(píng)價(jià)Fibonacci法的優(yōu)點(diǎn)（１）如果縮小的區(qū)間包含原來的試點(diǎn)，則該試點(diǎn)在下一步被利用；（２）效率最高，有限個(gè)試點(diǎn)的情況下，可將最優(yōu)點(diǎn)所在的區(qū)間縮小到最小．Fibonacci方法評(píng)價(jià)Fibonacci法的優(yōu)點(diǎn)（１）如Fibonacci法的缺點(diǎn)（１）搜索前先要計(jì)算搜索的步數(shù)；（２）每次搜索試點(diǎn)計(jì)算的公式不一致．1、黃金分割法（0.618法）與Fibonacci法的區(qū)別與聯(lián)系是什么？2、請讀者自己寫出算法和程序

Fibonacci法的缺點(diǎn)（１）搜索前先要計(jì)算搜索的步數(shù)；（二分法若的導(dǎo)數(shù)存在且容易計(jì)算，則線性搜索的速度可以得到提高．下面的二分法每次將區(qū)間縮小至原來的二分之一．設(shè)為下單峰函數(shù)，若在內(nèi)具有連續(xù)的一階導(dǎo)數(shù)，且二分法若的導(dǎo)數(shù)存在且容易計(jì)算，則線性搜索的速度可以得到提高．取若則為極小點(diǎn)；若則以代替若則以代替

二分法每次迭代都將區(qū)間縮短一半，故二分法的收斂速度也是線性的，收斂比為1/2。。

計(jì)算步驟：見P105

計(jì)算框圖:見P106取若則為極小點(diǎn)；若則以代替若則以代替二分法每次迭代多維無約束最優(yōu)化方法最速下降法(阻尼)牛頓法共軛梯度法多維無約束最優(yōu)化方法最速下降法問題提出問題：在點(diǎn)處，沿什么方向下降最快?分析：考查：顯然當(dāng)時(shí)，取極小值．因此：結(jié)論：負(fù)梯度方向使下降最快，亦即最速下降方向．最速下降法問題提出問題：在點(diǎn)處，沿什么方向下降最快?分析：考查：顯然當(dāng)最速下降法算法Step1:給出Step2:計(jì)算如果停．Step3:計(jì)算下降方向Step4:計(jì)算步長因子Step5:令轉(zhuǎn)步２.最速下降法算法Step1:給出Step2:計(jì)算如果停．Ste問題：設(shè)是正定二次函數(shù),由精確的線搜索確定的特別當(dāng)：問題：設(shè)是正定二次函數(shù),由精確的線搜索確定的特別當(dāng)：例1：用最速下降法求解：解：例1：用最速下降法求解：解：分析：(1)因此：最速下降法是整體收斂的，且是線性收斂的．(2)兩個(gè)相鄰的搜索方向是正交的．分析：(1)因此：最速下降法是整體收斂的，且是線性收斂的．(最優(yōu)化及最優(yōu)化方法講稿課件收斂性分析定理1:設(shè)在上存在且一致連續(xù)，則最速下降法產(chǎn)生的序列滿足或者對某個(gè)有或者證明：對于最速下降法，由以上定理立得．收斂性分析定理1:設(shè)在上存在且一致連續(xù)，則最速下降法產(chǎn)生的序收斂性分析定理2:設(shè)二次連續(xù)可微，且其中是個(gè)正常數(shù)，對任何給定的初始點(diǎn)最速下降算法或有限終止，或者或者證明：用以上的結(jié)論：收斂性分析定理2:設(shè)二次連續(xù)可微，且其中是個(gè)正常數(shù)，對任何給最速下降法優(yōu)點(diǎn)(1)程序設(shè)計(jì)簡單，計(jì)算量小，存儲(chǔ)量小，對初始點(diǎn)沒有特別要求．(2)有著很好的整體收斂性，即使對一般的目標(biāo)函數(shù)，它也整體收斂．最速下降法優(yōu)點(diǎn)(1)程序設(shè)計(jì)簡單，計(jì)算量小，存儲(chǔ)量小，對初始最速下降法缺點(diǎn)最速下降法是線性收斂的，并且有時(shí)是很慢的線性收斂．原因：①僅反映在處的局部性質(zhì)．②相繼兩次迭代中搜索方向是正交的．最速下降法缺點(diǎn)最速下降法是線性收斂的，并且有時(shí)是很慢的線性收小結(jié)最速下降法是基本算法之一，而非有效的實(shí)用算法．最速下降法的本質(zhì)是用線性函數(shù)來近似目標(biāo)函數(shù)，要想得到快速算法，需要考慮對目標(biāo)函數(shù)的高階逼近．小結(jié)最速下降法是基本算法之一，而非有效的實(shí)用算法．最速下降法基本思想利用目標(biāo)函數(shù)在點(diǎn)處的二階Taylor展開式去近似目標(biāo)函數(shù)，用二次函數(shù)的極小點(diǎn)去逼近目標(biāo)函數(shù)的極小點(diǎn)．牛頓法基本思想利用目標(biāo)函數(shù)在點(diǎn)處的二階Taylor展開式去近似目標(biāo)算法構(gòu)造問題：設(shè)二階連續(xù)可微，海色陣正定．如何從因?yàn)檎?，則有唯一極小點(diǎn)，用這個(gè)極小點(diǎn)作為算法構(gòu)造問題：設(shè)二階連續(xù)可微，海色陣正定．如何從因?yàn)檎?，則所以要求：即：因此：這就是牛頓法迭代公式．注：這里所以要求：即：因此：這就是牛頓法迭代公式．注：這里牛頓法算法Step1:給出Step2:計(jì)算如果停．Step3:否則計(jì)算Step4:令轉(zhuǎn)步２.并且求解方程得出牛頓法算法Step1:給出Step2:計(jì)算如果停．Step3例1：用牛頓法求解：解：例1：用牛頓法求解：解：牛頓法收斂定理定理1:設(shè)二次連續(xù)可微，是的局部極小點(diǎn)，正定．假定的海色陣滿足Lipschitz條件，即存在使得對于所有有：其中是海色陣的元素．則當(dāng)充分靠近時(shí)，對于一切牛頓迭代有意義，迭代序列收斂到并且具有二階收斂速度．牛頓法收斂定理定理1:設(shè)二次連續(xù)可微，是的局部極小點(diǎn)，正定．牛頓法優(yōu)點(diǎn)(1)(2)對正定二次函數(shù)，迭代一次就可以得到極小點(diǎn)．如果正定且初始點(diǎn)選取合適，算法二階收斂．牛頓法優(yōu)點(diǎn)(1)(2)對正定二次函數(shù)，迭代一次就可以得到極小牛頓法缺點(diǎn)(1)(2)對多數(shù)問題算法不是整體收斂的．每次都需要計(jì)算計(jì)算量大．(3)每次都需要解方程組有時(shí)奇異或病態(tài)的，無法確定或不是下降方向．(4)收斂到鞍點(diǎn)或極大點(diǎn)的可能性并不?。ｎD法缺點(diǎn)(1)(2)對多數(shù)問題算法不是整體收斂的．每次都需阻尼牛頓法算法Step1:給出Step2:計(jì)算如果停．Step3:否則計(jì)算Step4:沿并且求解方程得出進(jìn)行線搜索，得出Step5:令轉(zhuǎn)Step2.阻尼牛頓法算法Step1:給出Step2:計(jì)算如果停．Ste阻尼牛頓法收斂定理定理2:設(shè)二階連續(xù)可微，又設(shè)對任意的存在常數(shù)使得在上滿足：則在精確線搜索條件下，阻尼牛頓法產(chǎn)生的點(diǎn)列滿足：(1)當(dāng)是有限點(diǎn)列時(shí)，其最后一個(gè)點(diǎn)為的唯一極小點(diǎn)．(2)當(dāng)是無限點(diǎn)列時(shí)，收斂到的唯一極小點(diǎn)．阻尼牛頓法收斂定理定理2:設(shè)二階連續(xù)可微，又設(shè)對任意的存在常阻尼牛頓法收斂定理定理3:設(shè)二階連續(xù)可微，又設(shè)對任意的存在常數(shù)使得在上滿足：則在Wolfe不精確線搜索條件下，阻尼牛頓法產(chǎn)生的點(diǎn)列滿足：且收斂到的唯一極小點(diǎn)．阻尼牛頓法收斂定理定理3:設(shè)二階連續(xù)可微，又設(shè)對任意的存在常例2：用阻尼牛頓法求解：解：顯然不是正定的，但：于是，沿方向進(jìn)行線搜索，得其極小點(diǎn)從而迭代不能繼續(xù)下去．例2：用阻尼牛頓法求解：解：顯然不是正定的，但：于是，沿方向帶保護(hù)的牛頓法算法給出Step1:若為奇異的，轉(zhuǎn)Step8，否則，Step2:令Step3:若為奇異的，轉(zhuǎn)Step8，否則，則轉(zhuǎn)Step8，否則，Step4:若則轉(zhuǎn)Step9，否則，Step5:沿方向進(jìn)行線搜索，求出并令帶保護(hù)的牛頓法算法給出Step1:若為奇異的，轉(zhuǎn)Step8，Step6:若停；Step7:令轉(zhuǎn)Step1；Step8:令轉(zhuǎn)Step5；Step9:令轉(zhuǎn)Step5.Step6:若停；Step7:令轉(zhuǎn)Step1；Step8:令例3：用帶保護(hù)的牛頓法求解：解：顯然不是正定的，但：于是，因?yàn)?，故令，沿進(jìn)行線搜索得：例3：用帶保護(hù)的牛頓法求解：解：顯然不是正定的，但：于是，因第二次迭代：而：使故令沿進(jìn)行線搜索，得出于是:此時(shí):第二次迭代：而：使故令沿進(jìn)行線搜索，得出于是:此時(shí):問題1:如何建立有效的算法？