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

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

2、研究”或或“運用研究運用研究”。 一、一、 緒論緒論 1.1 運籌學(xué)產(chǎn)生運籌學(xué)產(chǎn)生 運籌學(xué)的三個來源是軍事、管理和經(jīng)濟(jì)運籌學(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)：打破德軍對英吉利海峽的封鎖 建議：用飛機(jī)代替艦艇投擲水雷，起爆深度由100米改為25米， 當(dāng)敵艦剛下潛時攻擊； 運送物資的船隊及護(hù)衛(wèi)艦的編隊由小規(guī)模、多批次改為大規(guī)模 、少批次。丘吉爾采納了

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

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

5、戰(zhàn)爭結(jié)束，MoresMores和和KimballKimball合著第一部運籌學(xué)專著合著第一部運籌學(xué)專著“運籌運籌 學(xué)的方法學(xué)的方法” 戰(zhàn)后，運籌學(xué)的應(yīng)用領(lǐng)域從軍事擴(kuò)展到其它各領(lǐng)域戰(zhàn)后，運籌學(xué)的應(yīng)用領(lǐng)域從軍事擴(kuò)展到其它各領(lǐng)域 19481948年英國成立運籌學(xué)學(xué)會年英國成立運籌學(xué)學(xué)會 19521952年美國成立運籌學(xué)學(xué)會年美國成立運籌學(xué)學(xué)會 19561956年法國成立運籌學(xué)學(xué)會年法國成立運籌學(xué)學(xué)會 19591959年英、美、法成立運籌學(xué)聯(lián)合會年英、美、法成立運籌學(xué)聯(lián)合會 第二階段第二階段危機(jī)期危機(jī)期 六、七十年代六、七十年代 第三階段第三階段運籌學(xué)發(fā)展的正確之路運籌學(xué)發(fā)展的正確之路 理念更新、實踐

6、為本、學(xué)科交融理念更新、實踐為本、學(xué)科交融 我國運籌學(xué)的發(fā)展我國運籌學(xué)的發(fā)展 2 2 運籌學(xué)的釋義運籌學(xué)的釋義 運籌學(xué)具有如下的性質(zhì)特點 （1）運籌學(xué)是一門應(yīng)用科學(xué)）運籌學(xué)是一門應(yīng)用科學(xué) (2) 運籌學(xué)的目的是尋找最佳解決問題的方案，運籌學(xué)的目的是尋找最佳解決問題的方案， 為決策者的最優(yōu)決策提供依據(jù)為決策者的最優(yōu)決策提供依據(jù) (3) 以數(shù)學(xué)為基礎(chǔ)提供定量分析以數(shù)學(xué)為基礎(chǔ)提供定量分析 （4）以計算機(jī)為手段）以計算機(jī)為手段 （5） 以軟科學(xué)研究軟系統(tǒng)以軟科學(xué)研究軟系統(tǒng) （6） 多學(xué)科專家集體協(xié)作研究多學(xué)科專家集體協(xié)作研究 由一支綜合性的隊伍，采用科學(xué)的方法，為一些涉及到有機(jī) 系統(tǒng)（人-機(jī)）的控制系

7、統(tǒng)問題提供解答，為該系統(tǒng)的總目標(biāo)服務(wù) 的學(xué)科。錢學(xué)森 運用科學(xué)方法來解決工業(yè)、商業(yè)、政府、國防等部門里有關(guān) 人力、機(jī)器、物資、金錢等大型系統(tǒng)的指揮或管理中所出現(xiàn)的 復(fù)雜問題的一門學(xué)科。其目的是“幫助管理者以科學(xué)方法確定 其方針和行動”英國運籌學(xué)會 運籌學(xué)是應(yīng)用系統(tǒng)的、科學(xué)的、數(shù)學(xué)分析的方法，通過建模、 檢驗和求解數(shù)學(xué)模型而獲得最優(yōu)決策的科學(xué)。近代運籌學(xué)工 作者 運籌學(xué)的定義運籌學(xué)的定義 執(zhí)行部門對所控制的業(yè)務(wù)作出決策提供數(shù)量上的科學(xué)或利用 所應(yīng)用科學(xué)，執(zhí)行部門對其所屬業(yè)務(wù)作出決策提供數(shù)量上依據(jù)的 一門科學(xué)。Morse 規(guī)劃論規(guī)劃論線性規(guī)劃線性規(guī)劃、目標(biāo)規(guī)劃、非線、目標(biāo)規(guī)劃、非線 性規(guī)劃、性規(guī)劃

