最優(yōu)化建模培訓(xùn)課件

最優(yōu)化（一）

一最優(yōu)化問題總論二一維搜索法三常用無約束最優(yōu)化方法四常用約束最優(yōu)化方法五程序設(shè)計(jì)及其他優(yōu)化方法最優(yōu)化（一）

一最優(yōu)化問題總論一最優(yōu)化問題總論

無論做任何一件事，人們總希望以最少的代價(jià)取得最大的效益，也就是力求最好，這就是優(yōu)化問題．最優(yōu)化就是在一切可能的方案中選擇一個(gè)最好的方案以達(dá)到最優(yōu)目標(biāo)的學(xué)科．例如，從甲地到乙地有公路、水路、鐵路、航空四種走法，如果我們追求的目標(biāo)是省錢，那么只要比較一下這四種走法的票價(jià)，從中選擇最便宜的那一種走法就達(dá)到目標(biāo)．這是最簡(jiǎn)單的最優(yōu)化問題，實(shí)際優(yōu)化問題一般都比較復(fù)雜．一最優(yōu)化問題總論

無論做任何一件事，人們總希望以最概括地說，凡是追求最優(yōu)目標(biāo)的數(shù)學(xué)問題都屬于最優(yōu)化問題作為最優(yōu)化問題，一般要有三個(gè)要素：第一是目標(biāo)；第二是方案；第三是限制條件．而且目標(biāo)應(yīng)是方案的“函數(shù)”．如果方案與時(shí)間無關(guān)，則該問題屬于靜態(tài)最優(yōu)化問題；否則稱為動(dòng)態(tài)最優(yōu)化問題本書只討論靜態(tài)最優(yōu)化問題．一最優(yōu)化問題總論

概括地說，凡是追求最優(yōu)目標(biāo)的數(shù)學(xué)問一最優(yōu)化問題總論

最簡(jiǎn)單的最優(yōu)化問題實(shí)際上在高等數(shù)學(xué)中已遇到，這就是所謂函數(shù)極值，我們習(xí)慣上又稱之為經(jīng)典極值問題．例1.1對(duì)邊長(zhǎng)為a的正方形鐵板，在四個(gè)角處剪去相等的正方形以制成方形無蓋水槽，問如何剪法使水槽的容積最大？一最優(yōu)化問題總論

最簡(jiǎn)單的最優(yōu)化問題實(shí)際上在高等數(shù)學(xué)一最優(yōu)化問題總論

解設(shè)剪去的正方形邊長(zhǎng)為x，由題意易知，與此相應(yīng)的水槽容積為

令

得兩個(gè)駐點(diǎn)：

一最優(yōu)化問題總論

一最優(yōu)化問題總論

第一個(gè)駐點(diǎn)不合實(shí)際，這是因?yàn)榧羧?個(gè)邊長(zhǎng)為的正方形相當(dāng)于將鐵板全部剪去．現(xiàn)在來判斷第二個(gè)駐點(diǎn)是否為極大點(diǎn)．因?yàn)樗允菢O大點(diǎn)

結(jié)論是：每個(gè)角剪去邊長(zhǎng)為的正方形可使所制成的水槽容積最大．一最優(yōu)化問題總論

第一個(gè)駐點(diǎn)不合實(shí)際，這是因?yàn)榧羧?個(gè)邊長(zhǎng)為的正方形相例1.2

求側(cè)面積為常數(shù)體積最大的長(zhǎng)方體體積．解設(shè)長(zhǎng)方體的長(zhǎng)、寬、高分別為，，，體積為，則依題意知體積為限制條件為

由拉格朗日乘數(shù)法，考慮函數(shù)§1.1最優(yōu)化問題數(shù)學(xué)模型例1.2求側(cè)面積為常數(shù)體積最大的長(zhǎng)方體體積．§1.1最令由題意可知應(yīng)是正數(shù)，由此，將上面三個(gè)等式分別乘以，并利用已知條件得到§1.1最優(yōu)化問題數(shù)學(xué)模型令§1.1最優(yōu)化問題數(shù)學(xué)模型比較以上三式可得

從而x=y=z=a，右側(cè)面積固定的長(zhǎng)方體的最大體積客觀存在，因此側(cè)面積固定的長(zhǎng)方體中以正方體體積最大．一最優(yōu)化問題總論

從而x=y=z=a，右側(cè)面積固定的長(zhǎng)方體的最大體積例1.3

某單位擬建一排四間的停車房，平面位置如圖1.1所示．由于資金及材料的限制，圍墻和隔墻的總長(zhǎng)度不能超過40m，為使車房面積最大，應(yīng)如何選擇長(zhǎng)、寬尺寸？x1x2一最優(yōu)化問題總論

例1.3某單位擬建一排四間的停車房，平面位置如圖1.1所解設(shè)四間車房長(zhǎng)為，寬為．由題意可知面積為且變量，，應(yīng)滿足即求 ，一最優(yōu)化問題總論

解設(shè)四間車房長(zhǎng)為，寬為．由題意可知面積為

最優(yōu)化問題的數(shù)學(xué)模型包含有三個(gè)要求：即變量（又稱設(shè)計(jì)變量）、目標(biāo)函數(shù)、約束條件．

一、變量

二、目標(biāo)函數(shù)

三、約束條件

四、帶約束條件的優(yōu)化問題數(shù)學(xué)模型表示形式一最優(yōu)化問題總論

最優(yōu)化問題的數(shù)學(xué)模型包含有三個(gè)要求：即變一最優(yōu)化問題綜上所述，全書所要討論的問題是如下的（靜態(tài)）最優(yōu)化問題，其表示形式有三種：第一種最優(yōu)化問題表示形式為

第二種最優(yōu)化問題表示形式為

一最優(yōu)化問題總論

綜上所述，全書所要討論的問題是如下的（靜態(tài)）最優(yōu)化問題，其表第三種最優(yōu)化問題表示形式為

（1.1）

其中一最優(yōu)化問題總論

一最優(yōu)化問題總論

上述三種表示形式中，稱為集約束．在所討論的最優(yōu)化問題中，集約束是無關(guān)緊要的．這是因?yàn)橐话?，不然的話，通常也可用不等式約束表達(dá)出來．因此今后一般不再考慮集約束．滿足所有約束的點(diǎn)稱為容許點(diǎn)或可行點(diǎn)．容許點(diǎn)的集合稱為容許集或可行域．可用表示．一最優(yōu)化問題總論

上述三種表示形式中，稱為集約束．在所討論的最優(yōu)化問題一般地，對(duì)于最優(yōu)化問題（1.1）的求解，是指在可行域內(nèi)找一點(diǎn)，使得目標(biāo)函數(shù)在該點(diǎn)取得極小值，即這樣的稱為問題（1.1）的最優(yōu)點(diǎn)，也稱極小點(diǎn)，而相應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)值；合起來稱為最優(yōu)解，但習(xí)慣上把本身稱為最優(yōu)解．最優(yōu)點(diǎn)的各分量和最優(yōu)值必須是有限數(shù)．一最優(yōu)化問題總論

一般地，對(duì)于最優(yōu)化問題（1.1）的求解，是指在可行域內(nèi)一、二維最優(yōu)化問題的圖解法討論二維最優(yōu)化問題為一最優(yōu)化問題總論

一、二維最優(yōu)化問題的圖解法一最優(yōu)化問題總論

（一）約束集合當(dāng)約束函數(shù)為線性時(shí)，等式約束在坐標(biāo)平面上為一條直線，不等式約束在坐標(biāo)平面上為一半平面；當(dāng)約束函數(shù)為非線性時(shí)，等式約束條件在坐標(biāo)平面上為一條曲線（如圖），不等式約束把坐標(biāo)平面分成兩部分當(dāng)中的一部分（如圖）．

一最優(yōu)化問題總論

（一）約束集合一最優(yōu)化問題總論

綜上所述，當(dāng)把約束條件中的每一個(gè)等式所確定的曲線，以及每一個(gè)不等式所確定的部分在坐標(biāo)平面上畫出之后，它們相交的公共部分即為約束集合D．一最優(yōu)化問題總論

綜上所述，當(dāng)把約束條件中的每一個(gè)一最優(yōu)化問題總論

例1.4

在坐標(biāo)平面上畫出約束集合解:滿足的區(qū)域?yàn)橐栽c(diǎn)為圓心，半徑為1的圓；滿足的區(qū)域?yàn)榈谝幌笙薜纳刃危ㄈ鐖D所示）．一最優(yōu)化問題總論

例1.4在坐標(biāo)平面上畫出約束集合一最優(yōu)化問題總論

