1、運(yùn) 籌 學(xué)Operational ResearchOperations Research,李 健 北京化工大學(xué)經(jīng)濟(jì)管理學(xué)院,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,2,本節(jié)內(nèi)容簡(jiǎn)介,課程說(shuō)明 緒論 線(xiàn)性規(guī)劃問(wèn)題及其數(shù)學(xué)模型 小結(jié),2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,3,課程說(shuō)明,教材 運(yùn)籌學(xué)（本科版）運(yùn)籌學(xué)教材編寫(xiě)組 清華大學(xué)出版社 2005-09 參考書(shū) 高孝偉，何大義編，運(yùn)籌學(xué)，中國(guó)大地出版社，2007，9。 運(yùn)籌學(xué)牛映武 西安交通大學(xué)出版社 2006-06 其它同類(lèi)書(shū) 考核方式: 考試 評(píng)分比例: 平時(shí)(30%) 期末(70%),2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,4,課程討論區(qū)

2、, Password: orppt123456,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,5,本節(jié)內(nèi)容簡(jiǎn)介,課程說(shuō)明 緒論 線(xiàn)性規(guī)劃問(wèn)題及其數(shù)學(xué)模型 小結(jié),2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,6,某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)、兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原料的消耗，單位產(chǎn)品的獲利如表所示。問(wèn)應(yīng)如何安排計(jì)劃使該工廠獲利最多？,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,7,第一章 緒論,第一節(jié) 運(yùn)籌學(xué)的簡(jiǎn)史 第二節(jié) 運(yùn)籌學(xué)的性質(zhì)和特點(diǎn) 第三節(jié) 運(yùn)籌學(xué)的工作步驟 第四節(jié) 運(yùn)籌學(xué)的模型 第五節(jié) 運(yùn)籌學(xué)的應(yīng)用 第六節(jié) 運(yùn)籌學(xué)的展望,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,8,第一章

3、 緒論,第一節(jié) 運(yùn)籌學(xué)的簡(jiǎn)史 早期運(yùn)籌思想 軍事運(yùn)籌學(xué)階段 管理運(yùn)籌學(xué)階段 運(yùn)籌學(xué)在中國(guó),2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,9,第一節(jié) 運(yùn)籌學(xué)的簡(jiǎn)史,早期運(yùn)籌思想： 1981年美國(guó)軍事運(yùn)籌學(xué)會(huì)出版了一本書(shū)，說(shuō)孫武是世界上第一個(gè)軍事運(yùn)籌學(xué)的實(shí)踐家。中國(guó)古代運(yùn)籌學(xué)思想的例子還有：田忌賽馬、圍魏救趙等等。 國(guó)外歷史上的阿基米德、達(dá)芬奇、伽利略研究過(guò)作戰(zhàn)問(wèn)題。,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,10,第一節(jié) 運(yùn)籌學(xué)的簡(jiǎn)史,早期運(yùn)籌思想： 第一次世界大戰(zhàn)時(shí)，希爾(A.V.Hill)為首的英國(guó)國(guó)防部防空試驗(yàn)小組進(jìn)行的高射炮系統(tǒng)利用研究. 英國(guó)的Lanchester（1914）戰(zhàn)斗方程（1954

4、年被硫黃島戰(zhàn)役（1945）數(shù)據(jù)證實(shí)）。這是首次真正成功地運(yùn)用近現(xiàn)代數(shù)學(xué)方法于運(yùn)籌學(xué)。,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,11,第一節(jié) 運(yùn)籌學(xué)的簡(jiǎn)史,早期運(yùn)籌思想： Erlang 1917 排隊(duì)論；Harris 1920 存儲(chǔ)論；Levinson 1930 零售貿(mào)易；康脫洛維奇 1939 線(xiàn)性規(guī)劃。,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,12,第一節(jié) 運(yùn)籌學(xué)的簡(jiǎn)史,軍事運(yùn)籌學(xué)階段（發(fā)展最早的分支） 1939年，以Blackett為首的一個(gè)研究小組，研究如何改進(jìn)英國(guó)的空防系統(tǒng)，提高英國(guó)本土防空能力。產(chǎn)生運(yùn)籌學(xué)（Operational research）一詞。 據(jù)不完全統(tǒng)計(jì)，二戰(zhàn)期間，僅在英

