信息系統(tǒng)項目管理師考試必須學(xué)會掌握運(yùn)籌學(xué)數(shù)學(xué)題

1、信息系統(tǒng)項目管理師運(yùn)籌學(xué)OR11信息系統(tǒng)項目管理師上午綜合題最后5道題（非英文題），一般都是運(yùn)籌學(xué)的題，因此需要考生知道如何使用運(yùn)籌學(xué)知識去解題。專業(yè)軟考交流論壇：歡迎您的光臨 、學(xué)習(xí)、交流、探討OR12第一章 緒論w 1.1題解 Operations 漢語翻譯工作、操作、行動、手術(shù)、運(yùn)算Operations Research日本運(yùn)用學(xué) 港臺作業(yè)研究中國大陸運(yùn)籌學(xué)Operational Research原來名稱，意為軍事行動研究歷史淵源OR13緒論w 1.2 運(yùn)籌學(xué)的歷史 早期運(yùn)籌思想：田忌賽馬 丁渭修宮 沈括運(yùn)糧 Erlang 1917 排隊論 Harris 1920 存儲論 Levinso

2、n 1930 零售貿(mào)易 康脫洛維奇 1939 LP OR14緒論w 1.2運(yùn)籌學(xué)的歷史 軍事運(yùn)籌學(xué)階段 德軍空襲 防空系統(tǒng) Blackett 運(yùn)輸船編隊 空襲逃避 深水炸彈 轟炸機(jī)編隊OR15緒論w 1.2運(yùn)籌學(xué)的歷史 管理運(yùn)籌學(xué)階段 戰(zhàn)后人員三分:軍隊、大學(xué)、企業(yè) 大學(xué)：課程、專業(yè)、碩士、博士 企業(yè)：美國鋼鐵聯(lián)合公司 英國國家煤炭局 運(yùn)籌學(xué)在中國：50年代中期引入 華羅庚推廣 優(yōu)選法、統(tǒng)籌法 中國郵遞員問題、運(yùn)輸問題 OR161.3學(xué)科性質(zhì)應(yīng)用學(xué)科Morse&Kimball定義：運(yùn)籌學(xué)是為決策機(jī)構(gòu)在對其控制的業(yè)務(wù)活動進(jìn)行決策時提供的數(shù)量化為基礎(chǔ)的科學(xué)方法。Churchman定義：運(yùn)籌

3、學(xué)是應(yīng)用科學(xué)的方法、技術(shù)和工具，來處理一個系統(tǒng)運(yùn)行中的問題，使系統(tǒng)控制得到最優(yōu)的解決方法。中國定義：運(yùn)籌學(xué)是應(yīng)用分析、試驗、量化的方法，對經(jīng)濟(jì)管理系統(tǒng)中人力、物力、財力等資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實現(xiàn)最有效的管理。OR171.4定性與定量w 例：店主進(jìn)貨w 兩者都是常用的決策方法w 定性是基礎(chǔ)，定量是工具，定量為定性服務(wù)。w 定性有主觀性也有有效性，定量有科學(xué)性也有局限性。管理科學(xué)的發(fā)展，定量越來越多。但定量不可替代定性。OR181.5運(yùn)籌學(xué)的模型w 模型：真實事物的模仿，主要因素、相互關(guān)系、系統(tǒng)結(jié)構(gòu)。w 形象模型：如地球儀、沙盤、風(fēng)洞w 模擬模型：建港口，模擬船只到達(dá)

