1、管理管理運籌學運籌學 (OR)( (美美Operations Research)Operations Research)( (英英 Operational Research)Operational Research)學時數(shù)：48學時教材：運籌學教材編寫組編運籌學，清華大學出版社參考書：其它版本的管理運籌學；胡運權(quán)主編運籌學教程清華大學出版社；牛映武主編運籌學 西安交通大學出版社；成績評定： 作業(yè)：10分；考勤：10分；期中考試：10分期末考試：70分1 1 運籌學的產(chǎn)生和發(fā)展運籌學的產(chǎn)生和發(fā)展運籌學是運用籌劃的科學，運籌學是運用籌劃的科學，原意原意“作戰(zhàn)研究作戰(zhàn)研究”或或“運用研究運用研究”。

2、一、一、 緒論緒論1.1 運籌學產(chǎn)生運籌學產(chǎn)生運籌學的三個來源是軍事、管理和經(jīng)濟運籌學的三個來源是軍事、管理和經(jīng)濟軍事 特點是：定量化、系統(tǒng)化方法迅速發(fā)展；采集真實的實際數(shù)據(jù)；多學科密切協(xié)作；解決方法滲透物理學的思想。（1）波得塞（Bawdsey)雷達站的研究1939年任務(wù)：如何最好地運用空軍及新發(fā)明的雷達保衛(wèi)國家（2）Morse小組領(lǐng)導的運籌學小組目標：打破德軍對英吉利海峽的封鎖建議：用飛機代替艦艇投擲水雷，起爆深度由100米改為25米，當敵艦剛下潛時攻擊； 運送物資的船隊及護衛(wèi)艦的編隊由小規(guī)模、多批次改為大規(guī)模、少批次。丘吉爾采納了建議（3）英國戰(zhàn)斗機援法德軍突破馬奇諾防線，法軍節(jié)節(jié)敗退，

3、英軍參與抗德。英軍的戰(zhàn)機均在法國上空與德軍作戰(zhàn)，指揮維護在法國。法國請求增援10中隊，邱吉爾同意。但運籌學小組認為：按現(xiàn)在的方式，英軍的援法戰(zhàn)機兩周內(nèi)會全軍覆滅；不增加戰(zhàn)機，而應以英國本土為基地與德軍戰(zhàn)斗，使局面大為改觀。經(jīng)濟 馮諾意曼（Von.neumann)對策論與經(jīng)濟行為管理 康托洛維齊（Kantorovich) 生產(chǎn)配置問題、原材料的合理利用、運輸問題等 生產(chǎn)組織與計劃中的數(shù)學方法1.1 運籌學的發(fā)展運籌學的發(fā)展運籌學的發(fā)展大概分三個階段運籌學的發(fā)展大概分三個階段第一個階段第一個階段蓬勃生長期蓬勃生長期3939年英國成立了世界上第一個運籌學工作小組，年英國成立了世界上第一個運籌學工作小

4、組，從事防空預警系統(tǒng)的研制（研究如何合理運用雷達）從事防空預警系統(tǒng)的研制（研究如何合理運用雷達）19391939年前蘇聯(lián)的康托洛維奇提出類似線性規(guī)劃模型年前蘇聯(lián)的康托洛維奇提出類似線性規(guī)劃模型19601960年年最佳資源利用的經(jīng)濟計算最佳資源利用的經(jīng)濟計算，獲諾貝爾獎，獲諾貝爾獎19471947年美國數(shù)學家，提出線性規(guī)劃模型及單純形算法年美國數(shù)學家，提出線性規(guī)劃模型及單純形算法 4242年美國成立運籌學工作小組，研究戰(zhàn)斗行動效能，年美國成立運籌學工作小組，研究戰(zhàn)斗行動效能，行動方式行動方式戰(zhàn)爭結(jié)束，戰(zhàn)爭結(jié)束，MoresMores和和KimballKimball合著第一部運籌學專著合著第一部運籌