（二）等高線我們知道在三維空間中表示一張曲面．其中為常數(shù)）在三維空間中表示平行于平面的一個(gè)平面，這個(gè)平面上任何一點(diǎn)的高度都等于常數(shù)（如圖）．在三維空間中曲面與平面有一條交線．交線在平面上的投影曲線是，可見曲線上的點(diǎn)到平面的高度都等于常數(shù)C，也即曲線上的的函數(shù)值都具有相同的值．一最優(yōu)化問題總論

（二）等高線一最優(yōu)化問題總論

當(dāng)常數(shù)取不同的值時(shí)，重復(fù)上面的討論，在平面上得到一族曲線——等高線.等高線的形狀完全由曲面的形狀所決定；反之，由等高線的形狀也可以推測(cè)出曲面的形狀．一最優(yōu)化問題總論

當(dāng)常數(shù)取不同的值時(shí)，重復(fù)上面的討論，在平面上得到例1.5

在坐標(biāo)平面上畫出目標(biāo)函數(shù)的等高線．

解:因?yàn)楫?dāng)取時(shí)，曲線表示是以原點(diǎn)為圓心，半徑為的圓．因此等高線是一族以原點(diǎn)為圓心的同心圓（如圖所示）

一最優(yōu)化問題總論

例1.5在坐標(biāo)平面上畫出目標(biāo)函數(shù)一最優(yōu)化

例1.6

用圖解法求解二維最優(yōu)化問題解:如圖，目標(biāo)函數(shù)的等高線是以為圓心的同心圓，并且這族同心圓的外圈比內(nèi)圈的目標(biāo)函數(shù)值大．因此，該問題為在約束集中找一點(diǎn),使其落在半徑最小的那個(gè)同心圓上。問題的最優(yōu)解為：一最優(yōu)化問題總論

例1.6用圖解法求解二維最優(yōu)化問題一最優(yōu)化問題總論二、最優(yōu)化問題的迭代解法

（一）迭代方法

在經(jīng)典極值問題中，解析法雖然具有概念簡(jiǎn)明,計(jì)算精確等優(yōu)點(diǎn)，但因只能適用于簡(jiǎn)單或特殊問題的尋優(yōu),對(duì)于復(fù)雜的工程實(shí)際問題通常無能為力，所以極少使用。最優(yōu)化問題的迭代算法是指：從某一選定的初始點(diǎn)出發(fā)，根據(jù)目標(biāo)函數(shù)、約束函數(shù)在該點(diǎn)的某些信息，確定本次迭代的一個(gè)搜索方向和適當(dāng)?shù)牟介L(zhǎng)，從而到達(dá)一個(gè)新點(diǎn)，用式子表示即為(1.2)一最優(yōu)化問題總論

二、最優(yōu)化問題的迭代解法

（一）迭代方法在經(jīng)典極

式中,——前一次已取得的迭代點(diǎn)，在開始計(jì)算時(shí)為迭代初始點(diǎn)；

——新的迭代點(diǎn)；

——第k次迭代計(jì)算的搜索方向；

——第k次迭代計(jì)算的步長(zhǎng)因子．一最優(yōu)化問題總論

按照式（1.2）進(jìn)行一系列迭代計(jì)算所根據(jù)的思想是所謂的“爬山法”，就是將尋求函數(shù)極小點(diǎn)（無約束或約束極小點(diǎn)）的過程比喻為向“山”的頂峰攀登的過程，始終保持向“高”的方向前進(jìn)，直至達(dá)到“山頂”．當(dāng)然“山頂”可以理解為目標(biāo)函數(shù)的極大值，也可以理解為極小值，前者稱為上升算法，后者稱為下降算法．這兩種算法都有一個(gè)共同的特點(diǎn)，就是每前進(jìn)一步都應(yīng)該使目標(biāo)函數(shù)有所改善，同時(shí)還要為下一步移動(dòng)的搜索方向提供有用的信息．如果是下降算法，則序列迭代點(diǎn)的目標(biāo)函數(shù)值必須滿足下列關(guān)系一最優(yōu)化問題總論

按照式（1.2）進(jìn)行一系列迭代計(jì)算所根據(jù)一最

如果是求一個(gè)約束的極小點(diǎn)，則每一次迭代的新點(diǎn)都應(yīng)該在約束可行域內(nèi)，即下圖為迭代過程一最優(yōu)化問題總論

如果是求一個(gè)約束的極小點(diǎn)，則每一次迭代的新點(diǎn)（二）收斂速度與計(jì)算終止準(zhǔn)則（1）收斂速度作為一個(gè)算法A，能夠收斂于問題的最優(yōu)解當(dāng)然是必要的，但光能收斂還不夠，還必須能以較快的速度收斂，這才是好的算法．定義1.1設(shè)由算法A產(chǎn)生的迭代點(diǎn)列在某種“||·||”的意義下收斂于點(diǎn)，即,若存在實(shí)數(shù)及一個(gè)與迭代次數(shù)無關(guān)的常數(shù)使得則算法A產(chǎn)生的迭代點(diǎn)列叫做具有階收斂速度,或算法A叫做是階收斂的，特別地:一最優(yōu)化問題總論

（二）收斂速度與計(jì)算終止準(zhǔn)則一最優(yōu)化問題總論

①當(dāng)，迭代點(diǎn)列稱為具有線性收斂速度或算法A稱為線性收斂的．②當(dāng)，或時(shí)，迭代點(diǎn)列叫做具有超線性收斂速度或稱算法A是超線性收斂．③當(dāng)時(shí)，迭代點(diǎn)列叫做具有二階收斂速度或算法A是二階收斂的．一般認(rèn)為，具有超線性收斂或二階收斂的算法是較快速的算法．一最優(yōu)化問題總論

①當(dāng)，迭代點(diǎn)列稱為具(2)計(jì)算終止準(zhǔn)則用迭代方法尋優(yōu)時(shí)，其迭代過程總不能無限制地進(jìn)行下去，那么什么時(shí)候截?cái)噙@種迭代呢？這就是迭代什么時(shí)候終止的問題．從理論上說，當(dāng)然希望最終迭代點(diǎn)到達(dá)理論極小點(diǎn)，或者使最終迭代點(diǎn)與理論極小點(diǎn)之間的距離足夠小時(shí)才終止迭代．但是這在實(shí)際上是辦不到的．因?yàn)閷?duì)于一個(gè)待求的優(yōu)化問題，其理論極小點(diǎn)在哪里并不知道．所知道的只是通過迭代計(jì)算獲得的迭代點(diǎn)列，因此只能從點(diǎn)列所提供的信息來判斷是否應(yīng)該終止迭代．對(duì)于無約束優(yōu)化問題通常采用的迭代終止準(zhǔn)則有以下幾種：一最優(yōu)化問題總論

(2)計(jì)算終止準(zhǔn)則一最優(yōu)化問題總論

①點(diǎn)距準(zhǔn)則相鄰兩迭代點(diǎn)之間的距離已達(dá)到充分小，即式中是一個(gè)充分小正數(shù)，代表計(jì)算精度．②函數(shù)下降量準(zhǔn)則相鄰兩迭代點(diǎn)的函數(shù)值下降量已達(dá)到充分小．當(dāng)時(shí)，可用函數(shù)絕對(duì)下降量準(zhǔn)則當(dāng)時(shí)，可用函數(shù)相對(duì)下降量準(zhǔn)則③梯度準(zhǔn)則目標(biāo)函數(shù)在迭代點(diǎn)的梯度已達(dá)到充分小，即這一準(zhǔn)則對(duì)于定義域上的凸函數(shù)是完全正確的．若是非凸函數(shù)，有可能導(dǎo)致誤把駐點(diǎn)作為最優(yōu)點(diǎn)。對(duì)于約束優(yōu)化問題，不同的優(yōu)化方法有各自的終止準(zhǔn)則．一最優(yōu)化問題總論

①點(diǎn)距準(zhǔn)則一最優(yōu)化問題總論

綜上所述，優(yōu)化算法的基本迭代過程如下：①選定初始點(diǎn)，置．②按照某種規(guī)則確定搜索方向．③按某種規(guī)則確定使得④計(jì)算⑤判定是否滿足終止準(zhǔn)則．若滿足，則打印和,停機(jī)；否則置,轉(zhuǎn)②．一最優(yōu)化問題總論

綜上所述，優(yōu)化算法的基本迭代過程如下：一最優(yōu)化問題總論

NYX是否滿足終止準(zhǔn)則輸出X，f(X)開始結(jié)束選定X0確定P確定t，使得f(X0+tP)<f(X0)X=X0+tPX0=X上述算法框圖如右圖一最優(yōu)化問題總論

NYX是否滿足終止準(zhǔn)則輸出X，f(X)開始結(jié)束選定X0確定

