第01講+緒論+線性規(guī)劃模型+

1、Operational Research 運籌學(xué)王坤 講師/博交通運輸與物流學(xué)院Operational Research 課程背景介紹p 教材 運籌學(xué)，第三版，清華大學(xué)出版社p 參考教材 數(shù)據(jù)、模型與決策，弗雷德里克 S 希利爾等著，任建標(biāo)譯，中國財政經(jīng)濟出版社.Operational Research Operational Research 課程背景介紹p 課程教學(xué)共68學(xué)時，授課60學(xué)時，習(xí)題課4學(xué)時，機動學(xué)習(xí)4學(xué)時。周次周次內(nèi)容內(nèi)容周次周次內(nèi)容內(nèi)容1緒論、線性規(guī)劃問題10動態(tài)規(guī)劃2單純形法11動態(tài)規(guī)劃應(yīng)用舉例3單線形法的矩陣描述及改進12排隊論4對偶問題及靈敏

2、度分析13排隊論5運輸問題14存儲論6整數(shù)規(guī)劃15對策論7圖與網(wǎng)絡(luò)優(yōu)化16復(fù)習(xí)+習(xí)題 8圖與網(wǎng)絡(luò)優(yōu)化17機動+答疑9習(xí)題+期中考試18考試 （考勤/作業(yè)，10%；期中，20%；期末，70%）Operational Research 一、緒論IntroductionOperational Research 1.為什么學(xué)習(xí)運籌學(xué)？經(jīng)經(jīng) 營營設(shè)計設(shè)計 管理管理 規(guī)劃規(guī)劃 組織、管理組織、管理 系統(tǒng)、優(yōu)化系統(tǒng)、優(yōu)化 技術(shù)、經(jīng)濟技術(shù)、經(jīng)濟 法律、法規(guī)法律、法規(guī) 市場、流通市場、流通信信息息技技術(shù)術(shù)交交通通運運輸輸倉倉 儲儲包包 裝裝流流通通加加工工裝裝卸卸p運籌學(xué)是物流工程專業(yè)的必修課Operation

3、al Research p運籌學(xué)能夠解決典型物流問題。 (1)存儲問題1.為什么學(xué)習(xí)運籌學(xué)？Operational Research (2)廠內(nèi)物料優(yōu)化問題1.為什么學(xué)習(xí)運籌學(xué)？Operational Research SF11098543276(3)最短路問題1.為什么學(xué)習(xí)運籌學(xué)？Operational Research (4)物流中心選址問題1.為什么學(xué)習(xí)運籌學(xué)？Operational Research 2.什么是運籌學(xué)？ 為決策機構(gòu)決策機構(gòu)在對其控制下業(yè)務(wù)活動進行決策決策時，提供以數(shù)量化數(shù)量化為基礎(chǔ)的科學(xué)方法方法。Morse，Kimball 運籌學(xué)是一門應(yīng)用科學(xué)，它廣泛應(yīng)用現(xiàn)有的科學(xué)技術(shù)

4、知識和數(shù)學(xué)方法，解決實際中提出的專門問題，為決策者選擇最優(yōu)決策提供定量依據(jù)。制定決策管理者管理者運用定量分析來改善決策的制定管理科學(xué)管理科學(xué)Operational Research 2.什么是運籌學(xué)？p 運籌學(xué)已被應(yīng)用于工商企業(yè)、軍事部門、民政事業(yè)等研究組織內(nèi)的統(tǒng)籌協(xié)調(diào)問題，故其應(yīng)用不受行業(yè)、部門的限制應(yīng)用不受行業(yè)、部門的限制；p 運籌學(xué)既對各種經(jīng)營進行創(chuàng)造性的科學(xué)研究，又涉及到組織的實際管理問題，它具有很強的實踐性很強的實踐性，最終應(yīng)能向決策者提供建設(shè)性意見，并應(yīng)收到實效；p 運籌學(xué)以整體最優(yōu)為目標(biāo)，從系統(tǒng)的觀點出發(fā)，力圖以整個系統(tǒng)最佳的方式來解決該系統(tǒng)各部門之間的利益沖突。對所研究的問題求