8、、整數(shù)規(guī)劃整數(shù)規(guī)劃、動態(tài)規(guī)劃動態(tài)規(guī)劃、組合規(guī)劃等、組合規(guī)劃等 圖與網(wǎng)絡(luò)圖與網(wǎng)絡(luò) 存儲論存儲論 排隊論排隊論 對策論對策論 決策論決策論 仿真仿真 馬爾科夫過程馬爾科夫過程 可靠性可靠性 多目標(biāo)規(guī)劃多目標(biāo)規(guī)劃 3 3 運籌學(xué)的分支運籌學(xué)的分支 3 3 運籌學(xué)的工作步驟運籌學(xué)的工作步驟 (1) 提出和形成問題。提出和形成問題。即要弄清問題的目標(biāo)，可能的約束，問 題的可控變量以及有關(guān)參數(shù)； (2) 建立模型。建立模型。即把問題中可控變量、參數(shù)和目標(biāo)與約束之間 的關(guān)系用一定的模型表示出來； (3) 求解。求解。用各種手段( 主要是數(shù)學(xué)方法，也可用其他方法 )將 模型求解。解可以是最優(yōu)解、次優(yōu)解、滿意解

9、。復(fù)雜模型的求 解需用計算機(jī)，解的精度要求可由決策者提出； (4) 解的檢驗。解的檢驗。首先檢查求解步驟和程序有無錯誤，然后檢查 解是否反應(yīng)現(xiàn)實問題； (5) 解的控制。解的控制。通過控制解的變化過程決定對解是否要作一定 的改變； (6) 解的實施。解的實施。是指將解用到實際中必須考慮到實施的問題， 如向?qū)嶋H部門講清楚用法、在實施中可能產(chǎn)生的問題和修改。 4 4 本課程的要求本課程的要求 本課程的授課對象是管理科學(xué)與工程類及交通運輸類專業(yè)本課程的授課對象是管理科學(xué)與工程類及交通運輸類專業(yè) 本科生，屬管理類專業(yè)技術(shù)基礎(chǔ)必修課。本科生，屬管理類專業(yè)技術(shù)基礎(chǔ)必修課。 學(xué)生通過學(xué)習(xí)該課程，應(yīng)了解管理運

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

11、法：理解、掌握基本理論和方法的基礎(chǔ)上，適當(dāng)作些學(xué)習(xí)方法：理解、掌握基本理論和方法的基礎(chǔ)上，適當(dāng)作些 習(xí)題。習(xí)題。 二二. 線性規(guī)劃線性規(guī)劃 (LP ) ( Linear Programming) 第一章第一章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法 1947年由美國空軍G.B.Dantzig提出。 本部分是課程的最重要部分 本節(jié)重點：本節(jié)重點： 線性規(guī)劃模型的特點線性規(guī)劃模型的特點 線性規(guī)劃解的存在情況線性規(guī)劃解的存在情況 線性規(guī)劃標(biāo)準(zhǔn)型線性規(guī)劃標(biāo)準(zhǔn)型 線性規(guī)劃解的基本概念線性規(guī)劃解的基本概念（特別是基解和基可行解）（特別是基解和基可行解） 1 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型