就優(yōu)化機(jī)制與行為而分，目前工程中常用的優(yōu)化算法主要可分為：經(jīng)典算法、構(gòu)造型算法、改進(jìn)型算法、基于系統(tǒng)動(dòng)態(tài)演化的算法和混合型算法等．（1）經(jīng)典算法．包括線性規(guī)劃、動(dòng)態(tài)規(guī)劃、整數(shù)規(guī)劃和分枝定界等運(yùn)籌學(xué)中的傳統(tǒng)算法，其算法計(jì)算復(fù)雜性一般很大，只適于求解小規(guī)模問題，在工程中往往不實(shí)用．一最優(yōu)化問題總論

就優(yōu)化機(jī)制與行為而分，目前工程中常用的優(yōu)化算法主要可（2）構(gòu)造型算法．用構(gòu)造的方法快速建立問題的解，通常算法的優(yōu)化質(zhì)量差，難以滿足工程需要．譬如，調(diào)度問題中的典型構(gòu)造型方法有：Johnson法、Palmer法、Gupta法、CDS法、Daunenbring的快速接近法、NEH法等．（3）改進(jìn)型算法，或稱鄰域搜索算法．從任一解出發(fā)，對(duì)其鄰域的不斷搜索和當(dāng)前解的替換來實(shí)現(xiàn)優(yōu)化．根據(jù)搜索行為，它又可分為局部搜索法和指導(dǎo)性搜索法．一最優(yōu)化問題總論

（2）構(gòu)造型算法．用構(gòu)造的方法快速建立問題的解，通常算法的優(yōu)（4）基于系統(tǒng)動(dòng)態(tài)演化的算法．將優(yōu)化過程轉(zhuǎn)化為系統(tǒng)動(dòng)態(tài)的演化過程，基于系統(tǒng)動(dòng)態(tài)的演化來實(shí)現(xiàn)優(yōu)化，如神經(jīng)網(wǎng)絡(luò)和混沌搜索等．（5）混合型算法．指上述各算法從結(jié)構(gòu)或操作上相混合而產(chǎn)生的各類算法．優(yōu)化算法當(dāng)然還可以從別的角度進(jìn)行分類，如確定性算法和不確定性算法，局部?jī)?yōu)化算法和全局優(yōu)化算法等．一最優(yōu)化問題總論

（4）基于系統(tǒng)動(dòng)態(tài)演化的算法．將優(yōu)化過程轉(zhuǎn)化為系統(tǒng)動(dòng)態(tài)的演化一、組合優(yōu)化問題建模歸納而言，最優(yōu)化問題可分為函數(shù)優(yōu)化問題和組合優(yōu)化問題兩大類。上一節(jié)介紹的最優(yōu)化數(shù)學(xué)模型屬于函數(shù)優(yōu)化問題，該函數(shù)優(yōu)化的對(duì)象是一定區(qū)間內(nèi)的連續(xù)變量。本節(jié)重點(diǎn)介紹組合優(yōu)化問題，組合優(yōu)化的對(duì)象是解空間中的離散狀態(tài)．一最優(yōu)化問題總論

一、組合優(yōu)化問題建模一最優(yōu)化問題總論

組合優(yōu)化問題是通過對(duì)數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)編排、分組、次序或篩選等，所研究的問題涉及信息技術(shù)、經(jīng)濟(jì)管理、工業(yè)工程、交通運(yùn)輸、通信網(wǎng)絡(luò)等諸多領(lǐng)域，該問題數(shù)學(xué)模式可表示為其中，為目標(biāo)函數(shù)，為約束函數(shù)，X為決策變量，表示有限個(gè)點(diǎn)組成的集合．一最優(yōu)化問題總論

組合優(yōu)化問題是通過對(duì)數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)例1.9

0-1背包問題（knapsackproblem）

設(shè)有一個(gè)容積為b的背包，n個(gè)體積分別為，價(jià)值分別為的物品，如何以最大的價(jià)值裝包?該問題稱為0-1背包問題．用數(shù)學(xué)模型表示為

(1.3)其中目標(biāo)(1.3)欲使包內(nèi)所裝物品的價(jià)值最大；(1.4)為包的能力限制；(1.5)表示xi為二進(jìn)制變量，xi=1表示裝第i個(gè)物品，xi=0表示不裝．一最優(yōu)化問題總論

例1.90-1背包問題（knapsackproblem例1.10

旅行商問題(TSP，travelingsalesmanproblem)一個(gè)商人欲到個(gè)城市推銷商品，每?jī)蓚€(gè)城市i和j之間的距離為，如何選擇一條道路使得商人每個(gè)城市走一遍后回到起點(diǎn)且所走路徑最短．TSP還可以細(xì)分為對(duì)稱和非對(duì)稱距離兩大類問題．當(dāng)對(duì)任意的I,j時(shí)都有,則稱該TSP為對(duì)稱距離TSP，否則稱非對(duì)稱距離TSP．

一最優(yōu)化問題總論

例1.10旅行商問題(TSP，travelingsale對(duì)一般的TSP，它的一種數(shù)學(xué)模型描述

一最優(yōu)化問題總論

對(duì)一般的TSP，它的一種數(shù)學(xué)模型描述一最優(yōu)化問題總論

以上是基于圖論的數(shù)學(xué)模型．式（1.10）中的決策變量表示商人行走的路線包含從城市i到城市路徑，表示商人沒有選擇走這條路．的約束可以減少變量的個(gè)數(shù)，使得共有個(gè)決策變量;目標(biāo)（1.6）要求距離之和最小;式（1.7）要求商人從城市出來一次;式（1.8）要求商人走入城市只有一次;式（1.7）和式（1.8）表示每個(gè)城市經(jīng)過一次;僅有式（1.7）和式（1.8）的約束無法避免回路的產(chǎn)生，一條回路是由個(gè)城市和k條弧組成，式（1.9）約束旅行商在任何一個(gè)城市子集中不形成回路，其中|S|表示集合S中元素個(gè)數(shù)．一最優(yōu)化問題總論

以上是基于圖論的數(shù)學(xué)模型．一最優(yōu)化問題總論

例1.11

聚類問題

m維空間上的n個(gè)模式要求聚類成k類，使得各類本身內(nèi)的點(diǎn)最相近，即

其中為第p類的中心，為第p類中的點(diǎn)數(shù)．一最優(yōu)化問題總論

例1.11聚類問題一最優(yōu)化問題總論

二一維搜索法§搜索區(qū)間及其確定方法§

對(duì)分法§Newton切線法§

黃金分割法§拋物線插值法二一維搜索法§搜索區(qū)間及其確定方法

由第一章關(guān)于求解最優(yōu)化問題概述中我們知道，從已知迭代點(diǎn)出發(fā)按照基本迭代格式來求解最優(yōu)化問題，其關(guān)鍵在于如何構(gòu)造一個(gè)搜索方向和確定一個(gè)步長(zhǎng)使下一迭代點(diǎn)處的目標(biāo)函數(shù)值下降，即現(xiàn)在我們來討論，當(dāng)搜索方向已經(jīng)確定的情況下，如何來確定步長(zhǎng)？

步長(zhǎng)因子的選取有多種方法，如取步長(zhǎng)為常數(shù)，但這樣選取的步長(zhǎng)并不最好，如何選取最好步長(zhǎng)呢？實(shí)際計(jì)算通常采用一維搜索來確定最優(yōu)步長(zhǎng)．二一維搜索法由第一章關(guān)于求解最優(yōu)化問題概述中我們知道，從

對(duì)無約束最優(yōu)化問題當(dāng)已知迭代點(diǎn)和下降方向時(shí)，要確定適當(dāng)?shù)牟介L(zhǎng)使

比有所下降，即相當(dāng)于對(duì)于參量的函數(shù)要在區(qū)間上選取使即．由于這種從已知點(diǎn)出發(fā)，沿某一下降的探索方向來確定步長(zhǎng)的問題，實(shí)質(zhì)上是單變量函數(shù)關(guān)于變量的一維搜索選取問題，故通常叫做一維搜索．

二一維搜索法對(duì)無約束最優(yōu)化問題二一維搜索法按這種方法確定的步長(zhǎng)又稱為最優(yōu)步長(zhǎng),這種方法的優(yōu)點(diǎn)是:它使目標(biāo)函數(shù)值在搜索方向上下降得最多．今后為了簡(jiǎn)便起見，我們用記號(hào)

表示從點(diǎn)

出發(fā)沿方向?qū)δ繕?biāo)函數(shù)作直線搜索所得到的極小點(diǎn)是

