最優(yōu)化導論課件

2023/6/7AlgorithmsDesignTechniquesandAnalysis1教學目的、內(nèi)容和形式目的:掌握數(shù)學建模及最優(yōu)化的基本理論；掌握幾類最優(yōu)化問題的算法；通過學習常用的一些建模的方法,培養(yǎng)分析問題、解決問題的能力.教材《數(shù)學建模與最優(yōu)化》，董文永,機械工業(yè)出版社，2009.參考書:見后面的參考書目錄.學習形式:自學、講授相結(jié)合.成績構(gòu)成:平時(30%-40%)+期末(60%-70%).2023/6/7AlgorithmsDesignTechniquesandAnalysis2參考文獻數(shù)學建模與數(shù)學實驗趙靜但琦高等教育出版社

系統(tǒng)仿真導論，肖田元張燕云陳加棟，清華大學出版社計算機仿真技術基礎，劉瑞葉任洪林李志民，電子工業(yè)出版社《自動控制原理》除第4、8、10三章，龐國仲，中國科大出版社；計算機仿真技術(吳旭光)，吳旭光，化學工業(yè)出版社系統(tǒng)仿真技術，彭曉源，北京航空航天大學出版社數(shù)學建模導論陳理榮北京郵電大學出版社數(shù)學建模方法齊歡華中理工大學出版社數(shù)學實驗姜啟源高等教育出版社數(shù)學建模袁震東，洪淵，林武忠等華東師范大學出版社數(shù)學模型引論唐煥文大連理工大學出版社運籌學錢頌迪等清華大學出版社現(xiàn)代優(yōu)化計算方法刑文訓清華大學出版社最優(yōu)化原理與方法，薛嘉慶，冶金工業(yè)出版社，1986。最優(yōu)化計算方法，席少霖，趙鳳治，上?？茖W技術出版社，1983。非線性方程組解法與最優(yōu)化方法，王德人，高等教育出版社，1985。非線性規(guī)劃，胡毓達，高等教育出版社，19902023/6/7AlgorithmsDesignTechniquesandAnalysis3MaincontentsPart1Optimization:TheoryandPracticeIntroduction:Concept,BackgroundandProgressLinearProgrammingNonlinearProgrammingSimulationOptimizationDynamicprogrammingandOptimizationControlNetworkOptimizationPart2TheTechnologyofMathematicModelingFuzzyModelingandDataAnalysisSystemIdentificationHierarchicalAnalysisAggregationAnalysisDifferentialModeling:TheoryandPracticePart3Meta-HeuristicOptimizationMethodsAntAlgorithmsITOAlgorithms2023/6/7AlgorithmsDesignTechniquesandAnalysis4數(shù)學家名人錄2023/6/7AlgorithmsDesignTechniquesandAnalysisChapter1Introduction:Concept,History,ProgressandClassofMathematicModelingandOptimization2023/6/7AlgorithmsDesignTechniquesandAnalysis6ContentsofCH1引言:數(shù)學建模與最優(yōu)化的背景數(shù)學建模的進展最優(yōu)化技術的進展數(shù)學建摸的基本概念與分類數(shù)學模型與數(shù)學建模數(shù)學模型的分類數(shù)學模型的應用領域數(shù)學建模舉例數(shù)學建模的過程最優(yōu)化的基本概念與分類最優(yōu)化的基本概念最優(yōu)化技術分類最優(yōu)化建模與求解示例數(shù)學建摸與最優(yōu)化的關系2023/6/7AlgorithmsDesignTechniquesandAnalysis71引言:數(shù)學建模與最優(yōu)化的背景1.1數(shù)學建模的歷史與意義1.2最優(yōu)化的歷史與意義2023/6/7AlgorithmsDesignTechniquesandAnalysis81.1數(shù)學建模的歷史與意義數(shù)學建模的歷史和數(shù)學的歷史基本上是一樣的；古埃及幾何學產(chǎn)生于尼羅河泛濫后土地的重新丈量；古印度幾何學的起源則與宗教密切相關中國的《周批算經(jīng)》是討論天文學測量的巨著；大約公元前５世紀，畢達哥拉斯學派重視自然及社會中不變因素的研究，把幾何、算術、天文、音樂稱為“四藝”，在其中追求宇宙的和諧規(guī)律性。17世紀出現(xiàn)了笛卡爾、牛頓、萊布尼茲等數(shù)學家，奠定了微積分的基礎，其研究的對象包括行星運動、流體運動、機械運動、植物生長等均屬于數(shù)學建模的范疇；19世紀后期，數(shù)學成為了研究數(shù)與形、運動與變化的學問；可以說，數(shù)學是模式的科學，其目的是要揭示人們從自然界和數(shù)學本身的抽象世界中所觀察到的結(jié)構(gòu)和對稱性。2023/6/7AlgorithmsDesignTechniquesandAnalysis91.2最優(yōu)化的歷史最優(yōu)化問題有相當長的發(fā)展歷史，最一早可以追溯到牛頓、拉格朗日時代。由于牛頓等對微積分的重要貢獻，才使得差分方程法解決最優(yōu)化問題成為可能。這其中的先鋒者包括貝諾利(Bemot)，歐拉(Eller)和拉格郎日等。Lagrange發(fā)明了有名的拉格郎日乘子法?？挛?Canchy)首先提出了最速下降法(解決無約束最小化問題)。盡管有這些早期的成果，最優(yōu)化的發(fā)展相當緩慢，直到50年代高速計算機的出現(xiàn)。50年代后，最優(yōu)化的發(fā)展進入旺盛期，出現(xiàn)了大量的新算法。Dantzig提出了解決線性規(guī)劃問題的simplex方法，Bellman提出了動態(tài)規(guī)劃最優(yōu)化最優(yōu)性原理，使得約束最優(yōu)化成為可能性。Kuhn和Tucher提出的最優(yōu)化規(guī)劃問題的充分和必要條件開創(chuàng)了非線性規(guī)劃優(yōu)化技術的基礎。幾何規(guī)劃優(yōu)化由Zountijker和Rosen在60年代提出，Gomory同時提出了積分規(guī)劃技術。隨機(或統(tǒng)計)規(guī)劃技術最早山Danzig和charnes提出，Cooper發(fā)展了該技術。2023/6/7AlgorithmsDesignTechniquesandAnalysis10構(gòu)成現(xiàn)代優(yōu)化理論的相關技術是模擬退火SA、遺傳算法GA等現(xiàn)代啟發(fā)式最優(yōu)化算法，他們均是從60年代發(fā)展起來的。SA算法是一種組合優(yōu)化算法，足模擬材半l)Jl日一中的退火處理(Annealing)得名的優(yōu)化算法。退火是材料加工的一種處理方式，即首先將固體加工到融化狀態(tài)，再逐漸冷卻，直到材料達到結(jié)品狀態(tài)。在這個過程中，固體內(nèi)的自由能最終被降低到最小狀態(tài)。在實踐中，冷卻過程必須非常小心控制，以防止固體結(jié)晶到局部最小能量狀態(tài)，即局部最優(yōu)解，從而影響材料的強度等各種性能。模擬退火算法模擬這樣的物理過程，將組合最小化能量狀態(tài)模擬為最終晶體狀態(tài)，并設計一個類似的處理過程，達到優(yōu)化的目的。2023/6/7AlgorithmsDesignTechniquesandAnalysis111.2數(shù)學建摸的基本概念與分類數(shù)學模型與數(shù)學建模數(shù)學模型的分類數(shù)學模型的應用領域數(shù)學建模舉例數(shù)學建模的過程2023/6/7AlgorithmsDesignTechniquesandAnalysis121.2.1數(shù)學建模與數(shù)學模型模型是把對象實體通過適當?shù)倪^濾,用適當?shù)谋憩F(xiàn)規(guī)則描繪出的簡潔的模仿品.通過這個模仿品,人們可以了解到所研究實體的本質(zhì),而且在形式上便于人們對實體進行分析和處理。模型概念