5、出最優(yōu)解，尋求最佳的行動方案，所以它也可以看成是一門優(yōu)化技術(shù)優(yōu)化技術(shù)，提供的是解決各類問題的優(yōu)化方法。Operational Research 3.運籌學(xué)的發(fā)展p1917年，愛爾朗的排隊論公式；年，愛爾朗的排隊論公式；p1939年，英國成立第一個運籌學(xué)工作小組，從事防空預(yù)警系統(tǒng)研年，英國成立第一個運籌學(xué)工作小組，從事防空預(yù)警系統(tǒng)研制（如何合理運用雷達），使原先平均擊落一架敵機要發(fā)制（如何合理運用雷達），使原先平均擊落一架敵機要發(fā)2萬發(fā)炮萬發(fā)炮彈改善為只要發(fā)彈改善為只要發(fā)4千發(fā)炮彈；千發(fā)炮彈；p1939年，前蘇聯(lián)的康托洛維奇提出類似線性規(guī)劃模型；年，前蘇聯(lián)的康托洛維奇提出類似線性規(guī)劃模型；p19

6、60年，年，康托洛維康托洛維奇出版奇出版最佳資源利用的經(jīng)濟計算最佳資源利用的經(jīng)濟計算一書，因一書，因此獲諾貝爾獎；此獲諾貝爾獎；p1942年，美國成立運籌學(xué)工作小組，研究戰(zhàn)斗行動效能、行動方年，美國成立運籌學(xué)工作小組，研究戰(zhàn)斗行動效能、行動方式；式；p1947年，美國數(shù)學(xué)家丹捷格提出線性規(guī)劃模型和單純形算法；年，美國數(shù)學(xué)家丹捷格提出線性規(guī)劃模型和單純形算法；p二戰(zhàn)后，二戰(zhàn)后，Morse和和Kimball合著第一部專著合著第一部專著運籌學(xué)方法運籌學(xué)方法；p運籌學(xué)的應(yīng)用領(lǐng)域從軍事擴展到其它各領(lǐng)域。運籌學(xué)的應(yīng)用領(lǐng)域從軍事擴展到其它各領(lǐng)域。Operational Research 3.運籌學(xué)的發(fā)展p1

7、948年，英國成立運籌學(xué)會；年，英國成立運籌學(xué)會；p1952年，美國成立運籌學(xué)會；年，美國成立運籌學(xué)會；p1956年，法國成立運籌學(xué)會；年，法國成立運籌學(xué)會；p1959年，英、美、法成立運籌學(xué)聯(lián)合會；年，英、美、法成立運籌學(xué)聯(lián)合會；p我國在我國在20世紀(jì)世紀(jì)50年代引入運籌學(xué)，年代引入運籌學(xué)，1956年時曾使用年時曾使用“運用運用學(xué)學(xué)”、1957年定名為年定名為“運籌學(xué)運籌學(xué)”，1982年加入世界運籌學(xué)聯(lián)年加入世界運籌學(xué)聯(lián)合會。合會。Operational Research 3.運籌學(xué)的發(fā)展p規(guī)劃論：線性規(guī)劃、目標(biāo)規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、動規(guī)劃論：線性規(guī)劃、目標(biāo)規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、

8、動態(tài)規(guī)劃、組合規(guī)劃等。態(tài)規(guī)劃、組合規(guī)劃等。p圖與網(wǎng)絡(luò)圖與網(wǎng)絡(luò) 存儲論存儲論 排隊論排隊論p對策論對策論 決策論決策論 啟發(fā)式方法啟發(fā)式方法 Operational Research 4.運籌學(xué)的工作步驟p弄清問題的目標(biāo)，可能的約束，問題的可控變量以及有弄清問題的目標(biāo)，可能的約束，問題的可控變量以及有關(guān)參數(shù)，搜集有關(guān)關(guān)參數(shù)，搜集有關(guān)資料。資料。p把問題中可控把問題中可控變量、參數(shù)變量、參數(shù)和目標(biāo)與約束之間的關(guān)系用一和目標(biāo)與約束之間的關(guān)系用一定的模型表示出來。定的模型表示出來。p用各種手段（主要是數(shù)學(xué)方法，也可用其他方法）將模用各種手段（主要是數(shù)學(xué)方法，也可用其他方法）將模型求解。解可以是最優(yōu)解、

9、次優(yōu)解、滿意解。復(fù)雜模型型求解。解可以是最優(yōu)解、次優(yōu)解、滿意解。復(fù)雜模型的求解需用計算機，解的精度要可的求解需用計算機，解的精度要可由決策者由決策者提出。提出。Operational Research 4.運籌學(xué)的工作步驟p首先檢查求解步驟和程序有無錯誤，然后檢查解是否反首先檢查求解步驟和程序有無錯誤，然后檢查解是否反映現(xiàn)實映現(xiàn)實問題。問題。p通過控制解的變化過程決定是否要作一定的通過控制解的變化過程決定是否要作一定的改變。改變。p將解用到實際中必須考慮到實施的問題，如向?qū)嶋H部門將解用到實際中必須考慮到實施的問題，如向?qū)嶋H部門講清解的用法，在實施中可能產(chǎn)生的問題和修改講清解的用法，在實施中可能

