最優(yōu)化理論與算法引言

最優(yōu)化理論與算法引言第一頁，共三十八頁，編輯于2023年，星期三提綱1.

線性規(guī)劃

對偶定理2.

非線性規(guī)劃

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

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

數(shù)學規(guī)劃黃紅選，韓繼業(yè)最優(yōu)化理論與算法陳寶林清華大學出版社第二頁，共三十八頁，編輯于2023年，星期三參考書目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.第三頁，共三十八頁，編輯于2023年，星期三LinearProgrammingandNetworkFlowsM.S.Bazaraa,J.J.Jarvis,JohnWiley&Sons,Inc.,1977.運籌學基礎(chǔ)手冊徐光輝、劉彥佩、程侃科學出版社，1999組合最優(yōu)化算法和復雜性CombinatorialOptimization

蔡茂誠、劉振宏

AlgorithmsandComplexity清華大學出版社，1988

Printice-HallInc.,1982/1998

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

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

第八頁，共三十八頁，編輯于2023年，星期三最優(yōu)化的發(fā)展歷程費馬:1638;牛頓,1670歐拉,1755Minf(x1x2···xn)

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

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

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

50

x,y

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

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

G(V,E)betweensandd,representingtheroutescarryingthetrafficofconnectionbetweensources

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

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

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

由此得穩(wěn)定約束：9.結(jié)構(gòu)設(shè)計問題第三十三頁，共三十八頁，編輯于2023年，星期三

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

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

f(x),xS的局部