5、、美和加拿大，參加運(yùn)籌學(xué)工作的科學(xué)家超過(guò)700名，主要研究解決二戰(zhàn)中短期的和戰(zhàn)術(shù)性的問(wèn)題，如運(yùn)輸船編隊(duì)、空襲逃避、深水炸彈、轟炸機(jī)編隊(duì)等。 Operations Research名稱(chēng)意為軍事行動(dòng)研究（作戰(zhàn)研究）；日本運(yùn)用學(xué)；港臺(tái)作業(yè)研究；中國(guó)大陸運(yùn)籌學(xué)。,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,13,第一節(jié) 運(yùn)籌學(xué)的簡(jiǎn)史,管理運(yùn)籌學(xué)階段 戰(zhàn)后人員三分:軍隊(duì)、大學(xué)、企業(yè)。 大學(xué)：1948年，美國(guó)麻省理工學(xué)院率先開(kāi)設(shè)了運(yùn)籌學(xué)課程，許多大學(xué)群起效法，內(nèi)容也日益豐富.碩士、博士。 企業(yè)：以Rand（research and development）公司為代表，著重研究戰(zhàn)略性問(wèn)題；其它還有美國(guó)鋼鐵聯(lián)合公

6、司；英國(guó)國(guó)家煤炭局；IBM等。 在工業(yè)、農(nóng)業(yè)、經(jīng)濟(jì)和社會(huì)問(wèn)題各領(lǐng)域得到應(yīng)用。 理論分支：數(shù)學(xué)規(guī)劃（線(xiàn)性規(guī)劃、非線(xiàn)性規(guī)劃、整數(shù)規(guī)劃、參數(shù)規(guī)劃、目標(biāo)規(guī)劃、動(dòng)態(tài)規(guī)劃、隨機(jī)規(guī)劃等）、圖論與網(wǎng)絡(luò)、存儲(chǔ)論、對(duì)策論、決策論、排隊(duì)論、維修更新理論、搜索論、可靠性和質(zhì)量管理等。 1959年成立國(guó)際運(yùn)籌學(xué)聯(lián)合會(huì)（IFORS）。,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,14,第一節(jié) 運(yùn)籌學(xué)的簡(jiǎn)史,運(yùn)籌學(xué)在中國(guó) 最早介紹者：錢(qián)昌祚，科學(xué)，1925，Vol.10。 1955年9月，錢(qián)學(xué)森、許國(guó)志在歸國(guó)途中醞釀了運(yùn)籌學(xué)的引進(jìn)（1956年成立了中國(guó)科學(xué)院力學(xué)研究所運(yùn)籌組，“三三制”，即三個(gè)理科專(zhuān)業(yè)，三個(gè)工科專(zhuān)業(yè)，三個(gè)社會(huì)科

7、學(xué)專(zhuān)業(yè) ）。 華羅庚推廣優(yōu)選法、統(tǒng)籌法（19701982），讓國(guó)人真正認(rèn)識(shí)運(yùn)籌學(xué)，提高了我國(guó)的化工、電子、郵電、冶金、煤炭、農(nóng)業(yè)、運(yùn)輸?shù)刃袠I(yè)的管理水平。 1980年成立運(yùn)籌學(xué)會(huì)，1982年加入IFORS。 理論貢獻(xiàn)：中國(guó)郵遞員問(wèn)題、投入占用產(chǎn)出分析、運(yùn)輸問(wèn)題等。,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,15,第一章 緒論,第二節(jié) 運(yùn)籌學(xué)的性質(zhì)和特點(diǎn) 1、OR定義 1951年，莫爾斯（Philip M.Morse）和金博爾(George E.Kimball)出版了（1946年內(nèi)部出版，1951年公開(kāi)出版）第一本運(yùn)籌學(xué)專(zhuān)著：運(yùn)籌學(xué)的方法（The Methods of Operations Rese