12、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兩種原材料的兩種原材料的 消耗、以及可獲利潤如表所示，問應(yīng)如何安排計劃使該消耗、以及可獲利潤如表所示，問應(yīng)如何安排計劃使該 工廠獲利最多？工廠獲利最多？ 可利用資源 設(shè)備 原材料 A 原材料 B 1 4 0 2 0 4 8 臺時 16kg 12kg 利潤23 ？元 設(shè)設(shè) x1、x2分別表示計劃期內(nèi)產(chǎn)品分別表示計劃期內(nèi)產(chǎn)品、的產(chǎn)量，、的產(chǎn)量， 建立數(shù)學(xué)模型：建立數(shù)學(xué)模型： 設(shè)備臺時設(shè)備臺時 約束條件約束條件

13、 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 原材料 B 1 4 0 2 0 4 8 臺時 16kg 12kg 利潤23 ？元 利潤最大利潤最大 目標(biāo)函數(shù)目標(biāo)函數(shù) max max z z = 2 = 2x1+ 3x2 例2 某工廠用鋼與橡膠生產(chǎn)3種產(chǎn)品A、B、C，有關(guān)資料如下表 40 45 24 3 3 2 2 3 1 A B C 單位產(chǎn)品利潤單位產(chǎn)品橡膠量單位產(chǎn)品鋼消耗量產(chǎn)品 已知每天可獲得100單位的鋼和120單位橡膠，問每天生產(chǎn)A、B、 C各多

14、少使總利潤最大？ 解解：設(shè)x1，x2， x3分別為A、B、C日產(chǎn)量，則有 約束條件 2 x1 + 3x2 + x3 100 3x1 + 3x2 + 2x3 120 x10，x20， x30稱x1，x2 ，x30為決策變量 目標(biāo)函數(shù)： max z=40 x1+45x2 +24x3 例例 3靠近某河流有兩個化工廠（見圖） ，流經(jīng)第一化工廠靠近某河流有兩個化工廠（見圖） ，流經(jīng)第一化工廠 的河流流量為每天的河流流量為每天 500 萬萬 m3， 在兩個工廠之間有一條流量為， 在兩個工廠之間有一條流量為 每天每天 200 萬萬 m3的支流。的支流。 第一化工廠每天排放含有某種有害物第一化工廠每天排放含有

15、某種有害物 質(zhì)的工業(yè)污水質(zhì)的工業(yè)污水 2 萬萬 m3，第二化工廠每天排放這種工業(yè)污水，第二化工廠每天排放這種工業(yè)污水 1. .4 萬萬 m3。從第一化工廠排出的工業(yè)污水流到第二化工廠以從第一化工廠排出的工業(yè)污水流到第二化工廠以 前，有前，有 20% %可以自然凈化。可以自然凈化。根據(jù)環(huán)保要求，河流中工業(yè)污水根據(jù)環(huán)保要求，河流中工業(yè)污水 的含量不應(yīng)大于的含量不應(yīng)大于 0. .2 2% %。 這兩個工廠都需各自處理一部分工業(yè)這兩個工廠都需各自處理一部分工業(yè) 污水。污水。第一化工廠處理工業(yè)污水的成本是第一化工廠處理工業(yè)污水的成本是 10001000 元元/ /萬萬 m m 3 3，第 ，第 二化工廠