模型是人們十分熟悉的東西，例如：玩具、照片及展覽會里的電站模型、火箭模型等實物模型；地圖、電路圖、分子結(jié)構(gòu)圖等經(jīng)過一定抽象的符號模型；大型水箱中的艦艇模型、風洞中的飛機模型等物理模型。

2023/6/7AlgorithmsDesignTechniquesandAnalysis13數(shù)學模型(MathematicalModel)和數(shù)學建模（MathematicalModeling)對于一個現(xiàn)實對象，為了一個特定目的，根據(jù)其內(nèi)在規(guī)律，作出必要的簡化假設，運用適當?shù)臄?shù)學工具，得到的一個數(shù)學結(jié)構(gòu)。建立數(shù)學模型的全過程（包括表述、求解、解釋、檢驗等）數(shù)學模型數(shù)學建模2023/6/7AlgorithmsDesignTechniquesandAnalysis14數(shù)學建模的具體應用

分析與設計

預報與決策

控制與優(yōu)化

規(guī)劃與管理數(shù)學建模計算機技術知識經(jīng)濟如虎添翼2023/6/7AlgorithmsDesignTechniquesandAnalysis15數(shù)學模型的分類按模型的應用領域分類

生物數(shù)學模型

醫(yī)學數(shù)學模型地質(zhì)數(shù)學模型

