優(yōu)化方法講稿____11.ppt

最優(yōu)化及最優(yōu)化方法 最優(yōu)化是一門應(yīng)用十分廣泛的學(xué)科 它研究在有限種或無(wú)限種可行方案中挑選最優(yōu)方案 構(gòu)造尋求最優(yōu)解的計(jì)算方法 達(dá)到最優(yōu)目標(biāo)的方案 稱為最優(yōu)方案 搜索最優(yōu)方案的方法 稱為最優(yōu)化方法 這種方法的數(shù)學(xué)理論 稱為最優(yōu)化理論 最優(yōu)化方法 也稱做運(yùn)籌學(xué)方法 是近幾十年形成的 它主要運(yùn)用數(shù)學(xué)方法研究各種系統(tǒng)的優(yōu)化途徑及方案 為決策者提供科學(xué)決策的依據(jù) 最優(yōu)化方法的研究對(duì)象及應(yīng)用 最優(yōu)化方法的主要研究對(duì)象是各種有組織系統(tǒng)的管理問題及其生產(chǎn)經(jīng)營(yíng)活動(dòng) 最優(yōu)化方法的目的在于針對(duì)所研究的系統(tǒng) 求得一個(gè)合理運(yùn)用人力 物力和財(cái)力的最佳方案 發(fā)揮和提高系統(tǒng)的效能及效益 最終達(dá)到系統(tǒng)的最優(yōu)目標(biāo) 實(shí)踐表明 隨著科學(xué)技術(shù)的日益進(jìn)步和生產(chǎn)經(jīng)營(yíng)的日益發(fā)展 最優(yōu)化方法已成為現(xiàn)代管理科學(xué)的重要理論基礎(chǔ)和不可缺少的方法 被人們廣泛地應(yīng)用到空間技術(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)設(shè)計(jì) 最優(yōu)計(jì)劃 最優(yōu)管理和最優(yōu)控制等四個(gè)方面 最優(yōu)設(shè)計(jì) 世界各國(guó)工程技術(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)計(jì)劃 現(xiàn)代國(guó)民經(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ā)展趨勢(shì)是幫助領(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)控制 主要用于對(duì)各種控制系統(tǒng)的優(yōu)化 例如 導(dǎo)彈系統(tǒng)的最優(yōu)控制 能保證用最少燃料完成飛行任務(wù) 用最短時(shí)間達(dá)到目標(biāo) 再如飛機(jī) 船舶 電力系統(tǒng)等的最優(yōu)控制 化工 冶金等工廠的最佳工況的控制 計(jì)算機(jī)接口裝置不斷完善和優(yōu)化方法的進(jìn)一步發(fā)展 還為計(jì)算機(jī)在線生產(chǎn)控制創(chuàng)造了有利條件 最優(yōu)控制的對(duì)象也將從對(duì)機(jī)械 電氣 化工等硬系統(tǒng)的控制轉(zhuǎn)向?qū)ι鷳B(tài) 環(huán)境以至社會(huì)經(jīng)濟(jì)系統(tǒng)的控制 最優(yōu)化的發(fā)展簡(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īng)用 在微積分出現(xiàn)以前 已有許多學(xué)者開始研究用數(shù)學(xué)方法解決最優(yōu)化問題 例如阿基米德證明 給定周長(zhǎng) 圓所包圍的面積為最大 這就是歐洲古代城堡幾乎都建成圓形的原因 最優(yōu)化的發(fā)展簡(jiǎn)史 但是最優(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ā)展簡(jiǎn)史 第二次世界大戰(zhàn)前后 由于軍事上的需要和科學(xué)技術(shù)和生產(chǎn)的迅速發(fā)展 許多實(shí)際的最優(yōu)化問題已經(jīng)無(wú)法用古典方法來解決 這就促進(jìn)了近代最優(yōu)化方法的產(chǎn)生 近代最優(yōu)化方法的形成和發(fā)展過程中最重要的事件有 1847年法國(guó)數(shù)學(xué)家Cauchy研究了函數(shù)值沿什么方向下降最快的問題 提出最速下降法 1939年前蘇聯(lián)數(shù)學(xué)家 B 提出了解決下料問題和運(yùn)輸問題這兩種線性規(guī)劃問題的求解方法 最優(yōu)化的發(fā)展簡(jiǎn)史 以蘇聯(lián) 康托羅維奇和美國(guó)G B 丹齊克為代表的線性規(guī)劃 以美國(guó)庫(kù)恩和塔克爾為代表的非線性規(guī)劃 以美國(guó)R 貝爾曼為代表的動(dòng)態(tài)規(guī)劃 以蘇聯(lián) 龐特里亞金為代表的極大值原理等 這些方法后來都形成體系 成為近代很活躍的學(xué)科 對(duì)促進(jìn)運(yùn)籌學(xué) 管理科學(xué) 控制論和系統(tǒng)工程等學(xué)科的發(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ī)劃 等等 幾何規(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ī)劃 利用其對(duì)偶原理 可以把高度非線性問題的求解轉(zhuǎn)化為具有線性約束的優(yōu)化問題求解 使計(jì)算大為簡(jiǎn)化 幾何規(guī)劃理論研究和算法軟件開發(fā) 發(fā)展都很快 并且在化工 機(jī)械 土木 電氣 核工程等部門的工程優(yōu)化設(shè)計(jì)和企業(yè)管理 資源分配 環(huán)境保護(hù)以及技術(shù)經(jīng)濟(jì)分析等方面都得到廣泛應(yīng)用 整數(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ù) 但對(duì)于某些具體問題 常要求解答必須是整數(shù) 例如 所求解是機(jī)器的臺(tái)數(shù) 工作的人數(shù)或裝貨的車數(shù)等 為了滿足整數(shù)的要求 初看起來似乎只要把已得的非整數(shù)解舍入化整就可以了 實(shí)際上化整后的數(shù)不見得是可行解和最優(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 戈莫里提出割平面法之后形成獨(dú)立分支的 30多年來發(fā)展出很多方法解決各種問題 解整數(shù)規(guī)劃最典型的做法是逐步生成一個(gè)相關(guān)的問題 稱它是原問題的衍生問題 對(duì)每個(gè)衍生問題又伴隨一個(gè)比它更易于求解的松弛問題 衍生問題稱為松弛問題的源問題 通過松弛問題的解來確定它的源問題的歸宿 即源問題應(yīng)被舍棄 還是再生成一個(gè)或多個(gè)它本身的衍生問題來替代它 隨即 再選擇一個(gè)尚未被舍棄的 或替代的原問題的衍生問題 重復(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ī)劃的常用方法是分枝定界法 對(duì)各種特殊問題還有一些特殊方法 例如求解指派問題用匈牙利方法就比較方便 組合最優(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)域之后 對(duì)擬陣中的一些理論問題的研究成為組合規(guī)劃研究的新課題 并得到應(yīng)用 現(xiàn)在應(yīng)用的主要方面仍是網(wǎng)絡(luò)上的最優(yōu)化問題 如最短路問題 最大 小 支撐樹問題 最優(yōu)邊無(wú)關(guān)集問題 最小截集問題 推銷員問題等 整數(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é)的對(duì)集問題 有效探險(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)用 隨機(jī)規(guī)劃 隨機(jī)規(guī)劃是對(duì)含有隨機(jī)變量的優(yōu)化問題建模的有效的工具并已有一個(gè)世紀(jì)的歷史 第一種隨機(jī)規(guī)劃是美國(guó)經(jīng)濟(jì)學(xué)家丹澤1955年提出的 康托羅維奇在這方面的貢獻(xiàn) 不在于這個(gè)新方法本身 而在于把它應(yīng)用于制定最優(yōu)計(jì)劃 是廣泛使用的期望值模型 即在期望約束條件下 使得期望收益達(dá)到最大或期望損失達(dá)到最小的優(yōu)化方法 第二種是由查納斯 A Charnes 和庫(kù)伯 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ī)劃是處理數(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)值 講授內(nèi)容 教材 最優(yōu)化方法及應(yīng)用案例 緒論 線性規(guī)劃 非線性規(guī)劃 動(dòng)態(tài)規(guī)劃 多目標(biāo)優(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ō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é)模型中有無(wú)約束函數(shù)分為有約束的最優(yōu)化問題和無(wú)約束的最優(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)解的相關(guān)定義 定義 1可行解滿足約束條 1 2 和 1 3 的x稱為可行解 也稱為可行點(diǎn)或容許點(diǎn) 定義 2可行域全體可行解構(gòu)成的集合稱為可行域 也稱為容許集 記為D 即 定義 3整體 全局 最優(yōu)解 對(duì)于一切 則稱 恒有 為最優(yōu)化 問題的整體 全局 最優(yōu)解 若 恒有 則稱 為最優(yōu)化 問題的嚴(yán)格整體 全局 最優(yōu)解 定義 4局部最優(yōu)解若 存在 的某鄰域 使得對(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ù) 兩類比較常見的范數(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ā) 確定方向與步長(zhǎng)的方法 要求滿足式 2 并使整個(gè)序列 或子列 具有收斂性 迭代算法 選取一個(gè)初始可行點(diǎn)由這個(gè)初始可行點(diǎn)出發(fā) 依次產(chǎn)生一個(gè)可行點(diǎn)列 恰好是問題的一個(gè)最優(yōu)解 或者該點(diǎn)列收斂到問題的一個(gè)最優(yōu)解 可行點(diǎn)列的產(chǎn)生 在 處求得一個(gè)方向 可行下降方向 在射線 上求一點(diǎn) 使得 其中 稱為步長(zhǎng) 下降方向 定義1 6 下降方向 在點(diǎn) 處 對(duì)于方向 若存在實(shí)數(shù) 使得任意的 有 成立 則稱 為函數(shù) 在點(diǎn) 處 的一個(gè)下降方向 當(dāng) 具有連續(xù)的一階偏導(dǎo)數(shù) 令 由Taylor公式 當(dāng) 時(shí) 有 所以 充分小時(shí) 是 在 處的一個(gè) 下降方向 通常稱滿足 的方向 為 在 處的下降方向 可行方向 定義1 7 可行方向 已知區(qū)域 對(duì)于向量 若存在實(shí)數(shù) 使得任意的 有 則稱 為 點(diǎn)處 關(guān)于區(qū)域 的可行方向 下降方向關(guān)于區(qū)域 可行 則稱為可行下降 方向 最優(yōu)化問題的算法的一般迭代格式 給定初始點(diǎn) 令 確定 處的可行下降方向 確定步長(zhǎng) 使得 令 若 滿足某種終止準(zhǔn)則 則停止 否則令 轉(zhuǎn) 收斂性 如果一個(gè)算法只有當(dāng)初始點(diǎn)充分接近最優(yōu)解時(shí) 產(chǎn)生的點(diǎn)列才收斂 則稱該算法為具有局部收斂的算法 如果對(duì)任意的初始點(diǎn) 由算法產(chǎn)生的點(diǎn)列都收斂 則稱該算法為具有全局收斂的算法 具有全局收斂性的算法才有實(shí)用意義 但對(duì)算法的局部收斂性分析 在理論上是重要的 因?yàn)樗侨质諗啃苑治龅幕A(chǔ) 收斂速度 定義1 8 設(shè)序列 收斂于 而且 若 則稱序列 為線性收斂的 稱 為收斂比 若 則稱序列 為超線性收斂的 收斂速度 定義1 9 設(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í)際問題深入研究的基礎(chǔ)上 利用有關(guān)數(shù)學(xué)的知識(shí)和概念 對(duì)自然規(guī)律的真實(shí)描述 數(shù)學(xué)描述 或模擬 實(shí)例分析1 生產(chǎn)計(jì)劃問題資源分配問題書第4 5頁(yè)例第195頁(yè)資源分配問題就是將數(shù)量一定的一種或若干種資源 例如原材料 資金 設(shè)備 設(shè)施 勞力等 恰當(dāng)?shù)胤峙浣o若干使用者或地區(qū) 從而使目標(biāo)函數(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 某城市要建設(shè)一個(gè)煤氣供應(yīng)中心 該中心向城市中個(gè)用戶 用戶位置固定 提供輸送煤氣服務(wù) 對(duì)于給定的坐標(biāo)系而言 已知第個(gè)用戶位置的坐標(biāo)為 如果輸送管道不受道路影響 即只考慮直線距離 問如何確定該中心的位置 才能使總的輸送管道最短 同時(shí)中心到第個(gè)用戶的距離必須介于和之間 非線性規(guī)劃模型 4 最短路問題 圖論極值問題 或最優(yōu)管道鋪設(shè)問題 類似問題166頁(yè) 動(dòng)態(tài)規(guī)劃模型 線性規(guī)劃 1 線性規(guī)劃模型的建立2 線性規(guī)劃模型的尋優(yōu) 線性規(guī)劃模型的建立 建立優(yōu)化模型的三大要素 1 確定決策變量 2 確定目標(biāo) 決策準(zhǔn)則 3 確定約束條件實(shí)例分析 1 生產(chǎn)計(jì)劃資源分配問題 例2 1某廠計(jì)劃在下一個(gè)生產(chǎn)周期內(nèi)生產(chǎn)甲 乙兩種產(chǎn)品 需要消耗R1 R2 和R3三種資源 例如鋼材 煤炭或設(shè)備臺(tái)時(shí)等 已知每件產(chǎn)品對(duì)這三種資源的消耗 這三種資源可供使用的量及每單位產(chǎn)品可獲得的利潤(rùn)如表2 1所示 問應(yīng)如何安排生產(chǎn)計(jì)劃 使得既能充分利用現(xiàn)有資源 又使總利潤(rùn)最大 試建立問題的數(shù)學(xué)模型 P10 11 表2 1 2 原材料的合理利用問題 P11 12 3 0 1背包問題 P12 背包問題 P13 4 運(yùn)輸問題 5 分派 指派 問題 線性的特點(diǎn) 比例性可加性 共同的特征 每一個(gè)線性規(guī)劃問題都用一組決策變量表示某一方案 這組決策變量的值就代表一個(gè)具體方案 一般這些變量取值是非負(fù)且連續(xù)的 2 要有各種資源和使用有關(guān)資源的技術(shù)數(shù)據(jù) 創(chuàng)造新價(jià)值的數(shù)據(jù) 共同的特征 繼續(xù) 3 存在可以量化的約束條件 這些約束條件可以用一組線性等式或線性不等式來表示 4 要有一個(gè)達(dá)到目標(biāo)的要求 它可用決策變量的線性函數(shù) 稱為目標(biāo)函數(shù) 來表示 按問題的不同 要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化 它們的對(duì)應(yīng)關(guān)系可用表格表示 線性規(guī)劃的一般模型形式 線性規(guī)劃模型的標(biāo)準(zhǔn)形式 線性規(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)型 續(xù) 3 當(dāng)約束條件的右端常數(shù)項(xiàng)時(shí) 只需將等式或不等式兩端同乘以即可 4 當(dāng)決策變量的取值約束為時(shí) 令 則有 5 當(dāng)決策變量的取值無(wú)任何約束時(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ī)劃問題中 可行解的集合稱為該問題的可行域 定義2 3在線性規(guī)劃問題的可行域中 使目標(biāo)函數(shù)值達(dá)到最優(yōu) 最大或最小 的可行解稱為該問題的最優(yōu)解 相應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)值 凸集 定義1 設(shè)集合 若對(duì)于任意兩點(diǎn) 及實(shí)數(shù) 都有 則稱集合 為凸集 注 常見的凸集 空集 整個(gè)歐氏空間 超平面 半空間 例1 證明超球 為凸集 證明 設(shè) 為超球中的任意兩點(diǎn) 則有 即點(diǎn) 屬于超球 所以超球?yàn)橥辜?凸集的性質(zhì) 有限個(gè) 可以改成無(wú)限 凸集的交集 為凸集 設(shè) 是凸集 是一實(shí)數(shù) 則下面的 集合是凸集 設(shè) 是凸集 則 的和集 是凸集 注 和集和并集有很大的區(qū)別 凸集的并集 未必是凸集 而凸集的和集是凸集 例 表示 軸上的點(diǎn) 表示 軸上的點(diǎn) 則 表示兩個(gè)軸的所有點(diǎn) 它不是凸集 而 凸集 推論 設(shè) 是凸集 則 也是凸集 其中 是實(shí)數(shù) 定義2 設(shè) 實(shí)數(shù) 則 稱為 的凸組合 注 凸集中任意有限個(gè)點(diǎn)的凸組合仍然在該 凸集中 極點(diǎn) 頂點(diǎn) 定義1 設(shè) 為凸集 若 中不存在 兩個(gè)相異的點(diǎn) 及某一實(shí)數(shù) 使得 則稱 為 的極點(diǎn) 例 則 上的點(diǎn)均為極點(diǎn) 證 設(shè) 若存在 及 使得 則 不等式要取等號(hào) 必須 且 容易證明 根據(jù)定義可知 為極點(diǎn) 與算法有關(guān)的概念 無(wú)窮多解圖解法中 此情況出現(xiàn)在目標(biāo)函數(shù)等值直線向優(yōu)化方向平移時(shí) 最后與可行域邊界的一條邊重合 此時(shí) 除該直線段的兩個(gè)端點(diǎn) 即可行域的兩個(gè)頂點(diǎn) 外 直線段上所有點(diǎn)的目標(biāo)函數(shù)值都達(dá)到最優(yōu) 無(wú)界解圖解法中 此情況出現(xiàn)在可行域?yàn)闊o(wú)界區(qū)域 且目標(biāo)函數(shù)等值直線向優(yōu)化方向平移時(shí) 始終無(wú)法脫離可行域 發(fā)生這種情況往往是建模時(shí)遺漏了某些約束條件所至 無(wú)解當(dāng)可行域?yàn)榭占瘯r(shí) 問題不存在可行解 發(fā)生此情況是因?yàn)槟Ｐ椭谐霈F(xiàn)了相互矛盾的約束條件 圖解法中解的概念 與算法有關(guān)的概念 可行解 最優(yōu)解基 基向量 基變量基解 基可行解可行基 與單純形法有關(guān)的解概念 可行解 最優(yōu)解 滿足約束條件 1 2 1 3 式的解稱為線性規(guī)劃問題的可行解 其中使目標(biāo)函數(shù)達(dá)到最小值的可行解稱為最優(yōu)解 基 基向量 基變量 基解 基可行解 基解 滿足約束方程組 1 2 且非基變量為0的解 基可行解 滿足非負(fù)條件 1 3 的基解 基可行解的非零分量的數(shù)目也不大于m 并且都是非負(fù)的 可行基 對(duì)應(yīng)于基可行解的基 稱為可行基 約束方程組 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ù)線性規(guī)劃問題 0 1規(guī)劃問題 平衡運(yùn)輸問題 指派問題 重要的方法 圖解法 對(duì)于只有兩個(gè)變量的線性規(guī)劃問題 可以采用在平面上作圖的方法求解 稱為圖解法 例1用圖解法求解因存在 所以必須在直角坐標(biāo)的第1象限內(nèi)作圖 求解 1 在平面直角坐標(biāo)系上畫出可行域 2 畫出目標(biāo)函數(shù)等值線 并沿其法線方向平移等值線 以求得最優(yōu)解 目標(biāo)值在 4 2 點(diǎn) 達(dá)到最大值14 目標(biāo)函數(shù) 圖1 可能出現(xiàn)的幾種情況 1 無(wú)窮多最優(yōu)解 多重最優(yōu)解 目標(biāo)函數(shù)maxz 2x1 4x2 圖3 2 無(wú)界解 圖4 3 無(wú)可行解 當(dāng)存在矛盾的約束條件時(shí) 為無(wú)可行域 如果在例1的數(shù)學(xué)模型中增加一個(gè)約束條件 該問題的可行域?yàn)榭占?即無(wú)可行解 不存在可行域 增加的約束條件 圖5 小結(jié) 1 線性規(guī)劃問題的模型特征 2 通過圖解法了解如何求解線性規(guī)劃問題 3 為求解高維線性規(guī)劃問題 必須建立的概念 線性規(guī)劃的單純形方法 線性規(guī)劃問題的幾個(gè)定理單純形法的原理初始基可行解的確定 線性規(guī)劃問題的幾個(gè)定理 定理1若線性規(guī)劃問題存在可行解 則問題的可行域是凸集 定理2線性規(guī)劃問題的基可行解對(duì)應(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) 單純形法的原理 單純形方法的基本思想從一個(gè)基可行解出發(fā) 求一個(gè)使目標(biāo)函數(shù)值有所改善的基可行解 通過不斷改進(jìn)基可行解 力圖達(dá)到最優(yōu)基可行解 它主要通過基可行解的轉(zhuǎn)換完成 基可行解的轉(zhuǎn)換考慮矩陣形式的標(biāo)準(zhǔn)形問題 式中 最優(yōu)性檢驗(yàn)和解的判別 單純形方法的計(jì)算步驟 步驟1找一個(gè)初始基可行解 常用大M法和兩階法找 步驟2解步驟3求單純形乘子 解 使用表格形式的單純形方法 使用表格形式的單純形方法 用單純形法解下列問題 初始基可行解的確定 大M法基本思想 在約束中增加人工變量 同時(shí)改變目標(biāo)函數(shù) 加上罰項(xiàng) 其中是很大的正數(shù) 這樣 在極小化目標(biāo)函數(shù)的過程中 由于大的存在 將使人工變量離基 考慮線性規(guī)劃問題 大M法 引進(jìn)人工變量 研究下列問題 用單純形法求解線性規(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 無(wú)可行解 問題 1 14 不存在有限最優(yōu)值 在單純形表中 這時(shí)問題 1 13 無(wú)界 問題 1 14 不存在有限最優(yōu)值 在單純形表中 這時(shí)問題 1 13 無(wú)可行解 大M法 用大M法求解下列問題 兩個(gè)階段法 基本思想 在約束中增加人工變量 以構(gòu)造一個(gè)單位矩陣 對(duì)添加了人工變量的線性規(guī)劃問題分兩個(gè)階段計(jì)算 第一階段是用單純形方法消去人工變量 如果可能的話 即把人工變量都變成非基變量 求出原來問題的一個(gè)基本可行解 消去人工變量的一種方法是解下列第一階段問題 兩個(gè)階段法 求解 1 16 設(shè)得到的最優(yōu)基本可行解是 此時(shí)必有下列三種情形之一 這時(shí) 1 13 無(wú)可行解 的分量都是非基變量 這時(shí)的基變量都是原來的變量 又知是 1 16 的基可行解 因此是 1 13 的一個(gè)基可行解 兩個(gè)階段法 的某些分量是基變量 這時(shí)可用主元消去法 把原來變量中的某些非基變量引進(jìn)基 替換出基變量中的人工變量 再開始兩階段法的第二階段 應(yīng)該指出 為替換出人工變量而采用的主元消去法 在主元的選擇上 并不要求遵守單純形法確定離進(jìn)基變量的規(guī)則 兩階段法的第二階段 就是從得到的基可行解出發(fā) 用單純形方法求 1 13 的最優(yōu)解 即在問題 1 16 中去掉人工變量 以第一階段最后的基變量為初始基變量開始迭代 操作上可直接在第一階段的最終單純形表基礎(chǔ)上進(jìn)行 只需在表中除去人工變量列 恢復(fù)目標(biāo)價(jià)值向量為原問題之前的狀況即可 兩個(gè)階段法 用兩階段法求解下列問題 內(nèi)點(diǎn)法 卡瑪卡 Karmarkar 算法 投影尺度法在大型問題的應(yīng)用中 顯示出能與單純形法競(jìng)爭(zhēng)的潛力不能直接用于通常形式的線性規(guī)劃問題原仿射尺度法 改進(jìn)的內(nèi)點(diǎn)法 可以直接求解標(biāo)準(zhǔn)形式的線性規(guī)劃問題 理論依據(jù) 定理2 5在仿射尺度變換下 的正卦限中的點(diǎn)仍變?yōu)檎韵拗械狞c(diǎn) 但其分量值發(fā)生變化 特別地 的像點(diǎn)為 定理2 6設(shè)為行滿秩矩陣 則向量在的零空間上的正交投影為 基本思想 先找出一個(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í) 迭代停止 計(jì)算步驟及框圖 計(jì)算步驟 P41 42 關(guān)鍵的問題是 對(duì)于任一迭代點(diǎn) 如何求得一個(gè)適當(dāng)?shù)囊苿?dòng)方向 使是一個(gè)改進(jìn)的內(nèi)點(diǎn)可行解 利用仿射尺度變換的逆變換定理2 5 2 6 可找到 計(jì)算框圖P42 例題及初始內(nèi)點(diǎn)可行解的確定 例2 10用原仿射尺度算法求解如下問題 P43 44 初始內(nèi)點(diǎn)可行解的確定 P44 方法 類似于單純形方法的大M法 線性規(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ī)求解 在上述標(biāo)準(zhǔn)形式中 目標(biāo)函數(shù)求極小 約束條件嚴(yán)格地分為三類 不等式約束且取 不等號(hà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í)必須按語(yǔ)法指定的順序?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ī)求解 寫出下列問題的Matlab調(diào)用代碼 分支定界法與隱枚舉法 解決的問題各是什么 理論依據(jù)Discuss基本思想計(jì)算步驟及框圖計(jì)算中的說明計(jì)算機(jī)求解的異同 講P62例2 13練P907 1 分支定界法的計(jì)算框圖 隱枚舉法的計(jì)算框圖 表上作業(yè)法與匈牙利法 解決的問題各是什么 理論依據(jù)Discuss基本思想計(jì)算步驟及框圖計(jì)算中的說明表上作業(yè)法是單純形法在求解運(yùn)輸問題時(shí)的一種簡(jiǎn)化方法 其實(shí)質(zhì)是單純形法 結(jié)合算法步驟講P63例2 14和P67例2 15 表上作業(yè)法的計(jì)算框圖 匈牙利法的計(jì)算框圖 第三專題非線性優(yōu)化問題 1 非線性優(yōu)化模型的建立2 非線性優(yōu)化模型的尋優(yōu) 非線性優(yōu)化模型的建立 確定決策變量確定目標(biāo) 決策準(zhǔn)則 確定約束條件 實(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ù) 通過測(cè)試獲得n組溫度與時(shí)間之間的實(shí)驗(yàn)數(shù)據(jù) 試確定參數(shù)使理論曲線盡可能地與n個(gè)測(cè)試點(diǎn)擬合 非線性規(guī)劃問題的共同特征 都是求一個(gè)目標(biāo)函數(shù)在一組約束條件下的極值問題 在目標(biāo)函數(shù)或約束條件中 至少有一個(gè)是變量的非線性函數(shù) 非線性規(guī)劃問題 一般形式 向量形式 非線性優(yōu)化問題的尋優(yōu) 相關(guān)概念及理論一維最優(yōu)化方法多維無(wú)約束最優(yōu)化方法多維有約束最優(yōu)化方法 非線性規(guī)劃的相關(guān)概念及理論 一階導(dǎo)數(shù) 二階導(dǎo)數(shù)和n元函數(shù)的Taylor公式 定義4 設(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ù) 在幾何上 表示連接 的線段 表示在點(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è) 若 在 上為嚴(yán)格 凸函數(shù) 則 在 上為嚴(yán)格凸函數(shù) 該定理的幾何意義是 凸函數(shù)上任意兩點(diǎn)之 間的部分是一段向下凸的弧 一階條件 定理2 1 設(shè)在凸集 上 可微 則 在 上為凸函數(shù)的充要條件是對(duì)任意的 都有 定理2 2 嚴(yán)格凸函數(shù) 充要條件 二階條件 定理3 設(shè)在開凸集 內(nèi) 二階可微 則 1 是 內(nèi)的凸函數(shù)的充要條件為 在 內(nèi)任一點(diǎn) 處 的海色矩陣 半正定 其中 二階條件 定理3 設(shè)在開凸集 內(nèi) 2 若在 內(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 若 是凸集 上的嚴(yán)格凸函數(shù) 且凸規(guī)劃問題 整體極小點(diǎn)存在 則整體極小點(diǎn)是唯一的 非線性規(guī)劃的最優(yōu)性條件 最優(yōu)性條件 是指非線性規(guī)劃模型的最優(yōu)解所要滿足的必要和充分條件 無(wú)約束最優(yōu)性條件約束最優(yōu)性條件 無(wú)約束最優(yōu)性條件 一 單 元函數(shù)的最優(yōu)性條件 若 為 的局部極小點(diǎn) 則 若 則 為 的嚴(yán)格局部極小點(diǎn) 若 為 的局部極小點(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ù)的二階充分條件 定理2 若在 內(nèi) 二階連續(xù)可導(dǎo) 且 正定 則 為嚴(yán)格局部 極小點(diǎn) 注 如果 負(fù)定 則 為嚴(yán)格局部極大點(diǎn) 二階必要條件和充要條件 定理3 若 為 的局部極小點(diǎn) 且在 內(nèi) 二階連續(xù)可導(dǎo) 則 半正定 定理4 設(shè) 在 上是凸函數(shù)且有一階連續(xù) 偏導(dǎo)數(shù) 則 為 的整體極小點(diǎn)的充要 條件是 例1 利用極值條件解下列問題 解 令 即 得到駐點(diǎn) 函數(shù) 的海色陣 由此 在點(diǎn) 處的海色陣依次為 由于矩陣 不定 則 不是極小點(diǎn) 負(fù)定 則 不是極小點(diǎn) 實(shí)際上它是極大點(diǎn) 正定 則 是局部極小點(diǎn) 約束最優(yōu)性條件 p133 p136 定義1 有效約束 若 中的一個(gè)可行點(diǎn) 使得 某個(gè)不等式約束 變成等式 即 則 稱為關(guān)于 的有效 積極 約束 非有效約束 若對(duì) 則 稱為 關(guān)于 的非有效 無(wú)效 約束 有效集 定義2 錐 的子集 如果它關(guān)于正的數(shù)乘運(yùn)算 是封閉的 如果錐也是凸集 則稱為凸錐 凸錐關(guān)于加法和正的數(shù)乘運(yùn)算是封閉的 一階必要條件 定理3 5 Kuhn Tucker一階必要條件 1951 設(shè) 在 K T條件 一階必要條件 定理1 Kuhn Tucker一階必要條件 互補(bǔ)松弛條件 例2 驗(yàn)證是否滿足Kuhn Tucker條件 試驗(yàn)證最優(yōu)點(diǎn) 為KT點(diǎn) 解 令 所以 即 所以 是KT點(diǎn) Lagrange函數(shù)及K T條件 在一定凸性下的最優(yōu)性的充分條件 一維最優(yōu)化方法 線性搜索方法 已知 并且求出了 處的可行下降方向 從 出發(fā) 沿方向 求目標(biāo)函數(shù)的最優(yōu)解 或者選取 使得 問題描述 即 設(shè)其最優(yōu)解為 叫精確步長(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)單的確定初始搜索區(qū)間方法 基本思想 是從一點(diǎn)出發(fā) 按一定步長(zhǎng) 試圖確定出函數(shù)值呈現(xiàn) 高 低 高 的三點(diǎn) 即這里 具體地說 就是給出初始點(diǎn) 初始步長(zhǎng) 若 則下一步從新點(diǎn)出發(fā) 加大步長(zhǎng) 再向前搜索 直到目標(biāo)函數(shù)上升為止 若 則下一步仍以為出發(fā)點(diǎn) 沿反方向同樣搜索 直到目標(biāo)函數(shù)上升就停止 這樣便得到一個(gè)搜索區(qū)間 這種方法叫進(jìn)退法 計(jì)算步驟 見P96計(jì)算框圖 見P97 黃金分割法 0 618法 基本思想 它通過對(duì)試探點(diǎn)的函數(shù)值進(jìn)行比較 使得包含極小點(diǎn)的區(qū)間不斷縮短 當(dāng)區(qū)間長(zhǎng)度小到精度范圍之內(nèi)時(shí) 可以粗略地認(rèn)為區(qū)間上各點(diǎn)的函數(shù)值均接近于極小值 設(shè) 在 上為下單峰函數(shù) 即有唯一 的極小點(diǎn) 在 左邊 嚴(yán)格下降 在 右邊 嚴(yán)格上升 在 內(nèi)任取 若 則 若 則 單峰函數(shù) 黃金分割法 黃金分割法 若第一次選取的試點(diǎn)為 則下一步保留 的區(qū)間為 或 兩者的機(jī)會(huì)是均等的 因此我們選取試點(diǎn)時(shí)希望 設(shè) 則 另外 我們希望如果縮小的區(qū)間包含原來的 試點(diǎn) 則該試點(diǎn)在下一步被利用 若保留的區(qū) 我們希望原來的 間為 前一次的試點(diǎn) 在這個(gè)區(qū)間內(nèi) 在縮小的區(qū)間內(nèi)成為 新的 我們根據(jù)這條件來計(jì)算 計(jì)算 的公式為 因此我們希望 即 化簡(jiǎn)得 若保留區(qū)間為 我們得到的結(jié)果是 一致的 該方法稱為黃金分割法 實(shí)際計(jì)算取 所以黃金分割法又稱為0 618法 黃金分割法每次縮小區(qū)間的比例是一致的 每次將區(qū)間長(zhǎng)度縮小到原來的0 618倍 黃金分割法的算法步驟 Step1 給定 以及 令 Step2 Step3 轉(zhuǎn)Step 令 轉(zhuǎn)Step 若 則 停 否則 轉(zhuǎn)Step Step4 若 則 轉(zhuǎn)Step3 黃金分割法的算法步驟 Step5 若 則 轉(zhuǎn)Step3 若 則 轉(zhuǎn)Step3 例1 黃金分割法 用黃金分割法求函數(shù) 在區(qū)間 上的極小點(diǎn) 要求最終區(qū)間長(zhǎng)度不大于 原始區(qū)間長(zhǎng)度的0 08倍 解 函數(shù) 在區(qū)間 上為下單峰函數(shù) 第一次迭代 縮短后區(qū)間為 第二次迭代 縮短后區(qū)間為 Fibonacci法 為了盡快得到結(jié)果 希望區(qū)間縮小的盡量小 如果在區(qū)間只有一個(gè)試點(diǎn) 我們無(wú)法將區(qū)間縮小 如果知道兩個(gè)試點(diǎn) 根據(jù) 的大 小關(guān)系 可以得到縮小的區(qū)間 或者 它與0 618法的主要區(qū)別之一在于 搜索區(qū)間長(zhǎng)度的縮短率不是采用0 618 而是采用Fibonacci數(shù) 下面我們考慮任給一個(gè) 另外一種思維方式為 的單峰區(qū)間 如果給定試點(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)為 和 若極小點(diǎn)在 內(nèi) 至多還有 個(gè)試點(diǎn) 則 若極小點(diǎn)在 內(nèi) 包括 在內(nèi)可以有 個(gè)試點(diǎn) 則 因此 如果我們采取合適的技巧 可以使得 另外 顯然 從而 滿足差分方程 此為Fibonacci數(shù)列 一般寫為 若原始區(qū)間為 要求最終區(qū)間長(zhǎng)度 則 由此可確定 區(qū)間縮短之后與 之前的比依次為 確定之后 最初兩個(gè)試點(diǎn)分別為 關(guān)于 對(duì)稱 由于 上述過程完成了依次迭代 新區(qū)間仍記為 若已經(jīng)進(jìn)行了 次迭代 第 次迭代時(shí) 還有 個(gè)試點(diǎn) 包括已經(jīng)計(jì)算過的函數(shù)值的一個(gè) 注意 若在一定的誤差范圍內(nèi) 則認(rèn)為 在 內(nèi) 最后的兩個(gè)試點(diǎn)的選取方式 例3 1 Fibonacci法 用Fibonacci法求函數(shù) 在區(qū)間 上的極小點(diǎn) 要求最終區(qū)間長(zhǎng)度不大于 原始區(qū)間長(zhǎng)度的0 08倍 解 函數(shù) 在區(qū)間 上為下單峰函數(shù) 由 可知 應(yīng)取 Fibonacci算法與0 618法幾乎完全相同 第一次迭代 縮短后區(qū)間為 第二次迭代 縮短后區(qū)間為 第三次迭代 縮短后區(qū)間為 第四次迭代 縮短后區(qū)間為 第五次迭代 取最優(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法的缺點(diǎn) 搜索前先要計(jì)算搜索的步數(shù) 每次搜索試點(diǎn)計(jì)算的公式不一致 1 黃金分割法 0 618法 與Fibonacci法 的區(qū)別與聯(lián)系是什么 2 請(qǐng)讀者自己寫出算法和程序 二分法 若 的導(dǎo)數(shù)存在且容易計(jì)算 則線性搜索 的速度可以得到提高 下面的二分法每次將 區(qū)間縮小至原來的二分之一 設(shè) 為下單峰函數(shù) 若 在 內(nèi) 具有連續(xù)的一階導(dǎo)數(shù) 且 取 若 則 為極小點(diǎn) 若 則以 代替 若 則以 代替 二分法每次迭代都將區(qū)間縮短一半 故二分法的收斂速度也是線性的 收斂比為1 2 計(jì)算步驟 見P105計(jì)算框圖 見P106 多維無(wú)約束最優(yōu)化方法 最速下降法 阻尼 牛頓法共軛梯度法 問題提出 問題 在點(diǎn) 處 沿什么方向 下降最快 分析 考查 顯然當(dāng) 時(shí) 取極小值 因此 結(jié)論 負(fù)梯度方向使 下降最快 亦即最速 下降方向 最速下降法 最速下降法算法 Step1 給出 Step2 計(jì)算 如果 停 Step3 計(jì)算下降方向 Step4 計(jì)算步長(zhǎng)因子 Step5 令 轉(zhuǎn)步 問題 設(shè) 是正定二次函數(shù) 由精確的線搜索確定的 特別當(dāng) 例1 用最速下降法求解 解 分析 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ì)一般的 目標(biāo)函數(shù) 它也整體收斂 最速下降法缺點(diǎn) 最速下降法是線性收斂的 并且有時(shí)是 很慢的線性收斂 原因 僅反映 在 處 的局部性質(zhì) 相繼兩次迭代中搜索 方向是正交的 小結(jié) 最速下降法是基本算法之一 而非有效 的實(shí)用算法 最速下降法的本質(zhì)是用線性函數(shù)來近似 目標(biāo)函數(shù) 要想得到快速算法 需要考 慮對(duì)目標(biāo)函數(shù)的高階逼近 基本思想 利用目標(biāo)函數(shù) 在點(diǎn) 處的二階Taylor 展開式去近似目標(biāo)函數(shù) 用二次函數(shù)的極小點(diǎn) 去逼近目標(biāo)函數(shù)的極小點(diǎn) 牛頓法 算法構(gòu)造 問題 設(shè) 二階連續(xù)可微 海色陣 正定 如何從 因?yàn)?正定 則 有唯一極小點(diǎn) 用這個(gè) 極小點(diǎn)作為 所以要求 即 因此 這就是牛頓法迭代公式 注 這里 牛頓法算法 Step1 給出 Step2 計(jì)算 如果 停 Step3 否則計(jì)算 Step4 令 轉(zhuǎn)步 并且求解方程 得出 例1 用牛頓法求解 解 牛頓法收斂定理 定理1 設(shè) 二次連續(xù)可微 是 的局 部極小點(diǎn) 正定 假定 的海色陣 滿足Lipschitz條件 即存在 使得對(duì)于所有 有 其中 是海色陣 的 元素 則當(dāng) 充分靠近 時(shí) 對(duì)于一切 牛頓迭代有意義 迭代序列 收斂到 并且具有二階收斂速度 牛頓法優(yōu)點(diǎn) 1 2 對(duì)正定二次函數(shù) 迭代一次就可以得到 極小點(diǎn) 如果 正定且初始點(diǎn)選取合適 算法 二階收斂 牛頓法缺點(diǎn) 1 2 對(duì)多數(shù)問題算法不是整體收斂的 每次都需要計(jì)算 計(jì)算量大 3 每次都需要解 方程組有時(shí)奇異或病態(tài)的 無(wú)法確定 或 不是下降方向 4 收斂到鞍點(diǎn)或極大點(diǎn)的可能性并不小 阻尼牛頓法算法 Step1 給出 Step2 計(jì)算 如果 停 Step3 否則計(jì)算 Step4 沿 并且求解方程 得出 進(jìn)行線搜索 得出 Step5 令 轉(zhuǎn)Step2 阻尼牛頓法收斂定理 定理2 設(shè) 二階連續(xù)可微 又設(shè)對(duì)任意的 存在常數(shù) 使得 在 上滿足 則在精確線搜索條件下 阻尼牛頓法產(chǎn)生的點(diǎn)列 滿足 1 當(dāng) 是有限點(diǎn)列時(shí) 其最后一個(gè)點(diǎn)為 的唯一極小點(diǎn) 2 當(dāng) 是無(wú)限點(diǎn)列時(shí) 收斂到 的唯一極小點(diǎn) 阻尼牛頓法收斂定理 定理3 設(shè) 二階連續(xù)可微 又設(shè)對(duì)任意的 存在常數(shù) 使得 在 上滿足 則在Wolfe不精確線搜索條件下 阻尼牛頓法 產(chǎn)生的點(diǎn)列 滿足 且 收斂到 的唯一極小點(diǎn) 例2 用阻尼牛頓法求解 解 顯然 不是正定的 但 于是 沿方向 進(jìn)行線搜索 得其極小點(diǎn) 從而迭代不能繼續(xù)下去 帶保護(hù)的牛頓法算法 給出 Step1 若 為奇異的 轉(zhuǎn)Step8 否則 Step2 令 Step3 若 為奇異的 轉(zhuǎn)Step8 否則 則轉(zhuǎn)Step8 否則 Step4 若 則轉(zhuǎn)Step9 否則 Step5 沿方向 進(jìn)行線搜索 求出 并令 Step6 若 停 Step7 令 轉(zhuǎn)Step1 Step8 令 轉(zhuǎn)Step5 Step9 令 轉(zhuǎn)Step5 例3 用帶保護(hù)的牛頓法求解 解 顯然 不是正定的 但 于是 因?yàn)?故令 沿 進(jìn)行線搜索得 第二次迭代 而 使 故令 沿 進(jìn)行線搜索 得出 于是 此時(shí) 問題1 如何建立有效的算法 從二次模型到一般模型 問題2 什么樣的算法有效呢 二次終止性 經(jīng)過有限次迭代必達(dá)到極小點(diǎn)的性質(zhì) 共軛梯度法 算法特點(diǎn) 建立在二次模型上 具有二次終止性 有效的算法 克服了最速下降法的慢 收斂性 又避免了牛頓法的計(jì)算量大和局部收 性的缺點(diǎn) 算法簡(jiǎn)單 易于編程 需存儲(chǔ)空間小等 優(yōu)點(diǎn) 是求解大規(guī)模問題的主要方法 共軛方向及其性質(zhì) 定義1 設(shè) 是 中任一組 非零向量 如果 則稱 是關(guān)于 共軛的 注 若 則是正交的 因此共軛是 正交的推廣 定理1 設(shè) 為 階正定陣 非零向量組 關(guān)于 共軛 則必線性無(wú)關(guān) 推論1 設(shè) 為 階正定陣 非零向量組 關(guān)于 共軛 則向量構(gòu)成 的一組基 推論2 設(shè) 為 階正定陣 非零向量組 關(guān)于 共軛 若向量 與 關(guān)于 共軛 則 求的極小點(diǎn)的方法共軛方向法算法 Step1 給出 計(jì)算 和初始下降方向 Step2 如果 停止迭代 Step3 計(jì)算 使得 使得 轉(zhuǎn)Step2 共軛方向法基本定理 定義2 設(shè) 維向量組 線性無(wú)關(guān) 向量集合 為 與 生成的 維超平面 引理1 設(shè) 是連續(xù)可微的嚴(yán)格凸函數(shù) 維向量組 線性無(wú)關(guān) 則 是 在 上 唯一極小點(diǎn)的充要條件是 定理2 設(shè) 為 階正定陣 向量組 關(guān)于 共軛 對(duì)正定二次函數(shù) 由任意 開始 依次進(jìn)行 次精確線搜索 則 是 在 上的極小點(diǎn) 推論 當(dāng) 時(shí) 為正定二次函數(shù)在 上的極小點(diǎn) 共軛梯度法 記 左乘 并使 得 Hestenes Stiefel公式 取 是一種特殊的共軛方向法 共軛梯度法基本性質(zhì) 定理3 對(duì)于正定二次函數(shù) 采用精確線搜索 的共軛梯度法在 步后終止 且對(duì) 成立下列關(guān)系式 共軛性 正交性 下降條件 系數(shù)的其他形式 FR公式 1964 2 PRP公式 1969 FR共軛梯度法算法 Step1 給出 Step2 如果 停 Step5 轉(zhuǎn)Step2 計(jì)算 Step4 Step3 由精確線搜索求 計(jì)算 例4 用FR共軛梯度法求解 解 化成 形式 1 2 例5 用FR共軛梯度法求解 解 化成 形式 1 2 注意 FR方法中初始搜索方向必須取最速下降方向 才滿足二次終止性 FR共軛梯度法收斂定理 定理4 假定 在有界水平集 上連續(xù)可微 且有下界 那么采用精確線搜索下的 FR共軛梯度法產(chǎn)生的點(diǎn)列 至少有一個(gè)聚點(diǎn) 是駐點(diǎn) 即 1 當(dāng) 是有窮點(diǎn)列時(shí) 其最后一個(gè)點(diǎn)是 的駐點(diǎn) 2 當(dāng) 是無(wú)窮點(diǎn)列時(shí) 它必有聚點(diǎn) 且任一 聚點(diǎn)都是 的駐點(diǎn) 再開始FR共軛梯度法算法 Step1 給出 Step2 計(jì)算 如果 停 Step4 否則 S