1、運籌學管理緒論第一章 緒論w 1.1題解 Operations 漢語翻譯工作、操作、行動、手術、運算Operations Research日本運用學 港臺作業研究中國大陸運籌學Operational Research原來名稱，意為軍事行動研究歷史淵源OR12緒論w 1.2 運籌學的歷史 早期運籌思想：田忌賽馬 丁渭修宮 沈括運糧 Erlang 1917 排隊論 Harris 1920 存儲論 Levinson 1930 零售貿易 康脫洛維奇 1939 LP OR13緒論w 1.2運籌學的歷史 軍事運籌學階段 德軍空襲 防空系統 Blackett 運輸船編隊 空襲逃避 深水炸彈 轟炸機編隊OR1

2、4緒論w 1.2運籌學的歷史 管理運籌學階段 戰后人員三分:軍隊、大學、企業 大學：課程、專業、碩士、博士 企業：美國鋼鐵聯合公司 英國國家煤炭局 運籌學在中國：50年代中期引入 華羅庚推廣 優選法、統籌法 中國郵遞員問題、運輸問題 OR151.3學科性質應用學科Morse&Kimball定義：運籌學是為決策機構在對其控制的業務活動進行決策時提供的數量化為基礎的科學方法。Churchman定義：運籌學是應用科學的方法、技術和工具，來處理一個系統運行中的問題，使系統控制得到最優的解決方法。中國定義：運籌學是應用分析、試驗、量化的方法，對經濟管理系統中人力、物力、財力等資源進行統籌安排，為決策者提

3、供有依據的最優方案，以實現最有效的管理。OR161.4定性與定量w 例：店主進貨w 兩者都是常用的決策方法w 定性是基礎，定量是工具，定量為定性服務。w 定性有主觀性也有有效性，定量有科學性也有局限性。管理科學的發展，定量越來越多。但定量不可替代定性。OR171.5運籌學的模型w 模型：真實事物的模仿，主要因素、相互關系、系統結構。w 形象模型：如地球儀、沙盤、風洞w 模擬模型：建港口，模擬船只到達。學生模擬企業管理系統運行。w 數學模型：用符號或數學工具描述現實系統。V=F（xi,yj,uk) G(xi,yj,uk)0OR181.6運籌學的學科體系w 規劃論：線性規劃、非線性規劃|、整數規劃

4、、目標規劃、動態規劃w 圖論與網絡w 存儲論w 排隊論w 決策論w 對策論w 計算機仿真OR191.7運籌學的工作步驟w 確定問題w 搜集數據建立模型w 檢驗模型w 求解模型w 結果分析w 結果實施OR1101.8運籌學與計算機w 計算機為運籌學提供解題工具。w 本書有現成的程序可以利用w 要學會解題的思路與方法，建立模型很重要。OR111第二章 線性規劃與單純形法w 2.1 LP(linear programming)的基本概念 LP是在有限資源的條件下，合理分配和利用資源，以期取得最佳的經濟效益的優化方法。LP有一組有待決策的變量， 一個線性的目標函數， 一組線性的約束條件。 OR1122

5、.1.1 LP的數學模型 例題1生產計劃問題w 某廠生產兩種產品，需要三種資源，已知各產品的利潤、各資源的限量和各產品的資源消耗系數如下表：產品A產品B資源限量勞動力設 備原材料9434510360200300利潤元/kg70120OR113例題1建模w 問題：如何安排生產計劃，使得獲利最多？w 步驟：1、確定決策變量：設生產A產品x1kg,B產品x2kg2、確定目標函數：maxZ=70X1+120X23、確定約束條件：人力約束 9X1+4X2360 設備約束 4X1+5X2 200 原材料約束3X1+10X2 300 非負性約束X10 X20OR114例題2配方問題w 養海貍鼠 飼料中營養要

6、求：VA每天至少700克，VB每天至少30克，VC每天剛好200克。現有五種飼料，搭配使用，飼料成分如下表：飼料VaVbVc價格元/KGIIIIIIIVV32161810.50.220.50.510.220.827495營養要求70030200OR115例題2建模w 設抓取飼料I x1kg;飼料II x2kg;飼料III x3kgw 目標函數：最省錢 minZ=2x1+7x2+4x3+9x4+5x5w 約束條件：3x2+2x2+x3+6x4+18x5 700營養要求： x1+0.5x2+0.2x3+2x4+0.5x5 30 0.5x1+x2+0.2x3+2x4+0.8x5 =200用量要求：

