北京交通大學(xué)-運(yùn)籌學(xué)-教案1-緒論與圖解法改

1、管理運(yùn)籌學(xué) (OR),(美Operations Research),(英 Operational Research),學(xué)時(shí)數(shù)：48學(xué)時(shí),,教材：運(yùn)籌學(xué)教材編寫(xiě)組編《運(yùn)籌學(xué)》，清華大學(xué)出版社,參考書(shū)：其它版本的《管理運(yùn)籌學(xué)》；胡運(yùn)權(quán)主編《運(yùn)籌學(xué)教程》清華大學(xué)出版社；牛映武主編《運(yùn)籌學(xué)》 西安交通大學(xué)出版社；,成績(jī)?cè)u(píng)定： 作業(yè)：10分；考勤：10分；期中考試：10分期末考試：70分,§1 運(yùn)籌學(xué)的產(chǎn)生和發(fā)展

2、,運(yùn)籌學(xué)是運(yùn)用籌劃的科學(xué)，原意“作戰(zhàn)研究”或“運(yùn)用研究”。,一、 緒論,§1.1 運(yùn)籌學(xué)產(chǎn)生運(yùn)籌學(xué)的三個(gè)來(lái)源是軍事、管理和經(jīng)濟(jì),軍事 特點(diǎn)是：定量化、系統(tǒng)化方法迅速發(fā)展；采集真實(shí)的實(shí)際數(shù)據(jù)；多學(xué)科密切協(xié)作；解決方法滲透物理學(xué)的思想。,（1）波得塞（Bawdsey)雷達(dá)站的研究,1939年,任務(wù)：如何最好地運(yùn)用空軍及新發(fā)明的雷達(dá)保衛(wèi)國(guó)家,（2）Morse小組領(lǐng)導(dǎo)的運(yùn)籌學(xué)小組目標(biāo)：打破德軍對(duì)英吉利海峽的封鎖

3、建議：用飛機(jī)代替艦艇投擲水雷，起爆深度由100米改為25米，當(dāng)敵艦剛下潛時(shí)攻擊； 運(yùn)送物資的船隊(duì)及護(hù)衛(wèi)艦的編隊(duì)由小規(guī)模、多批次改為大規(guī)模、少批次。丘吉爾采納了建議,（3）英國(guó)戰(zhàn)斗機(jī)援法德軍突破馬奇諾防線(xiàn)，法軍節(jié)節(jié)敗退，英軍參與抗德。英軍的戰(zhàn)機(jī)均在法國(guó)上空與德軍作戰(zhàn)，指揮維護(hù)在法國(guó)。法國(guó)請(qǐng)求增援10中隊(duì)，邱吉爾同意。但運(yùn)籌學(xué)小組認(rèn)為：按現(xiàn)在的方式，英軍的援法戰(zhàn)機(jī)兩周內(nèi)會(huì)全軍覆滅；不增加戰(zhàn)機(jī)，而應(yīng)以英國(guó)本土為基地與德軍戰(zhàn)斗，使局面大為

4、改觀。,經(jīng)濟(jì) 馮·諾意曼（Von.neumann)《對(duì)策論與經(jīng)濟(jì)行為》,管理 康托洛維齊（Kantorovich) 生產(chǎn)配置問(wèn)題、原材料的合理利用、運(yùn)輸問(wèn)題等 《生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法》,§1.1 運(yùn)籌學(xué)的發(fā)展,運(yùn)籌學(xué)的發(fā)展大概分三個(gè)階段,第一個(gè)階段——蓬勃生長(zhǎng)期,·39年英國(guó)成立了世界上第一個(gè)運(yùn)籌學(xué)工作小組，從事防空預(yù)警系統(tǒng)的研制（研究如何合理運(yùn)用雷達(dá)）&