數(shù)量經(jīng)濟學模型

數(shù)學社會學模型2023/6/7AlgorithmsDesignTechniquesandAnalysis16數(shù)學模型的分類按是否考慮隨機因素分類 確定性模型隨機性模型2023/6/7AlgorithmsDesignTechniquesandAnalysis17數(shù)學模型的分類(續(xù))按是否考慮模型的變化分類

靜態(tài)模型

動態(tài)模型按建立模型的數(shù)學方法分類

幾何模型

微分方程模型

圖論模型

規(guī)劃論模型

馬氏鏈模型按應用離散方法或連續(xù)方法

離散模型

連續(xù)模型2023/6/7AlgorithmsDesignTechniquesandAnalysis18數(shù)學模型的分類(續(xù))按人們對事物發(fā)展過程的了解程度分類

白箱模型：

指那些內(nèi)部規(guī)律比較清楚的模型。如力學、熱學、電學以及相關的工程技術問題。

灰箱模型：

指那些內(nèi)部規(guī)律尚不十分清楚，在建立和改善模型方面都還不同程度地有許多工作要做的問題。如氣象學、生態(tài)學經(jīng)濟學等領域的模型。黑箱模型：

指一些其內(nèi)部規(guī)律還很少為人們所知的現(xiàn)象。如生命科學、社會科學等方面的問題。但由于因素眾多、關系復雜，也可簡化為灰箱模型來研究。2023/6/7AlgorithmsDesignTechniquesandAnalysis19數(shù)學建模示例椅子能在不平的地面上放穩(wěn)嗎問題分析模型假設通常~三只腳著地放穩(wěn)~四只腳著地

四條腿一樣長，椅腳與地面點接觸，四腳連線呈正方形;

地面高度連續(xù)變化，可視為數(shù)學上的連續(xù)曲面;

地面相對平坦，使椅子在任意位置至少三只腳同時著地。2023/6/7AlgorithmsDesignTechniquesandAnalysis20模型構(gòu)成用數(shù)學語言把椅子位置和四只腳著地的關系表示出來

椅子位置利用正方形(椅腳連線)的對稱性xBADCOD′C′B′A′用(對角線與x軸的夾角)表示椅子位置

四只腳著地距離是的函數(shù)四個距離(四只腳)A,C兩腳與地面距離之和~f()B,D兩腳與地面距離之和~g()兩個距離椅腳與地面距離為零正方形ABCD繞O點旋轉(zhuǎn)正方形對稱性2023/6/7AlgorithmsDesignTechniquesandAnalysis21用數(shù)學語言把椅子位置和四只腳著地的關系表示出來f(),g()是連續(xù)函數(shù)對任意,f(),g()至少一個為0數(shù)學問題已知：f(),g()是連續(xù)函數(shù);

對任意，f()?g()=0;

且g(0)=0，f(0)>0.證明：存在0，使f(0)=g(0)=0.模型構(gòu)成地面為連續(xù)曲面

