最優(yōu)化問題數(shù)學模型

1、2021/6/161最優(yōu)化模型最優(yōu)化模型一、最優(yōu)化模型的概述一、最優(yōu)化模型的概述二、最優(yōu)化模型的分類二、最優(yōu)化模型的分類三、最優(yōu)化模型的建立及求解三、最優(yōu)化模型的建立及求解四、最優(yōu)化模型的評價分析四、最優(yōu)化模型的評價分析2021/6/162 數(shù)學家對最優(yōu)化問題的研究已經(jīng)有很多年的數(shù)學家對最優(yōu)化問題的研究已經(jīng)有很多年的歷史。歷史。 以前解決最優(yōu)化問題的數(shù)學方法只限于古典以前解決最優(yōu)化問題的數(shù)學方法只限于古典求導方法和變分法，拉格朗日（求導方法和變分法，拉格朗日（LagrangeLagrange）乘數(shù)）乘數(shù)法解決等式約束下的條件極值問題。法解決等式約束下的條件極值問題。 計算機技術的出現(xiàn)，使得數(shù)學

2、家研究出了許計算機技術的出現(xiàn)，使得數(shù)學家研究出了許多最優(yōu)化方法和算法用以解決以前難以解決的問多最優(yōu)化方法和算法用以解決以前難以解決的問題。題。一、最優(yōu)化模型的概述一、最優(yōu)化模型的概述 解決最優(yōu)生產(chǎn)計劃、最優(yōu)設計、最優(yōu)策略解決最優(yōu)生產(chǎn)計劃、最優(yōu)設計、最優(yōu)策略.2021/6/163 運用最優(yōu)化方法解決最優(yōu)化問題的一般方運用最優(yōu)化方法解決最優(yōu)化問題的一般方法步驟如下：法步驟如下：前期分析：分析問題，找出要解決的目標，約束條件，前期分析：分析問題，找出要解決的目標，約束條件，并確立最優(yōu)化的目標。并確立最優(yōu)化的目標。定義變量，建立最優(yōu)化問題的數(shù)學模型，列出目標函定義變量，建立最優(yōu)化問題的數(shù)學模型，列出目

3、標函數(shù)和約束條件。數(shù)和約束條件。針對建立的模型，選擇合適的求解方法或數(shù)學軟件。針對建立的模型，選擇合適的求解方法或數(shù)學軟件。編寫程序，利用計算機求解。編寫程序，利用計算機求解。對結果進行分析，討論諸如：結果的合理性、正確性，對結果進行分析，討論諸如：結果的合理性、正確性，算法的收斂性，模型的適用性和通用性，算法效率與算法的收斂性，模型的適用性和通用性，算法效率與誤差等。誤差等。2021/6/164 最優(yōu)化模型分類方法有很多，可按變量、約最優(yōu)化模型分類方法有很多，可按變量、約束條件、目標函數(shù)個數(shù)、目標函數(shù)和約束條件的束條件、目標函數(shù)個數(shù)、目標函數(shù)和約束條件的是否線性是否依賴時間等分類。是否線性是

4、否依賴時間等分類。 根據(jù)目標函數(shù)，約束條件的特點將最優(yōu)化模根據(jù)目標函數(shù)，約束條件的特點將最優(yōu)化模型包含的主要內(nèi)容大致如下劃分：型包含的主要內(nèi)容大致如下劃分： 線性規(guī)劃線性規(guī)劃 整數(shù)規(guī)劃整數(shù)規(guī)劃 非線性規(guī)劃非線性規(guī)劃 多目標規(guī)劃多目標規(guī)劃 動態(tài)動態(tài)規(guī)劃規(guī)劃 對策論對策論二、最優(yōu)化模型的分類二、最優(yōu)化模型的分類2021/6/165最優(yōu)化模型的求解方法分類最優(yōu)化模型的求解方法分類圖克定理庫恩極值原理有約束變分法微分法無約束解析法-. 1. 5. 4網(wǎng)絡優(yōu)化方法多目標優(yōu)化法隨機搜索法單純形法方向加速法步長加速法坐標輪換法多維搜索法插值法黃金分割法裴波那契法一維搜索法數(shù)值算法. 2復形法法法化有為無梯度

5、法梯度投影法可行方向法有約束梯度法變尺度法共軛梯度法擬牛頓法最速下降法無約束梯度法梯度算法SWIFTSUMT. 32021/6/166最優(yōu)化數(shù)學模型形式最優(yōu)化數(shù)學模型形式 min( )xf x. .( )0,1,2,.,( )0,1,2,.,iistg ximh xin 其中，極大值問題可以轉(zhuǎn)化為極小值問題來其中，極大值問題可以轉(zhuǎn)化為極小值問題來進行求解。如求：進行求解。如求：max( )xf x 可以轉(zhuǎn)化為：可以轉(zhuǎn)化為：min( )xf x三、最優(yōu)化模型的建立三、最優(yōu)化模型的建立目標：求函數(shù)極值或最值，求取得極值時變量的取值。目標：求函數(shù)極值或最值，求取得極值時變量的取值。2021/6/16

