最優(yōu)化方法介紹通用課件

《最優(yōu)化方法》

計劃學時數(shù)：64學時教材：最優(yōu)化方法，解可新，韓健，林友聯(lián)，天津大學出版社。主要參考書目：[1]最優(yōu)化理論與算法，陳寶林，清華大學出版社。[2]最優(yōu)化計算方法，席少霖，趙鳳治，上?？茖W技術出版社。[3]非線性規(guī)劃，胡毓達，高等教育出版社上課時間：01-16周，周二3,4節(jié)，周四3,4節(jié)

上課地點：3-249任課教師：李學文（中814）email:

最優(yōu)化問題至少有兩要素：一是可能的方案；二是要追求的目標。后者是前者的函數(shù)。最優(yōu)化所研究的問題是在眾多的可行方案中怎樣選擇最合理的一種以達到最優(yōu)目標。將達到最優(yōu)目標的方案稱為最優(yōu)方案或最優(yōu)決策，搜尋最優(yōu)方案的方法稱為最優(yōu)化方法，關于最優(yōu)化方法的數(shù)學理論稱為最優(yōu)化論。

最優(yōu)化技術是一門較新的學科分支。它是在本世紀五十年代初在電子計算機廣泛應用的推動下才得到迅速發(fā)展，并成為一門直到目前仍然十分活躍的新興學科。

最優(yōu)化方法也稱為數(shù)學規(guī)劃，是運籌學的一個分支.最優(yōu)化技術應用范圍十分廣泛。在我們日常生活中，在工農(nóng)業(yè)生產(chǎn)、社會經(jīng)濟、國防、航空航天工業(yè)中處處可見其用途。

最優(yōu)化技術工作被分成兩個方面，一是由實際生產(chǎn)或科技問題形成最優(yōu)化的數(shù)學模型，二是對所形成的數(shù)學問題進行求解。發(fā)展歷史微積分時代極值問題，Langrange乘子法1847年，Cauchy（柯西），最速下降法

函數(shù)值沿什么方向下降最快？1939年，康托洛維奇，線性規(guī)劃《生產(chǎn)組織與計劃中的數(shù)學方法》二次世界大戰(zhàn)后，形成一個新的學科

生產(chǎn)和科學研究的發(fā)展，計算機的推廣應用內容線性規(guī)劃

單純形法，Karmarkar方法，…無約束最優(yōu)化方法

最速下降法，Newton法，共軛梯度法，擬Newton法，…

約束最優(yōu)化方法

罰函數(shù)法，乘子法，投影梯度法，簡約梯度法，約束變尺度法，…整數(shù)規(guī)劃

分枝定界法，割平面法，…動態(tài)規(guī)劃幾何規(guī)劃隨機規(guī)劃……….運籌學的正式產(chǎn)生：第二次世界大戰(zhàn)鮑德西（Bawdsey）雷達站的研究1939年，以Blackett為首的一個研究小組（代號“Blackett馬戲團”），研究如何改進英國的空防系統(tǒng)，提高英國本土防空能力。Blackett備忘錄1941年12月，Blackett應盟國政府的要求，寫了五份題為“ScientistsattheOperationalLevel”的簡短備忘錄，建議在各大指揮部建立運籌學小組，此建議被迅速采納。據(jù)不完全統(tǒng)計，二戰(zhàn)期間，僅在英、美和加拿大，參加運籌學工作的科學家超過700名。大西洋反潛戰(zhàn)：研究如何打破德國對英吉利海峽的海上封鎖運籌學的產(chǎn)生和發(fā)展

英國OR小組，美國OR小組50年第一種運籌學雜志48年英國運籌協(xié)會,52年美國運籌協(xié)會59年國際運籌學會聯(lián)盟線性規(guī)劃在蘇聯(lián)和美國的出現(xiàn)和發(fā)展康托洛維奇Dantzig,Koopmans,VonNeumann

線性規(guī)劃的效用

58年，美國Mobil公司1975年，康托洛維奇，Koopmans，“最優(yōu)資源配置理論的貢獻”，諾貝爾經(jīng)濟學獎

由此可見運籌學一門應用性很強的學科。特別是隨著計算機技術的不斷發(fā)展，計算機成為運籌學最強有力的運算工具，運籌學越來越顯示出其廣泛的使用價值。

運籌學在工業(yè)，農(nóng)業(yè)，商業(yè)，物流，經(jīng)濟計劃，人力資源，軍事等行業(yè)都有著非常廣泛的應用。有人曾對世界上500家著名的企業(yè)集團或跨國公司進行過調查，發(fā)現(xiàn)其中95%曾使用過線性規(guī)劃，75%使用過運輸模型，90%使用過網(wǎng)絡計劃技術，90%使用過存儲模型，43%使用過動態(tài)規(guī)劃?，F(xiàn)代運籌學在中國的興起