4、。學(xué)生模擬企業(yè)管理系統(tǒng)運(yùn)行。w 數(shù)學(xué)模型：用符號或數(shù)學(xué)工具描述現(xiàn)實系統(tǒng)。V=F（xi,yj,uk) G(xi,yj,uk)0OR191.6運(yùn)籌學(xué)的學(xué)科體系w 規(guī)劃論：線性規(guī)劃、非線性規(guī)劃|、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動態(tài)規(guī)劃w 圖論與網(wǎng)絡(luò)w 存儲論w 排隊論w 決策論w 對策論w 計算機(jī)仿真OR1101.7運(yùn)籌學(xué)的工作步驟w 確定問題w 搜集數(shù)據(jù)建立模型w 檢驗?zāi)Ｐ蛍 求解模型w 結(jié)果分析w 結(jié)果實施OR1111.8運(yùn)籌學(xué)與計算機(jī)w 計算機(jī)為運(yùn)籌學(xué)提供解題工具。w 本書有現(xiàn)成的程序可以利用w 要學(xué)會解題的思路與方法，建立模型很重要。OR112第二章 線性規(guī)劃與單純形法w 2.1 LP(linear

5、programming)的基本概念 LP是在有限資源的條件下，合理分配和利用資源，以期取得最佳的經(jīng)濟(jì)效益的優(yōu)化方法。LP有一組有待決策的變量， 一個線性的目標(biāo)函數(shù)， 一組線性的約束條件。 OR1132.1.1 LP的數(shù)學(xué)模型 例題1生產(chǎn)計劃問題w 某廠生產(chǎn)兩種產(chǎn)品，需要三種資源，已知各產(chǎn)品的利潤、各資源的限量和各產(chǎn)品的資源消耗系數(shù)如下表：產(chǎn)品A產(chǎn)品B資源限量勞動力設(shè) 備原材料9434510360200300利潤元/kg70120OR114例題1建模w 問題：如何安排生產(chǎn)計劃，使得獲利最多？w 步驟：1、確定決策變量：設(shè)生產(chǎn)A產(chǎn)品x1kg,B產(chǎn)品x2kg2、確定目標(biāo)函數(shù)：maxZ=70X1+12

6、0X23、確定約束條件：人力約束 9X1+4X2360 設(shè)備約束 4X1+5X2 200 原材料約束3X1+10X2 300 非負(fù)性約束X10 X20OR115例題2配方問題w 養(yǎng)海貍鼠 飼料中營養(yǎng)要求：VA每天至少700克，VB每天至少30克，VC每天剛好200克?，F(xiàn)有五種飼料，搭配使用，飼料成分如下表：飼料VaVbVc價格元/KGIIIIIIIVV32161810.50.220.50.510.220.827495營養(yǎng)要求70030200OR116例題2建模w 設(shè)抓取飼料I x1kg;飼料II x2kg;飼料III x3kgw 目標(biāo)函數(shù)：最省錢 minZ=2x1+7x2+4x3+9x4+5x

7、5w 約束條件：3x2+2x2+x3+6x4+18x5 700營養(yǎng)要求： x1+0.5x2+0.2x3+2x4+0.5x5 30 0.5x1+x2+0.2x3+2x4+0.8x5 =200用量要求： x1 50,x2 60,x3 50,x4 70,x5 40非負(fù)性要求：x1 0,x2 0,x3 0,x4 0,x5 0 OR117例題3：人員安排問題w 醫(yī)院護(hù)士24小時值班，每次值班8小時。不同時段需要的護(hù)士人數(shù)不等。據(jù)統(tǒng)計： 序號時段最少人數(shù)安排人數(shù)1061060X12101470X23141860X34182250X45220220X56020630 x6OR118例題3建模w 目標(biāo)函數(shù)：m

8、in Z=x1+x2+x3+x4+x5+x6w 約束條件： x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 20 x5+x6 30非負(fù)性約束：xj 0,j=1,2,6OR119歸納：線性規(guī)劃的一般模式w 目標(biāo)函數(shù)：max(min)Z=c1x1+c2x2+c3x3+cnxnw 約束條件：a11x1+a12x2+a13x3+a1nxn (= )b1 a21x1+a22x2+a23x3+a2nxn (= )b2 am1x1+am2x2+am3x3+amnxn (= )bn非負(fù)性約束：x1 0,x2 0,xn 0OR1202.1.2線性規(guī)劃圖解法w 由中學(xué)知識可知：y=ax+b是一條