7、x1 50,x2 60,x3 50,x4 70,x5 40非負性要求：x1 0,x2 0,x3 0,x4 0,x5 0 OR116例題3：人員安排問題w 醫院護士24小時值班，每次值班8小時。不同時段需要的護士人數不等。據統計： 序號時段最少人數安排人數1061060X12101470X23141860X34182250X45220220X56020630 x6OR117例題3建模w 目標函數：min Z=x1+x2+x3+x4+x5+x6w 約束條件： x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 20 x5+x6 30非負性約束：xj 0,j=1,2,6OR118歸納：

8、線性規劃的一般模式w 目標函數：max(min)Z=c1x1+c2x2+c3x3+cnxnw 約束條件：a11x1+a12x2+a13x3+a1nxn (= )b1 a21x1+a22x2+a23x3+a2nxn (= )b2 am1x1+am2x2+am3x3+amnxn (= )bn非負性約束：x1 0,x2 0,xn 0OR1192.1.2線性規劃圖解法w 由中學知識可知：y=ax+b是一條直線，同理：Z=70 x1+120 x2x2=70/120 x1-Z/120也是一條直線，以Z為參數的一族等值線。 9x1+4x2 360 x1 360/9-4/9x2 是直線 x1=360/9-4/

9、9x2 下方的半平面。所有半平面的交集稱之為可行域，可行域內的任意一點，就是滿足所有約束條件的解，稱之為可行解。OR120例1圖示. 90 80 60 40 20 0 20 40 60 80 100 x1 x29x1+4x2 3604x1+5x2 200 3x1+10 x2 300ABCDEFGHIZ=70 x1+120 x2OR121概念w 概念：1、可行解：滿足所有約束條件的解。2、可行域：即可行解的集合。所有約束條件的交集，也就是各半平面的公共部分。滿足所有約束條件的解的集合，稱為可行域。3、基解：約束條件的交點稱為基解（直觀）4、基可行解：基解當中的可行解。5、凸集：集合內任意兩點的連

10、線上的點均屬于這個集合。如：實心球、三角形OR122結論w 可行域是個凸集w 可行域有有限個頂點w 最優值在可行域的頂點上達到w 無窮多解的情形w 無界解情形w 無解情形OR1232.1.3線性規劃的標準型w 代數式maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm xj 0 j=1,2,nOR124線性規劃的標準型w 和式：maxZ=cjxj aijxj=bi i=1,2,m xj 0 j=1,2,nj=1nnj=1OR125線性規劃的標準型w向量式：maxZ=CX pjxj=b

11、i i=1,2,m xj 0 j=1,2,n C=(c1,c2,c3,cn) X=(X1,X2,X3,Xn) Tnj=1OR126線性規劃的標準型w 矩陣式： maxZ=CX AX=b X 0 其中： b=(b1,b2,bm)T a11 a12 .a1n A= a21 a22 a2n am1 am2 amnOR127標準型的特征w 目標函數極大化w 約束條件為等式w 決策變量非負OR128非標準型轉化為標準型w 目標函數極小化轉為極大化： minZ=max(Z) ，一個數的極小化等價于其相反數的極大化。w 不等式約束的轉化： aijxjbi 加入松弛變量 aijxjbi 減去剩余變量 非正變量

12、：即xk 0 則令xk = xk 自由變量：即xk無約束，令xk= xkx”kOR129非標準型轉化舉例之一之一maxZ=70X1+120X2 maxZ=70X1+120X2 9X1+4X2360 9X1+4X2+X3=360 4X1+5X2 200 4X1+5X2 +x4=200 3X1+10X2 300 3X1+10X2+x5 =300 X10 X20 Xj0 j=1,2,5OR130非標準型轉化舉例之二之二minZ=x1+2x2-3x3 maxZ=x12x2+3(x3x”3) x1+x2+x3 9 x1+x2+x3 x”3 + x4=9 -x1-2x2+x3 2 x12x2+x3 x”3