6、7問題問題：某工廠在計劃期內(nèi)要安排生產(chǎn)：某工廠在計劃期內(nèi)要安排生產(chǎn)I、II兩種產(chǎn)品，已兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設備臺時及知生產(chǎn)單位產(chǎn)品所需的設備臺時及A、B兩種原材料的消兩種原材料的消耗，如下表所示耗，如下表所示 12kg40原材料原材料B16kg04原材料原材料A8臺時臺時21設備設備III該工廠每生產(chǎn)一件產(chǎn)品該工廠每生產(chǎn)一件產(chǎn)品I可獲利可獲利2元，每生產(chǎn)一件產(chǎn)品元，每生產(chǎn)一件產(chǎn)品II可獲利可獲利3元。問應如何安排計劃使該工廠獲利最多？元。問應如何安排計劃使該工廠獲利最多？ 2021/6/168解解：該工廠生產(chǎn)產(chǎn)品：該工廠生產(chǎn)產(chǎn)品I x1件，生產(chǎn)產(chǎn)品件，生產(chǎn)產(chǎn)品II x2件，件，我們

7、可建立如下數(shù)學模型：我們可建立如下數(shù)學模型：2132maxxxz0,12416482212121xxxxxxs.t. 2, 41421xxz2021/6/169 最優(yōu)化問題中的所有變量均為整數(shù)時，這類最優(yōu)化問題中的所有變量均為整數(shù)時，這類問題稱為整數(shù)規(guī)劃問題。問題稱為整數(shù)規(guī)劃問題。 整數(shù)規(guī)劃可分為線性整數(shù)規(guī)劃和非線性整數(shù)整數(shù)規(guī)劃可分為線性整數(shù)規(guī)劃和非線性整數(shù)規(guī)劃規(guī)劃 ，以及混合整數(shù)規(guī)劃等。，以及混合整數(shù)規(guī)劃等。 如果決策變量的取值要么為如果決策變量的取值要么為0 0，要么為，要么為1 1，則，則這樣的規(guī)劃問題稱為這樣的規(guī)劃問題稱為0 01 1規(guī)劃。規(guī)劃。2021/6/1610問題：問題：某班級

8、準備從某班級準備從5名名游泳隊員中選擇游泳隊員中選擇4人人組成接力隊，組成接力隊，參加學校的參加學校的4*100m混合泳接力比賽?；旌嫌窘恿Ρ荣?。5名隊員名隊員4種泳姿種泳姿的百的百米平均成績?nèi)绫砻灼骄煽內(nèi)绫?-1，問應如何選拔隊員組成接力隊？，問應如何選拔隊員組成接力隊？隊員隊員甲甲已已丙丙丁丁戊戊蝶泳蝶泳仰泳仰泳蛙泳蛙泳自由泳自由泳66.866.8秒秒57.257.27878707067.467.475.675.66666878758.658.666.466.4535367.867.874.274.2717184.684.659.459.469.669.657.257.283.883.8

9、62.462.4表表2-12-12021/6/1611問題分析：問題分析：記甲、乙、丙、丁、戊分別為記甲、乙、丙、丁、戊分別為i i=1,2,3,4,5; =1,2,3,4,5; 記泳姿記泳姿j j=1,2,3,4.=1,2,3,4.記隊員記隊員 i i 的第的第 j j 種泳姿的百米最好種泳姿的百米最好成績?yōu)槌煽優(yōu)閏_c_ijij(s),(s),則表則表2-12-1可以表示成表可以表示成表2-2.2-2.c_iji=1i=2i=3i=4i=5j=1j=2j=3j=466.866.857.257.27878707067.467.475.675.66666878758.658.666.466.4

10、535367.867.874.274.2717184.684.659.459.469.669.657.257.283.883.862.462.4表表2-22-22021/6/1612 決策變量：決策變量：引入引入0-1變量變量 ，若選擇隊員，若選擇隊員i參加泳姿參加泳姿j的的比賽比賽, 記，記， ，否則記，否則記 。 目標函數(shù)：目標函數(shù)：當隊員當隊員i入選泳姿入選泳姿j時，時， 表示該隊員的成表示該隊員的成績，否則績，否則 。于是接力隊的成績可表示為。于是接力隊的成績可表示為 約束條件：約束條件：根據(jù)接力隊要求，根據(jù)接力隊要求， 滿足約束條件滿足約束條件a. 每人最多只能入選每人最多只能入選4

