1、最優(yōu)化及最優(yōu)化方法 最優(yōu)化是一門運(yùn)用非常廣泛的學(xué)科，它研討在有限種或無限種可行方案中挑選最優(yōu)方案，構(gòu)造尋求最優(yōu)解的計(jì)算方法。到達(dá)最優(yōu)目的的方案，稱為最優(yōu)方案，搜索最優(yōu)方案的方法，稱為最優(yōu)化方法。這種方法的數(shù)學(xué)實(shí)際，稱為最優(yōu)化實(shí)際。 最優(yōu)化方法也稱做運(yùn)籌學(xué)方法是近幾十年構(gòu)成的，它主要運(yùn)用數(shù)學(xué)方法研討各種系統(tǒng)的優(yōu)化途徑及方案，為決策者提供科學(xué)決策的根據(jù)。最優(yōu)化方法的研討對(duì)象及運(yùn)用 最優(yōu)化方法的主要研討對(duì)象是各種有組織系統(tǒng)的管理問題及其消費(fèi)運(yùn)營(yíng)活動(dòng)。最優(yōu)化方法的目的在于針對(duì)所研討的系統(tǒng)，求得一個(gè)合理運(yùn)用人力、物 力和財(cái)力的最正確方案，發(fā)揚(yáng)和提高系統(tǒng)的效能及效益，最終到達(dá)系統(tǒng)的最優(yōu)目的。 實(shí)際闡明，隨

2、著科學(xué)技術(shù)的日益提高和消費(fèi)運(yùn)營(yíng)的日益開展，最優(yōu)化方法已成為現(xiàn)代管文科學(xué)的重要實(shí)際根底和不可短少的方法，被人們廣泛地運(yùn)用到空間技術(shù)、軍事科學(xué)、電子工程、通訊工程、自動(dòng)控制、系統(tǒng)識(shí)別、資源分配、計(jì)算數(shù)學(xué)、公共管理、經(jīng)濟(jì)管理等各個(gè)領(lǐng)域，發(fā)揚(yáng)著越來越重要的作用。最優(yōu)化方法的詳細(xì)運(yùn)用舉例 最優(yōu)化普通可以分為最優(yōu)設(shè)計(jì)、最優(yōu)方案、最優(yōu)管理和最優(yōu)控制等四個(gè)方面。 最優(yōu)設(shè)計(jì):世界各國(guó)工程技術(shù)界,尤其是飛機(jī)、造船、機(jī)械、建筑等部門都已廣泛運(yùn)用最優(yōu)化方法于設(shè)計(jì)中，從各種設(shè)計(jì)參數(shù)的優(yōu)選到最正確構(gòu)造外形的選取等，結(jié)合有限元方法已使許多設(shè)計(jì)優(yōu)化問題得到處理。一個(gè)新的開展動(dòng)向是最優(yōu)設(shè)計(jì)和計(jì)算機(jī)輔助設(shè)計(jì)相結(jié)合。電子線路的最優(yōu)

3、設(shè)計(jì)是另一個(gè)運(yùn)用最優(yōu)化方法的重要領(lǐng)域。配方配比的優(yōu)選方面在化工、橡膠、塑料等工業(yè)部門都得到勝利的運(yùn)用,并向計(jì)算機(jī)輔助搜索最正確配方、配比如向開展(見優(yōu)選法)。最優(yōu)化方法的詳細(xì)運(yùn)用舉例 最優(yōu)方案:現(xiàn)代國(guó)民經(jīng)濟(jì)或部門經(jīng)濟(jì)的方案，直至企業(yè)的開展規(guī)劃和年度消費(fèi)方案，尤其是農(nóng)業(yè)規(guī)劃、種植方案、能源規(guī)劃和其他資源、環(huán)境和生態(tài)規(guī)劃的制定,都已開場(chǎng)運(yùn)用最優(yōu)化方法。一個(gè)重要的開展趨勢(shì)是協(xié)助指點(diǎn)部門進(jìn)展各種優(yōu)化決策。最優(yōu)管理：普通在日常消費(fèi)方案的制定、調(diào)度和運(yùn)轉(zhuǎn)中都可運(yùn)用最優(yōu)化方法。隨著管理信息系統(tǒng)和決策支持系統(tǒng)的建立和運(yùn)用，使最優(yōu)管理得到迅速的開展。 最優(yōu)化方法的詳細(xì)運(yùn)用舉例 最優(yōu)控制：主要用于對(duì)各種控制系統(tǒng)的

4、優(yōu)化。例如，導(dǎo)彈系統(tǒng)的最優(yōu)控制，能保證用最少燃料 完成飛行義務(wù),用最短時(shí)間到達(dá)目的;再如飛機(jī)、船舶、電力系統(tǒng)等的最優(yōu)控制，化工、冶金等工廠的最正確工況的控制。計(jì)算機(jī)接口安裝不斷完善和優(yōu)化方法的進(jìn)一步開展，還為計(jì)算機(jī)在線消費(fèi)控制發(fā)明了有利條件。最優(yōu)控制的對(duì)象也將從對(duì)機(jī)械、電氣、化工等硬系統(tǒng)的控制轉(zhuǎn)向?qū)ι鷳B(tài)、環(huán)境以致社會(huì)經(jīng)濟(jì)系統(tǒng)的控制。 最優(yōu)化的開展簡(jiǎn)史 最優(yōu)化是一個(gè)古老的課題。長(zhǎng)期以來，人們對(duì)最優(yōu)化問題進(jìn)展著討論和研討。 公元前 500年古希臘在討論建筑美學(xué)中就已發(fā)現(xiàn)了長(zhǎng)方形長(zhǎng)與寬的最正確比例為1. 618,稱為黃金分割比。其倒數(shù)至今在優(yōu)選法中仍得到廣泛運(yùn)用。在微積分出現(xiàn)以前，已有許多學(xué)者開場(chǎng)研

5、討用數(shù)學(xué)方法處理最優(yōu)化問題。例如阿基米德證明：給定周長(zhǎng)，圓所包圍的面積為最大。這就是歐洲古代城堡幾乎都建成圓形的緣由。 最優(yōu)化的開展簡(jiǎn)史 但是最優(yōu)化方法真正構(gòu)成為科學(xué)方法那么在17世紀(jì)以后。 17世紀(jì)，I.牛頓和G.W.萊布尼茨在他們所創(chuàng)建的微積分中，提出求解具有多個(gè)自變量的實(shí)值函數(shù)的最大值和最小值的方法，后來又出現(xiàn)Lagrange乘數(shù)法。以后又進(jìn)一步討論具有未知函數(shù)的函數(shù)極值，從而構(gòu)成變分法。這一時(shí)期的最優(yōu)化方法可以稱為古典最優(yōu)化方法。最優(yōu)化的開展簡(jiǎn)史 第二次世界大戰(zhàn)前后，由于軍事上的需求和科學(xué)技術(shù)和消費(fèi)的迅速開展，許多實(shí)踐的最優(yōu)化問題曾經(jīng)無法用古典方法來處理，這就促進(jìn)了近代最優(yōu)化方法的產(chǎn)生

6、。 近代最優(yōu)化方法的構(gòu)成和開展過程中最重要的事件有： 1847年法國(guó)數(shù)學(xué)家Cauchy研討了函數(shù)值沿什么方向下降最快的問題，提出最速下降法。 1939年前蘇聯(lián)數(shù)學(xué)家.B.提出理處理下料問題和運(yùn)輸問題這兩種線性規(guī)劃問題的求解方法。最優(yōu)化的開展簡(jiǎn)史 以蘇聯(lián) .康托羅維奇和美國(guó)G.B.丹齊克為代表的線性規(guī)劃； 以美國(guó)庫恩和塔克爾為代表的非線性規(guī)劃；以美國(guó)R.貝爾曼為代表的動(dòng)態(tài)規(guī)劃； 以蘇聯(lián).龐特里亞金為代表的極大值原理等。這些方法后來都構(gòu)成體系，成為近代很活潑的學(xué)科，對(duì)促進(jìn)運(yùn)籌學(xué)、管文科學(xué)、控制論和系統(tǒng)工程等學(xué)科的開展起了重要作用。 最優(yōu)化方法的內(nèi)容 最優(yōu)化方法包括的內(nèi)容很廣泛，如線性規(guī)劃、非線性規(guī)

