最優(yōu)化方法及控制應(yīng)用1

1、最優(yōu)化方法及控制應(yīng)用最優(yōu)化方法及控制應(yīng)用主講人：董密信息科學(xué)與工程學(xué)院信息科學(xué)與工程學(xué)院參考書(shū)：1.實(shí)用最優(yōu)化方法 R.Fleter著，游兆永等譯 天津科技翻譯出版公司2.非線(xiàn)性規(guī)劃數(shù)值方法 袁亞湘 上?？茖W(xué)技術(shù)出版社 19953.非線(xiàn)性最優(yōu)方法 席少霖 高等教育出版社 4.工程優(yōu)化的算法分析 張可村 西安交大出版社 19895.最優(yōu)化方法 解文新，韓立興等 天津大學(xué)出版社 20016.最優(yōu)化方法 施光燕，董加禮 高等教育出版社 2001最優(yōu)化方法及控制應(yīng)用最優(yōu)化：在多種（有限種或無(wú)限種）決策中挑選最優(yōu)化：在多種（有限種或無(wú)限種）決策中挑選 最好決策的問(wèn)題。最好決策的問(wèn)題。最優(yōu)化方法：（也稱(chēng)做

2、運(yùn)籌學(xué)方法）是近幾十年最優(yōu)化方法：（也稱(chēng)做運(yùn)籌學(xué)方法）是近幾十年 形成的，主要運(yùn)用數(shù)學(xué)方法研究各種系形成的，主要運(yùn)用數(shù)學(xué)方法研究各種系統(tǒng)的優(yōu)化途徑及方案，為決策者提供科統(tǒng)的優(yōu)化途徑及方案，為決策者提供科學(xué)決策的依據(jù)。學(xué)決策的依據(jù)。最優(yōu)方案：是達(dá)到最優(yōu)目標(biāo)的方案。最優(yōu)方案：是達(dá)到最優(yōu)目標(biāo)的方案。最優(yōu)化理論：就是最優(yōu)化方法的理論。最優(yōu)化理論：就是最優(yōu)化方法的理論。 數(shù)學(xué)意義數(shù)學(xué)意義為了達(dá)到最優(yōu)化目的所提出的各種求解方法。從為了達(dá)到最優(yōu)化目的所提出的各種求解方法。從數(shù)學(xué)意義上說(shuō)，最優(yōu)化方法是一種求極值的方法，數(shù)學(xué)意義上說(shuō)，最優(yōu)化方法是一種求極值的方法，即在一組約束為等式或不等式的條件下，使系統(tǒng)的即在

3、一組約束為等式或不等式的條件下，使系統(tǒng)的目標(biāo)函數(shù)達(dá)到極值，即最大值或最小值。從經(jīng)濟(jì)意目標(biāo)函數(shù)達(dá)到極值，即最大值或最小值。從經(jīng)濟(jì)意義上說(shuō)，是在一定的人力、物力和財(cái)力資源條件下義上說(shuō)，是在一定的人力、物力和財(cái)力資源條件下，使經(jīng)濟(jì)效果達(dá)到最大（如產(chǎn)值、利潤(rùn)），或者在，使經(jīng)濟(jì)效果達(dá)到最大（如產(chǎn)值、利潤(rùn)），或者在完成規(guī)定的生產(chǎn)或經(jīng)濟(jì)任務(wù)下，使投入的人力、物完成規(guī)定的生產(chǎn)或經(jīng)濟(jì)任務(wù)下，使投入的人力、物力和財(cái)力等資源為最少。力和財(cái)力等資源為最少。發(fā)展簡(jiǎn)史發(fā)展簡(jiǎn)史 公元前公元前 500年古希臘在討論建筑美學(xué)中就已發(fā)現(xiàn)了年古希臘在討論建筑美學(xué)中就已發(fā)現(xiàn)了長(zhǎng)方形長(zhǎng)與寬的最佳比例為長(zhǎng)方形長(zhǎng)與寬的最佳比例為1.618

4、，稱(chēng)為黃金分割，稱(chēng)為黃金分割比。其倒數(shù)至今在優(yōu)選法中仍得到廣泛應(yīng)用。比。其倒數(shù)至今在優(yōu)選法中仍得到廣泛應(yīng)用。 在微積分出現(xiàn)以前，已有許多學(xué)者開(kāi)始研究用數(shù)學(xué)在微積分出現(xiàn)以前，已有許多學(xué)者開(kāi)始研究用數(shù)學(xué)方法解決最優(yōu)化問(wèn)題。方法解決最優(yōu)化問(wèn)題。 最優(yōu)化方法真正形成為科學(xué)方法則在最優(yōu)化方法真正形成為科學(xué)方法則在17世紀(jì)以后。世紀(jì)以后。工作步驟工作步驟 提出最優(yōu)化問(wèn)題，收集有關(guān)數(shù)據(jù)和資料；提出最優(yōu)化問(wèn)題，收集有關(guān)數(shù)據(jù)和資料；建立最優(yōu)化問(wèn)題的數(shù)學(xué)模型建立最優(yōu)化問(wèn)題的數(shù)學(xué)模型,確定變量確定變量,列出目標(biāo)列出目標(biāo)函數(shù)和約束條件；函數(shù)和約束條件；分析模型，選擇合適的最優(yōu)化方法；分析模型，選擇合適的最優(yōu)化方法；求

5、解，一般通過(guò)編制程序，用計(jì)算機(jī)求最優(yōu)解；求解，一般通過(guò)編制程序，用計(jì)算機(jī)求最優(yōu)解；最優(yōu)解的檢驗(yàn)和實(shí)施。最優(yōu)解的檢驗(yàn)和實(shí)施。模型的基本要素模型的基本要素最優(yōu)化模型包括：變量、約束條件和目標(biāo)函數(shù)最優(yōu)化模型包括：變量、約束條件和目標(biāo)函數(shù)變量：指最優(yōu)化問(wèn)題中待確定的某些量。變量可變量：指最優(yōu)化問(wèn)題中待確定的某些量。變量可用用x(x1，x2,xn)T表示。表示。約束條件約束條件:指在求最優(yōu)解時(shí)對(duì)變量的某些限制指在求最優(yōu)解時(shí)對(duì)變量的某些限制,包括包括技術(shù)上的約束、資源上的約束和時(shí)間上的約束等。技術(shù)上的約束、資源上的約束和時(shí)間上的約束等。約束條件可用約束條件可用 gi(x)0表示表示i1,2，m，m 表示表

6、示約束條件數(shù)；約束條件數(shù)；目標(biāo)函數(shù)：最優(yōu)化有一定的評(píng)價(jià)標(biāo)準(zhǔn)。目標(biāo)函數(shù)目標(biāo)函數(shù)：最優(yōu)化有一定的評(píng)價(jià)標(biāo)準(zhǔn)。目標(biāo)函數(shù)就是這種標(biāo)準(zhǔn)的數(shù)學(xué)描述，一般可用就是這種標(biāo)準(zhǔn)的數(shù)學(xué)描述，一般可用f(x)來(lái)表示，即來(lái)表示，即f(x)=f(x1，x2,xn)。最優(yōu)化方法最優(yōu)化方法最優(yōu)化問(wèn)題的求解方法可分成解析法、直接法、數(shù)最優(yōu)化問(wèn)題的求解方法可分成解析法、直接法、數(shù)值計(jì)算法和其他方法。值計(jì)算法和其他方法。解析法：只適用于目標(biāo)函數(shù)和約束條件有明顯的解析法：只適用于目標(biāo)函數(shù)和約束條件有明顯的解析表達(dá)式的情況。解析表達(dá)式的情況。求解方法是：先求出最優(yōu)的必要條件，得到一組方求解方法是：先求出最優(yōu)的必要條件，得到一組方程或不等