錢學森先生在MIT取得碩士學位，在加州理工大學（CaliforniaInstituteofTechnology）取得博士學位后成為該校的第一位Goddard講座教授。許國志先生在堪薩斯大學取得博士學位后，在馬里蘭大學流體力學和應用數(shù)學研究所當研究員。他們兩人是第一個運籌學小組的領導者。

現(xiàn)代運籌學被引入中國是在五十年代后期。中國第一個運籌學小組在錢學森、許國志先生的推動下在1956年于中國科學院力學研究所成立。

中國運籌學會(ORSC)

中國運籌學會于文化大革命后的1980年成立，當時作為中國數(shù)學會的一個分會。第一屆全國大會在山東省濟南召開，華羅庚教授當然地被選為第一屆理事長，副理事長有許國志先生。歷史回顧

中國運籌學會在1982年成為國際運籌學聯(lián)合會（IFORS）的成員。第二屆全國代表大會和學術會議于1984年在上海召開，越民義先生被選為該屆理事長。第三次全國會議于1988年在安徽省九華山召開，徐光煇先生任理事長。第五次全國代表大會和第六次全國代表大會分別于1996年和2000年在西安市和湖南長沙舉行，章祥蓀教授出任理事長。第七屆全國代表大會在青島于2004年10月19日舉行,袁亞湘為新一屆理事長.組織結構

中國運籌學會現(xiàn)有注冊會員1200多名。中國運籌學會下屬有多個專業(yè)分會：如決策科學分會；數(shù)學規(guī)劃分會；排序分會；圖論組合分會；排隊論分會；青年分會；可靠性分會；金融工程及金融風險管理分會；智能計算分會；企業(yè)管理運籌分會；經(jīng)濟數(shù)學分會等，各分會定期或不定期進行學術交流。北京、陜西、山東、大慶等一些省市還有地區(qū)性運籌學會，部隊系統(tǒng)有軍事運籌學學會,僅大慶油田運籌學會就有會員二百多名，他們在許多領域應用運籌學理論與方法，取得了很好的經(jīng)濟效益與社會效益。

運籌學在中國的一些近期應用

（1）中國運籌學近期應用的亮點是由華羅庚教授點燃的。在文化大革命期間，身為中國數(shù)學會理事長和中科院院士的他，親自率領一個小組，大家稱為“華羅庚小分隊”，到農(nóng)村、工廠講解基本的優(yōu)化技術和統(tǒng)籌方法（PERT），使用于日常的生產(chǎn)和生活中。自1965年起的十年中，他到了約二十個省和無數(shù)個城市，受到各界人士的歡迎，他的工作得到了毛澤東主席的肯定和表揚。華羅庚先生這一時期的推廣工作播下了運籌學哲學思想的種子，大大推動了運籌學在中國的普及和發(fā)展。直到今天，許多中國公民還記得“優(yōu)選法”這個詞匯，但不一定知道“運籌學”。糧食產(chǎn)量預測 （2）中科院陳錫康教授提出了系統(tǒng)綜合因素方法預測糧食產(chǎn)量。關鍵技術包括投入占用產(chǎn)出分析、考慮邊際收益率遞減的非線性預測方程，以及最小絕對和方法。自1980年始，在每年的四月底成功地預測中國全年的糧食產(chǎn)量，五月初報送給中國政府主要領導以及相關的政府職能部門。三個突出的特點：預測提前期在半年以上（一般預測方法提前期一般是2個月）；平均預測誤差為1.6%（一般預測方法的平均預測誤差為5-10%）；預報糧食產(chǎn)量豐、平、欠方向正確。1999年陳錫康研究員等在北京召開的第十五屆IFORS大會上獲得一等獎。 陳錫康提供（xkchen）金融管理與經(jīng)濟發(fā)展方面的運籌學應用

（3）將優(yōu)化及決策分析方法，應用于金融風險控制與管理、資產(chǎn)評估與定價分析模型等；例如陜西省運籌學會近年的一些運籌學應用:證券投資：滬深股市股指波動的交互影響效應分析深圳股市內幕交易（例資產(chǎn)重組）的實證分析經(jīng)濟發(fā)展（預測、評價、優(yōu)化）：陜北果業(yè)發(fā)展決策的優(yōu)化分析系統(tǒng)結構模型在陜北果業(yè)開發(fā)中的應用陜北水果生產(chǎn)基地戰(zhàn)略方針多層次分析決策模型陜西省經(jīng)濟、資源、環(huán)境協(xié)調發(fā)展的相對有效性評價陜西工業(yè)可持續(xù)發(fā)展的評價及對策

徐渝提供

（）

工程管理