其中l(wèi)和s分別是Linearsearch(直線搜索)兩詞的詞首,在目標(biāo)函數(shù)已確定的條件下(4.1)等價(jià)于如下兩式：二一維搜索法按這種方法確定的步長(zhǎng)又稱為最優(yōu)步長(zhǎng),這種方法的優(yōu)點(diǎn)是:它下面進(jìn)一步解釋迭代點(diǎn)的空間位置．容易證明，若從出發(fā)，沿方向進(jìn)步一維搜索得極小點(diǎn)

則該點(diǎn)處的梯度方向與搜索方向之間應(yīng)滿足事實(shí)上，設(shè)對(duì)求導(dǎo)有令即所以二一維搜索法下面進(jìn)一步解釋迭代點(diǎn)式（4.2）的幾何意義是明顯的:從某一點(diǎn)出發(fā)沿方向?qū)δ?/p>

標(biāo)函數(shù)作直線搜索,所得到

的極小點(diǎn)為式（4.2）指出，

梯度必與搜索方向正交.又因?yàn)榕c目標(biāo)函數(shù)過點(diǎn)的等值面正交，所以進(jìn)一步看到，搜索方向與這個(gè)等值面在點(diǎn)處相切（如圖所示）．

二一維搜索法式（4.2）的幾何意義是明顯的:二一維搜索法搜索區(qū)間及其確定方法

一、搜索區(qū)間

設(shè)一維最優(yōu)化問題為為了求解問題(4.3),我們引入如下的搜索區(qū)間概念．

定義4.1若存在閉區(qū)間使則稱是問題(4.3)的搜索區(qū)間．簡(jiǎn)言之，一個(gè)一維最優(yōu)化問題的搜索區(qū)間，就是包含該問題最優(yōu)解的一個(gè)閉區(qū)間．通常，在進(jìn)行一維搜索時(shí)，一般要先確定出問題的一個(gè)搜索區(qū)間，然后再此區(qū)間中進(jìn)行搜索求解．搜索區(qū)間及其確定方法一、搜索區(qū)間

二、加步探索法下面，介紹一個(gè)確定問題(4.3)的搜索區(qū)間的簡(jiǎn)單方法．這個(gè)方法的思想是：先選定一個(gè)初始點(diǎn)或和初始步長(zhǎng)然后，沿著軸的正方向探索前進(jìn)一個(gè)步長(zhǎng)，得到新點(diǎn)若目標(biāo)函數(shù)在新點(diǎn)處的值是下降了,即

則下一步就從新點(diǎn)出發(fā)加大步長(zhǎng)，再向前探索.若目標(biāo)函數(shù)在新點(diǎn)處的值上升,即則下一步仍以為出發(fā)點(diǎn)以原步長(zhǎng)開始向軸的負(fù)方向同樣探索．當(dāng)達(dá)到目標(biāo)函數(shù)上升的點(diǎn)時(shí)，就停止探索，這時(shí)便得到問題（4.3）的一個(gè)搜索區(qū)間．這種以加大步長(zhǎng)進(jìn)行探索來尋找探索區(qū)間的方法叫加步探索法．

搜索區(qū)間及其確定方法二、加步探索法搜索區(qū)間及其確定方法

加步探索法算法的計(jì)算步驟：(1)

選取初始數(shù)據(jù)．選取初始點(diǎn)計(jì)算給出初始步長(zhǎng)加步系數(shù)令(2)

比較目標(biāo)函數(shù)值．令計(jì)算，

若轉(zhuǎn)(3)．否則轉(zhuǎn)(4)．(3)加大探索步長(zhǎng),令同時(shí)令轉(zhuǎn)(2)．(4)反向探索,若轉(zhuǎn)換探索方向,令轉(zhuǎn)(2);否則,停止迭代,令輸出搜索區(qū)間及其確定方法加步探索法算法的計(jì)算步驟：搜索區(qū)間及其確定方法

加步探索法算法的流程圖如圖所示

開始選取初始點(diǎn)t0，初始步長(zhǎng)h0>0，加步系數(shù)α>1，令k=0φ0=φ(t0)，比較目標(biāo)函數(shù)值tk+1=tk+hk,φk+1=φ(tk+1)a=min{t，tk+1}b=max{t，tk+1}結(jié)束NYNYφk+1<φkhk+1=hk,t=tk,tk=tk+1,φk=φk+1,k=k+1k=0hk=－h(huán)k,k=k+1開始選取初始點(diǎn)t0，初始步長(zhǎng)h0>0，加步系數(shù)α>1

在加步探索法中，一般建議若能估計(jì)問題（4.3）的最優(yōu)解的大體位置的話，初始點(diǎn)要盡量取接近于問題（4.3）的最優(yōu)解.在具體運(yùn)用上述加步探索法時(shí)，有時(shí)還要考慮一些細(xì)節(jié)問題．例如，當(dāng)探索得到新點(diǎn)處的目標(biāo)函數(shù)值和出發(fā)點(diǎn)處相同時(shí)，以及初始步長(zhǎng)應(yīng)如何選取等，都需作適當(dāng)處理．搜索區(qū)間及其確定方法搜索區(qū)間及其確定方法

三、單谷區(qū)間與單谷函數(shù)由于以后要介紹的一些維搜索方法，主要適用于問題（4.3）在搜索區(qū)間中只有唯一的最優(yōu)解的情況，為此，我們?cè)俳o出下面單谷區(qū)間與單谷函數(shù)概念．定義4.2

設(shè)閉區(qū)間若存在點(diǎn)使得在上嚴(yán)格遞減，在上嚴(yán)格遞增，則稱

是函數(shù)的單谷區(qū)間，是上單谷函數(shù)．

搜索區(qū)間及其確定方法三、單谷區(qū)間與單谷函數(shù)搜索區(qū)間及其確定方法由定義4.2易知，一個(gè)區(qū)間是某函數(shù)的單谷區(qū)間意味著，在該區(qū)間中函數(shù)只有一個(gè)“凹谷”（極小值）．例如，左圖中的

是的單谷區(qū)間，也即是上的單谷函數(shù)．右圖中的不是的單谷區(qū)間，即不是上的單谷函數(shù)．

搜索區(qū)間及其確定方法由定義4.2易知，一個(gè)區(qū)間是某函數(shù)的單谷區(qū)間意味著，在該區(qū)間另外，從定義4.2還可知，某區(qū)間上的單谷函數(shù)在該區(qū)間上不一定是連續(xù)函數(shù)，而凸函數(shù)在所給區(qū)間上必然是單谷函數(shù)（如左圖所示）．由定義4.1和定義4.2知，函數(shù)的單谷區(qū)間總是相應(yīng)問題（4.3）的一個(gè)搜索區(qū)間（如左圖所示），但反之不然（如右圖所示）．搜索區(qū)間及其確定方法另外，從定義4.2還可知，某區(qū)間上的單谷函數(shù)在該區(qū)間上單谷區(qū)間和單谷函數(shù)有如下有用的性質(zhì)：定理4.1

設(shè)是的單谷區(qū)間，任取并且．（1）若有，則是的單谷區(qū)間．（2）若有，則是的單谷區(qū)間．定理4.1說明，經(jīng)過函數(shù)值的比較可以把單谷區(qū)間縮短為一個(gè)較小的單谷區(qū)間．換句話說利用這個(gè)定理可以把搜索區(qū)間無限縮小，從而求到極小點(diǎn).以下介紹的幾種一維搜索方法都是利用這個(gè)定理通過不斷地縮短搜索區(qū)間的長(zhǎng)度，來求得一維最優(yōu)化問題的近似最優(yōu)解．搜索區(qū)間及其確定方法單谷區(qū)間和單谷函數(shù)有如下有用的性質(zhì)：搜索區(qū)間及其確定方法一、對(duì)分法基本原理求解一維最優(yōu)化問題一般可先確定它的一個(gè)有限搜索區(qū)間，把問題化為求解問題，然后通過不斷縮短區(qū)間的長(zhǎng)度，最后求得最優(yōu)解．對(duì)分法一、對(duì)分法基本原理對(duì)分法設(shè)在已獲得的搜索區(qū)間內(nèi)具有連續(xù)的一階導(dǎo)數(shù)．因?yàn)樵谏峡晌?，故在上連續(xù)，由此知在上有最小值．令，總可求得極小點(diǎn)．不妨設(shè)在上是單減函數(shù)；在上是單增函數(shù)．所以時(shí)，，故；當(dāng)時(shí)，亦即．對(duì)分法的原理如圖．

對(duì)分法設(shè)在已獲得的搜索區(qū)間二、對(duì)分法迭代步驟已知，表達(dá)式，終止限．確定初始搜索區(qū)間，要求(2)計(jì)算的中點(diǎn)．(3)若，則，轉(zhuǎn)(4)；