7、劃、整數(shù)規(guī)劃、幾何規(guī)劃、動(dòng)態(tài)規(guī)劃、隨機(jī)規(guī)劃、多目的規(guī)劃、組合優(yōu)化(在給定有限集的一切具備某些條件的子集中，按某種目的找出一個(gè)最優(yōu)子集的一類數(shù)學(xué)規(guī)劃)等等。 幾何規(guī)劃非線性規(guī)劃的一個(gè)分支。是最有效的最優(yōu)化的方法之一。幾何規(guī)劃最初是由數(shù)學(xué)家R.J.達(dá)芬和 E.L.彼得森及C.M.查納等人于1961年在研討工程費(fèi)用極小化問題根底上提出的，直到1967年一書出版后才正式定名。幾何規(guī)劃的數(shù)學(xué)根底是G.H.哈代的平均實(shí)際。由于幾何平均不等式的關(guān)鍵性作用，幾何規(guī)劃由此得名。幾何規(guī)劃的目的函數(shù)和約束條件均由廣義多項(xiàng)式構(gòu)成 ，這是一類特殊的非線性規(guī)劃，利用其對(duì)偶原理，可以把高度非線性問題的求解轉(zhuǎn)化為具有線性約束

8、的優(yōu)化問題求解，使計(jì)算大為簡(jiǎn)化。幾何規(guī)劃實(shí)際研討和算法軟件開發(fā)、開展都很快，并且在化工、機(jī)械、土木、電氣、核工程等部門的工程優(yōu)化設(shè)計(jì)和企業(yè)管理、資源分配、環(huán)境維護(hù)以及技術(shù)經(jīng)濟(jì)分析等方面都得到廣泛運(yùn)用。 整數(shù)規(guī)劃整數(shù)規(guī)劃是指一類要求問題中的全部或一部分變量為整數(shù)的數(shù)學(xué)規(guī)劃。是近三十年來開展起來的、規(guī)劃論的一個(gè)分支. 整數(shù)規(guī)劃問題是要求決策變量取整數(shù)值的線性規(guī)劃或非線性規(guī)劃問題。普通以為非線性的整數(shù)規(guī)劃可分成線性部分和整數(shù)部分，因此經(jīng)常把整數(shù)規(guī)劃作為線性規(guī)劃的特殊部分。在線性規(guī)劃問題中，有些最優(yōu)解能夠是分?jǐn)?shù)或小數(shù)，但對(duì)于某些詳細(xì)問題，常要求解答必需是整數(shù)。例如，所求解是機(jī)器的臺(tái)數(shù)，任務(wù)的人數(shù)或裝貨

9、的車數(shù)等。為了滿足整數(shù)的要求，初看起來似乎只需把已得的非整數(shù)解舍入化整就可以了。實(shí)踐上化整后的數(shù)不見得是可行解和最優(yōu)解，所以應(yīng)該有特殊的方法來求解整數(shù)規(guī)劃。 在整數(shù)規(guī)劃中，假設(shè)一切變量都限制為整數(shù)，那么稱為純整數(shù)規(guī)劃；假設(shè)僅一部分變量限制為整數(shù)，那么稱為混合整數(shù)規(guī)劃。整數(shù)規(guī)劃的一種特殊情形是0-1規(guī)劃，它的變數(shù)僅限于0或1。 整數(shù)規(guī)劃是從1958年由R.E.戈莫里提出割平面法之后構(gòu)成獨(dú)立分支的 ，30多年來開展出很多方法處理各種問題。解整數(shù)規(guī)劃最典型的做法是逐漸生成一個(gè)相關(guān)的問題，稱它是原問題的衍生問題。對(duì)每個(gè)衍生問題又伴隨一個(gè)比它更易于求解的松弛問題衍生問題稱為松弛問題的源問題。經(jīng)過松弛問題

10、的解來確定它的源問題的歸宿，即源問題應(yīng)被舍棄，還是再生成一個(gè)或多個(gè)它本身的衍生問題來替代它。隨即 ，再選擇一個(gè)尚未被舍棄的 或替代的原問題的衍生問題，反復(fù)以上步驟直至不再剩有未處理的衍生問題為止。目前比較勝利又流行的方法是分枝定界法和割平面法，它們都是在上述框架下構(gòu)成的。01規(guī)劃在整數(shù)規(guī)劃中占有重要位置，一方面由于許多實(shí)踐問題，例如指派問題、選地問題、送貨問題都可歸結(jié)為此類規(guī)劃，另一方面任何有界變量的整數(shù)規(guī)劃都與01規(guī)劃等價(jià)，用01規(guī)劃方法還可以把多種非線性規(guī)劃問題表示成整數(shù)規(guī)劃問題，所以不少人努力于這個(gè)方向的研討。求解01規(guī)劃的常用方法是分枝定界法，對(duì)各種特殊問題還有一些特殊方法，例如求解指

11、派問題用匈牙利方法就比較方便。 組合最優(yōu)化 在給定有限集的一切具備某些條件的子集中，按某種目的找出一個(gè)最優(yōu)子集的一類數(shù)學(xué)規(guī)劃。又稱組合規(guī)劃。從最廣泛的意義上說，組合規(guī)劃與整數(shù)規(guī)劃這兩者的領(lǐng)域是一致的，都是指在有限個(gè)可供選擇的方案的組成集合中，選擇使目的函數(shù)到達(dá)極值的最優(yōu)子集。 組合最優(yōu)化開展的初期，研討一些比較適用的根本上屬于網(wǎng)絡(luò)極值方面的問題 ，如廣播網(wǎng)的設(shè)計(jì) 、開關(guān)電路設(shè)計(jì)、航船運(yùn)輸?shù)缆返姆桨浮⑷蝿?wù)指派、貨物裝箱方案等。自從擬陣概念進(jìn)入圖論領(lǐng)域之后，對(duì)擬陣中的一些實(shí)際問題的研討成為組合規(guī)劃研討的新課題，并得到運(yùn)用。如今運(yùn)用的主要方面仍是網(wǎng)絡(luò)上的最優(yōu)化問題，如最短路問題、最大小支撐樹問題、最

12、優(yōu)邊無關(guān)集問題、最小截集問題、推銷員問題等。 整數(shù)規(guī)劃與組合最優(yōu)化的關(guān)系整數(shù)規(guī)劃與組合最優(yōu)化從廣泛的意義上說，兩者的領(lǐng)域是一致的，都是在有限個(gè)可供選擇的方案中，尋覓滿足一定規(guī)范的最好方案。有許多典型的問題反映整數(shù)規(guī)劃的廣泛背景。例如，背袋或裝載問題、固定費(fèi)用問題、和睦探險(xiǎn)隊(duì)問題組合學(xué)的對(duì)集問題、有效探險(xiǎn)隊(duì)問題組合學(xué)的覆蓋問題、送貨問題等。因此整數(shù)規(guī)劃的運(yùn)用范圍也是極其廣泛的。它不僅在工業(yè)和工程設(shè)計(jì)和科學(xué)研討方面有許多運(yùn)用，而且在計(jì)算機(jī)設(shè)計(jì)、系統(tǒng)可靠性、編碼和經(jīng)濟(jì)分析等方面也有新的運(yùn)用。 隨機(jī)規(guī)劃 隨機(jī)規(guī)劃是對(duì)含有隨機(jī)變量的優(yōu)化問題建模的有效的工具并已有一個(gè)世紀(jì)的歷史。 第一種隨機(jī)規(guī)劃是美國(guó)經(jīng)濟(jì)

