北京交通大學-運籌學-教案1-緒論與圖解法改

1、管理運籌學 (OR),(美Operations Research),(英 Operational Research),學時數：48學時,,教材：運籌學教材編寫組編《運籌學》，清華大學出版社,參考書：其它版本的《管理運籌學》；胡運權主編《運籌學教程》清華大學出版社；牛映武主編《運籌學》 西安交通大學出版社；,成績評定： 作業(yè)：10分；考勤：10分；期中考試：10分期末考試：70分,§1 運籌學的產生和發(fā)展

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

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

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

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

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

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

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

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

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

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

12、。,,,學習方法：理解、掌握基本理論和方法的基礎上，適當作些,習題。,,,,二. 線性規(guī)劃 (LP )( Linear Programming),第一章 線性規(guī)劃與單純形法1947年由美國空軍G.B.Dantzig提出。,本部分是課程的最重要部分,§1 線性規(guī)劃問題及其數學模型,1．1 問題的提出,利潤最大 目標函數 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.向著目標函數的優(yōu)化方向平移等值線，直至得到等值線與可行域的最后交點，這種點就對應最優(yōu)解。,線性規(guī)劃問題解的存在情況：,(1)存在唯一最優(yōu)解,如例1,（2）有無窮多最優(yōu)解,若將例1目標函數變?yōu)?max z = 2x1+ 4x2，則問題變得存在無窮多最優(yōu)解。如圖,（3）有無界解( 無有限最優(yōu)解或無最優(yōu)解 ),（4）無可行解（可行域為空集）,思考：,1。