13、 - x5= 2 3x1+x2-3x3=5 3x1+x23(x3 x”3 )=5 x1 0 x2 0 x3無約束 x1 0 x2 0 x3 0 x”3 0 x40 x50 OR1312.1.4基可行解w基的概念基的概念：如前所述LP標準型和式：maxZ= cjxj aijxj=bi xj 0 j=1,2,n 矩陣式：maxZ=CX AX=b X 0 約束方程的系數矩陣A的秩為m，且m0 =bL/ aLk 。 這時原基變量XL=0，由基變量變成非基變量，aLk處在變量轉換的交叉點上，稱之為樞軸元素j 0OR140單純形法解題舉例單純形表的格式： CjC1 C2 Cn i CBXBbx1 x2 .

14、 xn C1 C2 Cmx1x2xmb 1b2bma11 a12 a1na21 a22 a2n am1 am2 amn 1 2 m j 1 2 n OR141 CjC1 C2 CnCBXBbX1 X2 X3 X4 X5j 0 0 0X3X4X5360200300 9 4 1 0 0 4 5 0 1 0 3 10 0 0 1 904030j0 70 120 0 0 0 0 0 120X3X4X224050 30 7.8 0 1 0 -0.4 2.5 0 0 1 -0.5 0.3 1 0 0 0.130.7620100j3600 34 0 0 0 -12701200X3X1X2842024 0 0

15、 1 -3.12 1.16 1 0 0 0.4 -0.2 0 1 0 -0.12 0.16j4280 0 0 0 -13.6 -5.2OR1422.2.3單純形法的計算步驟w 找到初始可行基，建立單純形表w 計算檢驗數，若所有j 0 則得最優解，結束。否則轉下步w 若某K 0而PK 0 ，則最優解無界，結束。否則轉下步w 根據max j = K 原則確定XK 進基變量；根據規則 ： = min bi / aik aik 0 = bL/ aLk 確定XL為出基變量w 以aLk 為樞軸元素進行迭代，回到第二步OR1432.3單純形法的進一步探討w 2.3.1極小化問題直接求解：檢驗數的判別由所有j

16、 0 即為最優，變為所有j 0則為最優。w 人工變量法之一：大M法 人工變量價值系數M例w 人工變量法之二：構造目標函數，分階段求解例w 2.3.2無窮多最優解情形：非基變量檢驗數 j= 0w 2.3.3退化解的情形：有兩個以上 值相等OR1442.3.4單純形法的計算機求解w 程序說明w 應用舉例例題1例題2OR1452.5LP應用舉例之一w 例13合理下料問題料長7.4米，截成2.9、2.1、1.5米各200根。如何截取余料最少？關鍵：設變量。 方案料型 1 2 3 4 5 6 7 8 2.9米 2.1米 1.5米 1 2 0 1 0 1 0 0 0 0 2 2 1 1 3 0 3 1 2

17、 0 3 1 0 4 合計 殘料 7.4 7.3 7.2 7.1 6.6 6.5 6.3 6.0 0 0.1 0.2 0.3 0.8 0.9 1.1 1.4OR146應用舉例之二 w 例14混合配方問題A、B、C、D四種原料配制三種產品，三類約束：技術要求、原料限量、市場容量。已知產品價格和原料價格，求利潤最大的配方。關鍵：設變量。OR147應用舉例之三w 例15.滾動投資問題茲有100萬元閑錢，投資方向有四： 第四年第一年第二年第三年A項目110%B項目135%C項目125%D項目104%第五年各年投資什么項目，使第五年末資本總額為最大？OR148應用舉例之四w 例16動態生產計劃問題 工廠

18、做n個月的生產計劃，第j月需求量dj、正常生產能力aj、加班生產能力bj、正常生產成本cj、加班生產成本ej、庫存能力為I、庫存費用hj，設期初、期末庫存為零。求費用最小的生產計劃。 設第月正常生產xj件，加班生產件yj，存儲zj件。則： 本期生產+上期庫存-本期庫存=本期需求OR149第三章 對偶問題與靈敏度分析w要求： 了解LP對偶問題的實際背景 了解對偶問題的建立規則與基本性質 掌握對偶最優解的計算及其經濟解釋 掌握LP的靈敏度分析 理解計算機輸出的影子價格與靈敏度分 析的內容OR1503.1 對偶問題w3.1.1 對偶問題的提出 回顧例題1： 現在A、B兩產品銷路不暢，可以將所有資源出