5、學專著“運籌運籌學的方法學的方法”戰(zhàn)后，運籌學的應用領(lǐng)域從軍事擴展到其它各領(lǐng)域戰(zhàn)后，運籌學的應用領(lǐng)域從軍事擴展到其它各領(lǐng)域19481948年英國成立運籌學學會年英國成立運籌學學會19521952年美國成立運籌學學會年美國成立運籌學學會19561956年法國成立運籌學學會年法國成立運籌學學會19591959年英、美、法成立運籌學聯(lián)合會年英、美、法成立運籌學聯(lián)合會 第二階段第二階段危機期危機期六、七十年代六、七十年代第三階段第三階段運籌學發(fā)展的正確之路運籌學發(fā)展的正確之路理念更新、實踐為本、學科交融理念更新、實踐為本、學科交融我國運籌學的發(fā)展我國運籌學的發(fā)展2 2 運籌學的釋義運籌學的釋義運籌學具

6、有如下的性質(zhì)特點（1）運籌學是一門應用科學）運籌學是一門應用科學(2) 運籌學的目的是尋找最佳解決問題的方案，運籌學的目的是尋找最佳解決問題的方案， 為決策者的最優(yōu)決策提供依據(jù)為決策者的最優(yōu)決策提供依據(jù)(3) 以數(shù)學為基礎(chǔ)提供定量分析以數(shù)學為基礎(chǔ)提供定量分析（4）以計算機為手段）以計算機為手段 （5） 以軟科學研究軟系統(tǒng)以軟科學研究軟系統(tǒng)（6） 多學科專家集體協(xié)作研究多學科專家集體協(xié)作研究 由一支綜合性的隊伍，采用科學的方法，為一些涉及到有機系統(tǒng)（人-機）的控制系統(tǒng)問題提供解答，為該系統(tǒng)的總目標服務(wù)的學科。錢學森 運用科學方法來解決工業(yè)、商業(yè)、政府、國防等部門里有關(guān)人力、機器、物資、金錢等大型

7、系統(tǒng)的指揮或管理中所出現(xiàn)的復雜問題的一門學科。其目的是“幫助管理者以科學方法確定其方針和行動”英國運籌學會 運籌學是應用系統(tǒng)的、科學的、數(shù)學分析的方法，通過建模、檢驗和求解數(shù)學模型而獲得最優(yōu)決策的科學。近代運籌學工作者運籌學的定義運籌學的定義 執(zhí)行部門對所控制的業(yè)務(wù)作出決策提供數(shù)量上的科學或利用所應用科學，執(zhí)行部門對其所屬業(yè)務(wù)作出決策提供數(shù)量上依據(jù)的一門科學。Morse 規(guī)劃論規(guī)劃論線性規(guī)劃線性規(guī)劃、目標規(guī)劃、非線、目標規(guī)劃、非線性規(guī)劃、性規(guī)劃、整數(shù)規(guī)劃整數(shù)規(guī)劃、動態(tài)規(guī)劃動態(tài)規(guī)劃、組合規(guī)劃等、組合規(guī)劃等 圖與網(wǎng)絡(luò)圖與網(wǎng)絡(luò) 存儲論存儲論 排隊論排隊論 對策論對策論 決策論決策論 仿真仿真 馬爾科

8、夫過程馬爾科夫過程 可靠性可靠性 多目標規(guī)劃多目標規(guī)劃 3 3 運籌學的分支運籌學的分支3 3 運籌學的工作步驟運籌學的工作步驟(1) 提出和形成問題。提出和形成問題。即要弄清問題的目標，可能的約束，問題的可控變量以及有關(guān)參數(shù)；(2) 建立模型。建立模型。即把問題中可控變量、參數(shù)和目標與約束之間的關(guān)系用一定的模型表示出來； (3) 求解。求解。用各種手段( 主要是數(shù)學方法，也可用其他方法 )將模型求解。解可以是最優(yōu)解、次優(yōu)解、滿意解。復雜模型的求解需用計算機，解的精度要求可由決策者提出；(4) 解的檢驗。解的檢驗。首先檢查求解步驟和程序有無錯誤，然后檢查解是否反應現(xiàn)實問題；(5) 解的控制。解

