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

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

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

4、優化。例如，導彈系統的最優控制，能保證用最少燃料 完成飛行義務,用最短時間到達目的;再如飛機、船舶、電力系統等的最優控制，化工、冶金等工廠的最正確工況的控制。計算機接口安裝不斷完善和優化方法的進一步開展，還為計算機在線消費控制發明了有利條件。最優控制的對象也將從對機械、電氣、化工等硬系統的控制轉向對生態、環境以致社會經濟系統的控制。 最優化的開展簡史 最優化是一個古老的課題。長期以來，人們對最優化問題進展著討論和研討。 公元前 500年古希臘在討論建筑美學中就已發現了長方形長與寬的最正確比例為1. 618,稱為黃金分割比。其倒數至今在優選法中仍得到廣泛運用。在微積分出現以前，已有許多學者開場研

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

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

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

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

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

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

11、派問題用匈牙利方法就比較方便。 組合最優化 在給定有限集的一切具備某些條件的子集中，按某種目的找出一個最優子集的一類數學規劃。又稱組合規劃。從最廣泛的意義上說，組合規劃與整數規劃這兩者的領域是一致的，都是指在有限個可供選擇的方案的組成集合中，選擇使目的函數到達極值的最優子集。 組合最優化開展的初期，研討一些比較適用的根本上屬于網絡極值方面的問題 ，如廣播網的設計 、開關電路設計、航船運輸道路的方案、任務指派、貨物裝箱方案等。自從擬陣概念進入圖論領域之后，對擬陣中的一些實際問題的研討成為組合規劃研討的新課題，并得到運用。如今運用的主要方面仍是網絡上的最優化問題，如最短路問題、最大小支撐樹問題、最

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

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

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

15、思想 可以運用最優化方法分析處理實踐問題最優化問題的數學模型普通方式最優化問題目的函數不等式約束等式約束其中最優化問題分類 經典優化問題靜態優化問題和現代優化問題動態優化問題 1、經典優化問題靜態優化問題 根據數學模型中有無約束函數分為有約束的最優化問題和無約束的最優化問題； 根據目的函數和約束函數的函數類型分類：線性最優化問題(整數規劃、規劃)、非線性最優化問題、二次規劃、多目的規劃。 2、現代優化問題動態優化問題 動態規劃與最優控制問題 組合優化問題最優解的相關定義定義.1 可行解滿足約束條(1.2)和(1.3)的x稱為可行解，也稱為可行點或允許點。定義.2 可行域全體可行解構成的集合稱為

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

17、較常見的范數P-范數：其中最常用的是2-范數，即：范數：最優化方法概述 求解 的一種算法，通常是指一種產生點列的程序。常表現為 的一種映射F，它經常滿足以下兩點要求： 1 ;2 式1實踐上常表現為 。因此通常構造映射F的關鍵就在于設計一種能從 出發，確定方向 與步長 的方法，要求滿足式2并使整個序列或子列具有收斂性。 迭代算法 選取一個初始可行點 由這個初始可行點出發，依次產生一個可行點列： 恰好是問題的一個最優解，或者該點列收斂到問題的一個最優解。可行點列的產生在處求得一個方向可行下降方向在射線上求一點：使得其中稱為步長。下降方向定義1.6下降方向：在點處，對于方向假設存在實數使得恣意的有：

18、成立，那么稱為函數在點處的一個下降方向。當具有延續的一階偏導數，令由Taylor公式：當時，有所以充分小時是在處的一個下降方向。通常稱滿足：的方向為在處的下降方向。可行方向定義1.7可行方向：知區域對于向量假設存在實數使得恣意的有：那么稱為點處關于區域的可行方向。下降方向關于區域可行，那么稱為可行下降方向。最優化問題的算法的普通迭代格式給定初始點令確定處的可行下降方向確定步長使得：令假設滿足某種終止準那么，那么停頓；否那么令轉收斂性 假設一個算法只需當初始點充分接近最優解時，產生的點列才收斂，那么稱該算法為具有部分收斂的算法。 假設對恣意的初始點，由算法產生的點列都收斂，那么稱該算法為具有全局

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

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

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

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

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

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

25、題中，可行解的集合稱為該問題的可行域。 定義2.3 在線性規劃問題的可行域中，使目的函數值到達最優最大或最小的可行解稱為該問題的最優解。相應的目的函數值稱為最優值。 凸集定義1設集合假設對于恣意兩點及實數都有：那么稱集合為凸集注：常見的凸集：空集，整個歐氏空間超平面：半空間：例1：證明超球為凸集證明：設為超球中的恣意兩點，那么有：即點屬于超球所以超球為凸集凸集的性質有限個可以改成無限凸集的交集為凸集設是凸集，是一實數，那么下面的集合是凸集：設是凸集，那么的和集是凸集注：和集和并集有很大的區別，凸集的并集未必是凸集，而凸集的和集是凸集例：表示軸上的點表示軸上的點那么表示兩個軸的一切點，它不是凸集

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

