軟件數(shù)學(xué)實(shí)驗(yàn)-最優(yōu)化

1、國防科技大學(xué)理學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)系數(shù)學(xué)實(shí)驗(yàn)最優(yōu)化liuxiongweigfkd.mtn 一、最優(yōu)化的一般概念1最優(yōu)化問題舉例 例1 紙盒容積問題： 有8尺5尺鐵皮一塊，將四角截去四個(gè)小方塊，折疊成一個(gè)無蓋盒子，試問截去小方塊的尺寸是多少才能使得鐵皮盒子的容積最大？（1）建立數(shù)學(xué)模型（2）選擇方法求解FindMaximum(8 - 2 x) (5 - 2 x) x, 0 = x 1.一、最優(yōu)化的一般概念1最優(yōu)化問題舉例 例2 兩曲線之間距離問題：（1）建立數(shù)學(xué)模型（2）選擇方法求解 已知兩曲線 無交點(diǎn)，試求兩曲線之間最短的距離。NMinimize(x1 - x2)2 + (x3 - x4)2,

2、2 Sinx1 - x3 = 0, x22 - x4 + 2 = 0, x1, x2, x3, x40.567353, x1 - 1.04091, x2 - 0.505432, x3 - 1.72573, x4 - 2.25546d = Sqrt%10.753228一、最優(yōu)化的一般概念1最優(yōu)化問題舉例 例3 貨棧選址問題：（1）建立數(shù)學(xué)模型（2）選擇方法求解 設(shè)有 n 個(gè)市場，第 j 個(gè)市場的位置為 ，對某種貨物的需求量為 ?，F(xiàn)在要求建立 m 個(gè)貨棧，第 i 個(gè)貨棧的容量為 。試確定貨棧的位置，使得貨棧到各市場的運(yùn)輸量與路程的乘積最小。一、最優(yōu)化的一般概念1最優(yōu)化問題舉例 例3 貨棧選址問題：

3、 某奶牛場每天每頭牛需要：蛋白質(zhì)700克，礦物質(zhì)30克，維生素1克?，F(xiàn)在有五種飼料可供選擇，各飼料每公斤所含營養(yǎng)成分及其價(jià)格如下表所示：一、最優(yōu)化的一般概念1最優(yōu)化問題舉例 例4 飼料選購問題：飼料種類12345需求量蛋白質(zhì)（克/公斤）41532700礦物質(zhì)（克/公斤）0.10.20.30.40.530維生素（克/公斤）0.020.010.040.050.031單擊（元/公斤）0.20.70.40.90.8希望確定既滿足營養(yǎng)需要又使得費(fèi)用最省的方案。一、最優(yōu)化的一般概念2最優(yōu)化模型分類上面的各種問題可以歸納為：目標(biāo)函數(shù)決策變量問題（*）的可行區(qū)域： 一、最優(yōu)化的一般概念2最優(yōu)化模型分類問題（*

4、）的可行區(qū)域： 二維、三維命令為RegionPlot或RegionPlot3D: RegionPlot1 x2 - y2 4 & x y 0 & y 0, x, 1, 2.5, y, 0, 1RegionPlot3Dx2 + y2 z2 & x2 + y2 + z2 35 一、最優(yōu)化的一般概念2最優(yōu)化模型分類上面的各種問題可以歸納為：(1) 當(dāng) 全部為線性函數(shù)時(shí)，稱（*）式為線性規(guī)劃。一、最優(yōu)化的一般概念2最優(yōu)化模型分類上面的各種問題可以歸納為：(2) 當(dāng) 為非線性函數(shù)且m = 0，稱（*）式為無約束非線性規(guī)劃。一、最優(yōu)化的一般概念2最優(yōu)化模型分類上面的各種問題可以歸納為：(3) 當(dāng) 中至少一

5、個(gè)為非線性函數(shù)時(shí)，稱（*）式為有約束非線性規(guī)劃。二、無約束非線性規(guī)劃設(shè)無約束非線性規(guī)劃為 如果存在 ，使得對于任意的 ，總有 ，則稱 為問題的全局最優(yōu)解（或全局最小點(diǎn)）。 如果存在 ，使得對于 的一個(gè) 鄰域，使得對于任意 ，總有 ，則稱 為問題的局部最優(yōu)解（或局部最小點(diǎn)）。1一維問題有解的條件與方法二、無約束非線性規(guī)劃 在函數(shù)可微的情況下，它們這些點(diǎn)駐點(diǎn)，可能的極值點(diǎn)；在幾何意義上講就是具有水平切線或水平切平面的位置。當(dāng)然也可能是不可微的位置。 在高等數(shù)學(xué)中我們介紹了解析求解的方法，但是在實(shí)際問題中，這些方法一般行不通。因此一般將問題轉(zhuǎn)化為求導(dǎo)數(shù)的零點(diǎn)的方法，常見的零點(diǎn)求解方法有切線法（一維牛

