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

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

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

上課地點(diǎn)：3-249任課教師：李學(xué)文（中814）email:

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

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

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

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

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

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

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

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

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

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

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

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

線性規(guī)劃的效用

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

由此可見運(yùn)籌學(xué)一門應(yīng)用性很強(qiáng)的學(xué)科。特別是隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展，計(jì)算機(jī)成為運(yùn)籌學(xué)最強(qiáng)有力的運(yùn)算工具，運(yùn)籌學(xué)越來越顯示出其廣泛的使用價(jià)值。

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

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

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

中國運(yùn)籌學(xué)會(huì)(ORSC)

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

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

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

運(yùn)籌學(xué)在中國的一些近期應(yīng)用

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

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

徐渝提供

（）

工程管理

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

徐渝提供（）

社會(huì)保障與服務(wù)業(yè)

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

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

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

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

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

?

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

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

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

張漢勤提供（）

最近的一些理論研究方向

(3)

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

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

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

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

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

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