若，則，轉(zhuǎn)(5)；

若，則，轉(zhuǎn)(4)．(4)若，則，轉(zhuǎn)(5)；否則轉(zhuǎn)(2)．(5)打印，停機(jī)．對(duì)分法二、對(duì)分法迭代步驟對(duì)分法Y開始確定[ab],要求c=(a+b)/2b=ct*=(a+b)/2輸出t*結(jié)束T*=cNa=cNYNY對(duì)分法的計(jì)算流程如圖所示Y開始確定[ab],要求c=(a+b)/2b=ct*=(a三、對(duì)分法有關(guān)說明對(duì)分法每次迭代都取區(qū)間的中點(diǎn)a.若這點(diǎn)的導(dǎo)數(shù)值小于零，說明的根位于右半?yún)^(qū)間中，因此去掉左半?yún)^(qū)間；b.若中點(diǎn)導(dǎo)數(shù)值大于零，則去掉右半?yún)^(qū)間；c.若中點(diǎn)導(dǎo)數(shù)值正好等于零，則該點(diǎn)就是極小點(diǎn)．因?yàn)槊看蔚际乖瓍^(qū)間縮短一半，所以稱為對(duì)分法或二分法．對(duì)分法三、對(duì)分法有關(guān)說明對(duì)分法Newton切線法一、Newton切線法基本原理設(shè)在已獲得的搜索區(qū)間內(nèi)具有連續(xù)二階導(dǎo)數(shù)，求．因?yàn)樵谏峡晌?，故在上有最小值，令．Newton切線法一、Newton切線法基本原理下面不妨設(shè)在區(qū)間中經(jīng)過次迭代已求得方程

的一個(gè)近似根．過作曲線的切線,其方程是

然后用這條切線與橫軸交點(diǎn)的橫坐標(biāo)作為根的新的近似（如圖）．它可由方程（4.4）在令的解出來，即這就是Newton切線法迭代公式．

Newton切線法下面不妨設(shè)在區(qū)間中經(jīng)過次迭代已求得方程二、Newton切線法迭代步驟已知，表達(dá)式，終止限．確定初始搜索區(qū)間，要求

選定．計(jì)算．若，則，轉(zhuǎn)（3）；否則轉(zhuǎn)（5）．打印，停機(jī)．Newton切線法二、Newton切線法迭代步驟Newton切線法Newton切線法的計(jì)算流程如圖所示Newton切線法的計(jì)算流程如圖所示

三、Newton切線法有關(guān)說明這種方法一旦用好，收斂速度是很高的．如果初始點(diǎn)選得適當(dāng)，通常經(jīng)過幾次迭代就可以得到滿足一般精度要求的結(jié)果.但是它也有缺點(diǎn)：第一，需要求二階導(dǎo)數(shù)．如果在多維最優(yōu)化問題的一維搜索中使用這種方法，就要涉及Hesse矩陣，一般是難于求出的．Newton切線法三、Newton切線法有關(guān)說明Newton切線法第二，當(dāng)曲線在上有較復(fù)雜的彎曲時(shí)，這種方法也往往失效．如圖(a)所示的迭代：結(jié)果跳出.迭代或者發(fā)散，或者找到的根并不是我們想要的結(jié)果．第三，即使曲線比較正常，在中或者上凹或者下凹，初始點(diǎn)的選取也必須適當(dāng)．在圖（b）的情況下，曲線上凹，應(yīng)選點(diǎn)b作為初始點(diǎn)；而在圖（c）的情況下，曲線下凹，應(yīng)選點(diǎn)a為初始點(diǎn)．否則都可能失敗．Newton切線法第二，當(dāng)曲線在上有較復(fù)黃金分割法一、黃金分割法基本原理要介紹黃金分割法有必要回顧一下古老的黃金分割問題．所謂黃金分割就是將一線段分為二段的方法．這樣分后，要求整段長(zhǎng)L與較長(zhǎng)段x的比值正好等于較長(zhǎng)段x與較短段的比值(如圖)黃金分割法一、黃金分割法基本原理于是則解得由此可見長(zhǎng)段的長(zhǎng)度應(yīng)為全長(zhǎng)的0.618倍，而短段的長(zhǎng)度應(yīng)為全長(zhǎng)的0.382倍．因?yàn)楣糯娜藗冋J(rèn)為按0.618的比率來分割線段是最協(xié)調(diào)，勝似黃金，故稱之為黃金分割．黃金分割法于是黃金分割法用黃金分割法進(jìn)行一維搜索，其基本思想是在單谷區(qū)間內(nèi)適當(dāng)插入兩點(diǎn)，由此把區(qū)間分為三段，然后再通過比較這兩點(diǎn)函數(shù)值大小，就可以確定是刪去最左段還是最右段，或者同時(shí)刪去左右兩段保留中間段．如此繼續(xù)下去可將單谷區(qū)間無限縮?。S金分割法用黃金分割法進(jìn)行一維搜索，其基本思想是在單谷區(qū)間內(nèi)適當(dāng)插二、黃金分割法迭代步驟現(xiàn)在提出一個(gè)問題，就在上如何選取二點(diǎn)使得迭代次數(shù)最小而區(qū)間縮短最快？要解決這個(gè)問題，人們想到對(duì)區(qū)間選二點(diǎn)等價(jià)于將區(qū)間長(zhǎng)度進(jìn)行黃金分割，也就是將第一個(gè)搜索點(diǎn)取在的0.618處，第二個(gè)搜索點(diǎn)取成的對(duì)稱點(diǎn)即的0.382處（如圖所示）

黃金分割法二、黃金分割法迭代步驟黃金分割法即要求接著計(jì)算與的值，并根據(jù)與的值的大小關(guān)系分情況討論：（1）若,說明是好點(diǎn)，于是把區(qū)間劃掉，保留，則內(nèi)有一保留點(diǎn)，置新的區(qū)間；（2）若，說明是好點(diǎn)，于是應(yīng)將劃掉，保留,則內(nèi)有保留點(diǎn),置新的區(qū)間．.黃金分割法即要求黃金分割法(3)若則應(yīng)具體分析,看極小點(diǎn)可能在哪一邊再?zèng)Q定取舍，在一般情況下，可同時(shí)劃掉和

僅保留中間的重置新的區(qū)間．接下來是在留下的區(qū)間內(nèi)找好點(diǎn)．重復(fù)上面的步驟，直到搜索區(qū)間小于給定的允許誤差為止。這樣就得到黃金分割法迭代算法：黃金分割法(3)若則應(yīng)具體分析,看極小已知，常數(shù)0.382，終止限．(1)確定的初始搜索區(qū)間．(2)計(jì)算．(3)計(jì)算．(4)

若,則打印，停機(jī)；否則，轉(zhuǎn)(5)．(5)

判別是否滿足：若滿足，則置，然后轉(zhuǎn)(3)；否則，置，然后轉(zhuǎn)(4)．

黃金分割法已知，常數(shù)0.382，終止限．黃黃金分割法算法流程如圖所示．黃金分割法算法流程如圖所示．

三、黃金分割法有關(guān)說明黃金分割法是通過所選試點(diǎn)的函數(shù)值而逐步縮短單谷區(qū)間來搜索最優(yōu)點(diǎn)．該方法適用于單谷區(qū)間上的任何函數(shù)，甚至可以是不連續(xù)函數(shù)，因此這種算法屬于直接法，適用相當(dāng)廣泛．

黃金分割法三、黃金分割法有關(guān)說明黃金分割法

拋物線插值法一、拋物線插值法基本原理考慮一維搜索問題假設(shè)其中是定義在區(qū)間上的單峰函數(shù)．首先用試探法在上找一點(diǎn)，使之滿足．拋物線插值法一、拋物線插值法基本原理

通過目標(biāo)函數(shù)曲線上的三個(gè)點(diǎn)

作它的二次擬合曲線（如圖所示）．

圖4.14

拋物線插值法通過目標(biāo)函數(shù)曲線上的三個(gè)點(diǎn)圖4.14拋物線插值

由于上述三個(gè)點(diǎn)既是目標(biāo)函數(shù)曲線上的點(diǎn)，又是二次擬合曲線上的點(diǎn)，故有方程組

將方程組（4.5）中的消去，得

拋物線插值法由于上述三個(gè)點(diǎn)既是目標(biāo)函數(shù)曲線上的點(diǎn)，又是二次

從方程組（4.6）可解出待定系數(shù)

對(duì)于二次擬合函數(shù)，我們很容易求得它的極小值點(diǎn)．令即，從中解出

即為二次擬合函數(shù)的極小值點(diǎn)．