6、頓法）、割線法、二次插值法等。 2多維問題有解的條件與方法二、無約束非線性規(guī)劃(1) 有解的必要條件：若 是局部最優(yōu)解，則必有(2) 有解的充分條件：若 使得 ，且，則 是局部最優(yōu)解。其中：矩陣正定海塞矩陣Hessian2多維問題有解的條件與方法二、無約束非線性規(guī)劃 對于多維問題的求解方法有梯度法，牛頓法，共軛方向法，擬牛頓法、方向加速法、步長加速法等方法。 優(yōu)點(diǎn)：（1）方法簡單，計(jì)算量小，存儲(chǔ)量也?。?（2）對初始點(diǎn)要求少，從一般初始點(diǎn)出發(fā)，都能收斂到某個(gè)局部極小值。 缺點(diǎn)：對于有些問題，收斂速度十分緩慢；穩(wěn)定性較差。 梯度法：2多維問題有解的條件與方法二、無約束非線性規(guī)劃 最突出的優(yōu)點(diǎn)：收

7、斂速度快，為二階收斂。 缺點(diǎn)：要求函數(shù)二階可微，迭代多次使用 ，這個(gè)比較困難，計(jì)算量大；另外對初始點(diǎn)有比較苛刻的要求。 牛頓法：2多維問題有解的條件與方法二、無約束非線性規(guī)劃 優(yōu)點(diǎn)：（1）計(jì)算公式簡單，存儲(chǔ)量小，對初始點(diǎn)要求少，對二次函數(shù)具有二次終止性質(zhì)（即通過有限步可以得到最小值點(diǎn)） （2）收斂速度介于上面兩種方法之間，對高維（維數(shù)較大時(shí)）的一般非線性函數(shù)有較高的效率）。 缺點(diǎn)：共軛方法的一些理論支撐還不夠完善，對于一維搜索依賴性很強(qiáng)，對于其執(zhí)行的影響需要進(jìn)一步探索。共軛方法：2多維問題有解的條件與方法二、無約束非線性規(guī)劃 優(yōu)點(diǎn)：具有較快的收斂速度和對二次函數(shù)具有二次終止的性質(zhì)，一般情況下優(yōu)

8、于共軛梯度法； 缺點(diǎn)：存儲(chǔ)容量要求大，對于大型問題帶來不便，但具有較高的數(shù)值穩(wěn)定性。因此，該方法受到人們的重視和歡迎，在實(shí)際應(yīng)用中與其他方法結(jié)合的話，能收到很好的效果。擬牛頓法：2多維問題有解的條件與方法二、無約束非線性規(guī)劃 優(yōu)點(diǎn)：（1）方法形象直觀，容易掌握和了解； （2）對目標(biāo)函數(shù)要求較少，適用范圍廣； （3）在直接方法中收斂速度較快，受到重視。 缺點(diǎn)：在目標(biāo)函數(shù)維數(shù)較大時(shí)，可能使得方法無效，目前有很多人在對該方法進(jìn)行改進(jìn)。方向加速法：2多維問題有解的條件與方法二、無約束非線性規(guī)劃 優(yōu)點(diǎn)：（1）方法簡單，易于理解和掌握，在計(jì)算機(jī)上易于實(shí)現(xiàn)； （2）對目標(biāo)函數(shù)要求較少，適用范圍廣； （3）大

9、量數(shù)值試驗(yàn)表明效果好，在實(shí)際應(yīng)用中比較成功。 缺點(diǎn)：是收斂速度慢，特別是到達(dá)最優(yōu)點(diǎn)附近情況更是如此。步長加速法：3Mathematica中無約束非線性規(guī)劃的求解二、無約束非線性規(guī)劃調(diào)用格式為：適用于各種連續(xù)可微的函數(shù)：FindMinimumf(x),x1,x10,x2,x20,.,Options 適用于某些連續(xù)而不一定可微的函數(shù)：FindMinimumf(x),x1,a1,b1,x2,a2,b2,.,Options Options可選參數(shù)，包含有算法（梯度法Gradient，共軛梯度法ConjugateGradient，牛頓法Newton，BFGS擬牛頓法QuasiNewton，以及L-M方法