9、直線，同理：Z=70 x1+120 x2x2=70/120 x1-Z/120也是一條直線，以Z為參數(shù)的一族等值線。 9x1+4x2 360 x1 360/9-4/9x2 是直線 x1=360/9-4/9x2 下方的半平面。所有半平面的交集稱之為可行域，可行域內(nèi)的任意一點，就是滿足所有約束條件的解，稱之為可行解。OR121例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 x2OR122概念w 概念：1、可行解：滿足所有約束條件的解。2、可行域：即

10、可行解的集合。所有約束條件的交集，也就是各半平面的公共部分。滿足所有約束條件的解的集合，稱為可行域。3、基解：約束條件的交點稱為基解（直觀）4、基可行解：基解當(dāng)中的可行解。5、凸集：集合內(nèi)任意兩點的連線上的點均屬于這個集合。如：實心球、三角形OR123結(jié)論w 可行域是個凸集w 可行域有有限個頂點w 最優(yōu)值在可行域的頂點上達(dá)到w 無窮多解的情形w 無界解情形w 無解情形OR1242.1.3線性規(guī)劃的標(biāo)準(zhǔn)型w 代數(shù)式maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm xj 0 j=1,

11、2,nOR125線性規(guī)劃的標(biāo)準(zhǔn)型w 和式：maxZ=cjxj aijxj=bi i=1,2,m xj 0 j=1,2,nj=1nnj=1OR126線性規(guī)劃的標(biāo)準(zhǔn)型w向量式：maxZ=CX pjxj=bi i=1,2,m xj 0 j=1,2,n C=(c1,c2,c3,cn) X=(X1,X2,X3,Xn) Tnj=1OR127線性規(guī)劃的標(biāo)準(zhǔn)型w 矩陣式： maxZ=CX AX=b X 0 其中： b=(b1,b2,bm)T a11 a12 .a1n A= a21 a22 a2n am1 am2 amnOR128標(biāo)準(zhǔn)型的特征w 目標(biāo)函數(shù)極大化w 約束條件為等式w 決策變量非負(fù)OR129非標(biāo)準(zhǔn)型

12、轉(zhuǎn)化為標(biāo)準(zhǔn)型w 目標(biāo)函數(shù)極小化轉(zhuǎn)為極大化： minZ=max(Z) ，一個數(shù)的極小化等價于其相反數(shù)的極大化。w 不等式約束的轉(zhuǎn)化： aijxjbi 加入松弛變量 aijxjbi 減去剩余變量w 非正變量：即xk 0 則令xk = xk 自由變量：即xk無約束，令xk= xkx”kOR130非標(biāo)準(zhǔn)型轉(zhuǎn)化舉例之一之一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,5OR131非標(biāo)準(zhǔn)

13、型轉(zhuǎn)化舉例之二之二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 - 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 OR1322.1.4基可行解w基的概念基的概念：如前所述LP標(biāo)準(zhǔn)型和式：maxZ= cjxj aijxj=bi xj 0 j=1,2,n 矩陣式：maxZ=CX AX=b X 0 約束方程的系數(shù)矩陣A的秩為m，且m0 =bL/

14、 aLk 。 這時原基變量XL=0，由基變量變成非基變量，aLk處在變量轉(zhuǎn)換的交叉點上，稱之為樞軸元素j 0OR141單純形法解題舉例單純形表的格式： CjC1 C2 Cn i CBXBbx1 x2 . xn C1 C2 Cmx1x2xmb 1b2bma11 a12 a1na21 a22 a2n am1 am2 amn 1 2 m j 1 2 n OR142 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 120X3X4X22

15、4050 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 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.2OR1432.2.3單純形法的計算步驟w 找到初始可行基，建立單純形表w 計算檢驗數(shù)，若所有j 0 則得最優(yōu)解，結(jié)束。否則轉(zhuǎn)下步w 若某K 0而PK 0 ，則最優(yōu)解無界，結(jié)束。否則轉(zhuǎn)下步w 根據(jù)max j = K 原則確定XK 進(jìn)基變量；根據(jù)規(guī)則 ： = min