13、學(xué)家丹澤1955年提出的，康托羅維奇在這方面的奉獻(xiàn)，不在于這個(gè)新方法本身，而在于把它運(yùn)用于制定最優(yōu)方案。是廣泛運(yùn)用的期望值模型，即在期望約束條件下，使得期望收益到達(dá)最大或期望損失到達(dá)最小的優(yōu)化方法。第二種是由查納斯A.Charnes和庫伯(W.W.Cooper于1959年提出的時(shí)機(jī)約束規(guī)劃，是在一定的概率意義下到達(dá)最優(yōu)的實(shí)際。第三種即是劉寶碇教授于1997年提出的相關(guān)時(shí)機(jī)規(guī)劃，是一種使事件的時(shí)機(jī)在隨機(jī)環(huán)境下到達(dá)最優(yōu)的實(shí)際。它與期望值模型和時(shí)機(jī)約束規(guī)劃一同構(gòu)成了隨機(jī)規(guī)劃的三個(gè)分支。隨機(jī)規(guī)劃是處置數(shù)據(jù)帶有隨機(jī)性的一類數(shù)學(xué)規(guī)劃，它與確定性數(shù)學(xué)規(guī)劃最大的不同在于其系數(shù)中引進(jìn)了隨機(jī)變量，這使得隨機(jī)規(guī)劃比

14、起確定性數(shù)學(xué)規(guī)劃更適宜于實(shí)踐問題。在管文科學(xué)、運(yùn)籌學(xué)、經(jīng)濟(jì)學(xué)、最優(yōu)控制等領(lǐng)域，隨機(jī)規(guī)劃有著廣泛的運(yùn)用。 隨機(jī)規(guī)劃的求解方法 隨機(jī)規(guī)劃的求解方法大致分兩種。 第一種是轉(zhuǎn)化法，即將隨機(jī)規(guī)劃轉(zhuǎn)化成各自確實(shí)定性等價(jià)類，然后利用已有確實(shí)定性規(guī)劃的求解方法解之； 另一種是逼近方法，利用隨機(jī)模擬技術(shù)，經(jīng)過一定的遺傳算法程序，得到隨機(jī)規(guī)劃問題的近似最優(yōu)解和目的函數(shù)的近似最優(yōu)值。 講授內(nèi)容教材：最優(yōu)化方法及運(yùn)用案例.緒論.線性規(guī)劃.非線性規(guī)劃.動(dòng)態(tài)規(guī)劃.多目的優(yōu)化及其運(yùn)用 預(yù)備知識(shí)和學(xué)習(xí)要求學(xué)習(xí)該課程的需求具備的根本知識(shí) 高等數(shù)學(xué) 線性代數(shù)學(xué)習(xí)該課程的要求 態(tài)度決議一切 正確了解根本概念和原理 掌握最優(yōu)化方法的

15、思想 可以運(yùn)用最優(yōu)化方法分析處理實(shí)踐問題最優(yōu)化問題的數(shù)學(xué)模型普通方式最優(yōu)化問題目的函數(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ù)目的函數(shù)和約束函數(shù)的函數(shù)類型分類：線性最優(yōu)化問題(整數(shù)規(guī)劃、規(guī)劃)、非線性最優(yōu)化問題、二次規(guī)劃、多目的規(guī)劃。 2、現(xiàn)代優(yōu)化問題動(dòng)態(tài)優(yōu)化問題 動(dòng)態(tài)規(guī)劃與最優(yōu)控制問題 組合優(yōu)化問題最優(yōu)解的相關(guān)定義定義.1 可行解滿足約束條(1.2)和(1.3)的x稱為可行解，也稱為可行點(diǎn)或允許點(diǎn)。定義.2 可行域全體可行解構(gòu)成的集合稱為

16、可行域，也稱為允許集，記為D,即：定義.3 整體(全局最優(yōu)解對(duì)于一切那么稱恒有為最優(yōu)化問題的整體(全局最優(yōu)解。假設(shè)恒有那么稱為最優(yōu)化問題的嚴(yán)厲整體全局最優(yōu)解。定義.4 部分最優(yōu)解假設(shè)：存在的某鄰域使得對(duì)于一切恒有那么稱為最優(yōu)化問題的局部最優(yōu)解。其中同樣有：嚴(yán)厲部分最優(yōu)解。而部分最優(yōu)解不一定是整體最優(yōu)解。顯然，整體最優(yōu)解一定是部分最優(yōu)解，留意：求解最優(yōu)化問題，實(shí)踐上是求可行域D上的整體最優(yōu)解。但是，在普通情況下，整體最優(yōu)解是很難求出的，往往只能求出部分最優(yōu)解。定義.5 范數(shù)：在維向量空間中，定義實(shí)函數(shù)使其滿足以下三個(gè)條件：對(duì)恣意有在當(dāng)且僅當(dāng)時(shí)對(duì)恣意及實(shí)數(shù)有對(duì)恣意有那么稱函數(shù)為上的向量范數(shù)。兩類比

17、較常見的范數(shù)P-范數(shù)：其中最常用的是2-范數(shù)，即：范數(shù)：最優(yōu)化方法概述 求解 的一種算法，通常是指一種產(chǎn)生點(diǎn)列的程序。常表現(xiàn)為 的一種映射F，它經(jīng)常滿足以下兩點(diǎn)要求： 1 ;2 式1實(shí)踐上常表現(xiàn)為 。因此通常構(gòu)造映射F的關(guān)鍵就在于設(shè)計(jì)一種能從 出發(fā)，確定方向 與步長(zhǎng) 的方法，要求滿足式2并使整個(gè)序列或子列具有收斂性。 迭代算法 選取一個(gè)初始可行點(diǎn) 由這個(gè)初始可行點(diǎn)出發(fā)，依次產(chǎn)生一個(gè)可行點(diǎn)列： 恰好是問題的一個(gè)最優(yōu)解，或者該點(diǎn)列收斂到問題的一個(gè)最優(yōu)解?？尚悬c(diǎn)列的產(chǎn)生在處求得一個(gè)方向可行下降方向在射線上求一點(diǎn)：使得其中稱為步長(zhǎng)。下降方向定義1.6下降方向：在點(diǎn)處，對(duì)于方向假設(shè)存在實(shí)數(shù)使得恣意的有：

18、成立，那么稱為函數(shù)在點(diǎn)處的一個(gè)下降方向。當(dāng)具有延續(xù)的一階偏導(dǎo)數(shù)，令由Taylor公式：當(dāng)時(shí)，有所以充分小時(shí)是在處的一個(gè)下降方向。通常稱滿足：的方向?yàn)樵谔幍南陆捣较??？尚蟹较蚨x1.7可行方向：知區(qū)域?qū)τ谙蛄考僭O(shè)存在實(shí)數(shù)使得恣意的有：那么稱為點(diǎn)處關(guān)于區(qū)域的可行方向。下降方向關(guān)于區(qū)域可行，那么稱為可行下降方向。最優(yōu)化問題的算法的普通迭代格式給定初始點(diǎn)令確定處的可行下降方向確定步長(zhǎng)使得：令假設(shè)滿足某種終止準(zhǔn)那么，那么停頓；否那么令轉(zhuǎn)收斂性 假設(shè)一個(gè)算法只需當(dāng)初始點(diǎn)充分接近最優(yōu)解時(shí)，產(chǎn)生的點(diǎn)列才收斂，那么稱該算法為具有部分收斂的算法。 假設(shè)對(duì)恣意的初始點(diǎn)，由算法產(chǎn)生的點(diǎn)列都收斂，那么稱該算法為具有全局

19、收斂的算法。 具有全局收斂性的算法才有實(shí)意圖義。但對(duì)算法的部分收斂性分析，在實(shí)際上是重要的，由于它是全局收斂性分析的根底。收斂速度定義1.8設(shè)序列收斂于而且假設(shè)那么稱序列為線性收斂的，稱為收斂比；假設(shè)那么稱序列為超線性收斂的。收斂速度定義1.9設(shè)序列收斂于假設(shè)對(duì)那么稱序列為有：階收斂的。特別當(dāng)：時(shí)稱為二階收斂的。終止準(zhǔn)那么對(duì)于一種算法，應(yīng)該有某種終止準(zhǔn)那么，當(dāng)某次迭代滿足終止準(zhǔn)那么時(shí)，就停頓迭代。常用的終止準(zhǔn)那么有：1或或其中是預(yù)先給定的。2最優(yōu)化模型的建立建立數(shù)學(xué)模型：在對(duì)實(shí)踐問題深化研討的根底上， 利用有關(guān)數(shù)學(xué)的知識(shí)和概念，對(duì)自然規(guī)律的真實(shí) 描畫數(shù)學(xué)描畫或模擬。實(shí)例分析1、消費(fèi)方案問題 資

20、源分配問題 書第4-5頁例 第195頁 資源分配問題就是將數(shù)量一定的一種或假設(shè)干種資源例如原資料、資金、設(shè)備、設(shè)備、勞力等，恰當(dāng)?shù)胤峙浣o假設(shè)干運(yùn)用者或地域，從而使目的函數(shù)最優(yōu)。 線性規(guī)劃模型2、食譜問題 設(shè)市場(chǎng)上可買到 種不同的食品，第 種食品的單位售價(jià)為 。每種食品含有 種根本營(yíng)養(yǎng)成分，第 種食品每一個(gè)單位含有第 種營(yíng)養(yǎng)成分為 。又設(shè)每人每天對(duì)第 種營(yíng)養(yǎng)成分的需求量不少于 。試確定在保證營(yíng)養(yǎng)要求條件下的最經(jīng)濟(jì)食譜。線性規(guī)劃模型3、選址問題類似的問題P89) 某城市要建立一個(gè)煤氣供應(yīng)中心，該中心向城市中 個(gè)用戶用戶位置固定提供保送煤氣效力。對(duì)于給定的坐標(biāo)系而言，知第 個(gè)用戶位置的坐標(biāo)為 。假設(shè)