10、LevenbergMarquardt等）的選擇，變量計(jì)算的精度，梯度處理方式，最大迭代次數(shù)。 3Mathematica中無約束非線性規(guī)劃的求解二、無約束非線性規(guī)劃例1 選用牛頓法，計(jì)算精度要求為，初始點(diǎn)取的無約束非線性規(guī)劃問題： In1:= FindMinimum x13 + x23 + x33 - 3 (x1 + 4 x2 + 9 x3), x1, 4, x2, 4, x3, 4, Method - Newton, PrecisionGoal - 10-6 Out1= -72., x1 - 1., x2 - 2., x3 - 3. 3Mathematica中無約束非線性規(guī)劃的求解二、無約束非

11、線性規(guī)劃例2 FindMinimum-3/(1 + Sqrtx12 + x22), x1, -1, 2, x2, -1, 1-3., x1 - 4.06087*10-11, x2 - 3.73719*10-11 ，求其極小值。因?yàn)樵谠c(diǎn)連續(xù)但不可微，所以使用第二種方法： 三、有約束非線性規(guī)劃有約束非線性規(guī)劃模型為 其求解方法有SUMT外點(diǎn)法（懲罰法）、SUMT內(nèi)點(diǎn)法（碰壁法）、精確罰函數(shù)法、乘子罰函數(shù)法、復(fù)合形法 。三、有約束非線性規(guī)劃 前面的五種方法總稱為罰函數(shù)方法，其思路是通過構(gòu)造罰函數(shù)，將有約束問題轉(zhuǎn)化為無約束優(yōu)化問題來求解。內(nèi)點(diǎn)法與外點(diǎn)法思路清晰，罰函數(shù)構(gòu)造簡單，迭代過程比較簡單，計(jì)算

12、機(jī)上容易實(shí)現(xiàn)，在實(shí)際應(yīng)用中效果較好。它存在明顯的缺點(diǎn)，就是在約束最優(yōu)點(diǎn)處，輔助函數(shù)的Hessian矩陣呈病態(tài)現(xiàn)象，直接影響算法的精度與收斂性。乘子法在罰函數(shù)結(jié)構(gòu)上與迭代過程相對幾種方法來說雖要復(fù)雜一些，但它克服了前面幾種方法所存在的缺點(diǎn)，從理論角度來看，它優(yōu)于其他幾種方法。 其求解方法有SUMT外點(diǎn)法（懲罰法）、SUMT內(nèi)點(diǎn)法（碰壁法）、精確罰函數(shù)法、乘子罰函數(shù)法、復(fù)合形法 。三、有約束非線性規(guī)劃 其求解方法有SUMT外點(diǎn)法（懲罰法）、SUMT內(nèi)點(diǎn)法（碰壁法）、精確罰函數(shù)法、乘子罰函數(shù)法、復(fù)合形法 。 復(fù)合形法優(yōu)于在迭代中只用到了目標(biāo)函數(shù)與約束函數(shù)的函數(shù)值，不需要導(dǎo)數(shù)值，因此對函數(shù)的要求十分寬

13、松，適用范圍非常廣泛；且其計(jì)算量小，在維數(shù)越高其優(yōu)越性相對于其它方法來說更具有優(yōu)越性；不受隨機(jī)因素干擾，均能穩(wěn)定收斂于約束問題的最優(yōu)點(diǎn)；也不受初始點(diǎn)的影響，常常能夠收斂于約束問題的全局極小點(diǎn)。 缺點(diǎn)是方法雖然形象直觀，但是結(jié)構(gòu)比較粗糙，計(jì)算精度較低，對某些目標(biāo)函數(shù)，附近的頂點(diǎn)可能退化到一個(gè)低維空間中，使得迭代無法繼續(xù)。 三、有約束非線性規(guī)劃有約束非線性規(guī)劃問題的Mathematica求解方法：例1 求解下面問題：In1:= NMinimize(x1 + x2 + x3)/( x12 + x2 x3), 3 x1 + 4 x2 + 5 x3 = 0, x2 = 0, x3 = 0, x1, x2

