最優(yōu)化方法緒論

最優(yōu)化方法

（學(xué)時(shí)：40）

楊豐梅北京化工大學(xué)理學(xué)院Email：yangfm@什么是最優(yōu)化(Optimization)最優(yōu)化就是在復(fù)雜環(huán)境中遇到的許多決策問(wèn)題時(shí)，從所有可能的方案中選擇最合理的一種方案，以達(dá)到最佳目標(biāo)的一門(mén)科學(xué)。什么是最優(yōu)化方法最優(yōu)化方法就是尋找最優(yōu)決策的方法。最優(yōu)化模型線性規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃、目標(biāo)規(guī)劃、動(dòng)態(tài)規(guī)劃(五規(guī)劃)對(duì)策論、存儲(chǔ)論、排隊(duì)論、決策論、圖論(五論)運(yùn)籌學(xué)運(yùn)籌學(xué)的“三個(gè)代表”模型理論算法最優(yōu)化首先是一種理念,其次才是一種方法.

最優(yōu)化方法被分成兩個(gè)方面：一是由實(shí)際生產(chǎn)或科技問(wèn)題形成最優(yōu)化的數(shù)學(xué)模型，？二是對(duì)所形成的數(shù)學(xué)問(wèn)題進(jìn)行數(shù)學(xué)加工和求解?！套顑?yōu)化的發(fā)展歷程費(fèi)馬:1638;牛頓,1670歐拉,1755Minf(x1x2···xn)

f(x)=0歐拉，拉格朗日：無(wú)窮維問(wèn)題，變分學(xué)柯西：最早應(yīng)用最速下降法拉格朗日，1797Minf(x1x2···xn)s.t.gk(x1x2···xn)=0,k=1,2,…,m一般最優(yōu)化問(wèn)題可寫(xiě)成如下形式:1930年代，康托諾維奇：線性規(guī)劃1940年代，Dantzig：?jiǎn)渭冃畏椒?，馮諾依曼：對(duì)策論1950年代，Bellman：動(dòng)態(tài)規(guī)劃，最優(yōu)性原理；

KKT條件；1960年代：Zoutendijk,Rosen,Carroll,etc.非線性規(guī)劃算法，Duffin，Zener等幾何規(guī)劃，Gomory，整數(shù)規(guī)劃,Dantzig等隨機(jī)規(guī)劃

6-70年代：Cook等復(fù)雜性理論，組合優(yōu)化迅速發(fā)展

電子計(jì)算機(jī)發(fā)展———最優(yōu)化方法最優(yōu)化應(yīng)用舉例具有廣泛的實(shí)用性運(yùn)輸問(wèn)題，車輛調(diào)度，員工安排，空運(yùn)控制等工程設(shè)計(jì)，結(jié)構(gòu)設(shè)計(jì)等資源分配，生產(chǎn)計(jì)劃等通信：光網(wǎng)絡(luò)、無(wú)線網(wǎng)絡(luò)，adhoc等.制造業(yè)：鋼鐵生產(chǎn)，車間調(diào)度等醫(yī)藥生產(chǎn)，化工處理等電子工程，集成電路VLSIetc.排版（TEX,Latex,etc.）1.

食譜問(wèn)題我每天要求一定量的兩種維生素，Vc和Vb。假設(shè)這些維生素可以分別從牛奶和雞蛋中得到。維生素奶中含量蛋中含量每日需求Vc(mg)2440Vb(mg)3250單價(jià)(US$)32.5需要確定每天喝奶和吃蛋的量，目標(biāo)以便以最低可能的花費(fèi)購(gòu)買(mǎi)這些食物，而滿足最低限度的維生素需求量。1.

食譜問(wèn)題（續(xù)）令x表示要買(mǎi)的奶的量，y為要買(mǎi)的蛋的量。食譜問(wèn)題可以寫(xiě)成如下的數(shù)學(xué)形式：運(yùn)籌學(xué)工作者參與建立關(guān)于何時(shí)出現(xiàn)最小費(fèi)用（或者最大利潤(rùn)）的排序，或者計(jì)劃，早期被標(biāo)示為programs。求最優(yōu)安排或計(jì)劃的問(wèn)題，稱作programming問(wèn)題。Min3x+2.5ys.t.2x+4y403x+2y

50

x,y

0.極小化目標(biāo)函數(shù)可行區(qū)域（單純形）可行解2

運(yùn)輸問(wèn)題設(shè)某種物資有m個(gè)產(chǎn)地A1,A2,…Am,各產(chǎn)地的產(chǎn)量是a1,a2,…,am;有n個(gè)銷地B1,B2,…,Bn.各銷地的銷量是b1,b2,…,bn.假定從產(chǎn)地Ai(i=1,2,…,m)到銷地Bj(j=1,2,…,n)運(yùn)輸單位物品的運(yùn)價(jià)是cij問(wèn)怎樣調(diào)運(yùn)這些物品才能使總運(yùn)費(fèi)最??？如果運(yùn)輸問(wèn)題的總產(chǎn)量等于總銷量，即有則稱該運(yùn)輸問(wèn)題為產(chǎn)銷平衡問(wèn)題；反之，稱產(chǎn)銷不平衡問(wèn)題。令xij表示由產(chǎn)地Ai運(yùn)往銷地Bj的物品數(shù)量，則產(chǎn)銷平衡問(wèn)題的數(shù)學(xué)模型為：2

運(yùn)輸問(wèn)題（續(xù)）以價(jià)格qi