21、保送管道不受道路影響即只思索直線間隔，問如何確定該中心的位置，才干使總的保送管道最短，同時(shí)中心到第 個(gè)用戶的間隔必需介于 和 之間 。非線性規(guī)劃模型4、最短路問題(圖論極值問題 或最優(yōu)管道鋪設(shè)問題 (類似問題166頁)動(dòng)態(tài)規(guī)劃模型線性規(guī)劃1、線性規(guī)劃模型的建立2、線性規(guī)劃模型的尋優(yōu)線性規(guī)劃模型的建立建立優(yōu)化模型的三大要素1確定決策變量2確定目的決策準(zhǔn)那么3確定約束條件實(shí)例分析 1消費(fèi)方案 資源分配問題 例2.1 某廠方案在下一個(gè)消費(fèi)周期內(nèi)消費(fèi)甲、乙兩種產(chǎn)品，需求耗費(fèi)R1、R2、和R3三種資源例如鋼材、煤炭或設(shè)備臺(tái)時(shí)等，知每件產(chǎn)品對(duì)這三種資源的耗費(fèi)、這三種資源可供運(yùn)用的量及每單位產(chǎn)品可獲得的利潤(rùn)

22、如表2.1所示。問應(yīng)如何安排消費(fèi)方案，使得既能充分利用現(xiàn)有資源，又使總利潤(rùn)最大？試建立問題的數(shù)學(xué)模型。(P10-11) 單件 產(chǎn)品 消耗資源 甲 乙可供使用資源量R1R2R35 22 31 5170100150單件利潤(rùn)10 18表2-12原資料的合理利用問題P11-1230-1背包問題(P12) 背包問題(P13)(4) 運(yùn)輸問題 (5)分派指派問題 線性的特點(diǎn)比例性可加性 共同的特征每一個(gè)線性規(guī)劃問題都用一組決策變量 表示某一方案，這組決策變量的值就代表一個(gè)詳細(xì)方案。普通這些變量取值是非負(fù)且延續(xù)的；(2) 要有各種資源 和運(yùn)用有關(guān)資源的技術(shù)數(shù)據(jù),發(fā)明新價(jià)值的數(shù)據(jù)；共同的特征繼續(xù)(3) 存在可

23、以量化的約束條件，這些約束 條件可以用一組線性等式或線性不等式 來表示；(4) 要有一個(gè)到達(dá)目的的要求，它可用決策 變量的線性函數(shù)(稱為目的函數(shù))來表示。 按問題的不同，要求目的函數(shù)實(shí)現(xiàn)最大化 或最小化。它們的對(duì)應(yīng)關(guān)系可用表格表示：線性規(guī)劃的普通模型方式線性規(guī)劃模型的規(guī)范方式線性規(guī)劃模型的幾種表示方式向量表示式矩陣表示式如何變換為規(guī)范形(1) 當(dāng)目的函數(shù)為求極最大值時(shí),即 ， 這時(shí)只需令 ，即轉(zhuǎn)化為 。這就同規(guī)范形的目的函數(shù)的方式一致了。(2) 約束方程為不等式。這里有兩種情況：一種是約束方程為“不等式，那么可在“不等式的左端參與非負(fù)松弛變量，把原“不等式變?yōu)榈仁?；另一種是約束方程為“不等式，

24、那么可在“不等式的左端減去一個(gè)非負(fù)剩余變量(也可稱松弛變量)，把不等式約束條件變?yōu)榈仁郊s束條件。如何變換為規(guī)范型(續(xù)3當(dāng)約束條件的右端常數(shù)項(xiàng) 時(shí)，只需將等式或不等式兩端同乘以 即可。4當(dāng)決策變量的取值約束為 時(shí)，令 ，那么有 。 5當(dāng)決策變量的取值無任何約束時(shí)，令 ，那么由 表示的 不受任何取值的約束。 線性規(guī)劃的分類 線性規(guī)劃普通線性規(guī)劃 特殊線性規(guī)劃 整數(shù)規(guī)劃 運(yùn)輸問題 純整數(shù)規(guī)劃 混合整數(shù)規(guī)劃 0-1規(guī)劃 指派問題的線性規(guī)劃 解的相關(guān)概念 根本概念 定義2.1 在線性規(guī)劃問題中，凡是滿足其全部約束條件包括變量取值約束的一組決策變量的取值稱作該線性規(guī)劃問題的可行解。 定義2.2 線性規(guī)劃問

25、題中，可行解的集合稱為該問題的可行域。 定義2.3 在線性規(guī)劃問題的可行域中，使目的函數(shù)值到達(dá)最優(yōu)最大或最小的可行解稱為該問題的最優(yōu)解。相應(yīng)的目的函數(shù)值稱為最優(yōu)值。 凸集定義1設(shè)集合假設(shè)對(duì)于恣意兩點(diǎn)及實(shí)數(shù)都有：那么稱集合為凸集注：常見的凸集：空集，整個(gè)歐氏空間超平面：半空間：例1：證明超球?yàn)橥辜C明：設(shè)為超球中的恣意兩點(diǎn)，那么有：即點(diǎn)屬于超球所以超球?yàn)橥辜辜男再|(zhì)有限個(gè)可以改成無限凸集的交集為凸集設(shè)是凸集，是一實(shí)數(shù)，那么下面的集合是凸集：設(shè)是凸集，那么的和集是凸集注：和集和并集有很大的區(qū)別，凸集的并集未必是凸集，而凸集的和集是凸集例：表示軸上的點(diǎn)表示軸上的點(diǎn)那么表示兩個(gè)軸的一切點(diǎn)，它不是凸集

26、；而凸集推論：設(shè)是凸集，那么也是凸集，其中是實(shí)數(shù)定義2:設(shè)實(shí)數(shù)那么 稱為 的凸組合 注：凸集中恣意有限個(gè)點(diǎn)的凸組合依然在該凸集中 極點(diǎn)頂點(diǎn)定義1設(shè)為凸集，假設(shè)中不存在兩個(gè)相異的點(diǎn)及某一實(shí)數(shù)使得那么稱為的極點(diǎn)例：那么上的點(diǎn)均為極點(diǎn)證：設(shè)假設(shè)存在及使得那么：不等式要取等號(hào)，必需且容易證明根據(jù)定義可知為極點(diǎn)與算法有關(guān)的概念無窮多解 圖解法中，此情況出如今目的函數(shù)等值直線向優(yōu)化方向平移時(shí)，最后與可行域邊境的一條邊重合，此時(shí)，除該直線段的兩個(gè)端點(diǎn)即可行域的兩個(gè)頂點(diǎn)外，直線段上一切點(diǎn)的目的函數(shù)值都到達(dá)最優(yōu)。無界解 圖解法中，此情況出如今可行域?yàn)闊o界區(qū)域，且目的函數(shù)等值直線向優(yōu)化方向平移時(shí)，一直無法脫離可行

27、域。發(fā)生這種情況往往是建模時(shí)脫漏了某些約束條件所至。無解 當(dāng)可行域?yàn)榭占瘯r(shí)，問題不存在可行解。發(fā)生此情況是由于模型中出現(xiàn)了相互矛盾的約束條件。 圖解法中解的概念與算法有關(guān)的概念可行解、最優(yōu)解基、基向量、基變量基解、基可行解可行基與單純形法有關(guān)的解概念可行解、最優(yōu)解滿足約束條件(1-2)，(1-3)式的解稱為線性規(guī)劃問題的可行解，其中使目的函數(shù)到達(dá)最小值的可行解稱為最優(yōu)解?；⒒蛄俊⒒兞炕?、基可行解 基解：滿足約束方程組1-2且非基變量為0的解。 基可行解：滿足非負(fù)條件1-3的基解. 基可行解的非零分量的數(shù)目也不大于m，并且都是非負(fù)的。 可行基 對(duì)應(yīng)于基可行解的基，稱為可行基。約束方程組(

28、1-2)具有基解的數(shù)目最多是 個(gè)。普通基可行解的數(shù)目要小于基解的數(shù)目。以上提到的幾種解的概念，它們之間的關(guān)系可用圖6闡明。另外還要闡明一點(diǎn)，基解中的非零分量的個(gè)數(shù)小于m個(gè)時(shí)，該基解是退化解。在以下討論時(shí)，假設(shè)不出現(xiàn)退化的情況。以上給出了線性規(guī)劃問題的解的概念和定義，它們將有助于用來分析線性規(guī)劃問題的求解過程。 可行解、基解、基可行解之間的關(guān)系圖6與算法有關(guān)的概念與內(nèi)點(diǎ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ù)

29、線性規(guī)劃問題0-1規(guī)劃問題平衡運(yùn)輸問題指派問題重要的方法 圖解法 對(duì)于只需兩個(gè)變量的線性規(guī)劃問題，可以采用在平面上作圖的方法求解，稱為圖解法。例1 用圖解法求解 因存在 ，所以必需在直角坐標(biāo)的第1象限內(nèi)作圖，求解。1在平面直角坐標(biāo)系上畫出可行域 (2)畫出目的函數(shù)等值線，并沿其法線方向平移等值線，以求得最優(yōu)解。目的值在4，2點(diǎn)，到達(dá)最大值14目的函數(shù)圖1能夠出現(xiàn)的幾種情況1無窮多最優(yōu)解(多重最優(yōu)解)目的函數(shù) max z=2x1+4x2 圖3 2無界解圖4 3無可行解 當(dāng)存在矛盾的約束條件時(shí)，為無可行域。假設(shè)在例1的數(shù)學(xué)模型中添加一個(gè)約束條件: 該問題的可行域?yàn)榭占?，即無可行解， 不存在可行域添