14、, x3Out1= 0.2, x1 - 5., x2 - 0., x3 - 0. 三、有約束非線性規(guī)劃如果目標(biāo)函數(shù)多出了二次項(xiàng)，則稱為二次規(guī)劃。 例2 求解下面二次規(guī)劃問題 In2:= NMinimizex12 + 2 x22 - x1*x2 - x1 - 10 x2, -3 x1 - 2 x2 = -6, x1 = 0, x2 = 0, x1, x2Out2= -13.75, x1 - 0.5, x2 - 2.25 例1 四、線性規(guī)劃 如果優(yōu)化模型中的目標(biāo)函數(shù)與約束函數(shù)均為線性函數(shù)，則這個(gè)模型稱為線性規(guī)劃模型。 如果令 坐標(biāo)形式矩陣形式四、線性規(guī)劃 如果優(yōu)化模型中的目標(biāo)函數(shù)與約束函數(shù)均為線性

15、函數(shù)，則這個(gè)模型稱為線性規(guī)劃模型。 例1 松弛變量剩余變量標(biāo)準(zhǔn)形式四、線性規(guī)劃 線性規(guī)劃標(biāo)準(zhǔn)形式的一般寫法為： 滿秩 四、線性規(guī)劃 線性規(guī)劃問題的Mathematica解法 ： LinearProgrammingc,A,b 約束右端向量b分量可正，可負(fù)或?yàn)?。例1 求解下列線性規(guī)劃問題： 四、線性規(guī)劃 線性規(guī)劃問題的Mathematica解法 ： LinearProgrammingc,A,b In1:= c = 1, -2, -3; b = -6, 12, 20, -20; A = -1, -1, -1, 1, -2, 4, 3, 2, 4, -3, -2, -4; LinearProgram

16、mingc, A, bOut1= 0, 2, 4In2:= c.%Out2= -16 四、線性規(guī)劃例1 求解下列線性規(guī)劃問題： In3:= NMaximize-x1 + 2 x2 + 3 x3, x1 + x2 + x3 = 12, 3 x1 + 2 x2 + 4 x3 = 20, x1 = 0, x2 = 0, x3 = 0, x1, x2, x3Out3= 16., x1 - 0., x2 - 2., x3 - 4. 五、整數(shù)規(guī)劃例1 背包問題： 在一個(gè)數(shù)學(xué)規(guī)劃中，如果它的全部（或部分）自變量要求取為整數(shù)時(shí)，則這個(gè)規(guī)劃為一個(gè)純整（或混整）規(guī)劃，簡稱為整數(shù)規(guī)劃。在特殊情況下，如果這些整數(shù)只限

17、于0或1，則稱這樣的規(guī)劃為0-1規(guī)劃。 假設(shè)一小商販從山下要攜帶一些商品到山上銷售，他的背包最多只能裝10公斤，現(xiàn)在有三種商品可供挑選，每種物品的重量與利潤為已知，如下表： 商品123重量（公斤/件）345利潤（元/件）456試問應(yīng)該選裝哪些商品，件數(shù)多少，才能使得總的效益（利潤）最大？ 五、整數(shù)規(guī)劃例1 背包問題： 商品123重量（公斤/件）345利潤（元/件）456背包最多只能裝10公斤設(shè)應(yīng)該攜帶商品的數(shù)量分別為 ,模型為：In1:= NMaximize4 x1 + 5 x2 + 6 x3, 3 x1 + 4 x2 + 5 x3 = 0, x2 = 0 & x3 = 0, x1, x2,

18、x3 Element Integers, x1, x2, x3Out1= 13., x1 - 2, x2 - 1, x3 - 0 六、全局優(yōu)化例1 求解全局優(yōu)化問題：在Mathematica中全局優(yōu)化的計(jì)算主要使用NMaximize和NMinimize來完成，通過帶用不同參數(shù)得到需要的結(jié)果。In1:= NMinimize(*目標(biāo)函數(shù)*)E(-0.3 x) Sin2 x,(*聲明變量*)x,(*參數(shù)之一：算法選擇及算法的參數(shù)*) Method - DifferentialEvolution, SearchPoints - 4(*種群規(guī)模5n10n*), ScalingFactor - 0.1(*搜索步長*), RandomSeed - 3(*隨機(jī)種子(01000)*)(*參數(shù)二*), MaxIterations - 10(*迭代次數(shù)*) / TimingOut1= 0.047, -1.27996, x - -0.859843六、全局優(yōu)化思考題：決策問題 必須要選修的課程只有一門（2個(gè)學(xué)分）；可供限定選修的課程有8門，任意選修課程有10門。由于課程之間有聯(lián)系，所以可能在選修某門課程中必須同時(shí)選修其他課程，18門課學(xué)分?jǐn)?shù)和要求信