16、bi / aik aik 0 = bL/ aLk 確定XL為出基變量w 以aLk 為樞軸元素進(jìn)行迭代，回到第二步OR1442.3單純形法的進(jìn)一步探討w 2.3.1極小化問題直接求解：檢驗數(shù)的判別由所有j 0 即為最優(yōu)，變?yōu)樗衘 0則為最優(yōu)。w 人工變量法之一：大M法 人工變量價值系數(shù)M例w 人工變量法之二：構(gòu)造目標(biāo)函數(shù)，分階段求解例w 2.3.2無窮多最優(yōu)解情形：非基變量檢驗數(shù) j= 0w 2.3.3退化解的情形：有兩個以上 值相等OR1452.3.4單純形法的計算機(jī)求解w 程序說明w 應(yīng)用舉例例題1例題2OR1462.5LP應(yīng)用舉例之一w 例13合理下料問題料長7.4米，截成2.9、2.1

17、、1.5米各200根。如何截取余料最少？關(guān)鍵：設(shè)變量。 方案料型 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 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.4OR147應(yīng)用舉例之二 w 例14混合配方問題A、B、C、D四種原料配制三種產(chǎn)品，三類約束：技術(shù)要求、原料限量、市場容量。已知產(chǎn)品價格和原料價格，求利潤最大的配方。關(guān)鍵：設(shè)變量。OR148應(yīng)用舉例之三w 例15.滾動投資問題茲有100萬元閑錢

18、，投資方向有四： 第四年第一年第二年第三年A項目110%B項目135%C項目125%D項目104%第五年各年投資什么項目，使第五年末資本總額為最大？OR149應(yīng)用舉例之四w 例16動態(tài)生產(chǎn)計劃問題 工廠做n個月的生產(chǎn)計劃，第j月需求量dj、正常生產(chǎn)能力aj、加班生產(chǎn)能力bj、正常生產(chǎn)成本cj、加班生產(chǎn)成本ej、庫存能力為I、庫存費用hj，設(shè)期初、期末庫存為零。求費用最小的生產(chǎn)計劃。 設(shè)第月正常生產(chǎn)xj件，加班生產(chǎn)件yj，存儲zj件。則： 本期生產(chǎn)+上期庫存-本期庫存=本期需求OR150第三章 對偶問題與靈敏度分析w要求： 了解LP對偶問題的實際背景 了解對偶問題的建立規(guī)則與基本性質(zhì) 掌握對偶最

19、優(yōu)解的計算及其經(jīng)濟(jì)解釋 掌握LP的靈敏度分析 理解計算機(jī)輸出的影子價格與靈敏度分 析的內(nèi)容OR1513.1 對偶問題w3.1.1 對偶問題的提出 回顧例題1： 現(xiàn)在A、B兩產(chǎn)品銷路不暢，可以將所有資源出租或外賣，現(xiàn)在要談判，我們的價格底線是什么？產(chǎn)品A產(chǎn)品B資源限制勞動力設(shè)備原材料 9 4 3 4 5 10 360 200 300單位利潤 70 120OR152對偶模型w 設(shè)每個工時收費Y1元，設(shè)備臺時費用Y2元，原材料附加費Y3元。 出租收入不低于生產(chǎn)收入： 9y1+4y2+3y3 70 4y1+5y2+10y3 120目標(biāo)：=360y1+200y2+300y3出租收入越多越好？至少不低于某

20、數(shù)OR153原問題與對偶問題之比較原問題： 對偶問題：maxZ=70X1+120X2 min=360y1+200y2+300y3 9X1+4X2360 9y1+4y2+3y3 70 4X1+5X2 200 (3.1) 4y1+5y2+10y3 120 (3.2) 3X1+10X2 300 y1 0, y2 0, y3 0X10 X20OR1543.1.2對偶規(guī)則原問題一般模型： 對偶問題一般模型：maxZ=CX min =Yb AX b YA C X 0 Y 0OR155對偶規(guī)則w 原問題有m個約束條件，對偶問題有m個變量w 原問題有n個變量，對偶問題有n個約束條件w 原問題的價值系數(shù)對應(yīng)對偶