30、加的約束條件圖5小結(jié)1 線性規(guī)劃問題的模型特征2 經(jīng)過圖解法了解如何求解線性規(guī)劃 問題3 為求解高維線性規(guī)劃問題，必需建 立的概念線性規(guī)劃的單純形方法線性規(guī)劃問題的幾個(gè)定理單純形法的原理初始基可行解確實(shí)定線性規(guī)劃問題的幾個(gè)定理定理1 假設(shè)線性規(guī)劃問題存在可行解，那么問題的 可行域是凸集。定理2 線性規(guī)劃問題的基可行解對(duì)應(yīng)線性規(guī)劃 問題可行域凸集的頂點(diǎn)極點(diǎn)。定理3 假設(shè)線性規(guī)劃問題有最優(yōu)解，那么一定存在 一個(gè)基可行解是最優(yōu)解。結(jié)論：求解線性規(guī)劃問題歸結(jié)為找最優(yōu)基可行 解， 即在其可行域凸集的頂點(diǎn)極點(diǎn) 中找使目的函數(shù)最小的頂點(diǎn)極點(diǎn)。單純形法的原理單純形方法的根本思想 從一個(gè)基可行解出發(fā)，求一個(gè)使目

31、的函數(shù)值有所改善的基可行解；經(jīng)過不斷改良基可行解，力圖到達(dá)最優(yōu)基可行解。 它主要經(jīng)過基可行解的轉(zhuǎn)換完成?；尚薪獾霓D(zhuǎn)換 思索矩陣方式的規(guī)范形問題： 式中最優(yōu)性檢驗(yàn)和解的判別單純形方法的計(jì)算步驟步驟1 找一個(gè)初始基可行解常用大M法和兩階法找。步驟2 解 步驟3 求單純形乘子 ，解運(yùn)用表格方式的單純形方法運(yùn)用表格方式的單純形方法 用單純形法解以下問題： 初始基可行解確實(shí)定大M法 根本思想：在約束中添加人工變量 ，同時(shí)改動(dòng)目的函數(shù) ，加上罰項(xiàng) ，其中 是很大的正數(shù)，這樣，在極小化目的函數(shù)的過程中，由于大 的存在，將使人工變量離基。 思索線性規(guī)劃問題大M法 引進(jìn)人工變量 ，研討以下問題： 用單純形法求

32、解線性規(guī)劃問題(1-14)，獲得其解，它與1-13的解的關(guā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法用大M法求解以下問題：兩個(gè)階段法根本思想：在約束中添加人工變量 ，以構(gòu)造一個(gè)單位矩陣。對(duì)添加了人工變量的線性規(guī)劃問題分兩個(gè)階段計(jì)算。 第一階段是用單純形方法消去人工變量假設(shè)能夠的話，即把人工變量 都變成非基變量，求出原來問題的一個(gè)根本可行解。消

33、去人工變量 的一種方法是解以下第一階段問題：兩個(gè)階段法 求解1-16，設(shè)得到的最優(yōu)根本可行解是 ，此時(shí)必有以下三種情形之一： 這時(shí)1-13無可行解。 的分量都是非基變量，這時(shí)的基變量都 是原來的變量，又知 是1-16的基可行解，因此 是1-13的一個(gè)基可行解。 兩個(gè)階段法 的某些分量是基變量，這時(shí)可用主元消去法，把原來變量中的某些非基變量引進(jìn)基，交換出基變量中的人工變量，再開場(chǎng)兩階段法的第二階段。應(yīng)該指出，為交換出人工變量而采用的主元消去法，在主元的選擇上，并不要求遵守單純形法確定離進(jìn)基變量的規(guī)那么。 兩階段法的第二階段，就是從得到的基可行解出發(fā)，用單純形方法求1-13的最優(yōu)解。即在問題1-1

34、6中去掉人工變量，以第一階段最后的基變量為初始基變量開場(chǎng)迭代。操作上可直接在第一階段的最終單純形表根底上進(jìn)展，只需在表中除去人工變量列、恢復(fù)目的價(jià)值向量為原問題之前的情況即可。兩個(gè)階段法用兩階段法求解以下問題：內(nèi)點(diǎn)法 卡瑪卡Karmarkar算法 -投影尺度法 在大型問題的運(yùn)用中，顯示出能與單純形法競(jìng)爭(zhēng)的潛力 不能直接用于通常方式的線性規(guī)劃問題 原仿射尺度法 (改良的內(nèi)點(diǎn)法 ) 可以直接求解規(guī)范方式的線性規(guī)劃問題 實(shí)際根據(jù) 定理2.5 在仿射尺度變換 下， 的正卦限中的點(diǎn)仍變?yōu)檎韵拗械狞c(diǎn)，但其分量值發(fā)生變化。特別地， 的像點(diǎn)為 。定理2.6 設(shè)為行滿秩矩陣 ，那么向量 在 的零空間上 的正交

35、投影為 根本思想 先找出一個(gè)內(nèi)點(diǎn)可行解 ；從該點(diǎn)出發(fā)，在可行域的內(nèi)部尋求一個(gè)使目的函數(shù)值下降的可行方向，沿該方向挪動(dòng)到一個(gè)新的內(nèi)點(diǎn)可行解 ；如此逐漸挪動(dòng)，當(dāng)挪動(dòng)到與最優(yōu)解充分接近時(shí)，迭代停頓。 計(jì)算步驟及框圖計(jì)算步驟 P41-42 關(guān)鍵的問題是：對(duì)于任一迭代點(diǎn) ，如何求得一個(gè)適當(dāng)?shù)呐矂?dòng)方向 ，使 是一個(gè)改良的內(nèi)點(diǎn)可行解。 利用仿射尺度變換 的逆變換 定理2.5-2.6，可找到： , 計(jì)算框圖P42 例題及初始內(nèi)點(diǎn)可行解確實(shí)定 例2.10 用原仿射尺度算法求解如下問題P43-44)初始內(nèi)點(diǎn)可行解確實(shí)定P44 方法：類似于單純形方法的大M法。 線性規(guī)劃問題的計(jì)算機(jī)求解 如今曾經(jīng)出現(xiàn)了很多可以求解線

36、性規(guī)劃問題的計(jì)算機(jī)軟件產(chǎn)品，如Lindo,Lingo或Matlab等。下面以Matlab 6.x 為背景，引見如何在Matlab中求解線性規(guī)劃。 將模型轉(zhuǎn)換成如下“規(guī)范方式： 線性規(guī)劃問題的計(jì)算機(jī)求解 在上述規(guī)范方式中，目的函數(shù)求極小，約束條件嚴(yán)厲地分為三類：不等式約束且取“ 不等號(hào)、等式約束及變量取值范圍約束。其中 線性規(guī)劃問題的計(jì)算機(jī)求解 調(diào)用時(shí)需留意以下幾點(diǎn)：1Matlab提供了一種機(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ù)，除非其位于參數(shù)表的尾部，否那么調(diào)用時(shí)必需以空數(shù)

37、組“方式占位。2假設(shè)問題的模型為目的函數(shù)求最極大，須先將目的函數(shù)轉(zhuǎn)換為最極小。 3代碼中所運(yùn)用的標(biāo)點(diǎn)分隔符，如逗號(hào)、分號(hào)、括號(hào)等，必需是半角字符。 線性規(guī)劃問題的計(jì)算機(jī)求解寫出以下問題的Matlab調(diào)用代碼：分支定界法 與隱枚舉法 處理的問題各是什么？實(shí)際根據(jù) Discuss根本思想計(jì)算步驟及框圖 計(jì)算中的闡明計(jì)算機(jī)求解的異同？講P62例2.13 練P90 71分支定界法的計(jì)算框圖隱枚舉法的計(jì)算框圖表上作業(yè)法 與匈牙利法 處理的問題各是什么？實(shí)際根據(jù) Discuss根本思想計(jì)算步驟及框圖 計(jì)算中的闡明 表上作業(yè)法是單純形法在求解運(yùn)輸問題時(shí)的一種簡(jiǎn)化方法，其本質(zhì)是單純形法。結(jié)合算法步驟講P63例