8、arch）。書(shū)中總結(jié)了第二次世界大戰(zhàn)中運(yùn)籌學(xué)的軍事應(yīng)用，并且給出了運(yùn)籌學(xué)的一個(gè)著名定義：運(yùn)籌學(xué)是為執(zhí)行部門(mén)對(duì)它們控制下的“業(yè)務(wù)”活動(dòng)采取決策提供定量依據(jù)的科學(xué)方法。,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,16,第一章 緒論,第二節(jié) 運(yùn)籌學(xué)的性質(zhì)和特點(diǎn) 1、OR定義 O1：是一門(mén)應(yīng)用科學(xué)，它廣泛用現(xiàn)有的科學(xué)技術(shù)知識(shí)和數(shù)學(xué)方法，解決實(shí)際中提出的專(zhuān)門(mén)問(wèn)題。 O2：OR是一門(mén)給出問(wèn)題壞的答案的藝術(shù)，否則的話(huà)問(wèn)題的結(jié)果會(huì)更壞。,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,17,第二節(jié) 運(yùn)籌學(xué)的性質(zhì)和特點(diǎn) 托姆林森六原則： 合伙原則 ：多方、多專(zhuān)業(yè)合作 催化原則：改變?cè)锌捶?互相滲透原則：彼此滲透地考慮問(wèn)

9、題 獨(dú)立原則：不受他人或部門(mén)的影響 寬容原則：解決問(wèn)題的思路要寬，方法要多 平衡原則：考慮各種矛盾平衡，關(guān)系的平衡,第一章 緒論,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,18,第三節(jié) 運(yùn)籌學(xué)的工作步驟,提出和形成問(wèn)題 建立模型 求解 解的檢驗(yàn) 解的控制 解的實(shí)施,第一章 緒論,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,19,第四節(jié) 運(yùn)籌學(xué)的模型,模型的形式 形象、模擬、符號(hào)或數(shù)學(xué)模型 構(gòu)造模型的方法和思路 直接分析法 類(lèi)比法 數(shù)據(jù)分析法 試驗(yàn)分析法 想定（構(gòu)想）法,第一章 緒論,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,20,第四節(jié) 運(yùn)籌學(xué)的模型,模型的一般數(shù)學(xué)形式,2020/9/3,北京化工大學(xué)

10、經(jīng)管學(xué)院,21,第五節(jié) 運(yùn)籌學(xué)的應(yīng)用,早期主要在軍事領(lǐng)域,二戰(zhàn)后轉(zhuǎn)向民用,主要有以下方面： 1、市場(chǎng)銷(xiāo)售； 6、 人事管理； 2、生產(chǎn)計(jì)劃； 7、 設(shè)備管理； 3、庫(kù)存管理； 8、 工程的優(yōu)化設(shè)計(jì)； 4、運(yùn)輸問(wèn)題； 9、 計(jì)算機(jī)和信息系統(tǒng)； 5、財(cái)政和會(huì)計(jì)；10、城市管理。,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,22,第六節(jié) 運(yùn)籌學(xué)的展望,三個(gè)領(lǐng)域 運(yùn)籌學(xué)應(yīng)用 運(yùn)籌科學(xué) 運(yùn)籌數(shù)學(xué) 兩個(gè)趨勢(shì) 軟運(yùn)籌學(xué) 軟系統(tǒng)方法論、戰(zhàn)略選擇、問(wèn)題結(jié)構(gòu)法、超對(duì)策、亞對(duì)策、對(duì)話(huà)式計(jì)劃等。 軟計(jì)算 遺傳算法、模擬退火算法、神經(jīng)網(wǎng)絡(luò)、模糊邏輯、進(jìn)化計(jì)算、禁忌算法、蟻群優(yōu)化等。,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,

