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

最優(yōu)化及最優(yōu)化方法

最優(yōu)化是一門應(yīng)用十分廣泛的學(xué)科，它研究在有限種或無限種可行方案中挑選最優(yōu)方案，構(gòu)造尋求最優(yōu)解的計算方法。達到最優(yōu)目標(biāo)的方案，稱為最優(yōu)方案，搜索最優(yōu)方案的方法，稱為最優(yōu)化方法。這種方法的數(shù)學(xué)理論，稱為最優(yōu)化理論。

最優(yōu)化方法（也稱做運籌學(xué)方法）是近幾十年形成的，它主要運用數(shù)學(xué)方法研究各種系統(tǒng)的優(yōu)化途徑及方案，為決策者提供科學(xué)決策的依據(jù)。最優(yōu)化方法的研究對象及應(yīng)用

最優(yōu)化方法的主要研究對象是各種有組織系統(tǒng)的管理問題及其生產(chǎn)經(jīng)營活動。最優(yōu)化方法的目的在于針對所研究的系統(tǒng)，求得一個合理運用人力、物

力和財力的最佳方案，發(fā)揮和提高系統(tǒng)的效能及效益，最終達到系統(tǒng)的最優(yōu)目標(biāo)。實踐表明，隨著科學(xué)技術(shù)的日益進步和生產(chǎn)經(jīng)營的日益發(fā)展，最優(yōu)化方法已成為現(xiàn)代管理科學(xué)的重要理論基礎(chǔ)和不可缺少的方法，被人們廣泛地應(yīng)用到空間技術(shù)、軍事科學(xué)、電子工程、通訊工程、自動控制、系統(tǒng)識別、資源分配、計算數(shù)學(xué)、公共管理、經(jīng)濟管理等各個領(lǐng)域，發(fā)揮著越來越重要的作用。

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

最優(yōu)化一般可以分為最優(yōu)設(shè)計、最優(yōu)計劃、最優(yōu)管理和最優(yōu)控制等四個方面。①最優(yōu)設(shè)計:世界各國工程技術(shù)界,尤其是飛機、造船、機械、建筑等部門都已廣泛應(yīng)用最優(yōu)化方法于設(shè)計中，從各種設(shè)計參數(shù)的優(yōu)選到最佳結(jié)構(gòu)形狀的選取等，結(jié)合有限元方法已使許多設(shè)計優(yōu)化問題得到解決。一個新的發(fā)展動向是最優(yōu)設(shè)計和計算機輔助設(shè)計相結(jié)合。電子線路的最優(yōu)設(shè)計是另一個應(yīng)用最優(yōu)化方法的重要領(lǐng)域。配方配比的優(yōu)選方面在化工、橡膠、塑料等工業(yè)部門都得到成功的應(yīng)用,并向計算機輔助搜索最佳配方、配比方向發(fā)展(見優(yōu)選法)。

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

②最優(yōu)計劃:現(xiàn)代國民經(jīng)濟或部門經(jīng)濟的計劃，直至企業(yè)的發(fā)展規(guī)劃和年度生產(chǎn)計劃，尤其是農(nóng)業(yè)規(guī)劃、種植計劃、能源規(guī)劃和其他資源、環(huán)境和生態(tài)規(guī)劃的制訂,都已開始應(yīng)用最優(yōu)化方法。一個重要的發(fā)展趨勢是幫助領(lǐng)導(dǎo)部門進行各種優(yōu)化決策。③最優(yōu)管理：一般在日常生產(chǎn)計劃的制訂、調(diào)度和運行中都可應(yīng)用最優(yōu)化方法。隨著管理信息系統(tǒng)和決策支持系統(tǒng)的建立和使用，使最優(yōu)管理得到迅速的發(fā)展。

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

④最優(yōu)控制：主要用于對各種控制系統(tǒng)的優(yōu)化。例如，導(dǎo)彈系統(tǒng)的最優(yōu)控制，能保證用最少燃料完成飛行任務(wù),用最短時間達到目標(biāo);再如飛機、船舶、電力系統(tǒng)等的最優(yōu)控制，化工、冶金等工廠的最佳工況的控制。計算機接口裝置不斷完善和優(yōu)化方法的進一步發(fā)展，還為計算機在線生產(chǎn)控制創(chuàng)造了有利條件。最優(yōu)控制的對象也將從對機械、電氣、化工等硬系統(tǒng)的控制轉(zhuǎn)向?qū)ι鷳B(tài)、環(huán)境以至社會經(jīng)濟系統(tǒng)的控制。

最優(yōu)化的發(fā)展簡史

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

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

最優(yōu)化的發(fā)展簡史

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

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

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

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

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

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

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

最優(yōu)化方法的內(nèi)容

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