38、2.14和P67例2.15. 表上作業(yè)法的計(jì)算框圖匈牙利法的計(jì)算框圖第三專題 非線性優(yōu)化問題1、非線性優(yōu)化模型的建立2、非線性優(yōu)化模型的尋優(yōu)非線性優(yōu)化模型的建立確定決策變量確定目的決策準(zhǔn)那么確定約束條件實(shí)例分析1投資決策問題P88)2曲線擬合問題 在實(shí)驗(yàn)數(shù)據(jù)處置或統(tǒng)計(jì)資料分析中，經(jīng)常遇到這樣的問題：如何利用有關(guān)變量的實(shí)驗(yàn)數(shù)據(jù)資料去確定這些變量間的函數(shù)關(guān)系。例如，知某物體的溫度 與時(shí)間 之間有如下方式的閱歷函數(shù)關(guān)系： 其中 是待定參數(shù)。經(jīng)過測(cè)試獲得n 組溫度與時(shí)間之間的實(shí)驗(yàn)數(shù)據(jù) ，試確定參數(shù) 使實(shí)際曲線盡能夠地與 n個(gè)測(cè)試點(diǎn)擬合。 非線性規(guī)劃問題的共同特征 都是求一個(gè)目的函數(shù)在一組約束條件下 的

39、極值問題。在目的函數(shù)或約束條件中，至少有一個(gè)是變量的非線性函數(shù)。非線性規(guī)劃問題普通方式：向量方式：非線性優(yōu)化問題的尋優(yōu)相關(guān)概念及實(shí)際一維最優(yōu)化方法多維無約束最優(yōu)化方法多維有約束最優(yōu)化方法非線性規(guī)劃的相關(guān)概念及實(shí)際一階導(dǎo)數(shù)、二階導(dǎo)數(shù)和n元函數(shù)的Taylor公式定義4設(shè)函數(shù)定義在凸集上，假設(shè)對(duì)恣意的及恣意的都有：那么稱函數(shù)為凸集上的凸函數(shù)定義5嚴(yán)厲凸函數(shù)注：將上述定義中的不等式反向，可以得到凹函數(shù)的定義凸函數(shù)例1：設(shè)試證明在上是嚴(yán)厲凸函數(shù)證明:設(shè)且都有：因此在上是嚴(yán)厲凸函數(shù)例2：試證線性函數(shù)是證明:設(shè)上的凸函數(shù)那么所以是凸函數(shù)類似可以證明是凹函數(shù)凸函數(shù)的幾何性質(zhì)對(duì)一元函數(shù)在幾何上表示銜接的線段表示

40、在點(diǎn)處的函數(shù)值所以一元凸函數(shù)表示銜接函數(shù)圖形上恣意兩點(diǎn)的線段總是位于曲線弧的上方凸函數(shù)的性質(zhì)設(shè)設(shè)函數(shù)，是凸集上的凸函數(shù)，實(shí)數(shù)那么也是上的凸函數(shù)是凸集上的凸實(shí)數(shù)那么也是上的凸函數(shù)設(shè)是凸集上的凸函數(shù)，是實(shí)數(shù)，那么程度集是凸集下面的圖形給出了凸函數(shù)的等值線的圖形，可以看出程度集是凸集凸函數(shù)的斷定定理1設(shè)上，令那么:(1)是定義在凸集是凸集上的凸函數(shù)的充要條件是對(duì)恣意的一元函數(shù)為上的凸函數(shù).(2)設(shè)假設(shè)在上為嚴(yán)厲凸函數(shù)，那么在上為嚴(yán)厲凸函數(shù)該定理的幾何意義是：凸函數(shù)上恣意兩點(diǎn)之間的部分是一段向下凸的弧一階條件定理2.1設(shè)在凸集上可微，那么：在上為凸函數(shù)的充要條件是對(duì)恣意的都有：定理2.2嚴(yán)厲凸函數(shù)(充

41、要條件)二階條件定理3設(shè)在開凸集內(nèi)二階可微，那么(1)是內(nèi)的凸函數(shù)的充要條件為，在內(nèi)任一點(diǎn)處，的海色矩陣半正定,其中：二階條件定理3設(shè)在開凸集內(nèi)(2)假設(shè)在內(nèi)正定,那么在內(nèi)二階可微，那么是嚴(yán)厲凸函數(shù)注:反之不成立例：顯然是嚴(yán)厲凸的，但在點(diǎn)處不是正定的凸規(guī)劃定義6設(shè)為凸集，為上的凸函數(shù)，那么稱規(guī)劃問題為凸規(guī)劃問題定理4(1)凸規(guī)劃問題的任一部分極小點(diǎn)是整體極小點(diǎn)，全體極小點(diǎn)組成凸集(2)假設(shè)是凸集上的嚴(yán)厲凸函數(shù)，且凸規(guī)劃問題整體極小點(diǎn)存在，那么整體極小點(diǎn)是獨(dú)一的非線性規(guī)劃的最優(yōu)性條件 最優(yōu)性條件：是指非線性規(guī)劃模型的最優(yōu)解所要滿足的必要和充分條件。無約束最優(yōu)性條件 約束最優(yōu)性條件 無約束最優(yōu)性條

42、件一單元函數(shù)的最優(yōu)性條件假設(shè)為的部分極小點(diǎn)，那么假設(shè)那么為的嚴(yán)厲部分極小點(diǎn)；假設(shè)為的部分極小點(diǎn)，那么：多元函數(shù)的一階必要條件P106-107)定理1:假設(shè)為的部分極小點(diǎn)，且在內(nèi)一階延續(xù)可導(dǎo)，那么注:(1)僅僅是必要條件，而非充分條件(2)滿足的點(diǎn)稱為駐點(diǎn)駐點(diǎn)分為：極小點(diǎn)，極大點(diǎn)，鞍點(diǎn)多元函數(shù)的二階充分條件定理2:假設(shè)在 內(nèi) 二階延續(xù)可導(dǎo)， 且 正定, 那么 為嚴(yán)厲部分 極小點(diǎn) 注:假設(shè) 負(fù)定, 那么 為嚴(yán)厲部分極大點(diǎn) 二階必要條件和充要條件定理3:假設(shè)為的部分極小點(diǎn)，且在內(nèi)二階延續(xù)可導(dǎo)，那么半正定定理4:設(shè)在上是凸函數(shù)且有一階延續(xù)偏導(dǎo)數(shù)，那么為的整體極小點(diǎn)的充要條件是例1：利用極值條件解以下問

43、題：解：令即：得到駐點(diǎn)：函數(shù)的海色陣：由此，在點(diǎn)處的海色陣依次為：由于矩陣不定，那么不是極小點(diǎn)負(fù)定，那么不是極小點(diǎn)，實(shí)踐上它是極大點(diǎn)正定，那么是部分極小點(diǎn)約束最優(yōu)性條件(p133-p)定義1:有效約束：假設(shè)(*)中的一個(gè)可行點(diǎn)使得某個(gè)不等式約束變成等式，即那么稱為關(guān)于的有效(積極約束非有效約束：假設(shè)對(duì)那么稱為關(guān)于的非有效(無效約束有效集：定義2:錐：的子集，假設(shè)它關(guān)于正的數(shù)乘運(yùn)算是封鎖的假設(shè)錐也是凸集，那么稱為凸錐凸錐關(guān)于加法和正的數(shù)乘運(yùn)算是封鎖的一階必要條件定理3.5:(Kuhn-Tucker一階必要條件)(1951)設(shè)在K-T條件一階必要條件定理1:(Kuhn-Tucker一階必要條件)互

44、補(bǔ)松弛條件例2：驗(yàn)證 能否滿足Kuhn-Tucker條件：實(shí)驗(yàn)證最優(yōu)點(diǎn)為KT點(diǎn)解：令所以即：所以：是KT點(diǎn)Lagrange函數(shù)及K-T條件在一定凸性下的最優(yōu)性的充分條件一維最優(yōu)化方法線性搜索方法知并且求出了處的可行下降方向從出發(fā)，沿方向求目的函數(shù)的最優(yōu)解，或者選取使得：?jiǎn)栴}描畫即設(shè)其最優(yōu)解為叫準(zhǔn)確步長(zhǎng)因子，所以線性搜索是求解一元函數(shù)的最優(yōu)化問題也叫一維最優(yōu)化問題。我們來求解：于是得到一個(gè)新點(diǎn)：普通地，線性搜索算法分成兩個(gè)階段：第一階段確定包含理想的步長(zhǎng)因子或問題最優(yōu)解的搜索區(qū)間；第二階段采用某種分割技術(shù)或插值方法減少這個(gè)區(qū)間。搜索區(qū)間：搜索區(qū)間求取方法 進(jìn)退法：一種簡(jiǎn)單確實(shí)定初始搜索區(qū)間方法.