購(gòu)買(mǎi)了si份股票i,i=1,2,…,n股票i的現(xiàn)價(jià)是pi你預(yù)期一年后股票的價(jià)格為ri

在出售股票時(shí)需要支付的稅金=資本收益×30%扣除稅金后，你的現(xiàn)金仍然比購(gòu)買(mǎi)股票前增多支付1%的交易費(fèi)用例如：將原先以每股30元的價(jià)格買(mǎi)入1000股股票，以每股50元的價(jià)格出售，則凈現(xiàn)金為：50×1000-0.3(50-30)1000-0.1×50×1000=390003

稅下投資問(wèn)題我們的目標(biāo)是要使預(yù)期收益最大。Xi：當(dāng)前拋出股票i的數(shù)量。3

稅下投資問(wèn)題（續(xù)）4

選址問(wèn)題實(shí)例:一組潛在位置（地址）,一組顧客集合及相應(yīng)的利潤(rùn)和費(fèi)用數(shù)據(jù)；解:

設(shè)施開(kāi)放(使用)的數(shù)目，他們的位置，以及顧客被哪個(gè)設(shè)施服務(wù)的具體安排方案；目標(biāo)：總的利潤(rùn)最大化。數(shù)據(jù)與約束J={1,2,…,n}:放置設(shè)施的可能的潛在位置集合I={1,2,…,m}:顧客集合,其要求的服務(wù)需要某設(shè)施所提供.4

選址問(wèn)題（續(xù)1）5選址問(wèn)題（續(xù)2）6負(fù)載平衡(續(xù)1)實(shí)例:網(wǎng)絡(luò)G(V,E)

及一組m

個(gè)數(shù)的集合{s,d>0}，表示

連接源點(diǎn)

s與匯點(diǎn)d

之間的流量解:{s,d>0}的一組路由,即G(V,E)

中m

條s

與

d間的路,

表示連接s與d

的負(fù)載流量的路徑。目標(biāo):極小化網(wǎng)絡(luò)負(fù)載6

負(fù)載平衡(續(xù)2)7.結(jié)構(gòu)設(shè)計(jì)問(wèn)題兩桿桁架的最優(yōu)設(shè)計(jì)問(wèn)題。由兩根空心圓桿組成對(duì)稱的兩桿桁架，其頂點(diǎn)承受負(fù)載為2p，兩支座之間的水平距離為2L，圓桿的壁厚為B，桿的比重為ρ，彈性模量為E，屈吸強(qiáng)度為δ。求在桁架不被破壞的情況下使桁架重量最輕的桁架高度h及圓桿平均直徑d。

受力分析圖圓桿截面圖桁桿示意圖

受力分析圖圓桿截面圖桁桿示意圖7.結(jié)構(gòu)設(shè)計(jì)問(wèn)題7.結(jié)構(gòu)設(shè)計(jì)問(wèn)題此應(yīng)力要求小于材料的屈吸極限，即解：桁桿的截面積為：桁桿的總重量為：負(fù)載2p在每個(gè)桿上的分力為：于是桿截面的應(yīng)力為：

圓桿中應(yīng)力小于等于壓桿穩(wěn)定的臨界應(yīng)力。由材料力學(xué)知：壓桿穩(wěn)定的臨界應(yīng)力為

由此得穩(wěn)定約束：7.結(jié)構(gòu)設(shè)計(jì)問(wèn)題

另外還要考慮到設(shè)計(jì)變量d和h有界。從而得到兩桿桁架最優(yōu)設(shè)計(jì)問(wèn)題的數(shù)學(xué)模型：7.結(jié)構(gòu)設(shè)計(jì)問(wèn)題重量應(yīng)力要求穩(wěn)定要求1.

線性規(guī)劃

對(duì)偶定理2.

非線性規(guī)劃

K-K-T定理3.最優(yōu)化算法

算法設(shè)計(jì)技巧使用教材：最優(yōu)化方法何堅(jiān)勇參考書(shū)：最優(yōu)化理論與算法陳寶林清華大學(xué)出版社其他參考書(shū)目NonlinearProgramming-TheoryandAlgorithmsMokhtarS.Bazaraa,C.M.ShettyJohnWiley&Sons,Inc.1979(2ndEdit,1993，3ndEdit，2006)LinearandNonlinearProgramming

DavidG.LuenbergerAddison-WesleyPublishingCompany,2ndEdition,1984/2003..ConvexAnalysis

R.T.RockafellarPrincetonLandmarksinMathematicsandPhysics,1996.OptimizationandNonsmoothAnalysis

FrankH.ClarkeSIAM,1990.LinearProgrammingandNetworkFlowsM.S.Bazaraa,J.J.Jarvis,JohnWiley&Sons,Inc.,1977.運(yùn)籌學(xué)基礎(chǔ)手冊(cè)徐光輝、劉彥佩、程侃科學(xué)出版社，1999組合最優(yōu)化算法和復(fù)雜性CombinatorialOptimization

蔡茂誠(chéng)、劉振宏

AlgorithmsandComplexity清華大學(xué)出版社，1988

Printice-HallInc.,1982/1998

其他參考書(shū)目《最優(yōu)化技術(shù)方法及MATLAB的實(shí)現(xiàn)》，曹衛(wèi)華，郭正，化學(xué)工業(yè)出版社，2005其他計(jì)算方面參考書(shū)目：《最優(yōu)化方法及其MATLAB程序設(shè)計(jì)》