9、的控制。通過控制解的變化過程決定對解是否要作一定的改變； (6) 解的實施。解的實施。是指將解用到實際中必須考慮到實施的問題，如向?qū)嶋H部門講清楚用法、在實施中可能產(chǎn)生的問題和修改。4 4 本課程的要求本課程的要求本課程的授課對象是管理科學與工程類及交通運輸類專業(yè)本課程的授課對象是管理科學與工程類及交通運輸類專業(yè)本科生，屬管理類專業(yè)技術(shù)基礎(chǔ)必修課。本科生，屬管理類專業(yè)技術(shù)基礎(chǔ)必修課。 學生通過學習該課程，應了解管理運籌學對優(yōu)化決策問題進學生通過學習該課程，應了解管理運籌學對優(yōu)化決策問題進行定量研究的特點，行定量研究的特點， 理解理解 線性規(guī)劃、整數(shù)規(guī)劃、動態(tài)規(guī)劃、圖與線性規(guī)劃、整數(shù)規(guī)劃、動態(tài)規(guī)劃

10、、圖與網(wǎng)絡(luò)、排隊論和庫存論網(wǎng)絡(luò)、排隊論和庫存論 等分支的基本優(yōu)化等分支的基本優(yōu)化原理，掌握原理，掌握 其中常用的其中常用的模型和算法模型和算法，具有一定的建模能力。具有一定的建模能力。 先修課程主要為先修課程主要為線性代數(shù)和概率統(tǒng)計線性代數(shù)和概率統(tǒng)計，學生對它們的掌握程，學生對它們的掌握程度直接影響本課程的學習，所以要求學生課前要做必要的復習。度直接影響本課程的學習，所以要求學生課前要做必要的復習。 學習方法：理解、掌握基本理論和方法的基礎(chǔ)上，適當作些學習方法：理解、掌握基本理論和方法的基礎(chǔ)上，適當作些習題。習題。 二二. 線性規(guī)劃線性規(guī)劃 (LP )( Linear Programming)

11、第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法1947年由美國空軍G.B.Dantzig提出。本部分是課程的最重要部分本節(jié)重點：本節(jié)重點：線性規(guī)劃模型的特點線性規(guī)劃模型的特點線性規(guī)劃解的存在情況線性規(guī)劃解的存在情況線性規(guī)劃標準型線性規(guī)劃標準型線性規(guī)劃解的基本概念線性規(guī)劃解的基本概念（特別是基解和基可行解）（特別是基解和基可行解）1 線性規(guī)劃問題及其數(shù)學模型線性規(guī)劃問題及其數(shù)學模型11 問題的提出問題的提出 例例 1 1某工廠計劃期內(nèi)要安排生產(chǎn)、兩種產(chǎn)品，某工廠計劃期內(nèi)要安排生產(chǎn)、兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時和已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時和A A、B B兩種原材料的兩種原材料的

12、消耗、以及可獲利潤如表所示，問應如何安排計劃使該消耗、以及可獲利潤如表所示，問應如何安排計劃使該工廠獲利最多？工廠獲利最多？可利用資源 設(shè)備 原材料 A 原材料 B140204 8 臺時 16kg 12kg 利潤23 ？元設(shè)設(shè) x1、x2分別表示計劃期內(nèi)產(chǎn)品分別表示計劃期內(nèi)產(chǎn)品、的產(chǎn)量，、的產(chǎn)量， 建立數(shù)學模型：建立數(shù)學模型： 設(shè)備臺時設(shè)備臺時 約束條件約束條件 s.t. x1 + 2x2 8 原材料原材料 A (Subject to) 4 x1 16 原材料原材料 B 4 x2 12 產(chǎn)品產(chǎn)量產(chǎn)品產(chǎn)量 x1，x2 0 可利用資源 設(shè)備 原材料 A 原材料 B140204 8 臺時 16kg