5、#183;1939年前蘇聯(lián)的康托洛維奇提出類(lèi)似線(xiàn)性規(guī)劃模型1960年《最佳資源利用的經(jīng)濟(jì)計(jì)算》，獲諾貝爾獎(jiǎng),··1947年美國(guó)數(shù)學(xué)家，提出線(xiàn)性規(guī)劃模型及單純形算法 ·42年美國(guó)成立運(yùn)籌學(xué)工作小組，研究戰(zhàn)斗行動(dòng)效能，行動(dòng)方式·戰(zhàn)爭(zhēng)結(jié)束，Mores和Kimball合著第一部運(yùn)籌學(xué)專(zhuān)著“運(yùn)籌學(xué)的方法”·戰(zhàn)后，運(yùn)籌學(xué)的應(yīng)用領(lǐng)域從軍事擴(kuò)展到其它各領(lǐng)域,·1948年英國(guó)

6、成立運(yùn)籌學(xué)學(xué)會(huì)·1952年美國(guó)成立運(yùn)籌學(xué)學(xué)會(huì)·1956年法國(guó)成立運(yùn)籌學(xué)學(xué)會(huì)·1959年英、美、法成立運(yùn)籌學(xué)聯(lián)合會(huì),第二階段——危機(jī)期,六、七十年代,第三階段——運(yùn)籌學(xué)發(fā)展的正確之路,理念更新、實(shí)踐為本、學(xué)科交融,我國(guó)運(yùn)籌學(xué)的發(fā)展,§2 運(yùn)籌學(xué)的釋義,運(yùn)籌學(xué)具有如下的性質(zhì)特點(diǎn),（1）運(yùn)籌學(xué)是一門(mén)應(yīng)用科學(xué),(2) 運(yùn)籌學(xué)的目的是尋找最佳解決問(wèn)題的方案， 為決策者的最優(yōu)決策提供依據(jù),

7、(3) 以數(shù)學(xué)為基礎(chǔ)提供定量分析,（4）以計(jì)算機(jī)為手段,（5） 以軟科學(xué)研究軟系統(tǒng),（6） 多學(xué)科專(zhuān)家集體協(xié)作研究,由一支綜合性的隊(duì)伍，采用科學(xué)的方法，為一些涉及到有機(jī)系統(tǒng)（人-機(jī)）的控制系統(tǒng)問(wèn)題提供解答，為該系統(tǒng)的總目標(biāo)服務(wù)的學(xué)科?！X(qián)學(xué)森,運(yùn)用科學(xué)方法來(lái)解決工業(yè)、商業(yè)、政府、國(guó)防等部門(mén)里有關(guān)人力、機(jī)器、物資、金錢(qián)等大型系統(tǒng)的指揮或管理中所出現(xiàn)的復(fù)雜問(wèn)題的一門(mén)學(xué)科。其目的是“幫助管理者以科學(xué)方法確定其方針和行動(dòng)”——英國(guó)運(yùn)籌學(xué)會(huì),運(yùn)

8、籌學(xué)是應(yīng)用系統(tǒng)的、科學(xué)的、數(shù)學(xué)分析的方法，通過(guò)建模、檢驗(yàn)和求解數(shù)學(xué)模型而獲得最優(yōu)決策的科學(xué)。——近代運(yùn)籌學(xué)工作者,運(yùn)籌學(xué)的定義,執(zhí)行部門(mén)對(duì)所控制的業(yè)務(wù)作出決策提供數(shù)量上的科學(xué)或利用所應(yīng)用科學(xué)，執(zhí)行部門(mén)對(duì)其所屬業(yè)務(wù)作出決策提供數(shù)量上依據(jù)的一門(mén)科學(xué)?！狹orse,·規(guī)劃論——線(xiàn)性規(guī)劃、目標(biāo)規(guī)劃、非線(xiàn)性規(guī)劃、整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃、組合規(guī)劃等 ·圖與網(wǎng)絡(luò) ·存儲(chǔ)論 ·排隊(duì)論

