最優(yōu)化理論與算法引言第一頁，共三十八頁，2022年，8月28日提綱1.

線性規(guī)劃

對(duì)偶定理2.

非線性規(guī)劃

K-K-T定理3.組合最優(yōu)化

算法設(shè)計(jì)技巧使用/參考教材：

數(shù)學(xué)規(guī)劃黃紅選，韓繼業(yè)最優(yōu)化理論與算法陳寶林清華大學(xué)出版社第二頁，共三十八頁，2022年，8月28日參考書目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.第三頁，共三十八頁，2022年，8月28日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

參考書目第四頁，共三十八頁，2022年，8月28日1,緒論----學(xué)科概述最優(yōu)化是從所有可能的方案中選擇最合理的一種方案,以達(dá)到最佳目標(biāo)的科學(xué).達(dá)到最佳目標(biāo)的方案是最優(yōu)方案,尋找最優(yōu)方案的方法----最優(yōu)化方法(算法)這種方法的數(shù)學(xué)理論即為最優(yōu)化理論.運(yùn)籌學(xué)的方法論之一.是其一重要組成部分.運(yùn)籌學(xué)的“三個(gè)代表”模型理論算法最優(yōu)化首先是一種理念,其次才是一種方法.第五頁，共三十八頁，2022年，8月28日1,緒論----學(xué)科概述

最優(yōu)化技術(shù)工作被分成兩個(gè)方面，一是由實(shí)際生產(chǎn)或科技問題形成最優(yōu)化的數(shù)學(xué)模型，二是對(duì)所形成的數(shù)學(xué)問題進(jìn)行數(shù)學(xué)加工和求解。對(duì)于第二方面的工作，目前已有一些較系統(tǒng)成熟的資料，但對(duì)于第一方面工作即如何由實(shí)際問題抽象出數(shù)學(xué)模型，目前很少有系統(tǒng)的資料，而這一工作在應(yīng)用最優(yōu)化技術(shù)解決實(shí)際問題時(shí)是十分關(guān)鍵的基礎(chǔ)，沒有這一工作，最優(yōu)化技術(shù)將成為無水之源，難以健康發(fā)展。第六頁，共三十八頁，2022年，8月28日緒論---運(yùn)籌學(xué)（OperationsResearch-OR）廣義：管理科學(xué)/決策科學(xué)(MS/DS)、系統(tǒng)科學(xué)/工程(SS/SE)、工業(yè)工程(IE)、運(yùn)作管理(OM)狹義：運(yùn)籌數(shù)學(xué)-最優(yōu)化、對(duì)策論、排隊(duì)論等連續(xù)優(yōu)化：數(shù)學(xué)規(guī)劃（線性規(guī)劃、非線性規(guī)劃）、非光滑優(yōu)化、全局優(yōu)化等離散優(yōu)化：組合優(yōu)化、網(wǎng)絡(luò)優(yōu)化、整數(shù)規(guī)劃等不確定規(guī)劃：隨機(jī)規(guī)劃、模糊規(guī)劃等OMOR/MS/DSSS/SEIE/EM第七頁，共三十八頁，2022年，8月28日OptimizationTree

第八頁，共三十八頁，2022年，8月28日最優(yōu)化的發(fā)展歷程費(fèi)馬:1638;牛頓,1670歐拉,1755Minf(x1x2···xn)

f(x)=0第九頁，共三十八頁，2022年，8月28日歐拉，拉格朗日：無窮維問題，變分學(xué)拉格朗日，1797Minf(x1x2···xn)s.t.gk(x1x2···xn)=0,k=1,2,…,m第十頁，共三十八頁，2022年，8月28日最優(yōu)化應(yīng)用舉例具有廣泛的實(shí)用性運(yùn)輸空運(yùn)控制，員工安排等通信：光網(wǎng)絡(luò)、無線網(wǎng)絡(luò)，adhocetc.制造業(yè)：鋼鐵生產(chǎn)，車間調(diào)度醫(yī)藥工程，電子，集成電路VLSIetc.排版（TEX,Latex,etc.）第十一頁，共三十八頁，2022年，8月28日1.

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

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

50

x,y