7、式，再求解這組方程或不等式，一般是用程或不等式，再求解這組方程或不等式，一般是用求導(dǎo)數(shù)的方法或變分法求出必要條件，通過(guò)必要條求導(dǎo)數(shù)的方法或變分法求出必要條件，通過(guò)必要條件將問(wèn)題簡(jiǎn)化，因此也稱(chēng)間接法。件將問(wèn)題簡(jiǎn)化，因此也稱(chēng)間接法。直接法：當(dāng)目標(biāo)函數(shù)較為復(fù)雜或者不能用變量顯直接法：當(dāng)目標(biāo)函數(shù)較為復(fù)雜或者不能用變量顯函數(shù)描述時(shí)，無(wú)法用解析法求必要條件?？刹捎弥焙瘮?shù)描述時(shí)，無(wú)法用解析法求必要條件?？刹捎弥苯铀阉鞯姆椒ń?jīng)過(guò)若干次迭代搜索到最優(yōu)點(diǎn)。接搜索的方法經(jīng)過(guò)若干次迭代搜索到最優(yōu)點(diǎn)。這種方法常常根據(jù)經(jīng)驗(yàn)或通過(guò)試驗(yàn)得到所需結(jié)果。這種方法常常根據(jù)經(jīng)驗(yàn)或通過(guò)試驗(yàn)得到所需結(jié)果。對(duì)于一維搜索對(duì)于一維搜索(單變量

8、極值問(wèn)題單變量極值問(wèn)題)，主要用消去法或，主要用消去法或多項(xiàng)式插值法；對(duì)于多維搜索問(wèn)題多項(xiàng)式插值法；對(duì)于多維搜索問(wèn)題(多變量極值問(wèn)題多變量極值問(wèn)題)主要應(yīng)用爬山法。主要應(yīng)用爬山法。數(shù)值計(jì)算法：也是一種直接法。它以梯度法為基數(shù)值計(jì)算法：也是一種直接法。它以梯度法為基礎(chǔ)，所以是一種解析與數(shù)值計(jì)算相結(jié)合的方法。礎(chǔ)，所以是一種解析與數(shù)值計(jì)算相結(jié)合的方法。其他方法：如網(wǎng)絡(luò)最優(yōu)化方法等其他方法：如網(wǎng)絡(luò)最優(yōu)化方法等最優(yōu)解的概念最優(yōu)解的概念最優(yōu)化問(wèn)題的解一般稱(chēng)為最優(yōu)解。如果只考察約束集最優(yōu)化問(wèn)題的解一般稱(chēng)為最優(yōu)解。如果只考察約束集合中某一局部范圍內(nèi)的優(yōu)劣情況，則解稱(chēng)為局部最優(yōu)合中某一局部范圍內(nèi)的優(yōu)劣情況，則解

9、稱(chēng)為局部最優(yōu)解。如果是考察整個(gè)約束集合中的情況，則解稱(chēng)為總解。如果是考察整個(gè)約束集合中的情況，則解稱(chēng)為總體最優(yōu)解。對(duì)于不同優(yōu)化問(wèn)題，最優(yōu)解有不同的含意體最優(yōu)解。對(duì)于不同優(yōu)化問(wèn)題，最優(yōu)解有不同的含意，因而還有專(zhuān)用的名稱(chēng)。，因而還有專(zhuān)用的名稱(chēng)。例如，在對(duì)策論和數(shù)理經(jīng)濟(jì)模型中稱(chēng)為平衡解；在控例如，在對(duì)策論和數(shù)理經(jīng)濟(jì)模型中稱(chēng)為平衡解；在控制問(wèn)題中稱(chēng)為最優(yōu)控制或極值控制；在多目標(biāo)決策問(wèn)制問(wèn)題中稱(chēng)為最優(yōu)控制或極值控制；在多目標(biāo)決策問(wèn)題中稱(chēng)為非劣解（又稱(chēng)帕雷托最優(yōu)解或有效解）。題中稱(chēng)為非劣解（又稱(chēng)帕雷托最優(yōu)解或有效解）。最優(yōu)化方法的應(yīng)用最優(yōu)化方法的應(yīng)用最優(yōu)化可分為最優(yōu)設(shè)計(jì)、最優(yōu)計(jì)劃、最優(yōu)管理和最最優(yōu)化可分為

10、最優(yōu)設(shè)計(jì)、最優(yōu)計(jì)劃、最優(yōu)管理和最優(yōu)控制等四個(gè)方面。優(yōu)控制等四個(gè)方面。最優(yōu)設(shè)計(jì)：世界各國(guó)工程技術(shù)界，尤其是飛機(jī)、最優(yōu)設(shè)計(jì)：世界各國(guó)工程技術(shù)界，尤其是飛機(jī)、造船、機(jī)械、建筑等部門(mén)都已廣泛應(yīng)用最優(yōu)化方法造船、機(jī)械、建筑等部門(mén)都已廣泛應(yīng)用最優(yōu)化方法于設(shè)計(jì)中，從各種設(shè)計(jì)參數(shù)的優(yōu)選到最佳結(jié)構(gòu)形狀于設(shè)計(jì)中，從各種設(shè)計(jì)參數(shù)的優(yōu)選到最佳結(jié)構(gòu)形狀的選取等，結(jié)合有限元方法已使許多設(shè)計(jì)優(yōu)化問(wèn)題的選取等，結(jié)合有限元方法已使許多設(shè)計(jì)優(yōu)化問(wèn)題得到解決。得到解決。最優(yōu)計(jì)劃：現(xiàn)代國(guó)民經(jīng)濟(jì)或部門(mén)經(jīng)濟(jì)的計(jì)劃，直最優(yōu)計(jì)劃：現(xiàn)代國(guó)民經(jīng)濟(jì)或部門(mén)經(jīng)濟(jì)的計(jì)劃，直至企業(yè)的發(fā)展規(guī)劃和年度生產(chǎn)計(jì)劃，尤其是農(nóng)業(yè)規(guī)至企業(yè)的發(fā)展規(guī)劃和年度生產(chǎn)計(jì)劃，尤其