9、 ·對(duì)策論 ·決策論 ·仿真 ·馬爾科夫過(guò)程 ·可靠性 多目標(biāo)規(guī)劃 ……,§3 運(yùn)籌學(xué)的分支,§3 運(yùn)籌學(xué)的工作步驟,(1) 提出和形成問(wèn)題。即要弄清問(wèn)題的目標(biāo)，可能的約束，問(wèn)題的可控變量以及有關(guān)參數(shù)；(2) 建立模型。即把問(wèn)題中可控變量、參數(shù)和目標(biāo)與約束之間的關(guān)系用一定的模型表示出來(lái)； (3) 求解。

10、用各種手段( 主要是數(shù)學(xué)方法，也可用其他方法 )將模型求解。解可以是最優(yōu)解、次優(yōu)解、滿(mǎn)意解。復(fù)雜模型的求解需用計(jì)算機(jī)，解的精度要求可由決策者提出；(4) 解的檢驗(yàn)。首先檢查求解步驟和程序有無(wú)錯(cuò)誤，然后檢查解是否反應(yīng)現(xiàn)實(shí)問(wèn)題；(5) 解的控制。通過(guò)控制解的變化過(guò)程決定對(duì)解是否要作一定的改變； (6) 解的實(shí)施。是指將解用到實(shí)際中必須考慮到實(shí)施的問(wèn)題，如向?qū)嶋H部門(mén)講清楚用法、在實(shí)施中可能產(chǎn)生的問(wèn)題和修改。,§4 本

11、課程的要求,本課程的授課對(duì)象是管理科學(xué)與工程類(lèi)及交通運(yùn)輸類(lèi)專(zhuān)業(yè),本科生，屬管理類(lèi)專(zhuān)業(yè)技術(shù)基礎(chǔ)必修課。,,,學(xué)生通過(guò)學(xué)習(xí)該課程，應(yīng)了解管理運(yùn)籌學(xué)對(duì)優(yōu)化決策問(wèn)題進(jìn),行定量研究的特點(diǎn)，,理解,線(xiàn)性規(guī)劃、整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃、圖與,網(wǎng)絡(luò)、排隊(duì)論和庫(kù)存論,等分支的基本優(yōu)化,原理，掌握,其中常用的,模型和算法,，,具有一定的建模能力。,,,先修課程主要為,線(xiàn)性代數(shù)和概率統(tǒng)計(jì),，學(xué)生對(duì)它們的掌握程,度直接影響本課程的學(xué)習(xí)，所以要求學(xué)生課前要做必要的復(fù)習(xí)

12、。,,,學(xué)習(xí)方法：理解、掌握基本理論和方法的基礎(chǔ)上，適當(dāng)作些,習(xí)題。,,,,二. 線(xiàn)性規(guī)劃 (LP )( Linear Programming),第一章 線(xiàn)性規(guī)劃與單純形法1947年由美國(guó)空軍G.B.Dantzig提出。,本部分是課程的最重要部分,§1 線(xiàn)性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,1．1 問(wèn)題的提出,利潤(rùn)最大 目標(biāo)函數(shù) max z = 2x1+ 3x2,x1,x2,,,,,0,,,,4,Q2(4,2),Q1,Q3

13、,Q4,,,,,,,,4x1=16,,4x2=12,,x1+2x2=8,3,Q2,,4o.向著目標(biāo)函數(shù)的優(yōu)化方向平移等值線(xiàn)，直至得到等值線(xiàn)與可行域的最后交點(diǎn)，這種點(diǎn)就對(duì)應(yīng)最優(yōu)解。,線(xiàn)性規(guī)劃問(wèn)題解的存在情況：,(1)存在唯一最優(yōu)解,如例1,（2）有無(wú)窮多最優(yōu)解,若將例1目標(biāo)函數(shù)變?yōu)?max z = 2x1+ 4x2，則問(wèn)題變得存在無(wú)窮多最優(yōu)解。如圖,（3）有無(wú)界解( 無(wú)有限最優(yōu)解或無(wú)最優(yōu)解 ),（4）無(wú)可行解（可行域?yàn)榭占?思考：,1。