45、根本思想：是從一點(diǎn)出發(fā)，按一定步長(zhǎng)，試圖確定出函數(shù)值呈現(xiàn)“高-低-高的三點(diǎn)，即 這里 。 詳細(xì)地說，就是給出初始點(diǎn) ，初始步長(zhǎng) ，假設(shè) ，那么下一步重新點(diǎn) 出發(fā)，加大步長(zhǎng)，再向前搜索，直到目的函數(shù)上升為止。 假設(shè) ，那么下一步仍以 為出發(fā)點(diǎn)，沿反方向同樣搜索，直到目的函數(shù)上升就停頓。這樣便得到一個(gè)搜索區(qū)間。這種方法叫進(jìn)退法。 計(jì)算步驟：見P96計(jì)算框圖:見P97黃金分割法0.618法根本思想： 它經(jīng)過對(duì)試探點(diǎn)的函數(shù)值進(jìn)展比較，使得包含極小點(diǎn)的區(qū)間不斷縮短，當(dāng)區(qū)間長(zhǎng)度小到精度范圍之內(nèi)時(shí)，可以粗略地以為區(qū)間上各點(diǎn)的函數(shù)值均接近于極小值。設(shè)在上為下單峰函數(shù)，即有獨(dú)一的極小點(diǎn)在左邊嚴(yán)厲下降，在右邊嚴(yán)厲

46、上升。在內(nèi)任取假設(shè)那么假設(shè)那么單峰函數(shù)：黃金分割法黃金分割法假設(shè)第一次選取的試點(diǎn)為那么下一步保管的區(qū)間為或兩者的時(shí)機(jī)是均等的因此我們選取試點(diǎn)時(shí)希望設(shè)那么另外，我們希望假設(shè)減少的區(qū)間包含原來的試點(diǎn)，那么該試點(diǎn)在下一步被利用假設(shè)保管的區(qū)我們希望原來的間為前一次的試點(diǎn)在這個(gè)區(qū)間內(nèi)在減少的區(qū)間內(nèi)成為新的我們根據(jù)這條件 來計(jì)算計(jì)算的公式為：因此我們希望：即：化簡(jiǎn)得：假設(shè)保管區(qū)間為我們得到的結(jié)果是一致的該方法稱為黃金分割法，實(shí)踐計(jì)算?。核渣S金分割法又稱為0.618法黃金分割法每次減少區(qū)間的比例是一致的，每次將區(qū)間長(zhǎng)度減少到原來的0.618倍 黃金分割法的算法步驟Step1給定以及令Step2Step3轉(zhuǎn)