11、是農(nóng)業(yè)規(guī)劃、種植計(jì)劃、能源規(guī)劃和其他資源、環(huán)境和生態(tài)劃、種植計(jì)劃、能源規(guī)劃和其他資源、環(huán)境和生態(tài)規(guī)劃的制訂，都已開(kāi)始應(yīng)用最優(yōu)化方法。一個(gè)重要規(guī)劃的制訂，都已開(kāi)始應(yīng)用最優(yōu)化方法。一個(gè)重要的發(fā)展趨勢(shì)是幫助領(lǐng)導(dǎo)部門(mén)進(jìn)行各種優(yōu)化決策。的發(fā)展趨勢(shì)是幫助領(lǐng)導(dǎo)部門(mén)進(jìn)行各種優(yōu)化決策。最優(yōu)管理：一般在日常生產(chǎn)計(jì)劃的制訂、調(diào)度和最優(yōu)管理：一般在日常生產(chǎn)計(jì)劃的制訂、調(diào)度和運(yùn)行中都可應(yīng)用最優(yōu)化方法。隨著管理信息系統(tǒng)和運(yùn)行中都可應(yīng)用最優(yōu)化方法。隨著管理信息系統(tǒng)和決策支持系統(tǒng)的建立和使用，使最優(yōu)管理得到迅速?zèng)Q策支持系統(tǒng)的建立和使用，使最優(yōu)管理得到迅速的發(fā)展。的發(fā)展。最優(yōu)控制：主要用于對(duì)各種控制系統(tǒng)的優(yōu)化。例最優(yōu)控制：主要

12、用于對(duì)各種控制系統(tǒng)的優(yōu)化。例如，導(dǎo)彈系統(tǒng)的最優(yōu)控制，能保證用最少燃料完成如，導(dǎo)彈系統(tǒng)的最優(yōu)控制，能保證用最少燃料完成飛行任務(wù)，用最短時(shí)間達(dá)到目標(biāo)飛行任務(wù)，用最短時(shí)間達(dá)到目標(biāo);；再如飛機(jī)、船舶；再如飛機(jī)、船舶、電力系統(tǒng)等的最優(yōu)控制，化工、冶金等工廠的最、電力系統(tǒng)等的最優(yōu)控制，化工、冶金等工廠的最佳工況的控制。佳工況的控制。一、組合最優(yōu)化一、組合最優(yōu)化TSP:（即旅行商問(wèn)題）假設(shè)有（即旅行商問(wèn)題）假設(shè)有n 個(gè)城市個(gè)城市 ，一個(gè)推銷(xiāo)員要在這，一個(gè)推銷(xiāo)員要在這 n個(gè)城市推銷(xiāo)產(chǎn)品個(gè)城市推銷(xiāo)產(chǎn)品，要求經(jīng)過(guò)每個(gè)城市且僅有一次要求經(jīng)過(guò)每個(gè)城市且僅有一次，如如 何選擇這條路徑，使路徑最短？何選擇這條路徑，使路徑

13、最短？二、動(dòng)態(tài)規(guī)劃二、動(dòng)態(tài)規(guī)劃管道鋪設(shè)：有管道鋪設(shè)：有n個(gè)城市鋪設(shè)管道，要求管道到達(dá)每個(gè)城市，個(gè)城市鋪設(shè)管道，要求管道到達(dá)每個(gè)城市，并且使總的費(fèi)用最低。并且使總的費(fèi)用最低。經(jīng)典極值問(wèn)題經(jīng)典極值問(wèn)題包括：無(wú)約束極值問(wèn)題約束條件下的極值問(wèn)題1、無(wú)約束極值問(wèn)題的數(shù)學(xué)模型 min( )xf x2、約束條件下極值問(wèn)題的數(shù)學(xué)模型 min( )xf x. .( )0,1,2,.,( )0,1,2,.,iistg ximh xin 其中，極大值問(wèn)題可以轉(zhuǎn)化為極小值問(wèn)題來(lái)進(jìn)行求解。如求：max( )xf x 可以轉(zhuǎn)化為：min( )xf x1、無(wú)約束極值問(wèn)題的求解 例1：求函數(shù)y=2x3+3x2-12x+14在

14、區(qū)間-3,4上的最大值與最小值。解：令f(x)=y=2x3+3x2-12x+14 f(x)=6x2+6x-12=6(x+2)(x-1)解方程f(x)=0，得到x1= -2，x2=1，又由于f(-3)=23，f(-2)=34，f(1)=7，f(4)=142，綜上得，函數(shù)f(x)在x=4取得在-3,4上得最大值f(4)=142，在x=1處取得在-3,4上取得最小值f(1)=7 有約束最優(yōu)化最優(yōu)化方法分類(lèi)（一）線(xiàn)性最優(yōu)化：目標(biāo)函數(shù)和約束條件都是線(xiàn)性的則稱(chēng)為線(xiàn)性最優(yōu)化。 非線(xiàn)性最優(yōu)化：目標(biāo)函數(shù)和約束條件如果含有非線(xiàn)性的，則稱(chēng)為非線(xiàn)性最優(yōu)化。（二）靜態(tài)最優(yōu)化：如果可能的方案與時(shí)間無(wú)關(guān)，則是靜態(tài)最優(yōu)化問(wèn)題

15、。 動(dòng)態(tài)最優(yōu)化：如果可能的方案與時(shí)間有關(guān)，則是動(dòng)態(tài)最優(yōu)化問(wèn)題有約束最優(yōu)化問(wèn)題的數(shù)學(xué)建模 有約束最優(yōu)化模型一般具有以下形式：min( ). .xf xst或max( ). .xf xst 其中f(x)為目標(biāo)函數(shù)，省略號(hào)表示約束式子，可以是等式約束，也可以是不等式約束。 根據(jù)目標(biāo)函數(shù)，約束條件的特點(diǎn)將最優(yōu)化方法包含的主要內(nèi)容大致如下劃分： 線(xiàn)性規(guī)劃 整數(shù)規(guī)劃 非線(xiàn)性規(guī)劃 動(dòng)態(tài)規(guī)劃 多目標(biāo)規(guī)劃 對(duì)策論最優(yōu)化方法主要內(nèi)容問(wèn)題一：某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)I、II兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗，如下表所示 12kg40原材料B16kg04原材料A8臺(tái)時(shí)21設(shè)備III該工

16、廠每生產(chǎn)一件產(chǎn)品I可獲利2元，每生產(chǎn)一件產(chǎn)品II可獲利3元。問(wèn)應(yīng)如何安排計(jì)劃使該工廠獲利最多？ 解：該工廠生產(chǎn)產(chǎn)品I x1件，生產(chǎn)產(chǎn)品II x2件，我們可建立如下數(shù)學(xué)模型：2132maxxxz0,12416482212121xxxxxxs.t.問(wèn)題二： 某廠每日8小時(shí)的產(chǎn)量不低于1800件.為了進(jìn)行質(zhì)量控制，計(jì)劃聘請(qǐng)兩種不同水平的檢驗(yàn)員.一級(jí)檢驗(yàn)員的標(biāo)準(zhǔn)為：速度25件/小時(shí)，正確率98%，計(jì)時(shí)工資4元/小時(shí)；二級(jí)檢驗(yàn)員的標(biāo)準(zhǔn)為：速度15件/小時(shí)，正確率95%，計(jì)時(shí)工資3元/小時(shí).檢驗(yàn)員每錯(cuò)檢一次，工廠要損失2元.為使總檢驗(yàn)費(fèi)用最省，該工廠應(yīng)聘一級(jí)、二級(jí)檢驗(yàn)員各幾名？解 設(shè)需要一級(jí)和二級(jí)檢驗(yàn)員的