拋物線插值法從方程組（4.6）可解出待定系數(shù)拋物線插值法將式（4.7）與式（4.8）代入式（4.9）得用區(qū)間上二次擬合函數(shù)的這個(gè)極小值點(diǎn)作為目標(biāo)函數(shù)在該區(qū)間極小值點(diǎn)的一個(gè)估計(jì)值．若和已充分接近，即對(duì)給定的允許誤差使成立時(shí)，就可被看作是在區(qū)間內(nèi)近似最優(yōu)解；否則應(yīng)縮短區(qū)間，按照值保持兩頭大、中間小的原則構(gòu)成新的三點(diǎn)，繼續(xù)上述過程，直至不等式（4.11）成立為止．

拋物線插值法將式（4.7）與式（4.8）代入式（4.9）得拋物線插值二、拋物線插值法迭代步驟下面具體介紹縮短區(qū)間,構(gòu)成新三點(diǎn)的方法．由式（4.10）得到的點(diǎn),在區(qū)間內(nèi)既可能在點(diǎn)的左側(cè)(即),又可能在的右側(cè)(即).分別對(duì)應(yīng)這兩種情形比較和的大小，又有等三種情形，故共有如下六種情況（如圖所示）：

拋物線插值法二、拋物線插值法迭代步驟拋物線插值法

拋物線插值法拋物線插值法（1）對(duì)于圖(a)的情況:因,所以相對(duì)為說是好點(diǎn)，故劃掉區(qū)間,保留為新區(qū)間，故置保持不變；（2）對(duì)于圖(b)的情況:因,所以相對(duì)來說是好點(diǎn)，故劃掉保留為新區(qū)間，故置與保持不變；（3）對(duì)于圖(c)的情況：因所以相對(duì)來說是好點(diǎn)，故劃掉,保留為新區(qū)間，故置

保持不變；

拋物線插值法（1）對(duì)于圖(a)的情況:因（4）對(duì)于圖(d)的情況:因所以相對(duì)來說是好點(diǎn)，故劃掉保留故置

，與保持不變．（5）對(duì)于圖(e)的情況：一般同時(shí)劃掉及僅留中間的，故置

（6）對(duì)于圖(f)的情況：一般同時(shí)劃掉及，僅留中間的，故置

拋物線插值法（4）對(duì)于圖(d)的情況:因通過上述討論,我們可直接給拋物線插值法的迭代流程圖.通過上述討論,我們可直接給拋物線插值法的迭代流程圖.

三、拋物線插值法有關(guān)說明拋物線插值法是多項(xiàng)式逼近法的一種．所謂多項(xiàng)式逼近，是利用目標(biāo)函數(shù)在若干點(diǎn)的函數(shù)值或?qū)?shù)值等信息，構(gòu)成一個(gè)與目標(biāo)函數(shù)相接近的低次插值多項(xiàng)式，用該多項(xiàng)式的最優(yōu)解作為目標(biāo)函數(shù)的近似最優(yōu)解．

拋物線插值法三、拋物線插值法有關(guān)說明拋物線插值法§習(xí)題

1．用加步探索法確定一維最優(yōu)化問題

的搜索區(qū)間，要求選取．2．用對(duì)分法求解

已知初始單谷區(qū)間，按精度計(jì)算．3．用Newton法求解

用第１題求得的區(qū)間，按精度計(jì)算．§習(xí)題1．用加步探索法確定一維最優(yōu)化問題４．用黃金分割法求解

已知初始單谷區(qū)間，按精度計(jì)算．５．用拋物線插值法求解

已知初始單谷區(qū)間．§習(xí)題

４．用黃金分割法求解§習(xí)題演講完畢，謝謝觀看！演講完畢，謝謝觀看！最優(yōu)化（一）

一最優(yōu)化問題總論二一維搜索法三常用無約束最優(yōu)化方法四常用約束最優(yōu)化方法五程序設(shè)計(jì)及其他優(yōu)化方法最優(yōu)化（一）

一最優(yōu)化問題總論一最優(yōu)化問題總論

無論做任何一件事，人們總希望以最少的代價(jià)取得最大的效益，也就是力求最好，這就是優(yōu)化問題．最優(yōu)化就是在一切可能的方案中選擇一個(gè)最好的方案以達(dá)到最優(yōu)目標(biāo)的學(xué)科．例如，從甲地到乙地有公路、水路、鐵路、航空四種走法，如果我們追求的目標(biāo)是省錢，那么只要比較一下這四種走法的票價(jià)，從中選擇最便宜的那一種走法就達(dá)到目標(biāo)．這是最簡(jiǎn)單的最優(yōu)化問題，實(shí)際優(yōu)化問題一般都比較復(fù)雜．一最優(yōu)化問題總論

無論做任何一件事，人們總希望以最概括地說，凡是追求最優(yōu)目標(biāo)的數(shù)學(xué)問題都屬于最優(yōu)化問題作為最優(yōu)化問題，一般要有三個(gè)要素：第一是目標(biāo)；第二是方案；第三是限制條件．而且目標(biāo)應(yīng)是方案的“函數(shù)”．如果方案與時(shí)間無關(guān)，則該問題屬于靜態(tài)最優(yōu)化問題；否則稱為動(dòng)態(tài)最優(yōu)化問題本書只討論靜態(tài)最優(yōu)化問題．一最優(yōu)化問題總論

概括地說，凡是追求最優(yōu)目標(biāo)的數(shù)學(xué)問一最優(yōu)化問題總論

最簡(jiǎn)單的最優(yōu)化問題實(shí)際上在高等數(shù)學(xué)中已遇到，這就是所謂函數(shù)極值，我們習(xí)慣上又稱之為經(jīng)典極值問題．例1.1對(duì)邊長(zhǎng)為a的正方形鐵板，在四個(gè)角處剪去相等的正方形以制成方形無蓋水槽，問如何剪法使水槽的容積最大？一最優(yōu)化問題總論

最簡(jiǎn)單的最優(yōu)化問題實(shí)際上在高等數(shù)學(xué)一最優(yōu)化問題總論

解設(shè)剪去的正方形邊長(zhǎng)為x，由題意易知，與此相應(yīng)的水槽容積為

令

得兩個(gè)駐點(diǎn)：

一最優(yōu)化問題總論

一最優(yōu)化問題總論

第一個(gè)駐點(diǎn)不合實(shí)際，這是因?yàn)榧羧?個(gè)邊長(zhǎng)為的正方形相當(dāng)于將鐵板全部剪去．現(xiàn)在來判斷第二個(gè)駐點(diǎn)是否為極大點(diǎn)．因?yàn)樗允菢O大點(diǎn)

結(jié)論是：每個(gè)角剪去邊長(zhǎng)為的正方形可使所制成的水槽容積最大．一最優(yōu)化問題總論

第一個(gè)駐點(diǎn)不合實(shí)際，這是因?yàn)榧羧?個(gè)邊長(zhǎng)為的正方形相例1.2

求側(cè)面積為常數(shù)體積最大的長(zhǎng)方體體積．解設(shè)長(zhǎng)方體的長(zhǎng)、寬、高分別為，，，體積為，則依題意知體積為限制條件為

由拉格朗日乘數(shù)法，考慮函數(shù)§1.1最優(yōu)化問題數(shù)學(xué)模型例1.2求側(cè)面積為常數(shù)體積最大的長(zhǎng)方體體積．§1.1最令由題意可知應(yīng)是正數(shù)，由此，將上面三個(gè)等式分別乘以，并利用已知條件得到§1.1最優(yōu)化問題數(shù)學(xué)模型令§1.1最優(yōu)化問題數(shù)學(xué)模型比較以上三式可得

從而x=y=z=a，右側(cè)面積固定的長(zhǎng)方體的最大體積客觀存在，因此側(cè)面積固定的長(zhǎng)方體中以正方體體積最大．一最優(yōu)化問題總論

從而x=y=z=a，右側(cè)面積固定的長(zhǎng)方體的最大體積例1.3

某單位擬建一排四間的停車房，平面位置如圖1.1所示．由于資金及材料的限制，圍墻和隔墻的總長(zhǎng)度不能超過40m，為使車房面積最大，應(yīng)如何選擇長(zhǎng)、寬尺寸？x1x2一最優(yōu)化問題總論

例1.3某單位擬建一排四間的停車房，平面位置如圖1.1所解設(shè)四間車房長(zhǎng)為，寬為．由題意可知面積為且變量，，應(yīng)滿足即求 ，一最優(yōu)化問題總論

解設(shè)四間車房長(zhǎng)為，寬為．由題意可知面積為

最優(yōu)化問題的數(shù)學(xué)模型包含有三個(gè)要求：即變量（又稱設(shè)計(jì)變量）、目標(biāo)函數(shù)、約束條件．