基于多層次灰色決策模型的施工方案評價 應用灰色理論、方法結合工程實例建立了多層次灰色決策模型對工程施工方案進行綜合評價，得到了滿意的結果。建設項目投資風險的仿真分析 結合贏利性民用建筑項目的特點，建立了經(jīng)濟模型及其投資回收期仿真模型，并對仿真模型進行了精度估計

徐渝提供（）

社會保障與服務業(yè)

1、運用排隊理論方法對超市收費系統(tǒng)進行分析，建立了在一定的顧客滿意度條件下超市的運營費用模型，按運營成本最小的目標進行了優(yōu)化； 2、住院排隊系統(tǒng)病床配置調整方法的分析研究 3、還應用排隊理論建立了門診排隊模型與住院排隊模型，進行了某醫(yī)院的住院排隊系統(tǒng)計算機仿真，針對擴建、新建醫(yī)院建立了線性規(guī)劃決策模型。

徐渝提供（）現(xiàn)代物流與供應鏈管理

供應鏈上庫存協(xié)調的利益分享機制研究 應用庫存理論及其整合模型建立并分析了競爭型與協(xié)商型庫存協(xié)調的利益分享模型，對其效率和特征進行了比較企業(yè)供應鏈模型和采購滿意度評價研究與陜西省物資儲運總公司合作的《陜西省區(qū)域現(xiàn)代物流配送示范工程》項目可行性分析與初步設計徐渝提供（）最近的一些理論研究方向(1)數(shù)學規(guī)劃研究?開展對非線性規(guī)劃信賴域方法的深入和細致的研究(袁亞湘);?開展對非線性共軛梯度法進行深入研究工作者(戴域虹、袁亞湘、韓繼業(yè)、鄧乃揚、王長鈺等);?鄧乃揚教授提出一類使用PCG技術的不精確牛頓法，大型問題顯示出其巨大潛在作用;?研究求解變分不等式問題的一類投影和收縮算法(何炳生、孫德峰、修乃華、王長鈺、王宜舉等);?開展對求解變分不等式問題的非光滑算法研究，以及開展對求解變分不等式問題的非內點光滑化算法研究。

修乃華提供（）最近的一些理論研究方向(2)

不確定性決策研究 ?供應鏈管理。主要研究基于信息更新下，供應鏈模型的優(yōu)化和決策。

?

隨機存儲模型。主要用博弈理論和隨機比較理論來研究供應商和銷售商之間的協(xié)調問題。

?在不確定性環(huán)境下實時供應鏈控制和應急管理

?具有多類顧客到達的隨機排隊網(wǎng)絡優(yōu)化與設計。主要研究優(yōu)化與設計中最基本的兩個問題，即具有多類顧客到達隨機排隊網(wǎng)絡的穩(wěn)定性與擴散逼近。

張漢勤提供（）

最近的一些理論研究方向

(3)

離散與組合優(yōu)化研究

基于判定樹計算模型的計算復雜性理論：Rivest-Vuillemin猜想(堵丁柱,高隨祥)近似算法：NP-難解問題的近似算法設計和分析Steiner樹問題：Steiner樹問題的幾何,網(wǎng)絡和各種推廣模型計算機和通訊網(wǎng)絡：交換網(wǎng)絡，光纖網(wǎng)絡，無線網(wǎng)絡和移動網(wǎng)絡(堵丁柱,胡曉東)排序問題：排序問題的在線，半在線和離線模型 (何勇)裝箱問題：裝箱問題的在線，離線和高維模型 (張國川)

胡曉東提供（）最近的一些理論研究方向

(4)信息科學、生命科學中的運籌學研究將全局最優(yōu)化、圖論、神經(jīng)網(wǎng)絡等運籌學理論及方法應用于分子生物信息學中的DNA與蛋白質序列比較、芯片測試、生物進化 分析、蛋白質結構預測等問 題的研究；最近中科院數(shù)學 與系統(tǒng)科學研究院成立了“生 物信息研究中心”，主要成員 是運籌學者和統(tǒng)計學家，由

章祥蓀擔任主任。最近的一些理論研究方向(5)與管理科學有關的運籌研究（管理有效性的概念及測算方法） ?管理本身存在著是否有效的問題。對管理好壞的程度進行科學的定量描述。 ?管理有效性的測算方法——二次相對效益。 ?測算管理有效性的數(shù)學模型

馮英俊提供（）內容總結《最優(yōu)化方法》。最優(yōu)化所研究的問題是在眾多的可行方案中怎樣選擇最合理的一種以達到最優(yōu)目標。生產(chǎn)和科學研究的發(fā)展，計算機的推廣應用。英國OR小組，美國OR小組。中國運籌學會于文化大革命后的1980年成立，當時作為中國數(shù)學會的一個分會。中國運籌學會下