17、人數(shù)分別為x1、x2人,則應(yīng)付檢驗(yàn)員的工資為：212124323848xxxx因檢驗(yàn)員錯(cuò)檢而造成的損失為：21211282)%5158%2258(xxxx故目標(biāo)函數(shù)為：2121213640)128()2432(minxxxxxxz約束條件為：0,18001582582121xxxx運(yùn)用最優(yōu)化方法解決最優(yōu)化問(wèn)題的一般方法步驟如下：前期分析：分析問(wèn)題，找出要解決的目標(biāo)，約束條件，并確立最優(yōu)化的目標(biāo)。定義變量，建立最優(yōu)化問(wèn)題的數(shù)學(xué)模型，列出目標(biāo)函數(shù)和約束條件。針對(duì)建立的模型，選擇合適的求解方法或數(shù)學(xué)軟件。編寫(xiě)程序，利用計(jì)算機(jī)求解。對(duì)結(jié)果進(jìn)行分析，討論諸如：結(jié)果的合理性、正確性，算法的收斂性，模型的適

18、用性和通用性，算法效率與誤差等。某豆腐店用黃豆制作兩種不同口感的豆腐出售。制作口感較鮮嫩的豆腐每千克需要0.3千克一級(jí)黃豆及0.5千克二級(jí)黃豆，售價(jià)10元；制作口感較厚實(shí)的豆腐每千克需要0.4千克一級(jí)黃豆及0.2千克二級(jí)黃豆，售價(jià)5元?，F(xiàn)小店購(gòu)入9千克一級(jí)黃豆和8千克二級(jí)黃豆。問(wèn)：應(yīng)如何安排制作計(jì)劃才能獲得最大收益。一、問(wèn)題前期分析該問(wèn)題是在不超出制作兩種不同口感豆腐所需黃豆總量條件下合理安排制作計(jì)劃，使得售出各種豆腐能獲得最大收益。二、模型假設(shè)1假設(shè)制作的豆腐能全部售出。2假設(shè)豆腐售價(jià)無(wú)波動(dòng)。變量假設(shè)： 設(shè)計(jì)劃制作口感鮮嫩和厚實(shí)的豆腐各x1千克和 x2千克，可獲得收益R元。目標(biāo)函數(shù)：獲得的總

19、收益最大。 總收益可表示為： 21510 xxR受一級(jí)黃豆數(shù)量限制： 受二級(jí)黃豆數(shù)量限制： 94 . 03 . 021xx82 . 05 . 021xx綜上分析，得到該問(wèn)題的線(xiàn)性規(guī)劃模型 21510maxxxR94 . 03 . 021xx82 . 05 . 021xx0,21xxs.t.用Matlab編程求解程序如下：X,FVAL,EXITFLAG,OUTPUT = LINPROG(f,A,b) f = -10 5;A = 0.3 0.4;0.5 0.2;B = 9;8;X,FVAL,EXITFLAG,OUTPUT = LINPROG(f,A,b)X = 10.0000 15.0000FVA

20、L = -175.0000用YALMIP編程求解程序如下：x=sdpvar(1,2);C=10 5;a=0.3 0.4;0.5 0.2;b=9 8;f=C*x;F=set(0=x=inf); F=F+set(a*x=b);solvesdp(F,-f)double(f)double(x) ans = 175ans = 10 15 設(shè)某工廠有甲、乙、丙、丁四個(gè)車(chē)間，生產(chǎn)A、B、C、D、E、F六種產(chǎn)品。根據(jù)機(jī)床性能和以前的生產(chǎn)情況，得知每單位產(chǎn)品所需車(chē)間的工作小時(shí)數(shù)、每個(gè)車(chē)間在一個(gè)季度工作小時(shí)的上限以及單位產(chǎn)品的利潤(rùn)，如下表所示(例如，生產(chǎn)一個(gè)單位的A產(chǎn)品，需要甲、乙、丙三個(gè)車(chē)間分別工作1小時(shí)、2小

21、時(shí)和4小時(shí))問(wèn)：每種產(chǎn)品各應(yīng)該每季度生產(chǎn)多少，才能使這個(gè)工廠每季度生產(chǎn)利潤(rùn)達(dá)到最大。 生產(chǎn)單位生產(chǎn)單位產(chǎn)品所需產(chǎn)品所需車(chē)間的工車(chē)間的工作小時(shí)數(shù)作小時(shí)數(shù) ABCDEF每個(gè)車(chē)間每個(gè)車(chē)間一個(gè)季度一個(gè)季度工作小時(shí)工作小時(shí)的上限的上限甲甲111323500乙乙255500丙丙425500丁丁138500利潤(rùn)利潤(rùn)(百元百元)4.02.45.55.04.58.5這是一個(gè)典型的最優(yōu)化問(wèn)題，屬線(xiàn)性規(guī)劃。假設(shè)：產(chǎn)品合格且能及時(shí)銷(xiāo)售出去；工作無(wú)等待情況等 變量說(shuō)明： xj：第j種產(chǎn)品的生產(chǎn)量（j=1,2,6） aij：第i車(chē)間生產(chǎn)單位第j種產(chǎn)品所需工作小時(shí)數(shù) （i=1,2,3,4;j=1,2,6） bi：第i車(chē)間的

22、最大工作上限 cj：第j種產(chǎn)品的單位利潤(rùn) 則： cjxj為第j種產(chǎn)品的利潤(rùn)總額； aijxj表示第i車(chē)間生產(chǎn)第j種產(chǎn)品所花時(shí)間總數(shù)； 于是，我們可建立如下數(shù)學(xué)模型：61maxjjjxcz6 , 5 , 4 , 3 , 2 , 1,max04 , 3 , 2 , 14161jabxibxaijiijjijij且為整數(shù)s.t.計(jì)算結(jié)果：Z(百元百元)x1x2x3x4x5x6132000604010040 要從甲城調(diào)出蔬菜2000噸，從乙城調(diào)出蔬菜2500噸，從丙地調(diào)出3000噸，分別供應(yīng)A地2000噸，B地2300噸、C地1800噸、D地1400噸，已知每噸運(yùn)費(fèi)如下表： 供應(yīng)單位供應(yīng)單位調(diào)出單位調(diào)

23、出單位ABCD甲甲21271340乙乙45513720丙丙32352030問(wèn)：如何調(diào)撥才能使運(yùn)費(fèi)最??？ 可以建立如下模型：3141minijijijxaz4131(1,2,3)(1,2,3,4)0(1,2,3;1,2,3,4)min( ,)ijijijjiijijijxbixcjxijxb cs.t. 最優(yōu)化問(wèn)題中的所有變量均為整數(shù)時(shí)，這類(lèi)問(wèn)題稱(chēng)為整數(shù)規(guī)劃問(wèn)題。 如果線(xiàn)性規(guī)劃中的所有變量均為整數(shù)時(shí)，稱(chēng)這類(lèi)問(wèn)題為線(xiàn)性整數(shù)規(guī)劃問(wèn)題。 整數(shù)規(guī)劃可分為線(xiàn)性整數(shù)規(guī)劃和非線(xiàn)性整數(shù)規(guī)劃 ，以及混合整數(shù)規(guī)劃等。 如果決策變量的取值要么為0，要么為1，則這樣的規(guī)劃問(wèn)題稱(chēng)為01規(guī)劃。例1 某鋼廠兩個(gè)煉鋼爐同時(shí)各用

24、一種方法煉鋼。第一種煉法每爐用a小時(shí)，第二種用b小時(shí)（包括清爐時(shí)間）。假定這兩種煉法，每爐出鋼都是k公斤，而煉1公斤鋼的平均燃料費(fèi)第一法為m元，第二法為n元。若要求在c小時(shí)內(nèi)煉鋼公斤數(shù)不少于d，試列出燃料費(fèi)最省的兩種方法的分配方案的數(shù)學(xué)模型。設(shè)用第一種煉法煉鋼x1爐，第二種煉鋼x2爐 )(maxnymxkz且為整數(shù)0,)(212121xxdxxkcbxcaxs.t.引例2.資源分配問(wèn)題： 某個(gè)中型的百貨商場(chǎng)要求售貨人員每周工作5天，連續(xù)休息2天，工資200元/周，已知對(duì)售貨人員的需求經(jīng)過(guò)統(tǒng)計(jì)分析如下表，問(wèn)如何安排可使配備銷(xiāo)售人員的總費(fèi)用最少？星期星期一一二二三三四四五五六六日日所需售貨員人數(shù)所

25、需售貨員人數(shù)18151216191412開(kāi)始休息的人數(shù) x1 x2 x3 x4 x5 x6 x7 設(shè)決策變量如上，可建立如下模型：1234567234563456745671567126712371234123451234567min200()18151216. .191414,0zxxxxxxxxxxxxxxxxxxxxxxxxxxxstxxxxxxxxxxxxxxxx x x x x x x且為整數(shù)非線(xiàn)性規(guī)劃非線(xiàn)性規(guī)劃問(wèn)題的一般數(shù)學(xué)模型：其中， ， 為目標(biāo)函數(shù)， 為約束函數(shù)，這些函數(shù)中至少有一個(gè)是非線(xiàn)性函數(shù)。min( ). .( )0,1,2,( )0,1,2, .ijf xstg xim

26、h xjlnEx)(xf)(),(xhxgji應(yīng)用實(shí)例： 供應(yīng)與選址 某公司有6個(gè)建筑工地要開(kāi)工，每個(gè)工地的位置（用平面坐標(biāo)系a，b表示，距離單位：km）及水泥日用量d(t)由下表給出目前有兩個(gè)臨時(shí)料場(chǎng)位于A(5,1)，B(2,7)，日儲(chǔ)量各有20t假設(shè)從料場(chǎng)到工地之間均有直線(xiàn)道路相連 （1）試制定每天的供應(yīng)計(jì)劃，即從A，B兩料場(chǎng)分別向各工地運(yùn)送多少水泥，可使總的噸千米數(shù)最小 （2）為了進(jìn)一步減少?lài)嵡讛?shù)，打算舍棄兩個(gè)臨時(shí)料場(chǎng)，改建兩個(gè)新的，日儲(chǔ)量各為20t，問(wèn)應(yīng)建在何處，節(jié)省的噸千米數(shù)有多大？（一）建立模型 記工地的位置為(ai，bi)，水泥日用量為di，i=1,6;料場(chǎng)位置為(xj，yj)