椅子在任意位置至少三只腳著地2023/6/7AlgorithmsDesignTechniquesandAnalysis22模型求解給出一種簡單、粗糙的證明方法將椅子旋轉(zhuǎn)900，對角線AC和BD互換。由g(0)=0，f(0)>0，知f(/2)=0,g(/2)>0.令h()=f()–g(),則h(0)>0和h(/2)<0.由f,g的連續(xù)性知

h為連續(xù)函數(shù),據(jù)連續(xù)函數(shù)的基本性質(zhì),必存在0,使h(0)=0,即f(0)=g(0).因為f()?g()=0,所以f(0)=g(0)=0.評注和思考建模的關鍵~假設條件的本質(zhì)與非本質(zhì)考察四腳呈長方形的椅子和f(),g()的確定2023/6/7AlgorithmsDesignTechniquesandAnalysis23商人們怎樣安全過河問題(智力游戲)3名商人3名隨從隨從們密約,在河的任一岸,一旦隨從的人數(shù)比商人多,就殺人越貨.但是乘船渡河的方案由商人決定.商人們怎樣才能安全過河?問題分析多步?jīng)Q策過程決策~每一步(此岸到彼岸或彼岸到此岸)船上的人員要求~在安全的前提下(兩岸的隨從數(shù)不比商人多),經(jīng)有限步使全體人員過河.河小船(至多2人)2023/6/7AlgorithmsDesignTechniquesandAnalysis24模型構(gòu)成xk~第k次渡河前此岸的商人數(shù)yk~第k次渡河前此岸的隨從數(shù)xk,yk=0,1,2,3;

k=1,2,sk=(xk,yk)~過程的狀態(tài)S={(x

,y)x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2}S~允許狀態(tài)集合uk~第k次渡船上的商人數(shù)vk~第k次渡船上的隨從數(shù)dk=(uk,vk)~決策D={(u

,v)u+v=1,2}~允許決策集合uk,vk=0,1,2;k=1,2,sk+1=sk

dk+(-1)k~狀態(tài)轉(zhuǎn)移律求dkD(k=1,2,n),使skS,并按轉(zhuǎn)移律由s1=(3,3)到達sn+1=(0,0).多步?jīng)Q策問題2023/6/7AlgorithmsDesignTechniquesandAnalysis25模型求解xy3322110

窮舉法~編程上機

圖解法狀態(tài)s=(x,y)~16個格點~10個點允許決策~移動1或2格;k奇,左下移;k偶,右上移.s1sn+1d1,，d11給出安全渡河方案評注和思考規(guī)格化方法,易于推廣d1d11允許狀態(tài)S={(x

,y)x=0,y=0,1,2,3;

x=3,y=0,1,2,3;x=y=1,2}2023/6/7AlgorithmsDesignTechniquesandAnalysis26Demo2023/6/7AlgorithmsDesignTechniquesandAnalysis27

數(shù)學建模的基本方法機理分析測試分析根據(jù)對客觀事物特性的認識，找出反映內(nèi)部機理的數(shù)量規(guī)律將對象看作“黑箱”,通過對量測數(shù)據(jù)的統(tǒng)計分析，找出與數(shù)據(jù)擬合最好的模型機理分析沒有統(tǒng)一的方法，主要通過實例研究(CaseStudies)來學習。二者結(jié)合用機理分析建立模型結(jié)構(gòu),用測試分析確定模型參數(shù)數(shù)學建模的方法和步驟2023/6/7AlgorithmsDesignTechniquesandAnalysis28

數(shù)學建模的一般步驟模型準備模型假設模型構(gòu)成模型求解模型分析模型檢驗模型應用模型準備了解實際背景明確建模目的搜集有關信息掌握對象特征形成一個比較清晰的‘問題’2023/6/7AlgorithmsDesignTechniquesandAnalysis29模型假設針對問題特點和建模目的作出合理的、簡化的假設在合理與簡化之間作出折中模型構(gòu)成用數(shù)學的語言、符號描述問題發(fā)揮想像力使用類比法盡量采用簡單的數(shù)學工具