19、租或外賣，現在要談判，我們的價格底線是什么？產品A產品B資源限制勞動力設備原材料 9 4 3 4 5 10 360 200 300單位利潤 70 120OR151對偶模型w 設每個工時收費Y1元，設備臺時費用Y2元，原材料附加費Y3元。 出租收入不低于生產收入： 9y1+4y2+3y3 70 4y1+5y2+10y3 120目標：=360y1+200y2+300y3出租收入越多越好？至少不低于某數OR152原問題與對偶問題之比較原問題： 對偶問題：maxZ=70X1+120X2 min=360y1+200y2+300y3 9X1+4X2360 9y1+4y2+3y3 70 4X1+5X2 20

20、0 (3.1) 4y1+5y2+10y3 120 (3.2) 3X1+10X2 300 y1 0, y2 0, y3 0X10 X20OR1533.1.2對偶規則原問題一般模型： 對偶問題一般模型：maxZ=CX min =Yb AX b YA C X 0 Y 0OR154對偶規則w 原問題有m個約束條件，對偶問題有m個變量w 原問題有n個變量，對偶問題有n個約束條件w 原問題的價值系數對應對偶問題的右端項w 原問題的右端項對應對偶問題的價值系數w 原問題的技術系數矩陣轉置后為對偶問題系數矩陣w 原問題的約束條件與對偶問題方向相反w 原問題與對偶問題優化方向相反OR155對偶規則. 原問題 對

21、偶問題目標函數 max min 目標函數約束條件 = 變量無約束 變量符號 無約束 約束條件=OR156對偶規則簡捷記法w原問題標準則對偶問題標準w原問題不標準則對偶問題不標準w例題2 max =7y1+4y2-2y3minZ=3x1+2x2-6x3+x5 2y1+ y2- y3 3 2x1+x2-4x3+x4+3x5 7 y1 +3y3 2 x1+ 2x3 -x4 4 -4y1+ 2y2 -6 -x1+3x2 -x4+ x5 =-2 y1 -y2 -y3 0 x1，x2，x3 0; 3y1 +y3=1 x4 0;x5無限制 y1 0y2 0y3 無約束 OR1573.1.3對偶問題的基本性質

22、w 對稱性：對偶問題的對偶問題是原問題w 弱對偶性：極大化原問題的任一可行解的目標函數值，不大于其對偶問題任意可行解的目標函數值 (鞍型圖)w 無界性：原問題無界，對偶問題無可行解w 對偶定理：若一個問題有最優解，則另一問題也有最優解，且目標函數值相等。若原問題最優基為B，則其對偶問題最優解Y*=CBB-1OR1583.1.4對偶最優解的經濟解釋影子價格w Z= =CX=Yb Z/ b=(Yb)=Yw Z=Yb= yibi的意義：Y是檢驗數的反數。在Y確定的前提下，每增加一個單位的i種資源，對目標函數的貢獻。w 結合例題1講解影子價格：y1=0:第一種資源過剩 y2=13.6：設備臺時最緊張，

23、每增加一個臺時， 利潤增加13.6元。y3=5.2w 影子價格所含有的信息： 1、資源緊缺狀況 2、確定資源轉讓基價參見：P40 3、取得緊缺資源的代價OR1593.2靈敏度分析w 為什么進行靈敏度分析？w 靈敏度分析的兩把尺子： j =Cj-CBB-1pj 0； xB= B-1b 03.2.1 價值系數的靈敏度分析 Cj變化到什么程度可以保持最優基不變？用 （參看P96）例題4： 87.5 C2 233.33；36 C1 96OR160靈敏度分析w 右端項的靈敏度分析： bi變化到什么程度可以保持最優基不變？用尺度 xB= B-1b 0例題5： 1 -3.12 1.16 360 B-1b= 0 0.4 -0.2 200 0 0 -0.12 0.16 b3 b3的變化范圍：227.586 b3 400OR161其它形式的靈敏度分析 新產品的分析：新產品的分析： 在資源結構沒有變化的條件下，是否生產這種新 產品，就看它的競爭力如何。例題6：新增一種C產品，單位利潤110元，使用勞動力6工時，設備5臺時，原材料7公斤，問要否調整產品結構？ 先算檢驗數j =Cj-CBB-1pj 6=C6-YP6=110-（0，13.6，5.2）（6，5，7）T = 110-104.4=5.6 大于零，有利可圖，將P6左乘B-1，加入到末表之中，繼續迭代，直