一、變量

二、目標(biāo)函數(shù)

三、約束條件

四、帶約束條件的優(yōu)化問題數(shù)學(xué)模型表示形式一最優(yōu)化問題總論

最優(yōu)化問題的數(shù)學(xué)模型包含有三個(gè)要求：即變一最優(yōu)化問題綜上所述，全書所要討論的問題是如下的（靜態(tài)）最優(yōu)化問題，其表示形式有三種：第一種最優(yōu)化問題表示形式為

第二種最優(yōu)化問題表示形式為

一最優(yōu)化問題總論

綜上所述，全書所要討論的問題是如下的（靜態(tài)）最優(yōu)化問題，其表第三種最優(yōu)化問題表示形式為

（1.1）

其中一最優(yōu)化問題總論

一最優(yōu)化問題總論

上述三種表示形式中，稱為集約束．在所討論的最優(yōu)化問題中，集約束是無關(guān)緊要的．這是因?yàn)橐话?，不然的話，通常也可用不等式約束表達(dá)出來．因此今后一般不再考慮集約束．滿足所有約束的點(diǎn)稱為容許點(diǎn)或可行點(diǎn)．容許點(diǎn)的集合稱為容許集或可行域．可用表示．一最優(yōu)化問題總論

上述三種表示形式中，稱為集約束．在所討論的最優(yōu)化問題一般地，對(duì)于最優(yōu)化問題（1.1）的求解，是指在可行域內(nèi)找一點(diǎn)，使得目標(biāo)函數(shù)在該點(diǎn)取得極小值，即這樣的稱為問題（1.1）的最優(yōu)點(diǎn)，也稱極小點(diǎn)，而相應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)值；合起來稱為最優(yōu)解，但習(xí)慣上把本身稱為最優(yōu)解．最優(yōu)點(diǎn)的各分量和最優(yōu)值必須是有限數(shù)．一最優(yōu)化問題總論

一般地，對(duì)于最優(yōu)化問題（1.1）的求解，是指在可行域內(nèi)一、二維最優(yōu)化問題的圖解法討論二維最優(yōu)化問題為一最優(yōu)化問題總論

一、二維最優(yōu)化問題的圖解法一最優(yōu)化問題總論

（一）約束集合當(dāng)約束函數(shù)為線性時(shí)，等式約束在坐標(biāo)平面上為一條直線，不等式約束在坐標(biāo)平面上為一半平面；當(dāng)約束函數(shù)為非線性時(shí)，等式約束條件在坐標(biāo)平面上為一條曲線（如圖），不等式約束把坐標(biāo)平面分成兩部分當(dāng)中的一部分（如圖）．

一最優(yōu)化問題總論

（一）約束集合一最優(yōu)化問題總論

綜上所述，當(dāng)把約束條件中的每一個(gè)等式所確定的曲線，以及每一個(gè)不等式所確定的部分在坐標(biāo)平面上畫出之后，它們相交的公共部分即為約束集合D．一最優(yōu)化問題總論

綜上所述，當(dāng)把約束條件中的每一個(gè)一最優(yōu)化問題總論

例1.4

在坐標(biāo)平面上畫出約束集合解:滿足的區(qū)域?yàn)橐栽c(diǎn)為圓心，半徑為1的圓；滿足的區(qū)域?yàn)榈谝幌笙薜纳刃危ㄈ鐖D所示）．一最優(yōu)化問題總論

例1.4在坐標(biāo)平面上畫出約束集合一最優(yōu)化問題總論

（二）等高線我們知道在三維空間中表示一張曲面．其中為常數(shù)）在三維空間中表示平行于平面的一個(gè)平面，這個(gè)平面上任何一點(diǎn)的高度都等于常數(shù)（如圖）．在三維空間中曲面與平面有一條交線．交線在平面上的投影曲線是，可見曲線上的點(diǎn)到平面的高度都等于常數(shù)C，也即曲線上的的函數(shù)值都具有相同的值．一最優(yōu)化問題總論

（二）等高線一最優(yōu)化問題總論

當(dāng)常數(shù)取不同的值時(shí)，重復(fù)上面的討論，在平面上得到一族曲線——等高線.等高線的形狀完全由曲面的形狀所決定；反之，由等高線的形狀也可以推測(cè)出曲面的形狀．一最優(yōu)化問題總論

當(dāng)常數(shù)取不同的值時(shí)，重復(fù)上面的討論，在平面上得到例1.5

在坐標(biāo)平面上畫出目標(biāo)函數(shù)的等高線．

解:因?yàn)楫?dāng)取時(shí)，曲線表示是以原點(diǎn)為圓心，半徑為的圓．因此等高線是一族以原點(diǎn)為圓心的同心圓（如圖所示）

一最優(yōu)化問題總論

例1.5在坐標(biāo)平面上畫出目標(biāo)函數(shù)一最優(yōu)化

例1.6

用圖解法求解二維最優(yōu)化問題解:如圖，目標(biāo)函數(shù)的等高線是以為圓心的同心圓，并且這族同心圓的外圈比內(nèi)圈的目標(biāo)函數(shù)值大．因此，該問題為在約束集中找一點(diǎn),使其落在半徑最小的那個(gè)同心圓上。問題的最優(yōu)解為：一最優(yōu)化問題總論

例1.6用圖解法求解二維最優(yōu)化問題一最優(yōu)化問題總論二、最優(yōu)化問題的迭代解法

（一）迭代方法

在經(jīng)典極值問題中，解析法雖然具有概念簡(jiǎn)明,計(jì)算精確等優(yōu)點(diǎn)，但因只能適用于簡(jiǎn)單或特殊問題的尋優(yōu),對(duì)于復(fù)雜的工程實(shí)際問題通常無能為力，所以極少使用。最優(yōu)化問題的迭代算法是指：從某一選定的初始點(diǎn)出發(fā)，根據(jù)目標(biāo)函數(shù)、約束函數(shù)在該點(diǎn)的某些信息，確定本次迭代的一個(gè)搜索方向和適當(dāng)?shù)牟介L(zhǎng)，從而到達(dá)一個(gè)新點(diǎn)，用式子表示即為(1.2)一最優(yōu)化問題總論

二、最優(yōu)化問題的迭代解法

（一）迭代方法在經(jīng)典極

式中,——前一次已取得的迭代點(diǎn)，在開始計(jì)算時(shí)為迭代初始點(diǎn)；

——新的迭代點(diǎn)；

——第k次迭代計(jì)算的搜索方向；

——第k次迭代計(jì)算的步長(zhǎng)因子．一最優(yōu)化問題總論

按照式（1.2）進(jìn)行一系列迭代計(jì)算所根據(jù)的思想是所謂的“爬山法”，就是將尋求函數(shù)極小點(diǎn)（無約束或約束極小點(diǎn)）的過程比喻為向“山”的頂峰攀登的過程，始終保持向“高”的方向前進(jìn)，直至達(dá)到“山頂”．當(dāng)然“山頂”可以理解為目標(biāo)函數(shù)的極大值，也可以理解為極小值，前者稱為上升算法，后者稱為下降算法．這兩種算法都有一個(gè)共同的特點(diǎn)，就是每前進(jìn)一步都應(yīng)該使目標(biāo)函數(shù)有所改善，同時(shí)還要為下一步移動(dòng)的搜索方向提供有用的信息．如果是下降算法，則序列迭代點(diǎn)的目標(biāo)函數(shù)值必須滿足下列關(guān)系一最優(yōu)化問題總論

按照式（1.2）進(jìn)行一系列迭代計(jì)算所根據(jù)一最

如果是求一個(gè)約束的極小點(diǎn)，則每一次迭代的新點(diǎn)都應(yīng)該在約束可行域內(nèi)，即下圖為迭代過程一最優(yōu)化問題總論

如果是求一個(gè)約束的極小點(diǎn)，則每一次迭代的新點(diǎn)（二）收斂速度與計(jì)算終止準(zhǔn)則（1）收斂速度作為一個(gè)算法A，能夠收斂于問題的最優(yōu)解當(dāng)然是必要的，但光能收斂還不夠，還必須能以較快的速度收斂，這才是好的算法．定義1.1設(shè)由算法A產(chǎn)生的迭代點(diǎn)列在某種“||·||”的意義下收斂于點(diǎn)，即,若存在實(shí)數(shù)及一個(gè)與迭代次數(shù)無關(guān)的常數(shù)使得則算法A產(chǎn)生的迭代點(diǎn)列叫做具有階收斂速度,或算法A叫做是階收斂的，特別地:一最優(yōu)化問題總論