數(shù)學建模的一般步驟2023/6/7AlgorithmsDesignTechniquesandAnalysis30模型求解各種數(shù)學方法、軟件和計算機技術如結(jié)果的誤差分析、統(tǒng)計分析、模型對數(shù)據(jù)的穩(wěn)定性分析模型分析模型檢驗與實際現(xiàn)象、數(shù)據(jù)比較，檢驗模型的合理性、適用性模型應用

數(shù)學建模的一般步驟2023/6/7AlgorithmsDesignTechniquesandAnalysis31數(shù)學建模的全過程現(xiàn)實對象的信息數(shù)學模型現(xiàn)實對象的解答數(shù)學模型的解答表述求解解釋驗證(歸納)(演繹)表述求解解釋驗證根據(jù)建模目的和信息將實際問題“翻譯”成數(shù)學問題選擇適當?shù)臄?shù)學方法求得數(shù)學模型的解答將數(shù)學語言表述的解答“翻譯”回實際對象用現(xiàn)實對象的信息檢驗得到的解答實踐現(xiàn)實世界數(shù)學世界理論實踐2023/6/7AlgorithmsDesignTechniquesandAnalysis321.3最優(yōu)化的基本概念與分類最優(yōu)化的基本概念最優(yōu)化技術分類最優(yōu)化建模與求解示例2023/6/7AlgorithmsDesignTechniquesandAnalysis33

最優(yōu)化的基本概念最優(yōu)化技術是一門較新的學科分支。它是在本世紀五十年代初在電子計算機廣泛應用的推動下才得到迅速發(fā)展，并成為一門直到目前仍然十分活躍的新興學科。最優(yōu)化所研究的問題是在眾多的可行方案中怎樣選擇最合理的一種以達到最優(yōu)目標。將達到最優(yōu)目標的方案稱為最優(yōu)方案或最優(yōu)決策，搜尋最優(yōu)方案的方法稱為最優(yōu)化方法，關于最優(yōu)化方法的數(shù)學理論稱為最優(yōu)化論。最優(yōu)化問題至少有兩要素：一是可能的方案；二是要追求的目標。后者是前者的函數(shù)。如果第一要素與時間無關就稱為靜態(tài)最優(yōu)化問題，否則稱為動態(tài)最優(yōu)化問題。2023/6/7AlgorithmsDesignTechniquesandAnalysis34最優(yōu)化技術應用范圍十分廣泛，在我們?nèi)粘Ｉ钪?，在工農(nóng)業(yè)生產(chǎn)、社會經(jīng)濟、國防、航空航天工業(yè)中處處可見其用途。比如我們自己所接觸過的課題有：結(jié)構(gòu)最優(yōu)設計、電子器件最優(yōu)設計、光學儀器最優(yōu)設計、化工工程最優(yōu)設計、標腔最優(yōu)配方、運輸方案、機器最優(yōu)配備、油田開發(fā)、水庫調(diào)度、飼料最優(yōu)配方、食品結(jié)構(gòu)優(yōu)化等等。2023/6/7AlgorithmsDesignTechniquesandAnalysis35最優(yōu)化技術工作被分成兩個方面，一是由實際生產(chǎn)或科技問題形成最優(yōu)化的數(shù)學模型，二是對所形成的數(shù)學問題進行數(shù)學加工和求解。對于第二方面的工作，目前已有一些較系統(tǒng)成熟的資料，但對于第一方面工作即如何由實際問題抽象出數(shù)學模型，目前很少有系統(tǒng)的資料，而這一工作在應用最優(yōu)化技術解決實際問題時是十分關鍵的基礎，沒有這一工作，最優(yōu)化技術將成為無水之源，難以健康發(fā)展。2023/6/7AlgorithmsDesignTechniquesandAnalysis36

最優(yōu)化問題舉例最優(yōu)化在物質(zhì)運輸、自動控制、機械設計、采礦冶金、經(jīng)濟管理等科學技術各領域中有廣泛應用。下面舉幾個專業(yè)性不強的實例。例1.把半徑為1的實心金屬球熔化后，鑄成一個實心圓柱體，問圓柱體取什么尺寸才能使它的表面積最??？解：決定圓柱體表面積大小有兩個決策變量：圓柱體底面半徑r、高h。問題的約束條件是所鑄圓柱體重量與球重相等。即2023/6/7AlgorithmsDesignTechniquesandAnalysis37即即問題追求的目標是圓柱體表面積最小。即