11、種泳姿之一，即種泳姿之一，即b. 每種泳姿必須有每種泳姿必須有1人而且只能有一人入選，即人而且只能有一人入選，即ijx0ijx1ijx. 151iijx. 141jijxijx.4151jiijijxcf0ijijxcijijxc2021/6/1613 綜上所述，這個問題的優(yōu)化模型可寫作：綜上所述，這個問題的優(yōu)化模型可寫作：.1 , 0ijx. 4 , 3 , 2 , 1, 151jxiij. 5 , 4 , 3 , 2 , 1, 1. .41ixtsjij4151minjiijijxcf2021/6/1614非線性規(guī)劃問題的一般數(shù)學模型：非線性規(guī)劃問題的一般數(shù)學模型：其中，其中， ， 為目標

12、函數(shù)，為目標函數(shù)， 為約束函數(shù)，這些函數(shù)中至少有為約束函數(shù)，這些函數(shù)中至少有一個是非線性函數(shù)。一個是非線性函數(shù)。min( ). .( )0,1,2,( )0,1,2, .ijf xstg ximh xjlnEx)(xf)(),(xhxgji2021/6/1615應用實例：應用實例： 供應與選址供應與選址 某公司有某公司有6個建筑工地要開工，每個工地的位置（用平面坐標系個建筑工地要開工，每個工地的位置（用平面坐標系a，b表示，距離單位：表示，距離單位：km）及水泥日用量）及水泥日用量d(t)由下表給出目前有由下表給出目前有兩個臨時料場位于兩個臨時料場位于A(5,1)，B(2,7)，日儲量，日儲量

13、各有各有20t假設從料場到假設從料場到工地之間均有直線道路相連工地之間均有直線道路相連 （1）試制定每天的供應計劃，即從）試制定每天的供應計劃，即從A，B兩料場兩料場分別向各工地運分別向各工地運送多少水泥，可使總的送多少水泥，可使總的噸千米數(shù)最小噸千米數(shù)最小 （2）為了進一步減少噸千米數(shù)，打算舍棄兩個臨時料場，改建兩）為了進一步減少噸千米數(shù)，打算舍棄兩個臨時料場，改建兩個新的，日儲量各為個新的，日儲量各為20t，問應建在何處，節(jié)省的噸千米數(shù)有多大？，問應建在何處，節(jié)省的噸千米數(shù)有多大？2021/6/1616建立模型建立模型 記工地的位置為記工地的位置為(ai，bi)，水泥日用量為，水泥日用量為

14、di，i=1,6;料場位置為料場位置為(xj，yj)，日儲量為，日儲量為ej，j=1,2；料場；料場j向工地向工地i的運送量為的運送量為Xij當用臨時料場時決策變量為：當用臨時料場時決策變量為：Xij，當不用臨時料場時決策變量為：當不用臨時料場時決策變量為：Xij，xj，yj2021/6/1617 事實上，客觀世界中的大多問題都是非線性的，給事實上，客觀世界中的大多問題都是非線性的，給予線性化處理是近似的，是在作了科學的假設和簡化后予線性化處理是近似的，是在作了科學的假設和簡化后得到的得到的. . 另一方面，有一些是不能進行線性化處理的，另一方面，有一些是不能進行線性化處理的，否則將嚴重影響模

15、型對實際問題近似的可依賴型否則將嚴重影響模型對實際問題近似的可依賴型. . 由于非線性規(guī)劃問題在理論分析和計算上通常是很由于非線性規(guī)劃問題在理論分析和計算上通常是很困難的，也不能像線性規(guī)劃那樣給出簡潔的結果形式和困難的，也不能像線性規(guī)劃那樣給出簡潔的結果形式和全面透徹的結論全面透徹的結論. . 所以，在數(shù)學建模時，要進行認真的所以，在數(shù)學建模時，要進行認真的分析，對實際問題進行合理的假設、簡化，首先考慮用分析，對實際問題進行合理的假設、簡化，首先考慮用線性規(guī)劃模型，線性規(guī)劃模型，若線性近似誤差較大時若線性近似誤差較大時，則考慮用非線，則考慮用非線性規(guī)劃性規(guī)劃. .2021/6/1618 在約在

16、約1萬米的高空的某邊長為萬米的高空的某邊長為160km的正方的正方形區(qū)域內(nèi)，經(jīng)常有若干架飛機作水平飛行，區(qū)形區(qū)域內(nèi)，經(jīng)常有若干架飛機作水平飛行，區(qū)域內(nèi)每架飛機的位置和速度向量均由計算機記域內(nèi)每架飛機的位置和速度向量均由計算機記錄其數(shù)據(jù)，以便進行飛行管理。當一架欲進入錄其數(shù)據(jù)，以便進行飛行管理。當一架欲進入該區(qū)域的飛機到達區(qū)域邊緣時，計算機記錄其該區(qū)域的飛機到達區(qū)域邊緣時，計算機記錄其數(shù)據(jù)后，要立即計算并判斷是否會發(fā)生碰撞。數(shù)據(jù)后，要立即計算并判斷是否會發(fā)生碰撞。若會發(fā)生碰撞，則應計算若會發(fā)生碰撞，則應計算如何調(diào)整如何調(diào)整各架飛機各架飛機（包括新進入的飛機）飛行的方向角，以避免（包括新進入的飛機

17、）飛行的方向角，以避免碰撞，且使飛機的調(diào)整的幅度盡量小，碰撞，且使飛機的調(diào)整的幅度盡量小，例例1 1995年全國數(shù)學建模年全國數(shù)學建模A題：飛行管理問題題：飛行管理問題例題講解例題講解2021/6/1619該題比較有意思的一句話是：該題比較有意思的一句話是： “使調(diào)整弧度最小使調(diào)整弧度最小”開放性的一句話，沒有限制得很死，較靈活，開放性的一句話，沒有限制得很死，較靈活，給參賽者的創(chuàng)新空間比較大一些，使得構建模型給參賽者的創(chuàng)新空間比較大一些，使得構建模型的目標函數(shù)表現(xiàn)形式很多，再加上模型求解方法的目標函數(shù)表現(xiàn)形式很多，再加上模型求解方法（算法）的多樣性，從而可以呈現(xiàn)出五花八門的（算法）的多樣性，

18、從而可以呈現(xiàn)出五花八門的論文。論文。2021/6/1620 不碰撞的標準為任意兩架飛機的距離大于不碰撞的標準為任意兩架飛機的距離大于8km;假設條件：假設條件：30 飛機飛行的方向角調(diào)整幅度不應超過飛機飛行的方向角調(diào)整幅度不應超過 ； （因飛機飛行的速度變化不大）所有飛機的飛行（因飛機飛行的速度變化不大）所有飛機的飛行 速度速度 v 均為均為800km/h;有時需要通過查閱文獻、資料給出合理假設有時需要通過查閱文獻、資料給出合理假設注：注：2021/6/1621 進入該區(qū)域的飛機在到達區(qū)域邊緣時，與區(qū)域內(nèi)進入該區(qū)域的飛機在到達區(qū)域邊緣時，與區(qū)域內(nèi) 飛機的距離應在飛機的距離應在60km以上；以上

19、； 最多需考慮六架飛機；最多需考慮六架飛機； 不必考慮飛機離開此區(qū)域后的狀況。不必考慮飛機離開此區(qū)域后的狀況。根據(jù)當年競賽題目給出的數(shù)據(jù)，可以驗證根據(jù)當年競賽題目給出的數(shù)據(jù)，可以驗證新進入的飛機與區(qū)域內(nèi)的飛機的距離超過新進入的飛機與區(qū)域內(nèi)的飛機的距離超過60公里。公里。根據(jù)當年競賽題目給出的數(shù)據(jù)，可以驗證根據(jù)當年競賽題目給出的數(shù)據(jù)，可以驗證區(qū)域內(nèi)的飛機不超過架區(qū)域內(nèi)的飛機不超過架(包括新進入的包括新進入的)。2021/6/1622 個人的想法不同，隊友之間爭執(zhí)不下的情況下，個人的想法不同，隊友之間爭執(zhí)不下的情況下，若時間允許，都可一一寫到論文中去，建立的模若時間允許，都可一一寫到論文中去，建立

20、的模型一、模型二型一、模型二；或者經(jīng)討論后，選擇一個認或者經(jīng)討論后，選擇一個認為更合理的。為更合理的。 現(xiàn)在看來，無論是構建模型，還是計算，都不太現(xiàn)在看來，無論是構建模型，還是計算，都不太難。難。 本例題未給出數(shù)據(jù)，將重點放在如何構建模型上本例題未給出數(shù)據(jù)，將重點放在如何構建模型上2021/6/1623解：解：(1)不考慮飛機的尺寸，用點代表飛機；不考慮飛機的尺寸，用點代表飛機；(2)已在區(qū)域內(nèi)的已在區(qū)域內(nèi)的5架飛機按給定的方向角作架飛機按給定的方向角作 直線飛行，則必不會碰撞，也不會發(fā)生直線飛行，則必不會碰撞，也不會發(fā)生 意外；意外；(應該根據(jù)題目中所給出的數(shù)據(jù)簡應該根據(jù)題目中所給出的數(shù)據(jù)簡

21、 單的單的 驗證一下驗證一下)(3)飛機調(diào)整方向角的過程可在瞬間完成飛機調(diào)整方向角的過程可在瞬間完成,(不不 計調(diào)整方向所花費的時間計調(diào)整方向所花費的時間)。為解決該問題，補充假設：為解決該問題，補充假設：2021/6/1624變量、參數(shù)的符號假設變量、參數(shù)的符號假設（為了建模）（為了建模） 00,1 26)iixyii 第第 架架機機的的初初始始位位置置, (，, (， ，01 26)iii 第第 架架機機的的整整前前的的方方向向角角, , ( (， ，1 26)iii 第第 架架機機的的整整后后的的方方向向角角, , ( (， ， 在區(qū)域內(nèi)飛行在區(qū)域內(nèi)飛行iiTi 第第 架架 機機按按方方

22、向向角角飛飛時間（可以根據(jù)數(shù)據(jù)算出來）時間（可以根據(jù)數(shù)據(jù)算出來）2021/6/1625四種情況：四種情況：四個象限，易用四個象限，易用4個表達式表示個表達式表示說明：說明：用初等數(shù)學的知識即可完成，用初等數(shù)學的知識即可完成，思考：思考：在哪個時間段某兩架飛機可能相撞？在哪個時間段某兩架飛機可能相撞？?ijTTor otherelseIn fact, 我們只需考慮兩架飛機我們只需考慮兩架飛機同時同時在區(qū)域內(nèi)在區(qū)域內(nèi)飛行時的情況，也就是說，飛行時的情況，也就是說， min,ijT T才是同在區(qū)域內(nèi)的狀況。才是同在區(qū)域內(nèi)的狀況。記為記為ijT2021/6/1626 00002202,mincosco

23、ssinsinijijijijijt Tijijdxxvtyyvt 根據(jù)題目條件，需計算第根據(jù)題目條件，需計算第 架飛機之間架飛機之間的的最短距離最短距離, i j2021/6/1627為此，我們可以給出原問題的模型如下：為此，我們可以給出原問題的模型如下： 00612min,60, ,1,2,6,. .,1,2,6.6iiiijijiidi jijs ti 思考：思考：是否還有其他的表達形式？是否還有其他的表達形式？非線性非線性規(guī)劃模規(guī)劃模型型分別從目標函數(shù)和約束條件角度思考分別從目標函數(shù)和約束條件角度思考2021/6/1628首先思考一下目標函數(shù)是否有其它的表達？首先思考一下目標函數(shù)是否有

24、其它的表達？ 061miniii 同學們首先想到的可能是同學們首先想到的可能是Oh, Sorry!有正有負有正有負抵消抵消2021/6/1629061miniii 0621miniii 最小一最小一乘乘 法法最小二最小二乘乘 法法 因最小一乘法帶絕對值，不好計算，以上兩式，因最小一乘法帶絕對值，不好計算，以上兩式，比較而言，后者較好。比較而言，后者較好。為了避免抵消為了避免抵消or2021/6/1630有的隊員這樣考慮：有的隊員這樣考慮：016min maxiii 令為令為 ,轉(zhuǎn)化為二次規(guī)劃轉(zhuǎn)化為二次規(guī)劃用到經(jīng)驗模型中確定參數(shù)的近似準則用到經(jīng)驗模型中確定參數(shù)的近似準則:就所有飛機而言，就所有飛

25、機而言， 讓調(diào)整弧度最大的讓調(diào)整弧度最大的即即盡可能小，盡可能小，Chebshavf 準則準則2021/6/1631其次討論一下約束條件是否有其它表達？其次討論一下約束條件是否有其它表達？ 若考慮區(qū)域內(nèi)不發(fā)生碰撞（若時間允許，也若考慮區(qū)域內(nèi)不發(fā)生碰撞（若時間允許，也可以考慮出了區(qū)域的情況，另外建模）、錯層可以考慮出了區(qū)域的情況，另外建模）、錯層飛行（飛高或者飛低避免碰撞），進行模型的飛行（飛高或者飛低避免碰撞），進行模型的進一步改進，重點應放在解決問題的方法上。進一步改進，重點應放在解決問題的方法上。 如如 02,1,2,6,6,60, ,1,2,6,iiijijidi jij 2021/6/

26、1632 無論選擇哪一種表達，怎樣考慮約束條件，無論選擇哪一種表達，怎樣考慮約束條件，目標函數(shù)都不可能是線性的。目標函數(shù)都不可能是線性的。 現(xiàn)在看來，那年的題目建模只是在條件的現(xiàn)在看來，那年的題目建模只是在條件的考慮上和建模中目標函數(shù)的表達方面較難一點?？紤]上和建模中目標函數(shù)的表達方面較難一點。 是一個帶不等式約束的非線性規(guī)劃問題。是一個帶不等式約束的非線性規(guī)劃問題。 而且不可能轉(zhuǎn)化成線性的形式。而且不可能轉(zhuǎn)化成線性的形式。2021/6/1633非線性規(guī)劃模型按約束條件可分為以下三類：非線性規(guī)劃模型按約束條件可分為以下三類： 無約束非線性規(guī)劃模型：無約束非線性規(guī)劃模型： 等式約束非線性規(guī)劃模型

27、：等式約束非線性規(guī)劃模型：min ( )nf xxRmin ( ). . ( )0,1,2,jf xst h xjr 不等式約束非線性規(guī)劃模型：不等式約束非線性規(guī)劃模型：min ( ). . ( )0,1,2,if xst g xim2021/6/1634如如數(shù)據(jù)擬合的最小二乘問題就是一個無約束極值問數(shù)據(jù)擬合的最小二乘問題就是一個無約束極值問題。題。 其思想是：觀察點（實驗數(shù)據(jù)點）到曲線的距其思想是：觀察點（實驗數(shù)據(jù)點）到曲線的距離的平方之和最小離的平方之和最小 無約束非線性規(guī)劃模型：無約束非線性規(guī)劃模型：2021/6/1635理論上無約束極值問題可化成求解理論上無約束極值問題可化成求解 0g

28、rad fx 即解一個即解一個 n 元方程組，且往往是非線性方程組。元方程組，且往往是非線性方程組。 而一般說來，非線性方程組的求解并不比求無而一般說來，非線性方程組的求解并不比求無約束極值容易。約束極值容易。2021/6/1636求解無約束極值問題的基本方法：求解無約束極值問題的基本方法：迭代法迭代法 從一個給定的初始可行點從一個給定的初始可行點 出發(fā)，依次出發(fā)，依次0 x產(chǎn)生一個可行點列產(chǎn)生一個可行點列12,kxxx的一個極小值點的一個極小值點,恰好是恰好是使得某個使得某個kx fx基本思路：基本思路：或或 kx收斂于收斂于x , 稱具有這種性質(zhì)的算法稱具有這種性質(zhì)的算法是是收斂的收斂的.

29、2021/6/1637由由kx迭代到迭代到1kx 時時,1,kkkkxxp 記記即即1,kkkkxxp kp其中向量其中向量為為搜索方向搜索方向, 實數(shù)實數(shù)k 稱為稱為步長步長,確定以后確定以后,kkp kx由由可唯一地確定可唯一地確定1,kx 從從0 x出發(fā)就可確定點列出發(fā)就可確定點列 .kx2021/6/1638迭代的方法很多迭代的方法很多, 各種迭代法的區(qū)別在于選取各種迭代法的區(qū)別在于選取,kkp 的方式不同的方式不同, 而而kp尤為關鍵尤為關鍵.一般要求一般要求 kfx遞減遞減, 具有這種性質(zhì)的算法叫做具有這種性質(zhì)的算法叫做下降下降算法算法.2021/6/1639若已得若已得,kx下降

30、得最多下降得最多,并確定了并確定了kx的可行下降方向的可行下降方向,kp上選取步長上選取步長則在射線則在射線 0kkxp ,k 使使 ,kkkkfxpfx 且使且使 kfx 00minmin,kkkkkfxpfxp 即求即求求求k 的過程稱為的過程稱為一維搜索一維搜索.1. 下降算法下降算法2021/6/1640于是一維搜索歸結為求解一維無約束極值問題于是一維搜索歸結為求解一維無約束極值問題: min,xxR 其算法有其算法有Newton法、平分法、黃金分割法法、平分法、黃金分割法（0.618法）、分數(shù)法（法）、分數(shù)法（Fibonacci法）、拋法）、拋物線法（二次插值法）等，物線法（二次插值

31、法）等， 前兩種算法需計算前兩種算法需計算 x 的導數(shù)，的導數(shù)，后三種算法只需計算后三種算法只需計算 x 的函數(shù)值。的函數(shù)值。下面僅介紹下面僅介紹Newton法，對其他方法的了解可法，對其他方法的了解可參考有關書籍。參考有關書籍。2021/6/1641按按0,1,2,k 給定初始可行點給定初始可行點 和控制誤差和控制誤差 ，0 x0 迭代格式迭代格式 1kkkkxxxx 迭代，迭代，當當1kkxx 時，時， x 即求得即求得的最優(yōu)解的近似解的最優(yōu)解的近似解1,kxx 停止計算。停止計算。Newton 法介紹法介紹2021/6/1642 一個好的算法必須以較快的速度收斂到一個好的算法必須以較快的

32、速度收斂到最優(yōu)解。最優(yōu)解。 kx設算法產(chǎn)生的點列設算法產(chǎn)生的點列收斂于最優(yōu)解收斂于最優(yōu)解,x 1p 若存在若存在及及1lim,kpkkxxCxx 0,C 使使 kx則稱則稱為為 p 階收斂的。階收斂的。該算法也是該算法也是 p 階收斂的。階收斂的。2021/6/1643 稱為稱為線性收斂；線性收斂；1lim,kpkkxxCxx 1p 當當且且01C時，時， 稱為稱為超線性收斂；超線性收斂；12p當當時，時， 稱為稱為平方收斂；平方收斂；2p 當當時，時，2021/6/1644一個算法是否收斂，一個算法是否收斂，0 x往往與往往與的選取有關的選取有關 若當若當0 x充分接近充分接近x 時，時，由

33、算法產(chǎn)生的點列由算法產(chǎn)生的點列 kx才收斂于才收斂于,x 則稱該算法為具有局部收斂則稱該算法為具有局部收斂性的算法；性的算法； 若對若對0,xD則稱該算法為具有全局收斂性的算法。則稱該算法為具有全局收斂性的算法。由算法產(chǎn)生由算法產(chǎn)生 的點列的點列 kx均收斂均收斂,x 于于2021/6/1645 Newton法是平方收斂的，具有局部收斂法是平方收斂的，具有局部收斂性；拋物線法是超線性收斂的，具有全局收斂性；拋物線法是超線性收斂的，具有全局收斂性；平分法、黃金分割法、分數(shù)法是線性收斂性；平分法、黃金分割法、分數(shù)法是線性收斂的，具有全局收斂性。的，具有全局收斂性。常見一維搜索算法的收斂性常見一維搜

34、索算法的收斂性2021/6/1646當當 x 具有多個極小值點時，具有多個極小值點時， 則算法求得則算法求得的往往是的往往是 x 的一個局部極小值點。的一個局部極小值點。此時可此時可改變改變0 x的取值，重新迭代求解。的取值，重新迭代求解。 若求得多個極小值點，則從中選擇一個若求得多個極小值點，則從中選擇一個較滿意的結果。較滿意的結果。 說明：說明：2021/6/1647 1847年年Cauchy提出了第一個無約束極值問提出了第一個無約束極值問題的算法題的算法梯度法或最速下降法：梯度法或最速下降法：2. 梯度法梯度法. 00)(0kX，令，允許誤差越接近最優(yōu)點越好步驟一：選定初始點).(),(

35、,kkkkXfPXfX選取搜索方向計算梯度優(yōu)點步驟二：假定已得非最.11返回繼續(xù)搜索令不滿足給定精度要求，如果kkXk).(min)( ,k0kkkk1PXfPXfPXXkkkkk，滿足：步驟三：選定搜索步長.1*1kkXXX搜索完成，近似最優(yōu)點滿足給定精度要求，則如果.)()()(.1111kkkkkkXXXfXfXfX或或斷準則：檢驗是否滿足收斂性判根據(jù)精度要求，要求的近似解是否是最優(yōu)點或是滿足步驟四：判斷2021/6/1648例題：應用梯度法求解例題：應用梯度法求解. 0:2 . 0)2 , 2(0kX，令，允許誤差步驟一：選定初始點.100, 4)(),(kkkXfPXf選取搜索方向步

36、驟二：計算梯度.02. 0,)1002(25)42()().(min)( ,02200000kkkk1解得優(yōu)步長第一點搜索計算：求最，滿足：步驟三：選定搜索步長PXfPXfPXfPXXkkkk.02. 031.100)()(),0 ,92. 1 (.)()()(.0111111不滿足，繼續(xù)搜索且第一點搜索計算：或或斷準則：檢驗是否滿足收斂性判根據(jù)精度要求，要求的近似解是否是最優(yōu)點或是滿足步驟四：判斷XfXfXXXXfXfXfXkkkkkk.25)(min2221xxXf解：解：2021/6/1649 該算法具有全局收斂性，是線性收斂的，該算法具有全局收斂性，是線性收斂的，但有時是很慢的線性收斂

37、，這似乎與但有時是很慢的線性收斂，這似乎與“最速下最速下降降”矛盾。其實不然，最速下降方向函數(shù)在某矛盾。其實不然，最速下降方向函數(shù)在某點處的局部性質(zhì)，對局部來說是最速下降方向，點處的局部性質(zhì)，對局部來說是最速下降方向，對全局來說卻不一定是最速下降方向，故梯度對全局來說卻不一定是最速下降方向，故梯度法不是有效的實用算法。法不是有效的實用算法。 通過對它改進或利用它與其他收斂快的算通過對它改進或利用它與其他收斂快的算法相結合可得法相結合可得Newton法、法、Fletcher-Reeves共軛梯度法、變尺度法和共軛梯度法、變尺度法和Powell法法等有效算等有效算法。法。2021/6/1650 下

38、面僅介紹前兩者，對后兩者的了解可參下面僅介紹前兩者，對后兩者的了解可參閱有關書籍。閱有關書籍。 121,kkkkxxfxg 當當1kkxx 時，時，則則 。1kxx 其中其中 1112121222122,nnnnnnx xkx xkx xkx xkx xkx xkkx xkx xkx xkfxfxfxfxfxfxfxfxfxfx 稱為稱為 fx在在 處的處的Hesse矩陣。矩陣。kxNewton法法2021/6/1651 該算法是平方收斂的，具有局部收斂性。該算法是平方收斂的，具有局部收斂性。 對對Newton法進行改進，可得具有超線性法進行改進，可得具有超線性收斂的且具有全局收斂性的收斂的且

39、具有全局收斂性的阻尼阻尼Newton法法或或修正修正Newton法法： 121102min,kkkkkkkkfxfxgfxgfxfx 當當1kkxx 時，時，有有 。1kxx 2021/6/1652 Fletcher-Reeves共軛梯度法共軛梯度法當當1kkxx 時，時，有有 。1kxx 該算法的收斂速度介于梯度法和該算法的收斂速度介于梯度法和Newton法法其中其中00,Pg 之間，既克服了前者的慢收斂性，又避免了之間，既克服了前者的慢收斂性，又避免了111TkkkkkTkkg gPgPgg 10min,kkkkkkfxfxpfxp 后者計算量大和僅具有局部收斂性的缺陷。后者計算量大和僅具

40、有局部收斂性的缺陷。2021/6/1653（2 2）只有等式約束的非線性規(guī)劃問題通常可用只有等式約束的非線性規(guī)劃問題通?？捎孟ā⒗窭嗜粘俗臃?，將其化為無約束問消元法、拉格朗日乘子法，將其化為無約束問題求解題求解. .（3 3）具有不等式約束的非線性規(guī)劃問題解起來具有不等式約束的非線性規(guī)劃問題解起來很復雜，求解這一類問題，通常將不等式化很復雜，求解這一類問題，通常將不等式化為等式約束，再將約束問題化為無約束問題，為等式約束，再將約束問題化為無約束問題，用線性逼近的方法將非線性規(guī)劃問題化為線用線性逼近的方法將非線性規(guī)劃問題化為線性規(guī)劃問題性規(guī)劃問題. 下面先介紹一個簡單的非線性規(guī)劃問題下面先

41、介紹一個簡單的非線性規(guī)劃問題的例子，其中的一些約束條件是等式，這類非的例子，其中的一些約束條件是等式，這類非線性規(guī)劃問題可用拉格朗日方法求解線性規(guī)劃問題可用拉格朗日方法求解.2021/6/16542021/6/16552021/6/16562021/6/16572021/6/1658Kuhn-Tucker定理：對于不等式約束非線性最優(yōu)化 極值問題若 ， 均可微，則其極值點存在的必要條件是：注：更詳細的結論參閱有關書籍注：更詳細的結論參閱有關書籍.()fX()igX 不等式約束非線性規(guī)劃模型不等式約束非線性規(guī)劃模型2021/6/1659注：1、庫-圖條件是判別有約束極值點的必要條件，并非充分條件

42、。但是對于凸函數(shù)、凸集問題也是判別其極值點的充分條件。固此時的局部最優(yōu)解也必為全局的最優(yōu)解。2、庫-圖乘子與拉格朗日乘子類似。但拉格朗日乘子的符號不是確定的，可正可負；而庫-恩乘子的符號是確定的，其規(guī)律為： a、求 ， 時，則 b、求 ， 時，則 c、求 ， 時，則 d、求 ， 時，則m in ( )f Xm in ( )f X( ) 0ig X ( ) 0ig X ()0ig X ( ) 0ig X 0i0i0i0ima x ( )f Xma x ( )f X2021/6/1660罰函數(shù)法罰函數(shù)法:約束最優(yōu)化問題化為無約束最優(yōu)化問題的一種求解方法約束最優(yōu)化問題化為無約束最優(yōu)化問題的一種求解方

43、法2021/6/16612021/6/1662罰函數(shù)法的步驟：（等式約束最優(yōu)化問題罰函數(shù)法）罰函數(shù)法的步驟：（等式約束最優(yōu)化問題罰函數(shù)法）2021/6/16632021/6/16642021/6/16652021/6/1666罰函數(shù)法步驟：（不等式約束最優(yōu)化問題罰函數(shù)法）罰函數(shù)法步驟：（不等式約束最優(yōu)化問題罰函數(shù)法）2021/6/16672021/6/16682021/6/1669注：罰函數(shù)法更多的詳細改進工作，需參閱相關書籍注：罰函數(shù)法更多的詳細改進工作，需參閱相關書籍2021/6/1670 在許多實際問題中，衡量一個方案的好壞標準往往不止一個，例如設計一個導彈，既要射程最遠，又要燃料最省，

44、還要精度最高. 這一類問題統(tǒng)稱為多目標最優(yōu)化問題或多目標規(guī)劃問題. 我們先來看一個投資計劃的例子.2021/6/1671例：例： 投資問題投資問題 某公司在一段時間內(nèi)有某公司在一段時間內(nèi)有a(億元億元)的資金可用于建廠投資。的資金可用于建廠投資。若可供選擇的項目記為若可供選擇的項目記為1,2,m。而且一旦對第。而且一旦對第i個項目投個項目投資就用去資就用去ai億元；而這段時間內(nèi)可得收益億元；而這段時間內(nèi)可得收益ci億元。問如何億元。問如何確定最佳的投資方案？確定最佳的投資方案？1i0iix對第 個項目投資不對第 個項目投資 最佳投資方案：投資最少，收益最大！最佳投資方案：投資最少，收益最大！2021/6/1672投資最少：投資最少：1121min( ,.,)mniiif x xxa x2121max( ,.,)mniiifx xxc x約束條件為：約束條件為：1(1)0,1,2,.miiiiia xaxxim收益最大：收益最大：2021/6/16732021/6/16742021/6/16752021/6/16762021/6/16772021/6/16782021/6/16792021/6/16802021/6/16812021/6/16822021/6/16832021/6/16842021/6/16852021