13、12kg 利潤23 ？元利潤最大利潤最大 目標函數(shù)目標函數(shù) max max z z = 2 = 2x1+ 3x2例2 某工廠用鋼與橡膠生產(chǎn)3種產(chǎn)品A、B、C，有關(guān)資料如下表404524332231 A B C單位產(chǎn)品利潤單位產(chǎn)品橡膠量單位產(chǎn)品鋼消耗量產(chǎn)品已知每天可獲得100單位的鋼和120單位橡膠，問每天生產(chǎn)A、B、C各多少使總利潤最大？解解：設(shè)x1，x2， x3分別為A、B、C日產(chǎn)量，則有 約束條件 2 x1 + 3x2 + x3 100 3x1 + 3x2 + 2x3 120 x10，x20， x30稱x1，x2 ，x30為決策變量 目標函數(shù)： max z=40 x1+45x2 +24x3

14、 例例 3靠近某河流有兩個化工廠（見圖） ，流經(jīng)第一化工廠靠近某河流有兩個化工廠（見圖） ，流經(jīng)第一化工廠的河流流量為每天的河流流量為每天 500 萬萬 m3， 在兩個工廠之間有一條流量為， 在兩個工廠之間有一條流量為每天每天 200 萬萬 m3的支流。的支流。 第一化工廠每天排放含有某種有害物第一化工廠每天排放含有某種有害物質(zhì)的工業(yè)污水質(zhì)的工業(yè)污水 2 萬萬 m3，第二化工廠每天排放這種工業(yè)污水，第二化工廠每天排放這種工業(yè)污水1. .4 萬萬 m3。從第一化工廠排出的工業(yè)污水流到第二化工廠以從第一化工廠排出的工業(yè)污水流到第二化工廠以前，有前，有 20% %可以自然凈化。可以自然凈化。根據(jù)環(huán)保

15、要求，河流中工業(yè)污水根據(jù)環(huán)保要求，河流中工業(yè)污水的含量不應大于的含量不應大于 0. .2 2% %。 這兩個工廠都需各自處理一部分工業(yè)這兩個工廠都需各自處理一部分工業(yè)污水。污水。第一化工廠處理工業(yè)污水的成本是第一化工廠處理工業(yè)污水的成本是 10001000 元元/ /萬萬 m m3 3，第，第二化工廠處理工業(yè)污水的成本是二化工廠處理工業(yè)污水的成本是 800800 元元/ /萬萬 m m3 3。 現(xiàn)在要問在滿現(xiàn)在要問在滿足環(huán)保要求的足環(huán)保要求的條件下，每廠各應處理多少工業(yè)污水，使這兩條件下，每廠各應處理多少工業(yè)污水，使這兩個工廠總的處理工業(yè)污水費用最小。個工廠總的處理工業(yè)污水費用最小。 2萬m3