47、Step.令轉(zhuǎn)Step.假設(shè)那么停；否那么轉(zhuǎn)Step.Step4假設(shè)那么轉(zhuǎn)Step3.黃金分割法的算法步驟Step5假設(shè)那么轉(zhuǎn)Step3.假設(shè)那么轉(zhuǎn)Step3.例1黃金分割法用黃金分割法求函數(shù)在區(qū)間上的極小點(diǎn)。要求最終區(qū)間長(zhǎng)度不大于原始區(qū)間長(zhǎng)度的0.08倍解：函數(shù)在區(qū)間上為下單峰函數(shù)，第一次迭代：縮短后區(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.

48、5280.5801.7511.757是Fibonacci法為了盡快得到結(jié)果，希望區(qū)間減少的盡量小。 假設(shè)在區(qū)間只需一個(gè)試點(diǎn)，我們無法將區(qū)間減少。假設(shè)知道兩個(gè)試點(diǎn)根據(jù)的大小關(guān)系，可以得到減少的區(qū)間或者 它與0.618法的主要區(qū)別之一在于：搜索區(qū)間長(zhǎng)度的縮短率不是采用0.618，而是采用Fibonacci數(shù)。 下面我們思索任給一個(gè)另外一種思想方式為，的單峰區(qū)間假設(shè)給定試點(diǎn)的個(gè)數(shù)如何使最后確定最優(yōu)值的區(qū)間盡量的小。按什么方式取點(diǎn)，求次函數(shù)值之后，可最多將多長(zhǎng)的原始區(qū)間長(zhǎng)度減少為設(shè)為試點(diǎn)個(gè)數(shù)為最終區(qū)間長(zhǎng)度為時(shí)、原始區(qū)間的最大能夠長(zhǎng)度。的包含設(shè)最初兩個(gè)試點(diǎn)為和假設(shè)極小點(diǎn)在內(nèi)，至多還有個(gè)試點(diǎn)，那么假設(shè)極小

49、點(diǎn)在內(nèi)，包括在內(nèi)可以有個(gè)試點(diǎn)，那么因此，假設(shè)我們采取適宜的技巧，可以使得：另外，顯然，從而滿足差分方程：此為Fibonacci數(shù)列，普通寫為：假設(shè)原始區(qū)間為要求最終區(qū)間長(zhǎng)度那么由此可確定區(qū)間縮短之后與之前的比依次為：確定之后，最初兩個(gè)試點(diǎn)分別為：關(guān)于對(duì)稱由于 上述過程完成了依次迭代，新區(qū)間仍記為假設(shè)曾經(jīng)進(jìn)展了次迭代，第次迭代時(shí)，還有個(gè)試點(diǎn)包括曾經(jīng)計(jì)算過的函數(shù)值的一個(gè)留意：假設(shè)在一定的誤差范圍內(nèi)，那么以為在內(nèi)。最后的兩個(gè)試點(diǎn)的選取方式：例3.1Fibonacci法用Fibonacci法求函數(shù)在區(qū)間上的極小點(diǎn)。要求最終區(qū)間長(zhǎng)度不大于原始區(qū)間長(zhǎng)度的0.08倍解：函數(shù)在區(qū)間上為下單峰函數(shù)，由可知應(yīng)取F

50、ibonacci算法與0.618法幾乎完全一樣 。第一次迭代：縮短后區(qū)間為第二次迭代：縮短后區(qū)間為第三次迭代：縮短后區(qū)間為第四次迭代：縮短后區(qū)間為第五次迭代：取最優(yōu)解Fibonacci方法評(píng)價(jià)Fibonacci法的優(yōu)點(diǎn)假設(shè)減少的區(qū)間包含原來的試點(diǎn)，那么該試點(diǎn)在下一步被利用；效率最高，有限個(gè)試點(diǎn)的情況下，可將最優(yōu)點(diǎn)所在的區(qū)間減少到最小Fibonacci法的缺陷搜索前先要計(jì)算搜索的步數(shù)；每次搜索試點(diǎn)計(jì)算的公式不一致1、黃金分割法0.618法與Fibonacci法的區(qū)別與聯(lián)絡(luò)是什么？2、請(qǐng)讀者本人寫出算法和程序 二分法假設(shè)的導(dǎo)數(shù)存在且容易計(jì)算，那么線性搜索的速度可以得到提高下面的二分法每次將區(qū)間減少

51、至原來的二分之一設(shè)為下單峰函數(shù)，假設(shè)在內(nèi)具有延續(xù)的一階導(dǎo)數(shù)，且取假設(shè)那么為極小點(diǎn)；假設(shè)那么以替代假設(shè)那么以替代 二分法每次迭代都將區(qū)間縮短一半，故二分法的收斂速度也是線性的，收斂比為1/2。 計(jì)算步驟：見P105 計(jì)算框圖:見P106多維無約束最優(yōu)化方法最速下降法(阻尼)牛頓法共軛梯度法問題提出問題：在點(diǎn)處，沿什么方向下降最快?分析：調(diào)查：顯然當(dāng)時(shí)，取極小值因此：結(jié)論：負(fù)梯度方向使下降最快，亦即最速下降方向最速下降法最速下降法算法Step1:給出Step2:計(jì)算假設(shè)停Step3:計(jì)算下降方向Step4:計(jì)算步長(zhǎng)因子Step5:令轉(zhuǎn)步.問題：設(shè)是正定二次函數(shù),由準(zhǔn)確的線搜索確定的特別當(dāng)：例1：用

52、最速下降法求解：解：分析：(1)因此：最速下降法是整體收斂的，且是線性收斂的(2)兩個(gè)相鄰的搜索方向是正交的收斂性分析定理1:設(shè)在上存在且一致延續(xù)，那么最速下降法產(chǎn)生的序列滿足或者對(duì)某個(gè)有或者證明：對(duì)于最速下降法，由以上定理立得收斂性分析定理2:設(shè)二次延續(xù)可微，且其中是個(gè)正常數(shù)，對(duì)任何給定的初始點(diǎn)最速下降算法或有限終止，或者或者證明：用以上的結(jié)論：最速下降法優(yōu)點(diǎn)(1)程序設(shè)計(jì)簡(jiǎn)單，計(jì)算量小，存儲(chǔ)量小，對(duì)初始點(diǎn)沒有特別要求(2)有著很好的整體收斂性，即使對(duì)普通的目的函數(shù)，它也整體收斂最速下降法缺陷最速下降法是線性收斂的，并且有時(shí)是很慢的線性收斂緣由：僅反映在處的部分性質(zhì)相繼兩次迭代中搜索方向是正

53、交的小結(jié)最速下降法是根本算法之一，而非有效的適用算法最速下降法的本質(zhì)是用線性函數(shù)來近似目的函數(shù)，要想得到快速算法，需求考慮對(duì)目的函數(shù)的高階逼近根本思想利用目的函數(shù)在點(diǎn)處的二階Taylor展開式去近似目的函數(shù)，用二次函數(shù)的極小點(diǎn)去逼近目的函數(shù)的極小點(diǎn)牛頓法算法構(gòu)造問題：設(shè)二階延續(xù)可微，海色陣正定如何從由于正定，那么有獨(dú)一極小點(diǎn)，用這個(gè)極小點(diǎn)作為所以要求：即：因此：這就是牛頓法迭代公式注：這里牛頓法算法Step1:給出Step2:計(jì)算假設(shè)停Step3:否那么計(jì)算Step4:令轉(zhuǎn)步.并且求解方程得出例1：用牛頓法求解：解：牛頓法收斂定理定理1:設(shè)二次延續(xù)可微，是的局部極小點(diǎn)，正定假定的海色陣滿足Li

54、pschitz條件，即存在使得對(duì)于一切有：其中是海色陣的元素那么當(dāng)充分接近時(shí)，對(duì)于一切牛頓迭代有意義，迭代序列收斂到并且具有二階收斂速度牛頓法優(yōu)點(diǎn)(1)(2)對(duì)正定二次函數(shù)，迭代一次就可以得到極小點(diǎn)假設(shè)正定且初始點(diǎn)選取適宜，算法二階收斂牛頓法缺陷(1)(2)對(duì)多數(shù)問題算法不是整體收斂的每次都需求計(jì)算計(jì)算量大(3)每次都需求解方程組有時(shí)奇特或病態(tài)的，無法確定或不是下降方向(4)收斂到鞍點(diǎn)或極大點(diǎn)的能夠性并不小阻尼牛頓法算法Step1:給出Step2:計(jì)算假設(shè)停Step3:否那么計(jì)算Step4:沿并且求解方程得出進(jìn)展線搜索，得出Step5:令轉(zhuǎn)Step2.阻尼牛頓法收斂定理定理2:設(shè)二階延續(xù)可微，

55、又設(shè)對(duì)恣意的存在常數(shù)使得在上滿足：那么在準(zhǔn)確線搜索條件下，阻尼牛頓法產(chǎn)生的點(diǎn)列滿足：(1)當(dāng)是有限點(diǎn)列時(shí)，其最后一個(gè)點(diǎn)為的獨(dú)一極小點(diǎn)(2)當(dāng)是無限點(diǎn)列時(shí)，收斂到的獨(dú)一極小點(diǎn)阻尼牛頓法收斂定理定理3:設(shè)二階延續(xù)可微，又設(shè)對(duì)恣意的存在常數(shù)使得在上滿足：那么在Wolfe不準(zhǔn)確線搜索條件下，阻尼牛頓法產(chǎn)生的點(diǎn)列滿足：且收斂到的獨(dú)一極小點(diǎn)例2：用阻尼牛頓法求解：解：顯然不是正定的，但：于是，沿方向進(jìn)展線搜索，得其極小點(diǎn)從而迭代不能繼續(xù)下去帶維護(hù)的牛頓法算法給出Step1:假設(shè)為奇特的，轉(zhuǎn)Step8，否那么，Step2:令Step3:假設(shè)為奇特的，轉(zhuǎn)Step8，否那么，那么轉(zhuǎn)Step8，否那么，Step4

56、:假設(shè)那么轉(zhuǎn)Step9，否那么，Step5:沿方向進(jìn)展線搜索，求出并令Step6:假設(shè)停；Step7:令轉(zhuǎn)Step1；Step8:令轉(zhuǎn)Step5；Step9:令轉(zhuǎn)Step5.例3：用帶維護(hù)的牛頓法求解：解：顯然不是正定的，但：于是，由于，故令，沿進(jìn)展線搜索得：第二次迭代：而：使故令沿進(jìn)展線搜索，得出于是:此時(shí):問題1:如何建立有效的算法？從二次模型到普通模型問題2:什么樣的算法有效呢？二次終止性(經(jīng)過有限次迭代必到達(dá)極小點(diǎn)的性質(zhì)共軛梯度法算法特點(diǎn)建立在二次模型上，具有二次終止性有效的算法，抑制了最速下降法的慢收斂性，又防止了牛頓法的計(jì)算量大和部分收性的缺陷算法簡(jiǎn)單，易于編程，需存儲(chǔ)空間小等優(yōu)點(diǎn)

57、，是求解大規(guī)模問題的主要方法共軛方向及其性質(zhì)定義1:設(shè)是中任一組非零向量，假設(shè)：那么稱是關(guān)于共軛的注：假設(shè)那么是正交的，因此共軛是正交的推行定理1:設(shè)為階正定陣，非零向量組關(guān)于共軛，那么必線性無關(guān)推論1:設(shè)為階正定陣，非零向量組關(guān)于共軛，那么向量構(gòu)成的一組基推論2:設(shè)為階正定陣，非零向量組關(guān)于共軛，假設(shè)向量與關(guān)于共軛，那么求 的極小點(diǎn)的方法共軛方向法算法Step1:給出計(jì)算和初始下降方向Step2:假設(shè)停頓迭代Step3:計(jì)算使得Step4:采用某種共軛方向法計(jì)算使得：Step5:令轉(zhuǎn)Step2.共軛方向法根本定理定義2:設(shè)維向量組線性無關(guān)，向量集合為與生成的維超平面引理1:設(shè)是延續(xù)可微的嚴(yán)厲

58、凸函數(shù)，維向量組線性無關(guān)，那么：是在上獨(dú)一極小點(diǎn)的充要條件是：定理2:設(shè)為階正定陣，向量組關(guān)于共軛，對(duì)正定二次函數(shù)由恣意開場(chǎng)，依次進(jìn)展次準(zhǔn)確線搜索：那么：是在上的極小點(diǎn)推論:當(dāng)時(shí)，為正定二次函數(shù)在上的極小點(diǎn)共軛梯度法記：左乘并使得：Hestenes-Stiefel公式取：是一種特殊的共軛方向法共軛梯度法根本性質(zhì)定理3:對(duì)于正定二次函數(shù)，采用準(zhǔn)確線搜索的共軛梯度法在步后終止，且對(duì)成立以下關(guān)系式：共軛性正交性下降條件系數(shù)的其他方式FR公式19642PRP公式1969FR共軛梯度法算法Step1:給出Step2:假設(shè)停Step5:轉(zhuǎn)Step2.計(jì)算Step4:Step3:由準(zhǔn)確線搜索求計(jì)算例4：用F

59、R共軛梯度法求解：解：化成方式(1)(2)例5：用FR共軛梯度法求解：解：化成方式(1)(2)留意：FR方法中初始搜索方向必需取最速下降方向，才滿足二次終止性。FR共軛梯度法收斂定理定理4:假定在有界程度集上延續(xù)可微，且有下界，那么采用準(zhǔn)確線搜索下的FR共軛梯度法產(chǎn)生的點(diǎn)列至少有一個(gè)聚點(diǎn)是駐點(diǎn)，即：(1)當(dāng)是有窮點(diǎn)列時(shí)，其最后一個(gè)點(diǎn)是的駐點(diǎn)(2)當(dāng)是無窮點(diǎn)列時(shí)，它必有聚點(diǎn)，且任一聚點(diǎn)都是的駐點(diǎn)再開場(chǎng)FR共軛梯度法算法Step1:給出Step2:計(jì)算假設(shè)停，Step4:否那么Step3:由準(zhǔn)確線搜索求并令：計(jì)算假設(shè)令轉(zhuǎn)Step2;假設(shè)停.Step5:假設(shè)令轉(zhuǎn)step2.Step6:計(jì)算Step7

60、:假設(shè)令轉(zhuǎn)step2,否那么轉(zhuǎn)step3.作業(yè)用FR共軛梯度法求解：多維約束最優(yōu)化方法懲罰函數(shù)法 SUMT:序列無約束極小化方法 (Sequential Unconstrained Minimization Technique) 乘子法外點(diǎn)法二次罰函數(shù)方法 內(nèi)點(diǎn)法內(nèi)點(diǎn)妨礙罰函數(shù)法 罰函數(shù)法根本思想設(shè)法將約束問題求解轉(zhuǎn)化為無約束問題求解詳細(xì)說：根據(jù)約束的特點(diǎn)，構(gòu)造某種懲罰函數(shù)，然后把它加到目的函數(shù)中去，將約束問題的求解化為一系列無約束問題的求解懲罰戰(zhàn)略：企圖違反約束的迭代點(diǎn)給予很大的目的函數(shù)值迫使一系列無約束問題的極小點(diǎn)或者無限地接近可行域，或者不斷堅(jiān)持在可行域內(nèi)挪動(dòng)，直到收斂到極小點(diǎn)外罰函數(shù)法