27、域。發生這種情況往往是建模時脫漏了某些約束條件所至。無解 當可行域為空集時，問題不存在可行解。發生此情況是由于模型中出現了相互矛盾的約束條件。 圖解法中解的概念與算法有關的概念可行解、最優解基、基向量、基變量基解、基可行解可行基與單純形法有關的解概念可行解、最優解滿足約束條件(1-2)，(1-3)式的解稱為線性規劃問題的可行解，其中使目的函數到達最小值的可行解稱為最優解。基、基向量、基變量基解、基可行解 基解：滿足約束方程組1-2且非基變量為0的解。 基可行解：滿足非負條件1-3的基解. 基可行解的非零分量的數目也不大于m，并且都是非負的。 可行基 對應于基可行解的基，稱為可行基。約束方程組(

28、1-2)具有基解的數目最多是 個。普通基可行解的數目要小于基解的數目。以上提到的幾種解的概念，它們之間的關系可用圖6闡明。另外還要闡明一點，基解中的非零分量的個數小于m個時，該基解是退化解。在以下討論時，假設不出現退化的情況。以上給出了線性規劃問題的解的概念和定義，它們將有助于用來分析線性規劃問題的求解過程。 可行解、基解、基可行解之間的關系圖6與算法有關的概念與內點法有關的解概念與算法有關的概念與其他算法有關的解概念與算法有關的概念與其他算法有關的解概念線性規劃的尋優方法圖解法單純形方法內點法 計算機求解分支定界法 隱枚舉法 表上作業法匈牙利法 只需二個變量的線性規劃問題普通LP特殊LP整數

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

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

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

32、解線性規劃問題(1-14)，獲得其解，它與1-13的解的關系如下：大M法到達問題1-14的最優解，且 ，這時得到的 為問題1-13的最優解。到達問題1-14的最優解，且 ，這時問題1-13無可行解。問題1-14不存在有限最優值，在單純形表中， ， 這時 問題1-13無界。問題1-14不存在有限最優值，在單純形表中， ， 這時 問題1-13無可行解。大M法用大M法求解以下問題：兩個階段法根本思想：在約束中添加人工變量 ，以構造一個單位矩陣。對添加了人工變量的線性規劃問題分兩個階段計算。 第一階段是用單純形方法消去人工變量假設能夠的話，即把人工變量 都變成非基變量，求出原來問題的一個根本可行解。消

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

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

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

36、性規劃問題的計算機軟件產品，如Lindo,Lingo或Matlab等。下面以Matlab 6.x 為背景，引見如何在Matlab中求解線性規劃。 將模型轉換成如下“規范方式： 線性規劃問題的計算機求解 在上述規范方式中，目的函數求極小，約束條件嚴厲地分為三類：不等式約束且取“ 不等號、等式約束及變量取值范圍約束。其中 線性規劃問題的計算機求解 調用時需留意以下幾點：1Matlab提供了一種機制，允許調用某個函數時提供 的參數個數少于定義該函數時所定義的參數個數。因此，在調用函數linprog傳送參數時必需按語法指定的順序對應傳送，假設短少某些參數，除非其位于參數表的尾部，否那么調用時必需以空數

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

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

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

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

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

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

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

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

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

46、上升。在內任取假設那么假設那么單峰函數：黃金分割法黃金分割法假設第一次選取的試點為那么下一步保管的區間為或兩者的時機是均等的因此我們選取試點時希望設那么另外，我們希望假設減少的區間包含原來的試點，那么該試點在下一步被利用假設保管的區我們希望原來的間為前一次的試點在這個區間內在減少的區間內成為新的我們根據這條件 來計算計算的公式為：因此我們希望：即：化簡得：假設保管區間為我們得到的結果是一致的該方法稱為黃金分割法，實踐計算取：所以黃金分割法又稱為0.618法黃金分割法每次減少區間的比例是一致的，每次將區間長度減少到原來的0.618倍 黃金分割法的算法步驟Step1給定以及令Step2Step3轉

47、Step.令轉Step.假設那么停；否那么轉Step.Step4假設那么轉Step3.黃金分割法的算法步驟Step5假設那么轉Step3.假設那么轉Step3.例1黃金分割法用黃金分割法求函數在區間上的極小點。要求最終區間長度不大于原始區間長度的0.08倍解：函數在區間上為下單峰函數，第一次迭代：縮短后區間為第二次迭代：縮短后區間為迭代次數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法為了盡快得到結果，希望區間減少的盡量小。 假設在區間只需一個試點，我們無法將區間減少。假設知道兩個試點根據的大小關系，可以得到減少的區間或者 它與0.618法的主要區別之一在于：搜索區間長度的縮短率不是采用0.618，而是采用Fibonacci數。 下面我們思索任給一個另外一種思想方式為，的單峰區間假設給定試點的個數如何使最后確定最優值的區間盡量的小。按什么方式取點，求次函數值之后，可最多將多長的原始區間長度減少為設為試點個數為最終區間長度為時、原始區間的最大能夠長度。的包含設最初兩個試點為和假設極小點在內，至多還有個試點，那么假設極小

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

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

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

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

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

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

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

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

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

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

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

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