0.極小化目標(biāo)函數(shù)可行區(qū)域（單純形）可行解第十三頁，共三十八頁，2022年，8月28日2運(yùn)輸問題數(shù)據(jù)第十四頁，共三十八頁，2022年，8月28日2運(yùn)輸問題第十五頁，共三十八頁，2022年，8月28日以價(jià)格qi購(gòu)買了si份股票i,i=1,2,…,n股票i的現(xiàn)價(jià)是pi你預(yù)期一年后股票的價(jià)格為ri

在出售股票時(shí)需要支付的稅金=資本收益×30%扣除稅金后，你的現(xiàn)金仍然比購(gòu)買股票前增多支付1%的交易費(fèi)用例如：將原先以每股30元的價(jià)格買入1000股股票，以每股50元的價(jià)格出售，則凈現(xiàn)金為：50×1000-0.3(50-30)1000-0.1×50×1000=390003稅下投資問題第十六頁，共三十八頁，2022年，8月28日我們的目標(biāo)是要使預(yù)期收益最大。Xi：當(dāng)前拋出股票i的數(shù)量。3稅下投資問題第十七頁，共三十八頁，2022年，8月28日4制造業(yè)問題第十八頁，共三十八頁，2022年，8月28日4制造業(yè)問題第十九頁，共三十八頁，2022年，8月28日數(shù)據(jù)和約束5能源擴(kuò)充問題第二十頁，共三十八頁，2022年，8月28日決策變量5能源擴(kuò)充問題第二十一頁，共三十八頁，2022年，8月28日5能源擴(kuò)充問題第二十二頁，共三十八頁，2022年，8月28日決策變量6調(diào)度問題第二十三頁，共三十八頁，2022年，8月28日6調(diào)度問題第二十四頁，共三十八頁，2022年，8月28日7選址問題Instance:Asetofpotentialsites,asetofclients,andrelevantProfitandcostdataSolution:thenumberoffacilitiestoopen,theirlocationsandanallocationofeachclienttoanopenfacility.Objective:TheprofitismaximumDataandconstraint第二十五頁，共三十八頁，2022年，8月28日7選址問題第二十六頁，共三十八頁，2022年，8月28日7選址問題第二十七頁，共三十八頁，2022年，8月28日8LoadBalanceInstance:AnetworkG(V,E)andasetofmnumbers{s,d>0}representingthetrafficofconnectionbetweensourcesanddestinationdSolution:Aroutingof{s,d>0},thatisasetofmpathsin

G(V,E)betweensandd,representingtheroutescarryingthetrafficofconnectionbetweensources

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

受力分析圖圓桿截面圖桁桿示意圖9.結(jié)構(gòu)設(shè)計(jì)問題第三十一頁，共三十八頁，2022年，8月28日9.結(jié)構(gòu)設(shè)計(jì)問題此應(yīng)力要求小于材料的屈吸極限，即解：桁桿的截面積為：桁桿的總重量為：負(fù)載2p在每個(gè)桿上的分力為：于是桿截面的應(yīng)力為：第三十二頁，共三十八頁，2022年，8月28日

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

由此得穩(wěn)定約束：9.結(jié)構(gòu)設(shè)計(jì)問題第三十三頁，共三十八頁，2022年，8月28日

另外還要考慮到設(shè)計(jì)變量d和h有界。從而得到兩桿桁架最優(yōu)設(shè)計(jì)問題的數(shù)學(xué)模型：9.結(jié)構(gòu)設(shè)計(jì)問題第三十四頁，共三十八頁，2022年，8月28日基本概念在上述例子中,有的目標(biāo)函數(shù)和約束函數(shù)都是線性的,稱之為線性規(guī)劃問題,而有的模型中含有非線性函數(shù),稱之為非線性規(guī)劃.在線性與非線性規(guī)劃中,滿足約束條件的點(diǎn)稱為可行點(diǎn),全體可行點(diǎn)組成的集合稱為可行集或可行域.如果一個(gè)問題的可行域是整個(gè)空間,則稱此問題為無約束問題.第三十五頁，共三十八頁，2022年，8月28日基本概念最優(yōu)化問題可寫成如下形式:第三十六頁，共三十八頁，2022年，8月28日基本概念Df1.1設(shè)f(x)為目標(biāo)函數(shù)，S為可行域，x0S,若對(duì)每一個(gè)xS,成立f(x)f(x0),則稱x0為極小化問題min

f(x),xS的最優(yōu)解（整體最優(yōu)解）則稱x0為極小化問