27、，日儲(chǔ)量為ej，j=1,2；料場(chǎng)j向工地i的運(yùn)送量為Xij當(dāng)用臨時(shí)料場(chǎng)時(shí)決策變量為：Xij，當(dāng)不用臨時(shí)料場(chǎng)時(shí)決策變量為：Xij，xj，yj多目標(biāo)規(guī)劃引例1.投資問(wèn)題 某公司在一段時(shí)間內(nèi)有a(億元)的資金可用于建廠投資。若可供選擇的項(xiàng)目記為1,2,m。而且一旦對(duì)第i個(gè)項(xiàng)目投資就用去ai億元；而這段時(shí)間內(nèi)可得收益ci億元。問(wèn)如何確定最佳的投資方案？1i0iix對(duì)第 個(gè)項(xiàng)目投資不對(duì)第 個(gè)項(xiàng)目投資 最佳投資方案：投資最少，收益最大！投資最少：1121min( ,.,)mniiif x xxa x2121max( ,.,)mniiifx xxc x約束條件為：1(1)0,1,2,.miiiiia xax

28、xim收益最大：引例2：生產(chǎn)問(wèn)題 某工廠生產(chǎn)兩種產(chǎn)品，產(chǎn)品A每單位利潤(rùn)為10元，而產(chǎn)品B每單位利潤(rùn)為8元；產(chǎn)品A每單位需3小時(shí)裝配時(shí)間而B(niǎo)為2小時(shí)，每周總裝配有效時(shí)間為120小時(shí)。工廠允許加班，但加班生產(chǎn)出來(lái)的產(chǎn)品利潤(rùn)要減去1元。根據(jù)最近的合同，廠商每周最少的向用戶(hù)提供兩種產(chǎn)品各30單位。要求：必須遵守合同；盡可能少加班；利潤(rùn)最大。問(wèn)應(yīng)怎樣安排生產(chǎn)？x1：每周正常時(shí)間生產(chǎn)得A產(chǎn)品的數(shù)量；x2：每周加班時(shí)間生產(chǎn)得A產(chǎn)品的數(shù)量；x3：每周正常時(shí)間生產(chǎn)得B產(chǎn)品的數(shù)量；x4：每周加班時(shí)間生產(chǎn)得B產(chǎn)品的數(shù)量；目標(biāo)函數(shù)（有兩個(gè)）：1234max10987xxxx24min32xx1234133030. .

