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

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

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

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

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

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

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

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

8、動(dòng)態(tài)規(guī)劃、組合規(guī)劃等。態(tài)規(guī)劃、組合規(guī)劃等。p圖與網(wǎng)絡(luò)圖與網(wǎng)絡(luò) 存儲(chǔ)論存儲(chǔ)論 排隊(duì)論排隊(duì)論p對策論對策論 決策論決策論 啟發(fā)式方法啟發(fā)式方法 Operational Research 4.運(yùn)籌學(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ù)雜模型的求解需用計(jì)算機(jī)，解的精度要可的求解需用計(jì)算機(jī)，解的精度要可由決策者由決策者提出。提出。Operational Research 4.運(yùn)籌學(xué)的工作步驟p首先檢查求解步驟和程序有無錯(cuò)誤，然后檢查解是否反首先檢查求解步驟和程序有無錯(cuò)誤，然后檢查解是否反映現(xiàn)實(shí)映現(xiàn)實(shí)問題。問題。p通過控制解的變化過程決定是否要作一定的通過控制解的變化過程決定是否要作一定的改變。改變。p將解用到實(shí)際中必須考慮到實(shí)施的問題，如向?qū)嶋H部門將解用到實(shí)際中必須考慮到實(shí)施的問題，如向?qū)嶋H部門講清解的用法，在實(shí)施中可能產(chǎn)生的問題和修改講清解的用法，在實(shí)施中可能

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

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

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

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

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

15、 B1 臺(tái)時(shí)4 kg0 kg2 臺(tái)時(shí)0 kg4 kg8臺(tái)時(shí)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 臺(tái)時(shí)4 kg0 kg2 臺(tái)時(shí)0 kg4 kg8臺(tái)時(shí)16kg12kg利潤2元3元 第3步 確定約束條件Operational Research 1.線性規(guī)劃問題及其數(shù)學(xué)模型產(chǎn)品車間A車間B單位產(chǎn)品利潤市場限制甲乙211

16、164車間可用工時(shí)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車間可用工時(shí)108Operational Research 1.線性規(guī)劃問題及其數(shù)學(xué)模型 第3步 確定約束條件產(chǎn)品車間A車間B單位產(chǎn)品利潤市場限制甲乙211164車間可用工時(shí)108Operational Research 1.線性規(guī)劃

17、問題及其數(shù)學(xué)模型12max23zxx121228416412xxxx120 xx、12max64zxx1212221087xxxxx120 xx、p 每一個(gè)問題都用一組表示某一方案，這組決策變量的值就代表一個(gè)具體方案。一般這些變量取值是的。p 存在有關(guān)的數(shù)據(jù)，同決策變量構(gòu)成，這些約束條件可以用來表示。p 都有一個(gè)，它可用決策變量及其有關(guān)的價(jià)值系數(shù)構(gòu)成的（稱為目標(biāo)函數(shù)）來表示。按問題的不同，要求目標(biāo)函數(shù)實(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ù)約束條件 滿足以上三個(gè)條件（決策變量、約束條件、目標(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：價(jià)值向量X：決策變量向量Operat