21、問題的右端項w 原問題的右端項對應(yīng)對偶問題的價值系數(shù)w 原問題的技術(shù)系數(shù)矩陣轉(zhuǎn)置后為對偶問題系數(shù)矩陣w 原問題的約束條件與對偶問題方向相反w 原問題與對偶問題優(yōu)化方向相反OR156對偶規(guī)則. 原問題 對偶問題目標(biāo)函數(shù) max min 目標(biāo)函數(shù)約束條件 = 變量無約束 變量符號 無約束 約束條件=OR157對偶規(guī)則簡捷記法w原問題標(biāo)準(zhǔn)則對偶問題標(biāo)準(zhǔn)w原問題不標(biāo)準(zhǔn)則對偶問題不標(biāo)準(zhǔn)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

22、 -x1+3x2 -x4+ x5 =-2 y1 -y2 -y3 0 x1，x2，x3 0; 3y1 +y3=1 x4 0;x5無限制 y1 0y2 0y3 無約束 OR1583.1.3對偶問題的基本性質(zhì)w 對稱性：對偶問題的對偶問題是原問題w 弱對偶性：極大化原問題的任一可行解的目標(biāo)函數(shù)值，不大于其對偶問題任意可行解的目標(biāo)函數(shù)值 (鞍型圖)w 無界性：原問題無界，對偶問題無可行解w 對偶定理：若一個問題有最優(yōu)解，則另一問題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。若原問題最優(yōu)基為B，則其對偶問題最優(yōu)解Y*=CBB-1OR1593.1.4對偶最優(yōu)解的經(jīng)濟(jì)解釋影子價格w Z= =CX=Yb Z/ b=(Yb)

23、=Yw Z=Yb= yibi的意義：Y是檢驗數(shù)的反數(shù)。在Y確定的前提下，每增加一個單位的i種資源，對目標(biāo)函數(shù)的貢獻(xiàn)。w 結(jié)合例題1講解影子價格：y1=0:第一種資源過剩 y2=13.6：設(shè)備臺時最緊張，每增加一個臺時， 利潤增加13.6元。y3=5.2w 影子價格所含有的信息： 1、資源緊缺狀況 2、確定資源轉(zhuǎn)讓基價參見：P40 3、取得緊缺資源的代價OR1603.2靈敏度分析w 為什么進(jìn)行靈敏度分析？w 靈敏度分析的兩把尺子： j =Cj-CBB-1pj 0； xB= B-1b 03.2.1 價值系數(shù)的靈敏度分析 Cj變化到什么程度可以保持最優(yōu)基不變？用 （參看P96）例題4： 87.5 C

24、2 233.33；36 C1 96OR161靈敏度分析w 右端項的靈敏度分析： bi變化到什么程度可以保持最優(yōu)基不變？用尺度 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 400OR162其它形式的靈敏度分析 新產(chǎn)品的分析：新產(chǎn)品的分析： 在資源結(jié)構(gòu)沒有變化的條件下，是否生產(chǎn)這種新 產(chǎn)品，就看它的競爭力如何。例題6：新增一種C產(chǎn)品，單位利潤110元，使用勞動力6工時，設(shè)備5臺時，原材料7公斤，問要否調(diào)整產(chǎn)品結(jié)構(gòu)？ 先算檢驗數(shù)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，加入到末表之中，繼續(xù)迭代，直到求得最優(yōu)解。OR1633.3用計算機(jī)進(jìn)行靈敏度分析w 例題7 參見P102OR164習(xí)題課：w P782.10（1）唯一最優(yōu)解：H3 0 ，H5 0 ， H1 0（2）無窮多最優(yōu)解：