幾何規(guī)劃非線性規(guī)劃劃的一個分支支。是最有有效的最優(yōu)優(yōu)化的方法法之一。幾幾何規(guī)劃最最初是由數(shù)數(shù)學(xué)家R.J.達芬和E.L.彼得森及C.M.查納等人于于1961年在研究工工程費用極極小化問題題基礎(chǔ)上提提出的，直直到1967年《幾何規(guī)劃》一書出版后后才正式定定名。幾何何規(guī)劃的數(shù)數(shù)學(xué)基礎(chǔ)是是G.H.哈代的平均均理論。由由于幾何平平均不等式式的關(guān)鍵性性作用，幾幾何規(guī)劃由由此得名。。幾何規(guī)劃劃的目標(biāo)函函數(shù)和約束束條件均由由廣義多項項式構(gòu)成，，這是一一類特殊的的非線性規(guī)規(guī)劃，利用用其對偶原原理，可以以把高度非非線性問題題的求解轉(zhuǎn)轉(zhuǎn)化為具有有線性約束束的優(yōu)化問問題求解，，使計算大大為簡化。。幾何規(guī)劃劃理論研究究和算法軟軟件開發(fā)、、發(fā)展都很很快，并且且在化工、、機械、土土木、電氣氣、核工程程等部門的的工程優(yōu)化設(shè)計和企業(yè)管理理、資源分分配、環(huán)境境保護以及及技術(shù)經(jīng)濟濟分析等方方面都得到到廣泛應(yīng)用用。整數(shù)規(guī)劃整數(shù)規(guī)劃是是指一類要要求問題中中的全部或或一部分變量為整數(shù)的數(shù)數(shù)學(xué)規(guī)劃。。是近三十十年來發(fā)展展起來的、、規(guī)劃論的的一個分支支.整數(shù)規(guī)劃問問題是要求求決策變量取整數(shù)值的的線性規(guī)劃或非線性規(guī)劃劃問題。一般認為非非線性的整整數(shù)規(guī)劃可可分成線性性部分和整整數(shù)部分，，因此常常常把整數(shù)規(guī)規(guī)劃作為線性規(guī)劃的特殊部分分。在線性性規(guī)劃問題題中，有些些最優(yōu)解可可能是分數(shù)數(shù)或小數(shù)，，但對于某某些具體問問題，常要要求解答必必須是整數(shù)數(shù)。例如，，所求解是是機器的臺臺數(shù)，工作作的人數(shù)或或裝貨的車車數(shù)等。為為了滿足整整數(shù)的要求求，初看起起來似乎只只要把已得得的非整數(shù)數(shù)解舍入化化整就可以以了。實際際上化整后后的數(shù)不見見得是可行行解和最優(yōu)優(yōu)解，所以以應(yīng)該有特特殊的方法法來求解整整數(shù)規(guī)劃。。在整數(shù)規(guī)劃劃中，如果果所有變量量都限制為為整數(shù)，則則稱為純整整數(shù)規(guī)劃；；如果僅一一部分變量量限制為整整數(shù)，則稱稱為混合整整數(shù)規(guī)劃。。整數(shù)規(guī)劃劃的一種特特殊情形是是0-1規(guī)劃，它的的變數(shù)僅限限于0或1。整數(shù)規(guī)劃是是從1958年由R.E.戈莫里提出出割平面法之后形成獨獨立分支的的，30多年來發(fā)展展出很多方方法解決各各種問題。。解整數(shù)規(guī)規(guī)劃最典型型的做法是是逐步生成成一個相關(guān)關(guān)的問題，，稱它是原原問題的衍衍生問題。。對每個衍衍生問題又又伴隨一個個比它更易易于求解的的松弛問題題（衍生問問題稱為松松弛問題的的源問題））。通過松松弛問題的的解來確定定它的源問問題的歸宿宿，即源問問題應(yīng)被舍舍棄，還是是再生成一一個或多個個它本身的的衍生問題題來替代它它。隨即，，再選擇擇一個尚未未被舍棄的的或替代的原原問題的衍衍生問題，，重復(fù)以上上步驟直至至不再剩有有未解決的的衍生問題題為止。目目前比較成成功又流行行的方法是是分枝定界法法和割平面法，它們都是是在上述框框架下形成成的。0—1規(guī)劃在整數(shù)規(guī)劃劃中占有重重要地位，，一方面因因為許多實實際問題，，例如指派派問題、選選地問題、、送貨問題題都可歸結(jié)結(jié)為此類規(guī)規(guī)劃，另一一方面任何何有界變量量的整數(shù)規(guī)規(guī)劃都與0—1規(guī)劃等價，，用0—1規(guī)劃方法還還可以把多多種非線性性規(guī)劃問題題表示成整整數(shù)規(guī)劃問問題，所以以不少人致致力于這個個方向的研研究。求解解0—1規(guī)劃的常用用方法是分分枝定界法法，對各種種特殊問題題還有一些些特殊方法法，例如求求解指派問問題用匈牙利方法法就比較方便便。組合最優(yōu)化化在給定有限限集的所有有具備某些些條件的子子集中，按按某種目標(biāo)標(biāo)找出一個個最優(yōu)子集集的一類數(shù)數(shù)學(xué)規(guī)劃。。又稱組合合規(guī)劃。從從最廣泛的的意義上說說，組合規(guī)規(guī)劃與整數(shù)規(guī)劃這兩者的領(lǐng)領(lǐng)域是一致致的，都是是指在有限限個可供選選擇的方案案的組成集集合中，選選擇使目標(biāo)標(biāo)函數(shù)達到到極值的最最優(yōu)子集。。組合最優(yōu)化化發(fā)展的初初期，研究究一些比較較實用的基基本上屬于于網(wǎng)絡(luò)極值值方面的問問題，如如廣播網(wǎng)的的設(shè)計、、開關(guān)電路路設(shè)計、航航船運輸路路線的計劃劃、工作指指派、貨物物裝箱方案案等。自從從擬陣概念念進入圖論論領(lǐng)域之后后，對擬陣陣中的一些些理論問題題的研究成成為組合規(guī)規(guī)劃研究的的新課題，，并得到應(yīng)應(yīng)用。現(xiàn)在在應(yīng)用的主主要方面仍仍是網(wǎng)絡(luò)上上的最優(yōu)化化問題，如如最短路問問題、最大大（小）支支撐樹問題題、最優(yōu)邊邊無關(guān)集問問題、最小小截集問題題、推銷員員問題等。。整數(shù)規(guī)劃與與組合最優(yōu)優(yōu)化的關(guān)系系整數(shù)規(guī)劃與與組合最優(yōu)優(yōu)化從廣泛泛的意義上上說，兩者者的領(lǐng)域是是一致的，，都是在有有限個可供供選擇的方方案中，尋尋找滿足一一定標(biāo)準(zhǔn)的的最好方案案。有許多多典型的問問題反映整整數(shù)規(guī)劃的的廣泛背景景。例如，，背袋（或或裝載）問問題、固定費用問題、和睦睦探險隊問問題（組合合學(xué)的對集集問題）、、有效探險險隊問題（（組合學(xué)的的覆蓋問題題）、送貨貨問題等。。因此整數(shù)數(shù)規(guī)劃的應(yīng)應(yīng)用范圍也也是極其廣廣泛的。它它不僅在工工業(yè)和工程程設(shè)計和科科學(xué)研究方方面有許多多應(yīng)用，而而且在計算算機設(shè)計、、系統(tǒng)可靠靠性、編碼碼和經(jīng)濟分析等方面也有有新的應(yīng)用用。隨機規(guī)劃隨機規(guī)劃是是對含有隨機變量的優(yōu)化問題題建模的有有效的工具具并已有一一個世紀的的歷史。第一種隨機機規(guī)劃是美美國經(jīng)濟學(xué)學(xué)家丹澤1955年提出的，，康托羅維奇奇在這方面的的貢獻，不不在于這個個新方法本本身，而在在于把它應(yīng)應(yīng)用于制定定最優(yōu)計劃劃。是廣泛泛使用的期期望值模型型，即在期期望約束條條件下，使使得期望收收益達到最最大或期望望損失達到到最小的優(yōu)優(yōu)化方法。。第二種是由由查納斯（A.Charnes）和庫伯）于1959年提出的機會約束規(guī)規(guī)劃，是在一定定的概率意意義下達到到最優(yōu)的理理論。第三種即是是劉寶碇教授于1997年提出的相相關(guān)機會規(guī)規(guī)劃，是一一種使事件件的機會在在隨機環(huán)境境下達到最最優(yōu)的理論論。它與期期望值模型型和機會約約束規(guī)劃一一起構(gòu)成了了隨機規(guī)劃劃的三個分分支。隨機規(guī)劃是是處理數(shù)據(jù)據(jù)帶有隨機機性的一類類數(shù)學(xué)規(guī)劃劃，它與確確定性數(shù)學(xué)學(xué)規(guī)劃最大大的不同在在于其系數(shù)數(shù)中引進了了隨機變量量，這使得得隨機規(guī)劃劃比起確定定性數(shù)學(xué)規(guī)規(guī)劃更適合合于實際問問題。在管理科學(xué)、運籌學(xué)、經(jīng)濟學(xué)、最優(yōu)控制等領(lǐng)域，隨隨機規(guī)劃有有著廣泛的的應(yīng)用。隨機規(guī)劃的的求解方法法隨機規(guī)劃的的求解方法法大致分兩兩種。第一種是轉(zhuǎn)轉(zhuǎn)化法，即即將隨機規(guī)規(guī)劃轉(zhuǎn)化成成各自的確確定性等價價類，然后后利用已有有的確定性性規(guī)劃的求求解方法解解之；另一種是逼逼近方法，，利用隨機機模擬技術(shù)，通過一定定的遺傳算法程序，得到到隨機規(guī)劃劃問題的近近似最優(yōu)解解和目標(biāo)函函數(shù)的近似似最優(yōu)值。。講授內(nèi)容教材：最優(yōu)優(yōu)化方法及及應(yīng)用案例例.緒論.線性規(guī)劃.非線性規(guī)劃劃.動態(tài)規(guī)劃.多目標(biāo)優(yōu)化化及其應(yīng)用用預(yù)備知識和和學(xué)習(xí)要求求學(xué)習(xí)該課程程的需要具具備的基本本知識高等數(shù)學(xué)線線性代代數(shù)學(xué)習(xí)該課程程的要求態(tài)度決定一一切正確理解基基本概念和和原理掌握最優(yōu)化化方法的思思想能夠運用最最優(yōu)化方法法分析解決決實際問題題最優(yōu)化問題題的數(shù)學(xué)模模型一般形形式最優(yōu)化問題題（目標(biāo)函數(shù)）（不等式約束）（等式約束）其中最優(yōu)化問題題分類經(jīng)典優(yōu)化問問題（靜態(tài)態(tài)優(yōu)化問題題）和現(xiàn)代優(yōu)化問問題（動態(tài)態(tài)優(yōu)化問題題）1、經(jīng)典優(yōu)化化問題（靜靜態(tài)優(yōu)化問問題）根據(jù)數(shù)學(xué)模模型中有無無約束函數(shù)數(shù)分為有約約束的最優(yōu)優(yōu)化問題和和無約束的的最優(yōu)化問問題；根據(jù)目標(biāo)函函數(shù)和約束束函數(shù)的函函數(shù)類型分分類：線性性最優(yōu)化問問題(整數(shù)規(guī)劃、、０－１規(guī)規(guī)劃)、非線性最最優(yōu)化問題題、二次規(guī)規(guī)劃、多目目標(biāo)規(guī)劃。。2、現(xiàn)代優(yōu)化化問題（動動態(tài)優(yōu)化問問題）動態(tài)規(guī)劃劃與最優(yōu)控控制問題題組合合優(yōu)化問問題最優(yōu)解的的相關(guān)定定義定義１.1可行解滿足約束束條(1.2)和(1.3)的x稱為可行行解，也也稱為可可行點或或容許點點。定義１.2可行域全體可行行解構(gòu)成成的集合合稱為可可行域，，也稱為為容許集集，記為為D,即：定義１.3整體(全局）最最優(yōu)解對于一切切則稱恒有為最優(yōu)化化問題的整整體(全局）最優(yōu)解。。若恒有則稱為最優(yōu)化化問題的嚴嚴格整體體（全局））最優(yōu)解解。定義１.4局部最優(yōu)優(yōu)解若若：存在的某鄰域域使得對于于一切恒有則稱為最優(yōu)化化問題的的局部最優(yōu)解解。其中同樣有：：嚴格局局部最優(yōu)優(yōu)解。而局部最最優(yōu)解不不一定是是整體最最優(yōu)解。。顯然，整整體最優(yōu)優(yōu)解一定定是局部部最優(yōu)解解，注意：求解最優(yōu)優(yōu)化問題題，實際際上是求求可行域域D上的整體體最優(yōu)解解。但是，在一般情情況下，，整體最優(yōu)優(yōu)解是很很難求出出的，往往往只能能求出局局部最優(yōu)優(yōu)解。定義１.5范數(shù)：在維向量空空間中，定義實函函數(shù)使其滿足足以下三三個條件件：（１）對對任意有在當(dāng)且僅當(dāng)當(dāng)時（２）對對任意及實數(shù)有（３）對對任意有則稱函數(shù)數(shù)為上的向量量范數(shù)。。兩類比較較常見的的范數(shù)P-范數(shù)：其中最常常用的是是2-范數(shù)，即即：范數(shù)：最優(yōu)化方方法概述述求解的的一種種算法，，通常是是指一種種產(chǎn)生點點列的程程序。常表現(xiàn)為為的的一種映映射F，它常常常滿足以以下兩點點要求：：（1）;（2）式（1）實際上上常表現(xiàn)現(xiàn)為。。因因此通常常構(gòu)造映映射F的關(guān)鍵就就在于設(shè)設(shè)計一種種能從出出發(fā)發(fā)，確定定方向與與步步長的的方法，，要求滿滿足式（（2）并使整整個序列列（或子子列）具具有收斂斂性。迭代算法法選取一個個初始可可行點由這個初初始可行行點出發(fā)發(fā)，依次次產(chǎn)生一一個可行行點列：：恰好是問問題的一一個最優(yōu)優(yōu)解，或或者該點點列收斂到問問題的一一個最優(yōu)優(yōu)解?？尚悬c列列的產(chǎn)生生在處求得一一個方向向（可行下下降方向向）在射線上求一點點：使得其中稱為步長長。下降方向向定義1.6下降方向向：在點處，對于方向向若存在實實數(shù)使得任意意的有：成立，則稱為函數(shù)在點處的一個下下降方向向。當(dāng)具有連續(xù)續(xù)的一階階偏導(dǎo)數(shù)數(shù)，令由Taylor公式：當(dāng)時，有所以（充分小時時）是在處的一個個下降方向向。通常稱滿滿足：的方向為在處的下降降方向。?？尚蟹较蛳蚨x1.7可行方向向：已知區(qū)域域?qū)τ谙蛄苛咳舸嬖趯崒崝?shù)使得任意意的有：則稱為點處關(guān)于區(qū)域域的可行方方向。下降方向向關(guān)于區(qū)區(qū)域可行，則則稱為可可行下降降方向。最優(yōu)化問問題的算算法的一一般迭代代格式給定初始始點令（１）確確定處的可行行下降方方向（２）確確定步長長使得：（３）令令（４）若若滿足某種種終止準(zhǔn)準(zhǔn)則，則則停止；；否則令轉(zhuǎn)（１））收斂性如果一個個算法只只有當(dāng)初初始點充充分接近近最優(yōu)解解時，產(chǎn)產(chǎn)生的點點列才收收斂，則則稱該算算法為具具有局部收斂斂的算法。。如果對任任意的初初始點，，由算法法產(chǎn)生的的點列都都收斂，，則稱該該算法為為具有全局收斂斂的算法。。具有全局局收斂性性的算法法才有實實用意義義。但對對算法的的局部收收斂性分分析，在在理論上上是重要要的，因因為它是是全局收收斂性分分析的基基礎(chǔ)。收斂速度度定義1.8設(shè)序列收斂于而且若則稱序列列為線性收收斂的，，稱為收斂比比；若則稱序列列為超線性性收斂的的。收斂速度度定義1.9設(shè)序列收斂于若對則稱序列列為有：階收斂的的。特別當(dāng)：：時稱為二二階收斂斂的。終止準(zhǔn)則則對于一種種算法，，應(yīng)該有有某種終終止準(zhǔn)則則，當(dāng)某某次迭代滿足終止止準(zhǔn)則時時，就停停止迭代代。常用用的終止準(zhǔn)則則有：（1）或或（３）其中是預(yù)先給給定的。。（2）最優(yōu)化模模型的建建立建立數(shù)學(xué)學(xué)模型：：在對實際際問題深深入研究究的基礎(chǔ)礎(chǔ)上，利用有關(guān)關(guān)數(shù)學(xué)的的知識和和概念，，對自然然規(guī)律的的真實描述（數(shù)數(shù)學(xué)描述述）或模模擬。實例分析析1、生產(chǎn)計計劃問題題資資源分分配問題題書第4-5頁例第第195頁資源分配配問題就就是將數(shù)數(shù)量一定定的一種種或若干干種資源源（例如如原材料料、資金金、設(shè)備備、設(shè)施施、勞力力等），，恰當(dāng)?shù)氐胤峙浣o給若干使使用者或或地區(qū)，，從而使使目標(biāo)函函數(shù)最優(yōu)優(yōu)。線性規(guī)劃劃模型2、食譜問問題設(shè)市場上上可買到到種種不同的的食品，，第種種食品品的單位位售價為為。。每種種食品含含有種種基基本營養(yǎng)養(yǎng)成分，，第種種食食品每一一個單位位含有第第種種營養(yǎng)成成分為。。又設(shè)每每人每天天對第種種營營養(yǎng)成分分的需要要量不少少于。。試確確定在保保證營養(yǎng)養(yǎng)要求條條件下的的最經(jīng)濟濟食譜。。線性規(guī)劃劃模型3、選址問問題（類類似的問問題P89)某城市要要建設(shè)一一個煤氣氣供應(yīng)中中心，該該中心向向城市中中個個用戶（（用戶位位置固定定）提供供輸送煤煤氣服務(wù)務(wù)。對于于給定的的坐標(biāo)系系而言，，已知第第個個用戶位位置的坐坐標(biāo)為。。如果輸輸送管道道不受道道路影響響（即只只考慮直直線距離離），問問如何確確定該中中心的位位置，才才能使總總的輸送送管道最最短，同同時中心心到第個個用用戶的距距離必須須介于和和之之間間。。非線性規(guī)規(guī)劃模型型4、最短路路問題(圖論極值值問題））或最優(yōu)管管道鋪設(shè)設(shè)問題(類似問題題166頁)動態(tài)規(guī)劃劃模型線性規(guī)劃劃1、線性規(guī)規(guī)劃模型型的建立立2、線性規(guī)規(guī)劃模型型的尋優(yōu)優(yōu)線性規(guī)劃劃模型的的建立建立優(yōu)化化模型的的三大要要素（1）確定決決策變量量（2）確定目目標(biāo)（決決策準(zhǔn)則則）（3）確定約約束條件件實例分析析（1）生產(chǎn)計計劃資資源分分配問題題例2.1某廠計劃劃在下一一個生產(chǎn)產(chǎn)周期內(nèi)內(nèi)生產(chǎn)甲甲、乙兩兩種產(chǎn)品品，需要要消耗R1、R2、和R3三種資源源（例如如鋼材、、煤炭或或設(shè)備臺臺時等）），已知知每件產(chǎn)產(chǎn)品對這這三種資資源的消消耗、這這三種資資源可供供使用的的量及每每單位產(chǎn)產(chǎn)品可獲獲得的利利潤如表表2.1所示。問問應(yīng)如何何安排生生產(chǎn)計劃劃，使得得既能充充分利用用現(xiàn)有資資源，又又使總利利潤最大大？試建建立問題題的數(shù)學(xué)學(xué)模型。。(P10-11)

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

甲乙可供使用資源量R1R2R3522315170100150單件利潤1018表2-1（2）原材料的合合理利用問題題（P11-12）（3）0-1背包問題(P12)背包問題(P13)(4)運輸問題(5)分派（指派））問題線性的特點比例性可加性共同的特征每一個線性規(guī)規(guī)劃問題都用用一組決策變變量表示某一方案案，這組決策策變量的值就就代表一個具具體方案。一一般這些變量量取值是非負負且連續(xù)的；；(2)要有各種資源源和使使用有關(guān)資源源的技術(shù)數(shù)據(jù)據(jù),創(chuàng)造新價值的的數(shù)據(jù)；共同的特征（（繼續(xù)）(3)存在可以量化化的約束條件件，這些約束束條件可以用一一組線性等式式或線性不等等式來表示；(4)要有一個達到到目標(biāo)的要求求，它可用決決策變量的線性函函數(shù)(稱為目標(biāo)函數(shù)數(shù))來表示。按問題的不同同，要求目標(biāo)標(biāo)函數(shù)實現(xiàn)最最大化或最小化。它們的對應(yīng)關(guān)關(guān)系可用表格格表示：線性規(guī)劃的一一般模型形式式線性規(guī)劃模型型的標(biāo)準(zhǔn)形式式線性規(guī)劃模型型的幾種表示示形式向量表示式矩陣表示式如何變換為標(biāo)標(biāo)準(zhǔn)形(1)當(dāng)目標(biāo)函數(shù)為為求極（最））大值時,即，，這時只只需令，，即即轉(zhuǎn)化為。。這這就同標(biāo)準(zhǔn)形形的目標(biāo)函數(shù)數(shù)的形式一致致了。(2)約束方程為不不等式。這里里有兩種情況況：一種是約約束方程為“≤”不等式，則可可在“≤”不等式的左端端加入非負松松弛變量，把把原“≤”不等式變?yōu)榈鹊仁?；另一種種是約束方程程為“≥”不等式，則可可在“≥”不等式的左端端減去一個非非負剩余變量量(也可稱松弛變變量)，把不等式約約束條件變?yōu)闉榈仁郊s束條條件。如何變換為標(biāo)標(biāo)準(zhǔn)型(續(xù)）（3）當(dāng)約束條件件的右端常數(shù)數(shù)項時時，只需將等等式或不等式式兩端同乘以以即即可。（4）當(dāng)決策變量量的取值約束束為時時，令，則有。。（5）當(dāng)決策變量量的取值無任任何約束時，，令，則由表表示示的不不受任何何取值的約束束。線性規(guī)劃的分分類線性規(guī)劃一般線性規(guī)劃劃特殊線性規(guī)劃整數(shù)規(guī)劃運輸問題純整數(shù)規(guī)劃混合整數(shù)規(guī)劃劃0-1規(guī)劃指派問題的線性規(guī)劃解的相關(guān)概念念基本概念定義2.1在線性規(guī)劃問問題中，凡是是滿足其全部部約束條件（（包括變量取取值約束）的的一組決策變變量的取值稱稱作該線性規(guī)規(guī)劃問題的可行解。定義2.2線性規(guī)劃問題題中，可行解解的集合稱為為該問題的可行域。定義2.3在線性規(guī)劃問問題的可行域域中，使目標(biāo)標(biāo)函數(shù)值達到到最優(yōu)（最大大或最?。┑牡目尚薪夥Q為為該問題的最優(yōu)解。相應(yīng)的目標(biāo)標(biāo)函數(shù)值稱為為最優(yōu)值。凸集定義1設(shè)集合若對于任意兩兩點及實數(shù)都有：則稱集合為凸集．注：常見的凸集：：空集，整個個歐氏空間超平面：半空間：例1：證明超球為凸集．證明：設(shè)為超球中的任任意兩點，則有：即點屬于超球所以超球為凸凸集．凸集的性質(zhì)（１）有限個（可以以改成無限））凸集的交集集為凸集．（２）設(shè)是凸集，是一實數(shù)，則下面的集合是凸集：：（３）設(shè)是凸集，則的和集是凸集注：和集和并集有有很大的區(qū)別別，凸集的并并集未必是凸集，，而凸集的和和集是凸集．．例：表示軸上的點．表示軸上的點．則表示兩個軸的的所有點，它不是凸集；；而凸集．推論：設(shè)是凸集，則也是凸集，其中是實數(shù)．定義2:設(shè)實數(shù)則稱為的凸組合．注：凸集中任意有有限個點的凸凸組合仍然在在該凸集中．極點（頂點））定義1設(shè)為凸集，若中不存在兩個相異的點點及某一實數(shù)使得則稱為的極點．例：則上的點均為極極點．證：設(shè)若存在及使得則：不等式要取取等號，必必須且容易證明根據(jù)定義可可知為極點．與算法有關(guān)關(guān)的概念無窮多解圖解法中，，此情況出出現(xiàn)在目標(biāo)標(biāo)函數(shù)等值值直線向優(yōu)優(yōu)化方向平平移時，最最后與可行行域邊界的的一條邊重重合，此時時，除該直直線段的兩兩個端點（（即可行域域的兩個頂頂點）外，，直線段上上所有點的的目標(biāo)函數(shù)數(shù)值都達到到最優(yōu)。無界解圖解法中，，此情況出出現(xiàn)在可行行域為無界界區(qū)域，且且目標(biāo)函數(shù)數(shù)等值直線線向優(yōu)化方方向平移時時，始終無無法脫離可可行域。發(fā)發(fā)生這種情情況往往是是建模時遺遺漏了某些些約束條件件所至。無解當(dāng)可行域為為空集時，，問題不存存在可行解解。發(fā)生此此情況是因因為模型中中出現(xiàn)了相相互矛盾的的約束條件件。圖解法中解解的概念與算法有關(guān)關(guān)的概念可行解、最最優(yōu)解基、基向量、基基變量基解、基可可行解可行基與單純形法法有關(guān)的解解概念可行解、最最優(yōu)解滿足約束條條件(1-2)，(1-3)式的解稱為線性規(guī)規(guī)劃問題的的可行解，其中使目目標(biāo)函數(shù)達達到最小值值的可行解解稱為最優(yōu)解。基、基向量量、基變量量基解、基可可行解基解：滿足足約束方程程組（1-2）且非基變變量為0的解?；尚薪猓海簼M足非負負條件（1-3）的基解.基可行解的的非零分量量的數(shù)目也也不大于m，并且都是是非負的。?？尚谢鶎?yīng)于基可可行解的基基，稱為可可行基。約束方程組組(1-2)具有基解的的數(shù)目最多多是個個。一般般基可行解解的數(shù)目要要小于基解解的數(shù)目。。以上提到的的幾種解的的概念，它它們之間的的關(guān)系可用用圖6表明。另外還要說說明一點，，基解中的的非零分量量的個數(shù)小小于m個時，該基基解是退化化解。在以以下討論時時，假設(shè)不不出現(xiàn)退化化的情況。。以上給出出了線性規(guī)規(guī)劃問題的的解的概念念和定義，，它們將有有助于用來來分析線性性規(guī)劃問題題的求解過過程?？尚薪狻⒒?、基可可行解之間間的關(guān)系圖6與算法有關(guān)關(guān)的概念與內(nèi)點法有有關(guān)的解概概念與算法有關(guān)關(guān)的概念與其他算法法有關(guān)的解解概念與算法有關(guān)關(guān)的概念與其他算法法有關(guān)的解解概念線性規(guī)劃的的尋優(yōu)方法法圖解法單純形方法法內(nèi)點法計算機求解解分支定界法法隱枚舉法表上作業(yè)法法匈牙利法只有二個變變量的線性性規(guī)劃問題題一般LP特殊LP整數(shù)線性規(guī)規(guī)劃問題0-1規(guī)劃問題平衡運輸問問題指派問題重要的方法法圖解法對于只有兩兩個變量的的線性規(guī)劃劃問題，可可以采用在在平面上作作圖的方法法求解，稱稱為圖解法。例1用圖解法求求解因存在，，所以必須須在直角坐坐標(biāo)的第1象限內(nèi)作圖圖，求解。。（1）在平面直直角坐標(biāo)系系上畫出可可行域(2)畫出目標(biāo)函函數(shù)等值線線，并沿其其法線方向向平移等值值線，以求求得最優(yōu)解解。目標(biāo)值值在（4，2）點，達到到最大值14目標(biāo)函數(shù)圖1可能出現(xiàn)的的幾種情況況（1）無窮多最優(yōu)優(yōu)解(多重最優(yōu)解解)目標(biāo)函數(shù)maxz=2x1+4x2圖3（2）無界解圖4（3）無可行解解當(dāng)存在矛盾盾的約束條條件時，為為無可行域域。如果在例1的數(shù)學(xué)模型型中增加一一個約束條條件:該問題的可可行域為空集，即無可行行解，不存在可行行域增加的約束束條件圖5小結(jié)（1）線性性規(guī)劃問題題的模型特特征（2）通過過圖解法了了解如何求求解線性規(guī)規(guī)劃問題（3）為求求解高維線線性規(guī)劃問問題，必須須建立的概念線性規(guī)劃的的單純形方方法線性規(guī)劃問問題的幾個個定理單純形法的的原理初始基可行行解的確定定線性規(guī)規(guī)劃問問題的的幾個個定理理定理1若線性性規(guī)劃劃問題題存在在可行行解，，則問問題的的可行域域是凸凸集。。定理2線性規(guī)規(guī)劃問問題的的基可可行解解對應(yīng)應(yīng)線性性規(guī)劃劃問題可可行域域（凸凸集））的頂頂點（（極點點）。。定理3若線性性規(guī)劃劃問題題有最最優(yōu)解解，則則一定定存在在一個基基可行行解是是最優(yōu)優(yōu)解。。結(jié)論：：求解解線性性規(guī)劃劃問題題歸結(jié)結(jié)為找找最優(yōu)優(yōu)基可可行解，即即在在其可可行域域（凸凸集））的頂頂點（（極點點）中找使使目標(biāo)標(biāo)函數(shù)數(shù)最小小的頂頂點（（極點點）。。單純形形法的的原理理單純形形方法法的基基本思思想從一個個基可可行解解出發(fā)發(fā)，求求一個個使目目標(biāo)函函數(shù)值值有所所改善善的基基可行行解；；通過過不斷斷改進進基可可行解解，力力圖達達到最最優(yōu)基基可行行解。。它主要要通過過基可可行解解的轉(zhuǎn)轉(zhuǎn)換完完成。?；尚行薪獾牡霓D(zhuǎn)換換考慮矩矩陣形形式的的標(biāo)準(zhǔn)準(zhǔn)形問問題：：式中最優(yōu)性性檢驗驗和解解的判判別單純形形方法法的計計算步步驟步驟1找一個個初始始基可可行解解（常常用大大M法和兩兩階法法找））。步驟2解步驟3求單純純形乘乘子，，解解使用表表格形形式的的單純純形方方法使用表表格形形式的的單純純形方方法用單純純形法法解下下列問問題：：初始基基可行行解的的確定定大M法基本思思想：：在約約束中中增加加人工工變量量，，同時時改變變目標(biāo)標(biāo)函數(shù)數(shù)，，加上上罰項項，，其其中是是很大大的正正數(shù)，，這樣樣，在在極小小化目目標(biāo)函函數(shù)的的過程程中，，由于于大的的存存在，，將使使人工工變量量離基基?？紤]線線性規(guī)規(guī)劃問問題大M法引進人人工變變量，，研究究下列列問題題：用單純純形法法求解解線性性規(guī)劃劃問題題(1-14)，獲得得其解解，它它與（（1-13）的解解的關(guān)關(guān)系如如下：：大M法達到問問題（（1-14）的最最優(yōu)解解，且且，，這這時得得到的的為為問題題（1-13）的最最優(yōu)解解。達到問問題（（1-14）的最最優(yōu)解解，且且，，這這時問問題（（1-13）無可可行解解。問題（（1-14）不存存在有有限最最優(yōu)值值，在在單純純形表表中，，，，這這時問題（（1-13）無界界。問題（（1-14）不存存在有有限最最優(yōu)值值，在在單純純形表表中，，，，這這時時問題（（1-13）無可可行解解。大M法用大M法求解解下列列問題題：兩個階階段法法基本思思想：：在約約束中中增加加人工工變量量，，以以構(gòu)造造一個個單位位矩陣陣。對對添加加了人人工變變量的的線性性規(guī)劃劃問題題分兩兩個階階段計計算。。第一階階段是是用單單純形形方法法消去去人工工變量量（如如果可可能的的話）），即即把人人工變變量都都變變成非非基變變量，，求出出原來來問題題的一一個基基本可可行解解。消消去人人工變變量的的一一種方方法是是解下下列第第一階階段問問題：：兩個階階段法法求解（（1-16），設(shè)設(shè)得到到的最最優(yōu)基基本可可行解解是，此時時必有有下列列三種種情形形之一一：這時（（1-13）無可可行解解。的分量量都是是非基基變量量，這這時的的基變變量都都是原來來的變變量，，又知知是（1-16）的基基可行行解，，因此此是是（1-13）的一一個基基可行行解。。兩個階階段法法的某些些分量量是基基變量量，這這時可可用主主元消消去法法，把把原來來變量量中的的某些些非基基變量量引進進基，，替換換出基基變量量中的的人工工變量量，再再開始始兩階階段法法的第第二階階段。。應(yīng)該該指出出，為為替換換出人人工變變量而而采用用的主主元消消去法法，在在主元元的選選擇上上，并并不要要求遵遵守單單純形形法確確定離離進基基變量量的規(guī)規(guī)則。。兩階段段法的的第二二階段段，就就是從從得到到的基基可行行解出出發(fā)，，用單單純形形方法法求（（1-13）的最最優(yōu)解解。即即在問問題（（1-16）中去去掉人人工變變量，，以第第一階階段最最后的的基變變量為為初始始基變變量開開始迭迭代。。操作作上可可直接接在第第一階階段的的最終終單純純形表表基礎(chǔ)礎(chǔ)上進進行，，只需需在表表中除除去人人工變變量列列、恢恢復(fù)目目標(biāo)價價值向向量為為原問問題之之前的的狀況況即可可。兩個階階段法法用兩階階段法法求解解下列列問題題：內(nèi)點法法卡瑪卡卡（Karmarkar）算法--投影尺尺度法法在大型型問題題的應(yīng)應(yīng)用中中，顯顯示出出能與與單純純形法法競爭爭的潛潛力不能直直接用用于通通常形形式的的線性性規(guī)劃劃問題題原仿射射尺度度法(改進的的內(nèi)點點法)可以直直接求求解標(biāo)標(biāo)準(zhǔn)形形式的的線性性規(guī)劃劃問題題理論依依據(jù)定理2.5在仿射射尺度度變換換下下，，的的正正卦限限中的的點仍仍變?yōu)闉檎载韵拗兄械狞c點，但但其分分量值值發(fā)生生變化化。特特別地地，的的像像點為為。。定理2.6設(shè)為行行滿秩秩矩陣陣，，則則向量量在的的零空空間上上的的正交交投影影為基本思思想先找出出一個個內(nèi)點可可行解解；從該該點出出發(fā)，，在可行域域的內(nèi)內(nèi)部尋求一一個使使目標(biāo)函函數(shù)值值下降降的可行方方向，沿該該方向向移動動到一一個新新的內(nèi)點可可行解解；如此此逐步步移動動，當(dāng)當(dāng)移動動到與與最優(yōu)優(yōu)解充充分接接近時時，迭迭代停停止。。計算步步驟及及框圖圖計算步步驟（P41-42）關(guān)鍵的的問題題是：對于于任一一迭代代點，，如何何求得得一個個適當(dāng)當(dāng)?shù)囊苿臃椒较?，使是是一個個改進的的內(nèi)點點可行行解。利用仿仿射尺尺度變變換的的逆變變換定理，可找到到：,計算算框框圖圖P42例題及及初始始內(nèi)點點可行行解的的確定定例2.10用原仿射尺度度算法求解如如下問題（P43-44)初始內(nèi)點可行行解的確定（（P44）方法：類似于于單純形方法法的大M法。線性規(guī)劃問題題的計算機求求解現(xiàn)在已經(jīng)出現(xiàn)現(xiàn)了很多能夠夠求解線性規(guī)規(guī)劃問題的計計算機軟件產(chǎn)產(chǎn)品，如Lindo,Lingo或Matlab等。下面以Matlab6.x為背景，介紹紹如何在Matlab中求解線性規(guī)規(guī)劃。將模型轉(zhuǎn)換成成如下“標(biāo)準(zhǔn)準(zhǔn)形式”：線性規(guī)劃問題題的計算機求求解在上述標(biāo)準(zhǔn)形形式中，目標(biāo)標(biāo)函數(shù)求極小小，約束條件件嚴格地分為為三類：不等等式約束且取取“”不等號、等式式約束及變量量取值范圍約約束。其中線性規(guī)劃問題題的計算機求求解調(diào)用時需注意意以下幾點：：（1）Matlab提供了一種機機制，允許調(diào)調(diào)用某個函數(shù)數(shù)時提供的的參數(shù)個數(shù)少少于定義該函函數(shù)時所定義義的參數(shù)個數(shù)數(shù)。因此，在在調(diào)用函數(shù)linprog傳遞參數(shù)時必必須按語法指指定的順序?qū)?yīng)傳遞，若若缺少某些參參數(shù)，除非其其位于參數(shù)表表的尾部，否否則調(diào)用時必必須以空數(shù)組組“[]”形式占位。（2）若問題的模模型為目標(biāo)函函數(shù)求最（極極）大，須先先將目標(biāo)函數(shù)數(shù)轉(zhuǎn)換為最（（極）小。（3）代碼中所使使用的標(biāo)點分分隔符，如逗逗號、分號、、括號等，必必須是半角字字符。線性規(guī)劃問題題的計算機求求解寫出下列問題題的Matlab調(diào)用代碼：分支定界法與與隱枚舉法法解決的問題各各是什么？理論依據(jù)Discuss基本思想計算步驟及框框圖計算中的說明明計算機求解的的異同？講P62例2.13練P907（1）分支定界法的的計算框圖隱枚舉法的計計算框圖表上作業(yè)法與與匈牙利法法解決的問題各各是什么？理論依據(jù)Discuss基本思想計算步驟及框框圖計算中的說明明表上作業(yè)法是是單純形法在在求解運輸問問題時的一種種簡化方法，，其實質(zhì)是單單純形法。結(jié)合算法步驟驟講P63例2.14和P67例2.15.表上作業(yè)法的的計算框圖匈牙利法的計計算框圖第三專題非非線線性優(yōu)化問題題1、非線性優(yōu)化化模型的建立立2、非線性優(yōu)化模模型的尋優(yōu)非線性優(yōu)化模模型的建立確定決策變量量確定目標(biāo)（決決策準(zhǔn)則）確定約束條件件實例分析（1）投資決策問問題（P88)（2）曲線擬合問問題在實驗數(shù)據(jù)處處理或統(tǒng)計資資料分析中，，常常遇到這這樣的問題：：如何利用有有關(guān)變量的實實驗數(shù)據(jù)（資資料）去確定定這些變量間間的函數(shù)關(guān)系系。例如，已已知某物體的的溫度與與時間之之間有有如下形式的的經(jīng)驗函數(shù)關(guān)關(guān)系：其中是是待定參數(shù)數(shù)。通過測試試獲得n組溫度與時間間之間的實驗驗數(shù)據(jù)，，試確定參數(shù)數(shù)使使理論曲線盡盡可能地與n個測試點擬合合。非線性規(guī)劃問問題的共同特特征都是求一個目目標(biāo)函數(shù)在一一組約束條件件下的極值問題。。在目標(biāo)函數(shù)或或約束條件中中，至少有一一個是變量的的非線性函數(shù)數(shù)。非線性規(guī)劃問問題一般形式：向量形式：非線性優(yōu)化問問題的尋優(yōu)相關(guān)概念及理理論一維最優(yōu)化方方法多維無約束最最優(yōu)化方法多維有約束最最優(yōu)化方法非線性規(guī)劃的的相關(guān)概念及及理論一階導(dǎo)數(shù)、二二階導(dǎo)數(shù)和n元函數(shù)的Taylor公式定義4設(shè)函數(shù)定義在凸集上，若對任意的及任意的都有：則稱函數(shù)為凸集上的凸函數(shù)．．定義5嚴格凸函數(shù)注：將上述定義中中的不等式反反向，可以得得到凹函數(shù)的定義義．凸函數(shù)例1：設(shè)試證明在上是嚴格凸函函數(shù)．證明:設(shè)且都有：因此在上是嚴格凸函函數(shù)．例2：試證線性函數(shù)數(shù)是證明:設(shè)上的凸函數(shù)．．則所以是凸函數(shù)．類似可以證明明是凹函數(shù)．凸函數(shù)的幾何何性質(zhì)對一元函數(shù)在幾何上表示連接的線段．表示在點處的函數(shù)值．所以一元凸函函數(shù)表示連接接函數(shù)圖形上上任意兩點的線段總是位位于曲線弧的的上方．凸函數(shù)的性質(zhì)質(zhì)（１）設(shè)（２）設(shè)函數(shù)，是凸集上的凸函數(shù)，，實數(shù)則也是上的凸函數(shù)．．是凸集上的凸實數(shù)則也是上的凸函數(shù)．．（３）設(shè)是凸集上的凸函數(shù)，，是實數(shù)，則水平集是凸集．下面的圖形給給出了凸函數(shù)數(shù)的等值線的圖圖形，可以看看出水平集是是凸集凸函數(shù)的判定定定理1設(shè)上，令則:(1)是定義在凸集集是凸集上的凸函數(shù)的的充要條件是是對任意的一元函數(shù)為上的凸函數(shù).(2)設(shè)若在上為嚴格凸函數(shù)，則在上為嚴格凸函函數(shù)．該定理的幾何何意義是：凸凸函數(shù)上任意意兩點之間的部分是一一段向下凸的的?。浑A條件定理2.1設(shè)在凸集上可微，則：在上為凸函數(shù)的的充要條件是是對任意的都有：定理2.2嚴格凸函數(shù)(充要條件)二階條件定理3設(shè)在開凸集內(nèi)二階可微，則則(1)是內(nèi)的凸函數(shù)的的充要條件為為，在內(nèi)任一點處，的海色矩陣半正定,其中：二階條件定理3設(shè)在開凸集內(nèi)(2)若在內(nèi)正定,則在內(nèi)二階可微，則則是嚴格凸函數(shù)數(shù)．注:反之不成立．．例：顯然是嚴格凸凸的，但在點處不是正定的凸規(guī)劃定義6設(shè)為凸集，為上的凸函數(shù)，，則稱規(guī)劃問題題為凸規(guī)劃問題題．定理4(1)凸規(guī)劃問題的的任一局部極極小點是整體極小點，，全體極小點點組成凸集．．(2)若是凸集上的嚴格凸函函數(shù)，且凸規(guī)劃問題題整體極小點存存在，則整體極小點點是唯一的．．非線性規(guī)劃的的最優(yōu)性條件件最優(yōu)性條件：：是指非線性性規(guī)劃模型的的最優(yōu)解所要要滿足的必要要和充分條件件。無約束最優(yōu)性性條件約束最優(yōu)性條條件無約束最優(yōu)性性條件一（單）元函函數(shù)的最優(yōu)性性條件（１）若（２）為的局部極小點點，則若則為的嚴格局部極極小點；若（３）為的局部極小點點，則：多元函數(shù)的一一階必要條件件（P106-107)定理1:若為的局部極小點點，且在內(nèi)一階連續(xù)可導(dǎo)導(dǎo)，則注:(1)僅僅是必要條條件，而非充充分條件．(2)滿足的點稱為駐點點．駐點分為：極極小點，極大大點，鞍點．．多元函數(shù)的二二階充分條件件定理2:若在內(nèi)二階連續(xù)可導(dǎo)導(dǎo)，且正定,則為嚴格局部極小點．注:如果負定,則為嚴格局部極極大點．二階必要條件件和充要條件件定理3:若為的局部極小點點，且在內(nèi)二階連續(xù)可導(dǎo)導(dǎo)，則半正定．定理4:設(shè)在上是凸函數(shù)且且有一階連續(xù)續(xù)偏導(dǎo)數(shù)，則為的整體極小點點的充要條件是例1：利用極值條件件解下列問題題：解：令即：得到駐點：函數(shù)的海色陣：由此，在點處的海色陣依依次為：由于于矩矩陣陣不定定，，則不是是極極小小點點．．負定定，，則不是是極極小小點點，，實際際上上它它是是極極大大點點．．正定定，，則是局局部部極極小小點點．．約束束最最優(yōu)優(yōu)性性條條件件(p133-p136)定義義1:有效效約約束束：：若(*)中的的一一個個可可行行點點使得得某個個不不等等式式約約束束變成成等等式式，，即則稱為為關(guān)關(guān)于于的有有效效(積極極））約約束束．．非有有效效約約束束：：若對對則稱為為關(guān)于于的非非有有效效(無效效）約約束束．．有效效集集：：定義義2:錐：：的子子集集，，如果果它它關(guān)關(guān)于于正正的的數(shù)數(shù)乘乘運運算算是封封閉閉的的．．如果果錐錐也也是是凸凸集集，，則則稱稱為為凸錐錐．凸錐錐關(guān)于于加加法法和和正正的的數(shù)數(shù)乘乘運運算算是是封封閉閉的的．．一階階必必要要條條件件定理理3.5:(Kuhn-Tucker一階階必必要要條條件件)(1951)設(shè)在（K-T條件件））一階階必必要要條條件件定理理1‘:(Kuhn-Tucker一階階必必要要條條件件)（互互補補松松弛弛條條件件））例2：驗證證是是否否滿滿足足Kuhn-Tucker條件件：：試驗驗證證最最優(yōu)優(yōu)點點為KT點．．解：：令所以以即：：所以以：：是KT點．．Lagrange函數(shù)數(shù)及及K-T條件件在一一定定凸凸性性下下的的最最優(yōu)優(yōu)性性的的充充分分條條件件一維維最最優(yōu)優(yōu)化化方方法法（（線線性性搜搜索索方方法法））已知知并且且求求出出了了處的的可可行行下下降降方方向向從出發(fā)發(fā)，，沿方方向向求目目標(biāo)標(biāo)函函數(shù)數(shù)的的最最優(yōu)優(yōu)解解，，或者者選選取取使得得：：問題題描描述述即設(shè)其其最最優(yōu)優(yōu)解解為為（叫叫精精確確步步長長因因子子）），，所以以線線性性搜搜索索是是求求解解一一元元函函數(shù)數(shù)的最最優(yōu)優(yōu)化化問問題（（也也叫叫一一維維最最優(yōu)優(yōu)化化問問題題））。。我們們來來求求解解：：于是是得得到到一一個個新新點點：：一般般地地，，線線性性搜搜索索算算法法分分成成兩兩個個階階段段：：第一一階階段段確確定定包包含含理理想想的的步步長長因因子子（或或問問題題最最優(yōu)優(yōu)解解））的的搜搜索索區(qū)區(qū)間間；；第二二階階段段采采用用某某種種分分割割技技術(shù)術(shù)或或插插值值方方法法縮小小這這個個區(qū)區(qū)間間。。搜索索區(qū)區(qū)間間：：搜索索區(qū)區(qū)間間求求取取方方法法進退退法法：：一種種簡簡單單的的確確定定初初始始搜搜索索區(qū)區(qū)間間方方法法.基本本思思想想：：是從從一一點點出出發(fā)發(fā)，，按按一一定定步步長長，，試試圖圖確確定定出出函函數(shù)數(shù)值值呈呈現(xiàn)現(xiàn)“高-低-高”的三三點點，，即即這里里。。具體體地地說說，，就就是是給給出出初初始始點點，初始始步步長長，若若，，則則下下一一步步從從新新點點出發(fā)發(fā)，，加加大大步步長長，，再再向向前前搜搜索索，，直直到到目標(biāo)標(biāo)函函數(shù)數(shù)上上升升為為止止。。若，，則則下下一一步步仍仍以以為為出出發(fā)發(fā)點點，，沿沿反反方方向向同同樣樣搜搜索索，，直直到到目目標(biāo)標(biāo)函函數(shù)數(shù)上上升升就就停停止止。。這這樣樣便便得得到到一一個個搜搜索索區(qū)區(qū)間間。。這這種種方方法法叫叫進進退退法法。。計算算步步驟驟：：見見P96計算算框框圖圖:見P97黃金金分分割割法法（（0.618法））基本本思思想想：：它通通過過對對試試探探點點的的函函數(shù)數(shù)值值進進行行比比較較，，使使得得包包含含極極小小點點的的區(qū)區(qū)間間不不斷斷縮縮短短，，當(dāng)當(dāng)區(qū)區(qū)間間長長度度小小到到精精度度范范圍圍之之內(nèi)內(nèi)時時，，可可以以粗粗略略地地認認為為區(qū)區(qū)間間上上各各點點的的函函數(shù)數(shù)值值均均接接近近于于極極小小值值。。設(shè)在上為下單峰函函數(shù)，即有唯一的極小點在左邊嚴格下降，在右邊嚴格上升。在內(nèi)任取若則若則單峰函數(shù)：黃金分割法黃金分割法若第一次選取取的試點為則下一步保留留的區(qū)間為或兩者的機會是是均等的．因此我們選取取試點時希望望設(shè)則另外，我們希希望如果縮小小的區(qū)間包含含原來的試點，則該試試點在下一步步被利用．若若保留的區(qū)我們希望原來來的間為前一次的試點點在這個區(qū)間內(nèi)內(nèi)．在縮小的區(qū)間間內(nèi)成為新的我們根據(jù)這條條件來來計算算計算的公式為：因此我們希望望：即：化簡得：若保留區(qū)間為為我們得到的結(jié)結(jié)果是一致的．該方法稱為黃黃金分割法，，實際計算取?。核渣S金分割割法又稱為0.618法．黃金分割法每每次縮小區(qū)間間的比例是一一致的，每次將區(qū)間長長度縮小到原原來的0.618倍．黃金分割法的的算法步驟Step1給定以及令Step2Step3轉(zhuǎn)Step２.令轉(zhuǎn)Step３.若則停；否則轉(zhuǎn)Step４.Step4若則轉(zhuǎn)Step3.黃金分割法的的算法步驟Step5若則轉(zhuǎn)Step3.若則轉(zhuǎn)Step3.例1（黃金分割法法）用黃金分割法法求函數(shù)在區(qū)間上的極小點。。要求最終區(qū)間間長度不大于于原始區(qū)間長度度的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.5280.5801.7511.757是Fibonacci法為了盡快得到到結(jié)果，希望望區(qū)間縮小的的盡量小。如果在區(qū)間只只有一個試點點，我們無法法將區(qū)間縮小小。如果知道兩個個試點根據(jù)的大小關(guān)系，可以得到縮小小的區(qū)間或者它與0.618法的主要區(qū)別別之一在于：：搜索區(qū)間長長度的縮短率不不是采用0.618，而是采用Fibonacci數(shù)。下面我們考慮慮任給一個另外一種思維維方式為，的單峰區(qū)間如果給定試點點的個數(shù)如何使最后確確定最優(yōu)值的區(qū)間間盡量的小。。按什么方式取取點，求次函數(shù)值之后后，可最多將多長長的原始區(qū)間間長度縮小為設(shè)為試點個數(shù)為為最終區(qū)間長度為時、原始區(qū)間的最大可能長長度。的包含設(shè)最初兩個試試點為和若極小點在內(nèi)，至多還有個試點，則若極小點在內(nèi)，包括在內(nèi)可以有個試點，則因此，如果我們采取取合適的技巧巧，可以使得得：另外，顯然，從而滿足差分方程程：此為Fibonacci數(shù)列，一般寫寫為：若原始區(qū)間為為要求最終區(qū)間間長度則由此可確定區(qū)間縮短之后后與之前的比依次次為：確定之后，最最初兩個試點點分別為：關(guān)于對稱由于上述過程完成成了依次迭代代，新區(qū)間仍仍記為若已經(jīng)進行了了次迭代，第次迭代時，還有個試點（包括括已經(jīng)計算過過的函數(shù)值的的一個）注意：（２）若在一一定的誤差范范圍內(nèi)，則認為在內(nèi)。（１）最后的的兩個試點的的選取方式：：例3.1（Fibonacci法）用Fibonacci法求函數(shù)在區(qū)間上的極小點。。要求最終區(qū)間間長度不大于于原始區(qū)間長度度的0.08倍．解：函數(shù)在區(qū)間上為下單峰函函數(shù)，由可知應(yīng)取６Fibonacci算法與0.618法幾乎完全相相同。第一次迭代：：縮短后區(qū)間為為第二次迭代：縮短后區(qū)間為為第三次迭代：：縮短后區(qū)間為為第四次迭代：：縮短后區(qū)間為為第五次迭代：：取最優(yōu)解Fibonacci方法評價Fibonacci法的優(yōu)點（１）如果縮縮小的區(qū)間包包含原來的試試點，則該試點在下一步步被利用；（２）效率最最高，有限個個試點的情況況下，可將最優(yōu)點所在的的區(qū)間縮小到到最?。瓼ibonacci法的缺點（１）搜索前前先要計算搜搜索的步數(shù)；；（２）每次搜搜索試點計算算的公式不一一致．1、黃金分割法法（0.618法）與Fibonacci法的區(qū)別與聯(lián)系系是什么？2、請讀者自己己寫出算法和和程序二分法若的導(dǎo)數(shù)存在且且容易計算，，則線性搜索的速度可以得得到提高．下面的二分法法每次將區(qū)間縮小至原原來的二分之之一．設(shè)為下單峰函數(shù)數(shù)，若在內(nèi)具有連續(xù)的一一階導(dǎo)數(shù)，且取若則為極小點；若則以代替若則以代替二分法每次迭迭代都將區(qū)間間縮短一半，，故二分法的的收斂速度也也是線性的，，收斂比為1/2。。計算步驟：見見P105計算框圖:見P106多維無約束最最優(yōu)化方法最速下降法(阻尼)牛頓法共軛梯度法問題提出問題：在點處，沿什么方向下降最快?分析：考查：顯然當(dāng)時，取極小值．因此：結(jié)論：負梯度方向使使下降最快，亦即最速下降方向．最速下降法最速下降法算算法Step1:給出Step2:計算如果停．Step3:計算下降方向向Step4:計算步長因子子Step5:令轉(zhuǎn)步２.問題：設(shè)是正定二次函函數(shù),由精確的線搜搜索確定的特別當(dāng)：例1：用最速下降法法求解：解：分析：(1)因此：最速下降法是是整體收斂的的，且是線性收斂斂的．(2)兩個相鄰的搜搜索方向是正正交的．收斂性分析定理1:設(shè)在上存在且一致致連續(xù)，則最速下降法法產(chǎn)生的序列列滿足或者對某某個有或者證明：對于最速下降降法，由以上定理立立得．收斂性分析定理2:設(shè)二次連續(xù)可微微，且其中是個正常數(shù)，，對任何給定的的初始點最速下降算法法或有限終止止，或者或者證明：用以上的結(jié)論論：最速下降法優(yōu)優(yōu)點(1)程序設(shè)計簡單單，計算量小小，存儲量小小，對初始點沒有有特別要求．．(2)有著很好的整整體收斂性，，即使對一般般的目標(biāo)函數(shù)，它它也整體收斂斂．最速下降法缺缺點最速下降法是是線性收斂的的，并且有時