29、321200,1,2,3,4ixxxxstxxxi kX1kXkPkt0X10 1 2kkkkXXt Pk， ，011()()()()kkf Xf Xf Xf X0 1 2kXD k， ，*X*lim | 0kkXX0k*1*|lim|kkkXXqXXkX0q0, 1qkX0, 21q0, 1qkX2kX|1kkXX1| )(|1kXf| )()(|1kkXfXf1| )(|1kXf|)()()(|11kkkXfXfXf)(1kXf0X0kkPkt)()(kkkkXfPtXfkkkkPtXX11kX1kX)(1kXf1 kkNYX是否滿(mǎn)足終止準(zhǔn)則輸出X，f(X)開(kāi)始結(jié)束選定X0確定P確定t，使

30、得f(X0+tP)0，加步系數(shù)1，令k=00=(t0)，比較目標(biāo)函數(shù)值tk+1=tk+hk, k+1=(tk+1) a=mint，tk+1b=maxt，tk+1結(jié)束NYNY k+1khk+1=hk,t=tk ,tk=tk+1 ,k=k+1,k=k+1k=0hk = hk ,k=k+1 在加步探索法中，一般建議 若能估計(jì)問(wèn)題（4.3）的最優(yōu)解的大體位置的話(huà)，初始點(diǎn)要盡量取接近于問(wèn)題（4.3）的最優(yōu)解. 在具體運(yùn)用上述加步探索法時(shí)，有時(shí)還要考慮一些細(xì)節(jié)問(wèn)題例如，當(dāng)探索得到新點(diǎn)處的目標(biāo)函數(shù)值和出發(fā)點(diǎn)處相同時(shí)，以及初始步長(zhǎng)應(yīng)如何選取等，都需作適當(dāng)處理2, 由于以后要介紹的一些維搜索方法，主要適用于問(wèn)由

31、于以后要介紹的一些維搜索方法，主要適用于問(wèn)題（題（4.3）在搜索區(qū)間中只有唯一的最優(yōu)解的情況，為）在搜索區(qū)間中只有唯一的最優(yōu)解的情況，為此，我們?cè)俳o出下面單谷區(qū)間與單谷函數(shù)概念此，我們?cè)俳o出下面單谷區(qū)間與單谷函數(shù)概念 定義定義4.2 設(shè)設(shè) 閉區(qū)間閉區(qū)間 若存在點(diǎn)若存在點(diǎn) 使得使得 在在 上嚴(yán)格遞減，上嚴(yán)格遞減， 在在 上嚴(yán)格遞增，則上嚴(yán)格遞增，則稱(chēng)稱(chēng) 是函數(shù)是函數(shù) 的的單谷區(qū)間單谷區(qū)間， 是是 上上單谷函單谷函數(shù)數(shù) 11:,RR1 , ,a bR,*bat ( ) t* ,a t( ) t* , tb,ba)(t)(t,ba 由定義由定義4.2易知，一個(gè)區(qū)間是某函數(shù)的單谷區(qū)間意味著，易知，一個(gè)

32、區(qū)間是某函數(shù)的單谷區(qū)間意味著，在該區(qū)間中函數(shù)只有一個(gè)在該區(qū)間中函數(shù)只有一個(gè)“凹谷凹谷”（極小值）例如，（極小值）例如，左圖中的左圖中的 是是 的單谷區(qū)間，也即的單谷區(qū)間，也即 是是 上的單上的單谷函數(shù)右圖中的谷函數(shù)右圖中的 不是不是 的單谷區(qū)間，即的單谷區(qū)間，即 不不是是 上的單谷函數(shù)上的單谷函數(shù) ,ba)(t)(t,ba,ba)(t)(t,ba 另外，從定義另外，從定義4.2還可知，某區(qū)間上的單谷函數(shù)在該還可知，某區(qū)間上的單谷函數(shù)在該區(qū)間上不一定是連續(xù)函數(shù)，而凸函數(shù)在所給區(qū)間上必然區(qū)間上不一定是連續(xù)函數(shù)，而凸函數(shù)在所給區(qū)間上必然是單谷函數(shù)（如左圖所示）由定義是單谷函數(shù)（如左圖所示）由定義4.

33、1和定義和定義4.2知，知，函數(shù)的單谷區(qū)間總是相應(yīng)問(wèn)題（函數(shù)的單谷區(qū)間總是相應(yīng)問(wèn)題（4.3）的一個(gè)搜索區(qū)間）的一個(gè)搜索區(qū)間（如左圖所示），但反之不然（如右圖所示）（如左圖所示），但反之不然（如右圖所示）單谷區(qū)間和單谷函數(shù)有如下有用的性質(zhì)：定理4.1 設(shè) 是的單谷區(qū)間，任取 并且 （1）若有 ，則 是 的單谷區(qū)間（2）若有 ，則 是 的單谷區(qū)間定理4.1說(shuō)明，經(jīng)過(guò)函數(shù)值的比較可以把單谷區(qū)間縮短為一個(gè)較小的單谷區(qū)間換句話(huà)說(shuō)利用這個(gè)定理可以把搜索區(qū)間無(wú)限縮小，從而求到極小點(diǎn).以下介紹的幾種一維搜索方法都是利用這個(gè)定理通過(guò)不斷地縮短搜索區(qū)間的長(zhǎng)度，來(lái)求得一維最優(yōu)化問(wèn)題的近似最優(yōu)解, ,:11baRR

34、,21batt12tt)()(12tt,1ta)(t)()(12tt,2bt)(t 求解一維最優(yōu)化問(wèn)題求解一維最優(yōu)化問(wèn)題 一般可先確定它的一個(gè)有限一般可先確定它的一個(gè)有限搜索區(qū)間搜索區(qū)間 ，把問(wèn)題化為求解問(wèn)題，把問(wèn)題化為求解問(wèn)題 ，然后通，然后通過(guò)不斷縮短區(qū)間的長(zhǎng)度，最后求得最優(yōu)解過(guò)不斷縮短區(qū)間的長(zhǎng)度，最后求得最優(yōu)解min ( ) t,ba)(mintbta 設(shè)設(shè) 在已獲得的搜索區(qū)間在已獲得的搜索區(qū)間 內(nèi)具有連續(xù)的內(nèi)具有連續(xù)的一階導(dǎo)數(shù)因?yàn)橐浑A導(dǎo)數(shù)因?yàn)?在在 上可微，故上可微，故 在在 上連上連續(xù)，由此知續(xù)，由此知 在在 上有最小值上有最小值 令令 ，總可求得極小點(diǎn)，總可求得極小點(diǎn) 不妨設(shè)不妨設(shè)

35、 在在 上是單減函數(shù)；在上是單減函數(shù)；在 上是單增函數(shù)。所以上是單增函數(shù)。所以 時(shí)，時(shí)， ，故，故 ；當(dāng)；當(dāng) 時(shí)，時(shí)， 亦即亦即 對(duì)分法的原理如圖對(duì)分法的原理如圖 0)( t*t)(t),(*ta),(*bt*( ,)ta t0)( t0)( a),(*btt0)( t0)( b11RR ：,ba)(t,ba)(t,ba)(t,ba已知已知 ， 表達(dá)式，終止限表達(dá)式，終止限 確定初始搜索區(qū)間確定初始搜索區(qū)間 ，要求，要求(2) 計(jì)算計(jì)算 的中點(diǎn)的中點(diǎn) (3) 若若 ，則，則 ，轉(zhuǎn)，轉(zhuǎn)(4)(4)； 若若 ，則，則 ，轉(zhuǎn)，轉(zhuǎn)(5)(5)； 若若 ，則，則 ，轉(zhuǎn)，轉(zhuǎn)(4)(4)(4) 若若 ，則，

36、則 ，轉(zhuǎn)，轉(zhuǎn)(5)(5)；否則轉(zhuǎn)；否則轉(zhuǎn)(2)(2)(5) 打印打印 ，停機(jī)，停機(jī))(t)(t,ba( )0( )0ab，,ba)(21bac0)( cca 0)( cct *0)( ccb |ba)(21*bat*tY開(kāi)始確定ab,要求c=(a+b)/2b=ct*=(a+b)/2輸出t*結(jié)束T*=cNa=cNYNY對(duì)分法的計(jì)算流程如圖所示( )0( )0ab，0)( c( )0c|ba 對(duì)分法每次迭代都取區(qū)間的中點(diǎn)對(duì)分法每次迭代都取區(qū)間的中點(diǎn) a.若這點(diǎn)的導(dǎo)數(shù)值小于零，說(shuō)明的根位于右半?yún)^(qū)間中，因若這點(diǎn)的導(dǎo)數(shù)值小于零，說(shuō)明的根位于右半?yún)^(qū)間中，因此去掉左半?yún)^(qū)間；此去掉左半?yún)^(qū)間；b.若中點(diǎn)導(dǎo)數(shù)值大

