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

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

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

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

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

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

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

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

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

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

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

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

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