16、1.4萬m3 設(shè)設(shè) x1、x2 分別為第一、第二化工廠每天處理的工業(yè)污水量。分別為第一、第二化工廠每天處理的工業(yè)污水量。約束條件：約束條件： 第一化工廠到第二化工廠之間的污水含量要不大于第一化工廠到第二化工廠之間的污水含量要不大于 0. .2 2% % (2 -(2 - x1) / 500 2 / 1000 流經(jīng)第二化工廠后，河流中的污水含量仍不大于流經(jīng)第二化工廠后，河流中的污水含量仍不大于 0. .2 2% %0.0. 8(2 -8(2 - x1) + ( (1. .4-4- x2) / 700 2 / 1000 污水處理量限制污水處理量限制 x1 2，x2 1. .4 4，x1 0，x2

17、0目標函數(shù)：目標函數(shù)： 要求兩廠用于處理工業(yè)污水的費用最小要求兩廠用于處理工業(yè)污水的費用最小 min z = 1000 x1+800 x22萬m31.4萬m3整理得數(shù)學模型：整理得數(shù)學模型：目標函數(shù)目標函數(shù) min min z z = 1000 = 1000 x1+ 800 x2約束條件約束條件 s.t. x1 1 0. .8 8 x1 + x2 1. .6 6 x1 2 x2 1. .4 4 x1 0，x2 0 線線性性規(guī)規(guī)劃劃問問題題的的共共同同特特征征 （模模型型的的三三要要素素） 每每一一個個問問題題都都用用一一組組決決策策變變量量(x1，x2，xn)表表示示某某一一方方案案； 這這組

18、組決決策策變變量量的的值值就就代代表表一一個個具具體體方方案案。一一般般這這些些變變量量取取值值都都是是非非負負的的。 存存在在一一定定的的約約束束條條件件， 這這些些約約束束條條件件可可以以用用一一組組線線性性等等式式或或線線性性不不等等式式來來表表示示。 都都有有一一個個要要求求達達到到的的目目標標， 它它可可用用決決策策變變量量的的線線性性函函數(shù)數(shù)（稱稱為為目目標標函函數(shù)數(shù)）來來表表示示。按按問問題題的的不不同同，要要求求目目標標函函數(shù)數(shù)實實現(xiàn)現(xiàn)最最大大化化或或最最小小化化。 線性規(guī)劃模型的一般形式為：線性規(guī)劃模型的一般形式為： max(min) z =c1x1 + c2x2 + cnx

19、n (1.1) s.t. a11x1 + a12x2 + a1nxn ( = , ) b1 a21x1 + a22x2 + a2nxn ( = , ) b2 (1 (1.2)2) am1x1 + am2x2 + amnxn ( = , ) bm x1，x2，xn 0 (1.3) 求解線性規(guī)劃問題的任務(wù)是求解線性規(guī)劃問題的任務(wù)是：在滿足在滿足(1.2)、(1.3) 的所有的所有(x1，x2，xn)（可行解可行解）中求出使）中求出使(1.1)達到最大達到最大(小小)z 值的決策變量值值的決策變量值(x1*，x2*，xn*)（最優(yōu)解最優(yōu)解） 。） 。12 圖圖解解法法 只只有有兩兩個個決決策策變變量

20、量的的問問題題可可用用圖圖解解法法。圖圖解解法法有有助助于于理理解解線線性性規(guī)規(guī)劃劃問問題題的的求求解解原原理理。 例例 1 max max z z = 2 = 2x1 + 3x2 s.t. x1 + 2 x2 8 4 x1 16 4 x2 12 x1，x2 0 解解 法法 ：1 1o o. .建立平面直角坐標系；建立平面直角坐標系； 2 2o o. .找找出出表表示示每每個個約約束束的的半半平平面面， 所所有有半半平平面面的的交交集集是是可可行行域域 （全全體體可可行行解解的的集集合合） ； 3 3o o. .畫畫出出目目標標函函數(shù)數(shù)的的等等值值線線 ； max max z z = 2 = 2x1+ 3x2s.t. x1 + 2 x2 8 4 x1 16 4 x2 12 x1，x2 0 x1x204Q2(4,2)Q1Q3Q44x1=164x2=12 x1+2x2=82x1+3x2=03Q24o.向著目標函數(shù)的優(yōu)化方向平移等值線，直至得到等值線與向著目標函數(shù)的優(yōu)化方向平移等值線，直至得到等值線與可行域的最后交點，這種點就對應最優(yōu)解。可行域的最后交點，這種點就對應最優(yōu)解。 線性規(guī)劃問題解的存在情況：線性規(guī)劃