16、處理工業(yè)污水的成本是二化工廠處理工業(yè)污水的成本是 800800 元元/ /萬萬 m m 3 3。 。 現(xiàn)在要問在滿現(xiàn)在要問在滿 足環(huán)保要求的足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，使這兩條件下，每廠各應(yīng)處理多少工業(yè)污水，使這兩 個工廠總的處理工業(yè)污水費用最小。個工廠總的處理工業(yè)污水費用最小。 2萬m3 1.4萬m3 設(shè)設(shè) x1、x2 分別為第一、第二化工廠每天處理的工業(yè)污水量。分別為第一、第二化工廠每天處理的工業(yè)污水量。 約束條件：約束條件： 第一化工廠到第二化工廠之間的污水含量要不大于第一化工廠到第二化工廠之間的污水含量要不大于 0. .2 2% % (2 -(2 - x1) / 50

17、0 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 0 目標(biāo)函數(shù)：目標(biāo)函數(shù)： 要求兩廠用于處理工業(yè)污水的費用最小要求兩廠用于處理工業(yè)污水的費用最小 min z = 1000 x1+800 x2 2萬m3 1.4萬m3 整理得數(shù)學(xué)模型：整理得數(shù)學(xué)模型： 目標(biāo)函數(shù)目標(biāo)函數(shù) min min z z = 1000 = 1000 x1+ 800

18、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) 表表示示某某一一方方案案； 這這組組決決策策變變量量的的值值就就代代表表一一個個具具體體方方案案。 一一般般這這些些變變量量取取值值都都是是非非負(fù)負(fù)的的。 存存在在一一定定的的約約束束條條件件， 這這些些約約束束條條件件可可以以用用一一組組 線線性性等等式式或或線線性性不不等等式式來來表表示示。 都都有有

19、一一個個要要求求達(dá)達(dá)到到的的目目標(biāo)標(biāo)， 它它可可用用決決策策變變量量的的線線 性性函函數(shù)數(shù)（稱稱為為目目標(biāo)標(biāo)函函數(shù)數(shù)）來來表表示示。按按問問題題的的不不同同，要要求求 目目標(biāo)標(biāo)函函數(shù)數(shù)實實現(xiàn)現(xiàn)最最大大化化或或最最小小化化。 線性規(guī)劃模型的一般形式為：線性規(guī)劃模型的一般形式為： max(min) z =c1x1 + c2x2 + cnxn (1.1) s.t. a11x1 + a12x2 + a1nxn ( = , ) b1 a21x1 + a22x2 + a2nxn ( = , ) b2 (1 (1.2)2) am1x1 + am2x2 + amnxn ( = , ) bm x1，x2，xn

20、0 (1.3) 求解線性規(guī)劃問題的任務(wù)是求解線性規(guī)劃問題的任務(wù)是：在滿足在滿足(1.2)、(1.3) 的所有的所有(x1， x2，xn)（可行解可行解）中求出使）中求出使(1.1)達(dá)到最大達(dá)到最大(小小)z 值的決策變量值值的決策變量值 (x1*，x2*，xn*)（最優(yōu)解最優(yōu)解） 。） 。 12 圖圖解解法法 只只有有兩兩個個決決策策變變量量的的問問題題可可用用圖圖解解 法法。圖圖解解法法有有助助于于理理解解線線性性規(guī)規(guī)劃劃問問題題的的求求 解解原原理理。 例例 1 max max z z = 2 = 2x1 + 3x2 s.t. x1 + 2 x2 8 4 x1 16 4 x2 12 x1，

21、x2 0 解解 法法 ： 1 1 o o. .建立平面直角坐標(biāo)系； 建立平面直角坐標(biāo)系； 2 2 o o. .找 找出出表表示示每每個個約約束束的的半半平平面面， 所所有有半半平平面面的的交交集集是是可可行行域域 （全全 體體可可行行解解的的集集合合） ； 3 3 o o. .畫 畫出出目目標(biāo)標(biāo)函函數(shù)數(shù)的的等等值值線線 ； max max z z = 2 = 2x1+ 3x2 s.t. x1 + 2 x2 8 4 x1 16 4 x2 12 x1，x2 0 x1 x2 0 4 Q2(4,2) Q1 Q3 Q4 4x1=16 4x2=12 x1+2x2=8 2x1+3x2=0 3 Q2 4o.向著目標(biāo)函數(shù)的優(yōu)化方向平移等值線，直至得到等值線與向著目標(biāo)函數(shù)的優(yōu)化方向平移等值線，直至得到等值線與 可行域的最后交點，這種點就對應(yīng)最優(yōu)解?？尚杏虻淖詈蠼稽c，這種點就對應(yīng)最優(yōu)解。 線性規(guī)劃問題解的存在情況：線性規(guī)劃問題解的存在情況： (1)(1)存在唯一最