10、產(chǎn)生的問題和修改Operational Research 4.運籌學(xué)的工作步驟問題的確定分析問題建立模型軟件求解結(jié)果分析確定解決方案實施方案控制Operational Research 5.運籌學(xué)的模型p研究者對研究者對經(jīng)過思維經(jīng)過思維后用后用描述所認識到的客觀對象描述所認識到的客觀對象。p利用模型可以進行一定的預(yù)測、靈敏度分析等。利用模型可以進行一定的預(yù)測、靈敏度分析等。模型是一件實際事物或情況的代表或抽象模型是一件實際事物或情況的代表或抽象。實際實際事物是事物是A A，若，若B B能夠真實地描述能夠真實地描述A A，則稱，則稱B B為為A A的的模型。模型。形象模型模擬模型符號或數(shù)學(xué)模型

11、把實際事物的尺寸加以改變（放大或縮?。?，看起來和實際的東西基本相似的模型。 如地圖的等高線、地圖的顏色、飛機風(fēng)洞試驗、模擬駕駛等。 用數(shù)學(xué)符號建立起來的通過等式和不等式以及圖表、框圖等來描述實際事物的特征或內(nèi)在關(guān)系的模型。Operational Research 5.運籌學(xué)的模型p直接分析法直接分析法：按研究者對問題內(nèi)在機理的認識直接構(gòu)造出模型。如，：按研究者對問題內(nèi)在機理的認識直接構(gòu)造出模型。如，線性規(guī)劃模型、投入產(chǎn)出模型、排隊模型、存儲模型、決策和對策線性規(guī)劃模型、投入產(chǎn)出模型、排隊模型、存儲模型、決策和對策模型等。模型等。p類比法類比法：針對某一問題，應(yīng)用不同方法構(gòu)造結(jié)構(gòu)性質(zhì)類同的模型進

12、：針對某一問題，應(yīng)用不同方法構(gòu)造結(jié)構(gòu)性質(zhì)類同的模型進行類比。如，物理學(xué)中的機械系統(tǒng)、氣體運力學(xué)系統(tǒng)、水力學(xué)系統(tǒng)、行類比。如，物理學(xué)中的機械系統(tǒng)、氣體運力學(xué)系統(tǒng)、水力學(xué)系統(tǒng)、熱力學(xué)系統(tǒng)及電路系統(tǒng)之間類比。熱力學(xué)系統(tǒng)及電路系統(tǒng)之間類比。p數(shù)據(jù)分析法數(shù)據(jù)分析法：通過數(shù)據(jù)的搜集，應(yīng)用統(tǒng)計分析方法，了解問題機理：通過數(shù)據(jù)的搜集，應(yīng)用統(tǒng)計分析方法，了解問題機理的建模過程。如，回歸分析模型、概率統(tǒng)計模型等。的建模過程。如，回歸分析模型、概率統(tǒng)計模型等。p試驗分析法試驗分析法：通過對局部試驗的數(shù)據(jù)加以分析來構(gòu)造模型的方法。：通過對局部試驗的數(shù)據(jù)加以分析來構(gòu)造模型的方法。p想定（構(gòu)想）法想定（構(gòu)想）法：在已有的

13、知識、經(jīng)驗和研究基礎(chǔ)上，對于將來可：在已有的知識、經(jīng)驗和研究基礎(chǔ)上，對于將來可能發(fā)生的情況給出邏輯上合理的設(shè)想和描述，然后用已有的方法構(gòu)能發(fā)生的情況給出邏輯上合理的設(shè)想和描述，然后用已有的方法構(gòu)造模型并不斷修正完善的方法。如，社會、經(jīng)濟、軍事問題等。造模型并不斷修正完善的方法。如，社會、經(jīng)濟、軍事問題等。Operational Research 5.運籌學(xué)的模型(,)ijkUf x y(,)0ijkg x yixjykOperational Research 6.運籌學(xué)的應(yīng)用n生產(chǎn)管理n交通網(wǎng)絡(luò)n物流配送n市場營銷n項目評價n等等Operational Research 運籌學(xué)Operatio

14、nal Research交通運輸與物流學(xué)院Operational Research 第一章 線性規(guī)劃與單純形法p線性規(guī)劃問題及其數(shù)學(xué)模型p圖解法及線性規(guī)劃的幾何意義p單純形法與單純形表p單純形法的進一步討論p應(yīng)用舉例Operational Research 1.線性規(guī)劃問題及其數(shù)學(xué)模型（p8）產(chǎn)品產(chǎn)品資源限制設(shè) 備原材料 A原材料 B1 臺時/件4 kg/件0 kg/件2 臺時/件0 kg/件4 kg/件8臺時16kg12kg利潤2元3元問：如何組織生產(chǎn)才能使利潤最大？ 問題描述Operational Research 1.線性規(guī)劃問題及其數(shù)學(xué)模型（p8）產(chǎn)品產(chǎn)品資源限制設(shè) 備原材料 A原材料