（二）收斂速度與計(jì)算終止準(zhǔn)則一最優(yōu)化問題總論

①當(dāng)，迭代點(diǎn)列稱為具有線性收斂速度或算法A稱為線性收斂的．②當(dāng)，或時(shí)，迭代點(diǎn)列叫做具有超線性收斂速度或稱算法A是超線性收斂．③當(dāng)時(shí)，迭代點(diǎn)列叫做具有二階收斂速度或算法A是二階收斂的．一般認(rèn)為，具有超線性收斂或二階收斂的算法是較快速的算法．一最優(yōu)化問題總論

①當(dāng)，迭代點(diǎn)列稱為具(2)計(jì)算終止準(zhǔn)則用迭代方法尋優(yōu)時(shí)，其迭代過程總不能無限制地進(jìn)行下去，那么什么時(shí)候截?cái)噙@種迭代呢？這就是迭代什么時(shí)候終止的問題．從理論上說，當(dāng)然希望最終迭代點(diǎn)到達(dá)理論極小點(diǎn)，或者使最終迭代點(diǎn)與理論極小點(diǎn)之間的距離足夠小時(shí)才終止迭代．但是這在實(shí)際上是辦不到的．因?yàn)閷?duì)于一個(gè)待求的優(yōu)化問題，其理論極小點(diǎn)在哪里并不知道．所知道的只是通過迭代計(jì)算獲得的迭代點(diǎn)列，因此只能從點(diǎn)列所提供的信息來判斷是否應(yīng)該終止迭代．對(duì)于無約束優(yōu)化問題通常采用的迭代終止準(zhǔn)則有以下幾種：一最優(yōu)化問題總論

(2)計(jì)算終止準(zhǔn)則一最優(yōu)化問題總論

①點(diǎn)距準(zhǔn)則相鄰兩迭代點(diǎn)之間的距離已達(dá)到充分小，即式中是一個(gè)充分小正數(shù)，代表計(jì)算精度．②函數(shù)下降量準(zhǔn)則相鄰兩迭代點(diǎn)的函數(shù)值下降量已達(dá)到充分小．當(dāng)時(shí)，可用函數(shù)絕對(duì)下降量準(zhǔn)則當(dāng)時(shí)，可用函數(shù)相對(duì)下降量準(zhǔn)則③梯度準(zhǔn)則目標(biāo)函數(shù)在迭代點(diǎn)的梯度已達(dá)到充分小，即這一準(zhǔn)則對(duì)于定義域上的凸函數(shù)是完全正確的．若是非凸函數(shù)，有可能導(dǎo)致誤把駐點(diǎn)作為最優(yōu)點(diǎn)。對(duì)于約束優(yōu)化問題，不同的優(yōu)化方法有各自的終止準(zhǔn)則．一最優(yōu)化問題總論

①點(diǎn)距準(zhǔn)則一最優(yōu)化問題總論

綜上所述，優(yōu)化算法的基本迭代過程如下：①選定初始點(diǎn)，置．②按照某種規(guī)則確定搜索方向．③按某種規(guī)則確定使得④計(jì)算⑤判定是否滿足終止準(zhǔn)則．若滿足，則打印和,停機(jī)；否則置,轉(zhuǎn)②．一最優(yōu)化問題總論

綜上所述，優(yōu)化算法的基本迭代過程如下：一最優(yōu)化問題總論

NYX是否滿足終止準(zhǔn)則輸出X，f(X)開始結(jié)束選定X0確定P確定t，使得f(X0+tP)<f(X0)X=X0+tPX0=X上述算法框圖如右圖一最優(yōu)化問題總論

NYX是否滿足終止準(zhǔn)則輸出X，f(X)開始結(jié)束選定X0確定

就優(yōu)化機(jī)制與行為而分，目前工程中常用的優(yōu)化算法主要可分為：經(jīng)典算法、構(gòu)造型算法、改進(jìn)型算法、基于系統(tǒng)動(dòng)態(tài)演化的算法和混合型算法等．（1）經(jīng)典算法．包括線性規(guī)劃、動(dòng)態(tài)規(guī)劃、整數(shù)規(guī)劃和分枝定界等運(yùn)籌學(xué)中的傳統(tǒng)算法，其算法計(jì)算復(fù)雜性一般很大，只適于求解小規(guī)模問題，在工程中往往不實(shí)用．一最優(yōu)化問題總論

就優(yōu)化機(jī)制與行為而分，目前工程中常用的優(yōu)化算法主要可（2）構(gòu)造型算法．用構(gòu)造的方法快速建立問題的解，通常算法的優(yōu)化質(zhì)量差，難以滿足工程需要．譬如，調(diào)度問題中的典型構(gòu)造型方法有：Johnson法、Palmer法、Gupta法、CDS法、Daunenbring的快速接近法、NEH法等．（3）改進(jìn)型算法，或稱鄰域搜索算法．從任一解出發(fā)，對(duì)其鄰域的不斷搜索和當(dāng)前解的替換來實(shí)現(xiàn)優(yōu)化．根據(jù)搜索行為，它又可分為局部搜索法和指導(dǎo)性搜索法．一最優(yōu)化問題總論

（2）構(gòu)造型算法．用構(gòu)造的方法快速建立問題的解，通常算法的優(yōu)（4）基于系統(tǒng)動(dòng)態(tài)演化的算法．將優(yōu)化過程轉(zhuǎn)化為系統(tǒng)動(dòng)態(tài)的演化過程，基于系統(tǒng)動(dòng)態(tài)的演化來實(shí)現(xiàn)優(yōu)化，如神經(jīng)網(wǎng)絡(luò)和混沌搜索等．（5）混合型算法．指上述各算法從結(jié)構(gòu)或操作上相混合而產(chǎn)生的各類算法．優(yōu)化算法當(dāng)然還可以從別的角度進(jìn)行分類，如確定性算法和不確定性算法，局部?jī)?yōu)化算法和全局優(yōu)化算法等．一最優(yōu)化問題總論

（4）基于系統(tǒng)動(dòng)態(tài)演化的算法．將優(yōu)化過程轉(zhuǎn)化為系統(tǒng)動(dòng)態(tài)的演化一、組合優(yōu)化問題建模歸納而言，最優(yōu)化問題可分為函數(shù)優(yōu)化問題和組合優(yōu)化問題兩大類。上一節(jié)介紹的最優(yōu)化數(shù)學(xué)模型屬于函數(shù)優(yōu)化問題，該函數(shù)優(yōu)化的對(duì)象是一定區(qū)間內(nèi)的連續(xù)變量。本節(jié)重點(diǎn)介紹組合優(yōu)化問題，組合優(yōu)化的對(duì)象是解空間中的離散狀態(tài)．一最優(yōu)化問題總論

一、組合優(yōu)化問題建模一最優(yōu)化問題總論

組合優(yōu)化問題是通過對(duì)數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)編排、分組、次序或篩選等，所研究的問題涉及信息技術(shù)、經(jīng)濟(jì)管理、工業(yè)工程、交通運(yùn)輸、通信網(wǎng)絡(luò)等諸多領(lǐng)域，該問題數(shù)學(xué)模式可表示為其中，為目標(biāo)函數(shù)，為約束函數(shù)，X為決策變量，表示有限個(gè)點(diǎn)組成的集合．一最優(yōu)化問題總論

組合優(yōu)化問題是通過對(duì)數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)例1.9

0-1背包問題（knapsackproblem）

設(shè)有一個(gè)容積為b的背包，n個(gè)體積分別為，價(jià)值分別為的物品，如何以最大的價(jià)值裝包?該問題稱為0-1背包問題．用數(shù)學(xué)模型表示為

(1.3)其中目標(biāo)(1.3)欲使包內(nèi)所裝物品的價(jià)值最大；(1.4)為包的能力限制；(1.5)表示xi為二進(jìn)制變量，xi=1表示裝第i個(gè)物品，xi=0表示不裝．一最優(yōu)化問題總論

例1.90-1背包問題（knapsackproblem例1.10

旅行商問題(TSP，travelingsalesmanproblem)一個(gè)商人欲到個(gè)城市推銷商品，每?jī)蓚€(gè)城市i和j之間的距離為，如何選擇一條道路使得商人每個(gè)城市走一遍后回到起點(diǎn)且所走路徑最短．TSP還可以細(xì)分為對(duì)稱和非對(duì)稱距離兩大類問題．當(dāng)對(duì)任意的I,j時(shí)都有,則稱該TSP為對(duì)稱距離TSP，否則稱非對(duì)稱距離TSP．

一最優(yōu)化問題總論

例1.10旅行商問題(TSP，travelingsale對(duì)一般的TSP，它的一種數(shù)學(xué)模型描述