11、23,本節(jié)內(nèi)容簡(jiǎn)介,課程說(shuō)明 緒論 線(xiàn)性規(guī)劃問(wèn)題及其數(shù)學(xué)模型 小結(jié),重點(diǎn),2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,24,2.1 問(wèn)題的提出,某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)、兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原料的消耗，單位產(chǎn)品的獲利如表所示。問(wèn)應(yīng)如何安排計(jì)劃使該工廠獲利最多？（回想解決問(wèn)題的一般步驟？模型的一般數(shù)學(xué)形式？）,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,25,2.1 問(wèn)題的提出,提出和形成問(wèn)題：弄清問(wèn)題的目標(biāo)、可能的約束、可控變量及其參數(shù)，收集有關(guān)資料等。 建立模型：將變量、參數(shù)、目標(biāo)及約束關(guān)系用模型表示出來(lái)。,問(wèn)題的目標(biāo)：獲利最多。 可能的約束：設(shè)備臺(tái)時(shí)、原材料A、B

12、。 可控變量:產(chǎn)品生產(chǎn)量。 建立模型：將變量、參數(shù)、目標(biāo)及約束關(guān)系表示出來(lái)。,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,26,2.1 問(wèn)題的提出,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,27,練習(xí),例2-2 某企業(yè)生產(chǎn)甲、乙、丙三種型號(hào)產(chǎn)品，其產(chǎn)量主要受原料A和工時(shí)的限制，基本情況如表2-2所示，試建立該問(wèn)題的線(xiàn)性規(guī)劃模型。,表2-2 產(chǎn)品的基本情況,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,28,2.1 問(wèn)題的提出,模型特點(diǎn) 都用一組決策變量表示某一方案，且決策變量取值非負(fù)； 都有一個(gè)要達(dá)到的目標(biāo)，并且目標(biāo)要求可以表示成決策變量的線(xiàn)性函數(shù)； 都有一組約束條件，這些約束條件可以用決策變量的線(xiàn)性等式

13、或線(xiàn)性不等式來(lái)表示。 滿(mǎn)足以上三個(gè)條件的數(shù)學(xué)模型稱(chēng)為線(xiàn)性規(guī)劃的數(shù)學(xué)模型。,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,29,2.1 問(wèn)題的提出,線(xiàn)性規(guī)劃模型的一般形式為,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,30,2.2 圖解法,圖解法是用畫(huà)圖的方式求解線(xiàn)性規(guī)劃的一種方法。它雖然只能用于解二維（兩個(gè)變量）或三維的問(wèn)題，但其主要作用并不在于求解，而是在于能夠直觀地說(shuō)明線(xiàn)性規(guī)劃解的一些重要性質(zhì)。,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,31,1.2 圖解法,1 2 3 4 5 6 7 8,1 2 3 4 5 6,x2,x1,(4 2),0,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,32,2.2 圖解法,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,33,無(wú)窮多最優(yōu)解,無(wú)界解,x1,x1,x2,x2,x1,x2,無(wú)可行解,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,35,練習(xí):用圖解法求解下列線(xiàn)性規(guī)劃問(wèn)題,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,36,2.2 圖解法,圖解法直觀、簡(jiǎn)便，適合變量數(shù)為三個(gè)以下的情形。變量數(shù)超過(guò)三個(gè)時(shí)怎么求解？,LP解的情況,唯 一 解（例1） 無(wú) 窮 解（例2） 無(wú) 界 解（例3） 無(wú)可行解（例4）,有最優(yōu)解,無(wú)最優(yōu)解,2020/9/3,北京化工大學(xué)經(jīng)管學(xué)院,37,本節(jié)內(nèi)容簡(jiǎn)介,課程說(shuō)明 緒論 線(xiàn)性規(guī)劃問(wèn)題及其數(shù)學(xué)模型 小結(jié)