15、 B1 臺時4 kg0 kg2 臺時0 kg4 kg8臺時16kg12kg利潤2元3元 第1步 確定決策變量 問題中要確定的未知量，表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制。1x2x產(chǎn)品的產(chǎn)量產(chǎn)品的產(chǎn)量 第2步 確定目標(biāo)函數(shù)12max23zxxOperational Research 1.線性規(guī)劃問題及其數(shù)學(xué)模型（p8）產(chǎn)品產(chǎn)品資源限制設(shè) 備原材料 A原材料 B1 臺時4 kg0 kg2 臺時0 kg4 kg8臺時16kg12kg利潤2元3元 第3步 確定約束條件Operational Research 1.線性規(guī)劃問題及其數(shù)學(xué)模型產(chǎn)品車間A車間B單位產(chǎn)品利潤市場限制甲乙211

16、164車間可用工時108問：如何組織生產(chǎn)才能使利潤最大？ 問題描述Operational Research 1.線性規(guī)劃問題及其數(shù)學(xué)模型 第1步 確定決策變量 問題中要確定的未知量，表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制。1x2x產(chǎn)品甲的產(chǎn)量產(chǎn)品乙的產(chǎn)量 第2步 確定目標(biāo)函數(shù)12max64zxx產(chǎn)品車間A車間B單位產(chǎn)品利潤市場限制甲乙211164車間可用工時108Operational Research 1.線性規(guī)劃問題及其數(shù)學(xué)模型 第3步 確定約束條件產(chǎn)品車間A車間B單位產(chǎn)品利潤市場限制甲乙211164車間可用工時108Operational Research 1.線性規(guī)劃

17、問題及其數(shù)學(xué)模型12max23zxx121228416412xxxx120 xx、12max64zxx1212221087xxxxx120 xx、p 每一個問題都用一組表示某一方案，這組決策變量的值就代表一個具體方案。一般這些變量取值是的。p 存在有關(guān)的數(shù)據(jù)，同決策變量構(gòu)成，這些約束條件可以用來表示。p 都有一個，它可用決策變量及其有關(guān)的價值系數(shù)構(gòu)成的（稱為目標(biāo)函數(shù)）來表示。按問題的不同，要求目標(biāo)函數(shù)實現(xiàn)。Operational Research 1.線性規(guī)劃問題及其數(shù)學(xué)模型1 122max(min)nnzc xc xc x11 11221121 1222221 12212( , )( , )

18、( , ),0nnnnmmmnnmna xa xa xba xa xa xba xaxaxbxxx 目標(biāo)函數(shù)約束條件 滿足以上三個條件（決策變量、約束條件、目標(biāo)函數(shù)決策變量、約束條件、目標(biāo)函數(shù)）的數(shù)學(xué)模型稱為線性規(guī)劃的數(shù)學(xué)模型，其一般形式為：Operational Research 1.線性規(guī)劃問題及其數(shù)學(xué)模型Operational Research 1.線性規(guī)劃問題及其數(shù)學(xué)模型1 122maxnnzc xc xc x11 11221121 1222221 12212,0nnnnmmmnnmna xa xa xba xa xa xba xaxaxbxxx目標(biāo)函數(shù)約束條件Operational

19、Research 1.線性規(guī)劃問題及其數(shù)學(xué)模型1 122maxnnzc xc xc x11 11221121 1222221 12212,0nnnnmmmnnmna xa xa xba xa xa xba xaxaxbxxx11max 1,2,.0 1,2,.,njjinijjijjzc xa xbimxjn簡寫Operational Research 1.線性規(guī)劃問題及其數(shù)學(xué)模型11max 1,2,.0 1,2,.,njjinijjijjzc xa xbimxjn112111222max0 1,2,. () njjjjnjjjnmmjzCXP xbxjnC = c ,c ,.caxbaxbX P b .xba其中：1111231 m ax 00 .0. (,.,) 0.0 C- nmm nzCXAXbXaaAPPPaab X - 111121 max 00 .0. ( ,.,) 0.0nnmmnZCXAXbXaaAP PPaa用向量表示用矩陣表示A：約束條件系數(shù)矩陣b：資源向量 C：價值向量X：決策變量向量Operat