37、于零，則去掉右半?yún)^(qū)間；若中點(diǎn)導(dǎo)數(shù)值大于零，則去掉右半?yún)^(qū)間；c.若中點(diǎn)導(dǎo)數(shù)值正好等于零，則該點(diǎn)就是極小點(diǎn)若中點(diǎn)導(dǎo)數(shù)值正好等于零，則該點(diǎn)就是極小點(diǎn) 因?yàn)槊看蔚际乖瓍^(qū)間縮短一半，所以稱(chēng)為對(duì)分法或因?yàn)槊看蔚际乖瓍^(qū)間縮短一半，所以稱(chēng)為對(duì)分法或二分法二分法 設(shè)設(shè) 在已獲得的搜索區(qū)間在已獲得的搜索區(qū)間 內(nèi)具有連續(xù)二內(nèi)具有連續(xù)二階導(dǎo)數(shù)，求階導(dǎo)數(shù)，求 因?yàn)橐驗(yàn)?在在 上可微，故上可微，故 在在 上有最小值，上有最小值，令令 11:RR ,ba)(mintbta)(t,ba)(t,ba0)( t 下面不妨設(shè)在區(qū)間下面不妨設(shè)在區(qū)間 中經(jīng)過(guò)中經(jīng)過(guò) 次迭代已求得方程次迭代已求得方程 的一個(gè)近似根的一個(gè)近似根 。

38、過(guò)。過(guò) 作曲線(xiàn)作曲線(xiàn) 的的切線(xiàn)切線(xiàn) ,其方程是其方程是 然后用這條切線(xiàn)與橫軸交點(diǎn)的橫坐標(biāo)然后用這條切線(xiàn)與橫軸交點(diǎn)的橫坐標(biāo) 作為根的新的作為根的新的近似（如圖）它可由方程（近似（如圖）它可由方程（4.4）在令）在令 的解出來(lái)，的解出來(lái)，即即 這就是這就是Newton切線(xiàn)法迭代公式切線(xiàn)法迭代公式 1kt0y)()(1kkkktttt 0)( t,bakkt)(,(kktt)(ty( )( )()4.4kkkytttt已知已知 ， 表達(dá)式，終止限表達(dá)式，終止限 確定初始搜索區(qū)間確定初始搜索區(qū)間 ，要求，要求 選定選定 計(jì)算計(jì)算 若若 ，則，則 ，轉(zhuǎn)（，轉(zhuǎn)（3）；否則轉(zhuǎn)（）；否則轉(zhuǎn)（5） 打印打印 ，

39、停機(jī)，停機(jī)000( )/( )tttt|0tttt 0( )tt，)(t)(t,ba( )0( )0ab，0t000() /()tttt輸出*,t開(kāi)始結(jié)束0ttYN0tt*00,()ttt選定 t0,確定ab,要求( )0,( )0abNewton切線(xiàn)法的計(jì)算流程如圖所示 這種方法一旦用好，收斂速度是很高的如果初始點(diǎn)選這種方法一旦用好，收斂速度是很高的如果初始點(diǎn)選得適當(dāng)，通常經(jīng)過(guò)幾次迭代就可以得到滿(mǎn)足一般精度要得適當(dāng)，通常經(jīng)過(guò)幾次迭代就可以得到滿(mǎn)足一般精度要求的結(jié)果求的結(jié)果.但是它也有缺點(diǎn)：但是它也有缺點(diǎn)： 第一，需要求二階導(dǎo)數(shù)如果在多維最優(yōu)化問(wèn)題的一維第一，需要求二階導(dǎo)數(shù)如果在多維最優(yōu)化問(wèn)題

40、的一維搜索中使用這種方法，就要涉及搜索中使用這種方法，就要涉及Hesse矩陣，一般是難矩陣，一般是難于求出的于求出的第二，當(dāng)曲線(xiàn) 在 上有較復(fù)雜的彎曲時(shí)，這種方法也往往失效如圖(a)所示的迭代： 結(jié)果 跳出 .迭代或者發(fā)散，或者找到的根并不是我們想要的結(jié)果第三，即使曲線(xiàn)比較正常，在 中或者上凹或者下凹，初始點(diǎn)的選取也必須適當(dāng)在圖（b）的情況下，曲線(xiàn)上凹，應(yīng)選點(diǎn)b作為初始點(diǎn)；而在圖（c）的情況下，曲線(xiàn)下凹，應(yīng)選點(diǎn)a為初始點(diǎn)否則都可能失敗)(ty,ba012,ttt2t,ba,ba 要介紹黃金分割法有必要回顧一下古老的黃金分要介紹黃金分割法有必要回顧一下古老的黃金分割問(wèn)題。所謂黃金分割就是將一線(xiàn)段

41、分為二段的割問(wèn)題。所謂黃金分割就是將一線(xiàn)段分為二段的方法。這樣分后，要求整段長(zhǎng)方法。這樣分后，要求整段長(zhǎng)L與較長(zhǎng)段與較長(zhǎng)段x的比值的比值正好等于較長(zhǎng)段正好等于較長(zhǎng)段x與較短段與較短段 的比值的比值(如圖如圖)xL 于是于是 則則 解得解得 由此可見(jiàn)長(zhǎng)段的長(zhǎng)度應(yīng)為全長(zhǎng)的由此可見(jiàn)長(zhǎng)段的長(zhǎng)度應(yīng)為全長(zhǎng)的0.618倍，而倍，而短段的長(zhǎng)度應(yīng)為全長(zhǎng)的短段的長(zhǎng)度應(yīng)為全長(zhǎng)的0.382倍倍 因?yàn)楣糯娜藗冋J(rèn)為按因?yàn)楣糯娜藗冋J(rèn)為按0.618的比率來(lái)分割線(xiàn)的比率來(lái)分割線(xiàn)段是最協(xié)調(diào)，勝似黃金，故稱(chēng)之為黃金分割段是最協(xié)調(diào)，勝似黃金，故稱(chēng)之為黃金分割xLxxL022LLxxLLx618. 0215 用黃金分割法進(jìn)行一維搜

42、索，其基本思想是在單谷用黃金分割法進(jìn)行一維搜索，其基本思想是在單谷區(qū)間內(nèi)適當(dāng)插入兩點(diǎn)，由此把區(qū)間分為三段，然后區(qū)間內(nèi)適當(dāng)插入兩點(diǎn)，由此把區(qū)間分為三段，然后再通過(guò)比較這兩點(diǎn)函數(shù)值大小，就可以確定是刪去再通過(guò)比較這兩點(diǎn)函數(shù)值大小，就可以確定是刪去最左段還是最右段，或者同時(shí)刪去左右兩段保留中最左段還是最右段，或者同時(shí)刪去左右兩段保留中間段如此繼續(xù)下去可將單谷區(qū)間無(wú)限縮小間段如此繼續(xù)下去可將單谷區(qū)間無(wú)限縮小 現(xiàn)在提出一個(gè)問(wèn)題，就在 上如何選取二點(diǎn)使得迭代次數(shù)最小而區(qū)間縮短最快？要解決這個(gè)問(wèn)題，人們想到對(duì)區(qū)間 選二點(diǎn) 等價(jià)于將區(qū)間長(zhǎng)度 進(jìn)行黃金分割，也就是將第一個(gè)搜索點(diǎn) 取在 的0.618處，第二個(gè)搜索