min則得原問題的數(shù)學模型：

s.t.Subjectto.固定.2023/6/7AlgorithmsDesignTechniquesandAnalysis38利用在高等數(shù)學中所學的Lagrange乘子法可求解本問題

分別對r.h.λ求偏導數(shù),并令其等于零.有:2023/6/7AlgorithmsDesignTechniquesandAnalysis39例2.多參數(shù)曲線擬合問題已知兩個物理量x和y之間的依賴關系為:

其中和待定參數(shù),為確定這些參數(shù),對x.y測得m個實驗點:試將確定參數(shù)的問題表示成最優(yōu)化問題.2023/6/7AlgorithmsDesignTechniquesandAnalysis40解:很顯然對參數(shù)和任意給定的一組數(shù)值,就由上式確定了y關于x的一個函數(shù)關系式,在幾何上它對應一條曲線,這條曲線不一定通過那m個測量點,而要產(chǎn)生“偏差”.將測量點沿垂線方向到曲線的距離的平方和作為這種“偏差”的度量.即顯然偏差S越小,曲線就擬合得越好,說明參數(shù)值就選擇得越好，從而我們的問題就轉(zhuǎn)化為5維無約束最優(yōu)化問題。即：2023/6/7AlgorithmsDesignTechniquesandAnalysis41例3：兩桿桁架的最優(yōu)設計問題。由兩根空心圓桿組成對稱的兩桿桁架，其頂點承受負載為2p，兩支座之間的水平距離為2L，圓桿的壁厚為B，桿的比重為ρ，彈性模量為E，屈吸強度為δ。求在桁架不被破壞的情況下使桁架重量最輕的桁架高度h及圓桿平均直徑d。

受力分析圖圓桿截面圖桁桿示意圖2023/6/7AlgorithmsDesignTechniquesandAnalysis42解：桁桿的截面積為：桁桿的總重量為：負載2p在每個桿上的分力為：于是桿截面的應力為：此應力要求小于材料的屈吸極限，即

2023/6/7AlgorithmsDesignTechniquesandAnalysis43

圓桿中應力小于等于壓桿穩(wěn)定的臨界應力。由材料力學知：壓桿穩(wěn)定的臨界應力為由此得穩(wěn)定約束：2023/6/7AlgorithmsDesignTechniquesandAnalysis44

另外還要考慮到設計變量d和h有界。從而得到兩桿桁架最優(yōu)設計問題的數(shù)學模型：2023/6/7AlgorithmsDesignTechniquesandAnalysis45例4.（混合飼料配合）以最低成本確定滿足動物所需營養(yǎng)的最優(yōu)混合飼料。下面舉一個簡化了的例子予以說明。設每天需要混合飼料的批量為100磅，這份飼料必須含：至少0.8%而不超過1.2%的鈣;至少22%的蛋白質(zhì);至多5%的粗纖維。假定主要配料包括石灰石、谷物、大豆粉。這些配料的主要營養(yǎng)成分為：2023/6/7AlgorithmsDesignTechniquesandAnalysis46配料每磅配料中的營養(yǎng)含量鈣蛋白質(zhì)纖維每磅成本（元）石灰石谷物大豆粉0.3800.000.000.0010.090.020.0020.500.08

0.01640.04630.1250解:根據(jù)前面介紹的建模要素得出此問題的數(shù)學模型如下:設是生產(chǎn)100磅混合飼料所須的石灰石、谷物、大豆粉的量（磅）。2023/6/7AlgorithmsDesignTechniquesandAnalysis472023/6/7AlgorithmsDesignTechniquesandAnalysis48最優(yōu)化問題的基本概念n維歐氏空間向量向量變量實值函數(shù)：無約束最優(yōu)問題：2023/6/7AlgorithmsDesignTechniquesandAnalysis49最優(yōu)化問題的基本概念向量變量向量值函數(shù)：其中