43、點(diǎn) 取成 的對(duì)稱(chēng)點(diǎn)即 的0.382處（如圖所示） ,ba21, tt,baab 1t,ba2t1t,ba 即要求即要求 接著計(jì)算接著計(jì)算 與與 的值，并根據(jù)的值，并根據(jù) 與與 的值的值的大小關(guān)系分情況討論：的大小關(guān)系分情況討論： （1 1） 若若 ,說(shuō)明說(shuō)明 是好點(diǎn)，于是把區(qū)間是好點(diǎn)，于是把區(qū)間 劃掉，保留劃掉，保留 ，則，則 內(nèi)有一保留點(diǎn)內(nèi)有一保留點(diǎn) ，置新的，置新的區(qū)間區(qū)間 ； （2 2）若若 ，說(shuō)明，說(shuō)明 是好點(diǎn)，于是應(yīng)將是好點(diǎn)，于是應(yīng)將 劃 掉 ， 保 留劃 掉 ， 保 留 , 則則 內(nèi) 有 保 留 點(diǎn)內(nèi) 有 保 留 點(diǎn) , 置 新 的 區(qū)置 新 的 區(qū)間間 .)(618. 01aba

44、t)(382. 02abat)(1t)(2t)(1t)(2t)()(21tt1t,2ta,2bt,2bt1t112, , a btb)()(21tt2t,1bt,1ta,1ta2t111, , a ba t (3)(3)若若 則應(yīng)具體分析則應(yīng)具體分析,看極小點(diǎn)可能在哪一邊看極小點(diǎn)可能在哪一邊再?zèng)Q定取舍，在一般情況下，可同時(shí)劃掉再?zèng)Q定取舍，在一般情況下，可同時(shí)劃掉 和和 僅保留中間的僅保留中間的 重置新的區(qū)間重置新的區(qū)間 接下來(lái)是在留下的區(qū)間接下來(lái)是在留下的區(qū)間 內(nèi)找好點(diǎn)重復(fù)上面的內(nèi)找好點(diǎn)重復(fù)上面的步驟，直到搜索區(qū)間步驟，直到搜索區(qū)間 小于給定的允許誤差小于給定的允許誤差 為止。為止。 這樣就得

45、到黃金分割法迭代算法：這樣就得到黃金分割法迭代算法：12( )( ),tt,2ta,1bt,12tt1121 , , a btt,11ba,iiba0 已知已知 ，常數(shù)，常數(shù) 0.382，終止限，終止限 (1)(1)確定確定 的初始搜索區(qū)間的初始搜索區(qū)間 (2)(2)計(jì)算計(jì)算 (3)(3)計(jì)算計(jì)算 (4)(4) 若若 ,則打印則打印 ，停機(jī)；否則，轉(zhuǎn)，停機(jī)；否則，轉(zhuǎn)(5)(5) (5)(5) 判別是否滿(mǎn)足判別是否滿(mǎn)足 ：若滿(mǎn)足，則置：若滿(mǎn)足，則置 ， 然后轉(zhuǎn)然后轉(zhuǎn)(3)(3)；否則，置；否則，置 然后轉(zhuǎn)然后轉(zhuǎn)(4)(4) )(t)(t,ba)()(222tabat，1211( )tabtt，2

46、21*ttt2122121at tt，11212222()( )bt tttabat，|21tt*,t開(kāi) 始 確 定 a,b(51) / 22()tba22()12tabt11()t2212bttt*12() / 2ttt*()t結(jié) 束 N Y N Y 12tt11212,attt222(),()tbat12黃金分割法算法流程如圖所示12 黃金分割法是通過(guò)所選試點(diǎn)的函數(shù)值而逐步縮短單谷區(qū)黃金分割法是通過(guò)所選試點(diǎn)的函數(shù)值而逐步縮短單谷區(qū)間來(lái)搜索最優(yōu)點(diǎn)該方法適用于單谷區(qū)間上的任何函數(shù)，間來(lái)搜索最優(yōu)點(diǎn)該方法適用于單谷區(qū)間上的任何函數(shù)，甚至可以是不連續(xù)函數(shù)，因此這種算法屬于直接法，適甚至可以是不連續(xù)函

47、數(shù)，因此這種算法屬于直接法，適用相當(dāng)廣泛用相當(dāng)廣泛 考慮一維搜索問(wèn)題考慮一維搜索問(wèn)題 假設(shè)其中假設(shè)其中 是定義在區(qū)間是定義在區(qū)間 上的單峰函數(shù)首上的單峰函數(shù)首先用試探法在先用試探法在 上找一點(diǎn)上找一點(diǎn) ，使之滿(mǎn)足，使之滿(mǎn)足 )(min21tttt)(t,21tt,21tt0t)()()()(0201tttt， 通過(guò)目標(biāo)函數(shù)曲線(xiàn)上的三個(gè)點(diǎn)通過(guò)目標(biāo)函數(shù)曲線(xiàn)上的三個(gè)點(diǎn) 作它的二次擬合曲線(xiàn)（如圖所示）作它的二次擬合曲線(xiàn)（如圖所示） )(,(),(,(),(,(220011tttttt2210)(tataatP圖4.14 由于上述三個(gè)點(diǎn)既是目標(biāo)函數(shù)曲線(xiàn)由于上述三個(gè)點(diǎn)既是目標(biāo)函數(shù)曲線(xiàn) 上的點(diǎn)，又上的點(diǎn)，又

48、是二次擬合曲線(xiàn)是二次擬合曲線(xiàn) 上的點(diǎn)，故有方程組上的點(diǎn)，故有方程組 將方程組（將方程組（4.5）中的）中的 消去，得消去，得 )(t)(tP2101 12 112001 02 002201 22 22( )( )( )( )4.5( )( )P taata ttP taata ttP taata tt，0a22110210102210220202()()( )( )4.6()()( )( )a tta tttta tta tttt， 從方程組（從方程組（4.6）可解出待定系數(shù)）可解出待定系數(shù) 對(duì)于二次擬合函數(shù)對(duì)于二次擬合函數(shù) ，我們很容易求得，我們很容易求得它的極小值點(diǎn)令它的極小值點(diǎn)令 即即

49、， 從中解出從中解出 即為二次擬合函數(shù)即為二次擬合函數(shù) 的極小值點(diǎn)的極小值點(diǎn)22222202121010211002210212101022100221() ( )() ( )() ( )4.7()()()() ( )() ( )() ( )4.8()()()tttttttttatttttttttttttttatttttt2210)(tataatP0)(dttdP0221taa124.92ata )(tP 將式（將式（4.7）與式（）與式（4.8）代入式（）代入式（4.9）得）得 用區(qū)間用區(qū)間 上二次擬合函數(shù)上二次擬合函數(shù) 的這個(gè)極小值點(diǎn)的這個(gè)極小值點(diǎn) 作為目標(biāo)函數(shù)作為目標(biāo)函數(shù) 在該區(qū)間極小值點(diǎn)的一個(gè)估計(jì)值在該區(qū)間極小值點(diǎn)的一個(gè)估計(jì)值 若若 和和 已充分接近，即對(duì)給定的允許誤差已充分接近，即對(duì)給定的允許誤差 使使 成立時(shí)，成立時(shí)