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

信息系統(tǒng)項(xiàng)目管理師運(yùn)籌學(xué) OR1 1 信息系統(tǒng)項(xiàng)目管理師上午綜合題最后5道題 非英文題 一般都是運(yùn)籌學(xué)的題 因此需要考生知道如何使用運(yùn)籌學(xué)知識去解題 專業(yè)軟考交流論壇 歡迎您的光臨 學(xué)習(xí) 交流 探討 OR1 2 第一章緒論 1 1題解Operations漢語翻譯工作 操作 行動 手術(shù) 運(yùn)算OperationsResearch日本 運(yùn)用學(xué)港臺 作業(yè)研究中國大陸 運(yùn)籌學(xué)OperationalResearch原來名稱 意為軍事行動研究 歷史淵源 OR1 3 緒論 1 2運(yùn)籌學(xué)的歷史早期運(yùn)籌思想 田忌賽馬丁渭修宮沈括運(yùn)糧Erlang1917排隊論Harris1920存儲論Levinson1930零售貿(mào)易康脫洛維奇1939LP OR1 4 緒論 1 2運(yùn)籌學(xué)的歷史軍事運(yùn)籌學(xué)階段德軍空襲防空系統(tǒng)Blackett運(yùn)輸船編隊空襲逃避深水炸彈轟炸機(jī)編隊 OR1 5 緒論 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)輸問題 OR1 6 1 3學(xué)科性質(zhì) 應(yīng)用學(xué)科Morse Kimball定義 運(yùn)籌學(xué)是為決策機(jī)構(gòu)在對其控制的業(yè)務(wù)活動進(jìn)行決策時提供的數(shù)量化為基礎(chǔ)的科學(xué)方法 Churchman定義 運(yùn)籌學(xué)是應(yīng)用科學(xué)的方法 技術(shù)和工具 來處理一個系統(tǒng)運(yùn)行中的問題 使系統(tǒng)控制得到最優(yōu)的解決方法 中國定義 運(yùn)籌學(xué)是應(yīng)用分析 試驗(yàn) 量化的方法 對經(jīng)濟(jì)管理系統(tǒng)中人力 物力 財力等資源進(jìn)行統(tǒng)籌安排 為決策者提供有依據(jù)的最優(yōu)方案 以實(shí)現(xiàn)最有效的管理 OR1 7 1 4定性與定量 例 店主進(jìn)貨兩者都是常用的決策方法定性是基礎(chǔ) 定量是工具 定量為定性服務(wù) 定性有主觀性也有有效性 定量有科學(xué)性也有局限性 管理科學(xué)的發(fā)展 定量越來越多 但定量不可替代定性 OR1 8 1 5運(yùn)籌學(xué)的模型 模型 真實(shí)事物的模仿 主要因素 相互關(guān)系 系統(tǒng)結(jié)構(gòu) 形象模型 如地球儀 沙盤 風(fēng)洞模擬模型 建港口 模擬船只到達(dá) 學(xué)生模擬企業(yè)管理系統(tǒng)運(yùn)行 數(shù)學(xué)模型 用符號或數(shù)學(xué)工具描述現(xiàn)實(shí)系統(tǒng) V F xi yj uk G xi yj uk 0 OR1 9 1 6運(yùn)籌學(xué)的學(xué)科體系 規(guī)劃論 線性規(guī)劃 非線性規(guī)劃 整數(shù)規(guī)劃 目標(biāo)規(guī)劃 動態(tài)規(guī)劃圖論與網(wǎng)絡(luò)存儲論排隊論決策論對策論計算機(jī)仿真 OR1 10 1 7運(yùn)籌學(xué)的工作步驟 確定問題搜集數(shù)據(jù)建立模型檢驗(yàn)?zāi)Ｐ颓蠼饽Ｐ徒Y(jié)果分析結(jié)果實(shí)施 OR1 11 1 8運(yùn)籌學(xué)與計算機(jī) 計算機(jī)為運(yùn)籌學(xué)提供解題工具 本書有現(xiàn)成的程序可以利用要學(xué)會解題的思路與方法 建立模型很重要 OR1 12 第二章線性規(guī)劃與單純形法 2 1LP linearprogramming 的基本概念LP是在有限資源的條件下 合理分配和利用資源 以期取得最佳的經(jīng)濟(jì)效益的優(yōu)化方法 LP有一組有待決策的變量 一個線性的目標(biāo)函數(shù) 一組線性的約束條件 OR1 13 2 1 1LP的數(shù)學(xué)模型例題1 生產(chǎn)計劃問題 某廠生產(chǎn)兩種產(chǎn)品 需要三種資源 已知各產(chǎn)品的利潤 各資源的限量和各產(chǎn)品的資源消耗系數(shù)如下表 OR1 14 例題1建模 問題 如何安排生產(chǎn)計劃 使得獲利最多 步驟 1 確定決策變量 設(shè)生產(chǎn)A產(chǎn)品x1kg B產(chǎn)品x2kg2 確定目標(biāo)函數(shù) maxZ 70X1 120X23 確定約束條件 人力約束9X1 4X2 360設(shè)備約束4X1 5X2 200原材料約束3X1 10X2 300非負(fù)性約束X1 0X2 0 OR1 15 例題2 配方問題 養(yǎng)海貍鼠飼料中營養(yǎng)要求 VA每天至少700克 VB每天至少30克 VC每天剛好200克 現(xiàn)有五種飼料 搭配使用 飼料成分如下表 OR1 16 例題2建模 設(shè)抓取飼料Ix1kg 飼料IIx2kg 飼料IIIx3kg 目標(biāo)函數(shù) 最省錢minZ 2x1 7x2 4x3 9x4 5x5約束條件 3x2 2x2 x3 6x4 18x5 700營養(yǎng)要求 x1 0 5x2 0 2x3 2x4 0 5x5 300 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 OR1 17 例題3 人員安排問題 醫(yī)院護(hù)士24小時值班 每次值班8小時 不同時段需要的護(hù)士人數(shù)不等 據(jù)統(tǒng)計 OR1 18 例題3建模 目標(biāo)函數(shù) minZ x1 x2 x3 x4 x5 x6約束條件 x1 x2 70 x2 x3 60 x3 x4 50 x4 x5 20 x5 x6 30非負(fù)性約束 xj 0 j 1 2 6 OR1 19 歸納 線性規(guī)劃的一般模式 目標(biāo)函數(shù) max min Z c1x1 c2x2 c3x3 cnxn約束條件 a11x1 a12x2 a13x3 a1nxn b1a21x1 a22x2 a23x3 a2nxn b2 am1x1 am2x2 am3x3 amnxn bn非負(fù)性約束 x1 0 x2 0 xn 0 OR1 20 2 1 2線性規(guī)劃圖解法 由中學(xué)知識可知 y ax b是一條直線 同理 Z 70 x1 120 x2 x2 70 120 x1 Z 120也是一條直線 以Z為參數(shù)的一族等值線 9x1 4x2 360 x1 360 9 4 9x2是直線x1 360 9 4 9x2下方的半平面 所有半平面的交集稱之為可行域 可行域內(nèi)的任意一點(diǎn) 就是滿足所有約束條件的解 稱之為可行解 OR1 21 例1圖示 9080604020 020406080100 x1 x2 9x1 4x2 360 4x1 5x2 200 3x1 10 x2 300 A B C D E F G H I Z 70 x1 120 x2 OR1 22 概念 概念 1 可行解 滿足所有約束條件的解 2 可行域 即可行解的集合 所有約束條件的交集 也就是各半平面的公共部分 滿足所有約束條件的解的集合 稱為可行域 3 基解 約束條件的交點(diǎn)稱為基解 直觀 4 基可行解 基解當(dāng)中的可行解 5 凸集 集合內(nèi)任意兩點(diǎn)的連線上的點(diǎn)均屬于這個集合 如 實(shí)心球 三角形 OR1 23 結(jié)論 可行域是個凸集可行域有有限個頂點(diǎn)最優(yōu)值在可行域的頂點(diǎn)上達(dá)到無窮多解的情形無界解情形無解情形 OR1 24 2 1 3線性規(guī)劃的標(biāo)準(zhǔn)型 代數(shù)式maxZ c1x1 c2x2 cnxna11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmxj 0j 1 2 n OR1 25 線性規(guī)劃的標(biāo)準(zhǔn)型 和式 maxZ cjxj aijxj bii 1 2 mxj 0j 1 2 n j 1 n n j 1 OR1 26 線性規(guī)劃的標(biāo)準(zhǔn)型 向量式 maxZ CX pjxj bii 1 2 mxj 0j 1 2 nC c1 c2 c3 cn X X1 X2 X3 Xn T n j 1 OR1 27 線性規(guī)劃的標(biāo)準(zhǔn)型 矩陣式 maxZ CXAX bX 0其中 b b1 b2 bm Ta11a12 a1nA a21a22 a2n am1am2 amn OR1 28 標(biāo)準(zhǔn)型的特征 目標(biāo)函數(shù)極大化約束條件為等式?jīng)Q策變量非負(fù) OR1 29 非標(biāo)準(zhǔn)型轉(zhuǎn)化為標(biāo)準(zhǔn)型 目標(biāo)函數(shù)極小化轉(zhuǎn)為極大化 minZ max Z 一個數(shù)的極小化等價于其相反數(shù)的極大化 不等式約束的轉(zhuǎn)化 aijxj bi加入松弛變量 aijxj bi減去剩余變量非正變量 即xk 0則令x k xk自由變量 即xk無約束 令xk x k x k OR1 30 非標(biāo)準(zhǔn)型轉(zhuǎn)化舉例之一 maxZ 70X1 120X2maxZ 70X1 120X29X1 4X2 3609X1 4X2 X3 3604X1 5X2 2004X1 5X2 x4 2003X1 10X2 3003X1 10X2 x5 300X1 0X2 0Xj 0j 1 2 5 OR1 31 非標(biāo)準(zhǔn)型轉(zhuǎn)化舉例之二 minZ x1 2x2 3x3maxZ x 1 2x2 3 x 3 x 3 x1 x2 x3 9 x 1 x2 x 3 x 3 x4 9 x1 2x2 x3 2x 1 2x2 x 3 x 3 x5 23x1 x2 3x3 5 3x 1 x2 3 x 3 x 3 5x1 0 x2 0 x3無約束x 1 0 x2 0 x 3 0 x 3 0 x4 0 x5 0 OR1 32 2 1 4基可行解 基的概念 如前所述LP標(biāo)準(zhǔn)型和式 maxZ cjxj aijxj bixj 0j 1 2 n矩陣式 maxZ CXAX bX 0約束方程的系數(shù)矩陣A的秩為m 且m n 設(shè)A B N B是A中m m階非奇異子矩陣 則稱B是LP的一個基 即 B是A中m個線性無關(guān)向量組 n j 1 n j 1 OR1 33 基解的概念 不失一般性 設(shè)B是A的前m列 即B p1 p2 pm 其相對應(yīng)的變量XB x1 x2 xm T 稱為基變量 其余變量XN Xm 1 Xn T稱為非基變量 令所有非基變量等于零 則X x1 x2 xm 0 0 T稱為基解 OR1 34 基可行解的概念 基可行解 基解可正可負(fù) 負(fù)則不可行 違背非負(fù)性約束條件 稱滿足所有約束條件的基解為基可行解 退化的基可行解 若某個基變量取值為零 則稱之為退化的基可行解 基解的數(shù)目 最多Cmn n m n m OR1 35 例題6基可行解說明 maxZ 70X1 120X2P1P2P3P4P59X1 4X2 X3 360941004X1 5X2 x4 200A 450103X1 10X2 x5 300310001Xj 0j 1 2 5這里m 3 n 5 Cmn 10 OR1 36 例題6基可行解說明 基 p3 p4 p5 令非基變量x1 x2 0 則基變量x3 360 x4 200 x5 300 可行解基 p2 p4 p5 令非基變量x1 0 x3 0基變量x2 90 x4 250 x5 600 非可行解基 p2 p3 p4 令非基變量x1 x5 0 則基變量x2 30 x3 240 x4 50 可行解 P21圖 OR1 37 2 2單純形法 2 2 1初始基可行解的確定從系數(shù)矩陣中找到一個可行基B 不妨設(shè)B由A的前m列組成 即B P1 P2 Pm 進(jìn)行等價變換 約束方程兩端分別左乘B 1得X1 a 1m 1xm 1 a 1nxn b 1x2 a 2m 1xm 1 a 2nxn b 2 xm a mm 1xm 1 a mnxn b m令非基變量為0 得基可行解X 0 b1 b2 bm 0 0 Tz0 cibi OR1 38 2 2單純形法 2 2 2最優(yōu)性檢驗(yàn) LP經(jīng)過若干步迭代 成為如下形式 X1 a 1m 1xm 1 a 1nxn b 1x1 b 1 a 1jxjx2 a 2m 1xm 1 a 2nxn b 2x2 b 2 a 2jxj xm a mm 1xm 1 a mnxn b mxm b m a mjxj OR1 39 單純形法 一般性表示 xi b i a ijxji 1 2 m將xi代入目標(biāo)函數(shù)得 Z cjxj cixi cjxj ci b i a ijxj cjxj cibi cj cia ij xj令 j cj cia ijz0 cibi 則Z z0 jxj j判別準(zhǔn)則 j 0時 達(dá)到最優(yōu)解 OR1 40 單純形法 2 2 2基變換若存在 j 0 則取max j K 相應(yīng)之非基變量XK若取非零 將使Z增加 故令XK進(jìn)基 令XK 0 其余非基變量保持為零 XK原是非基變量 取零值 若XK 0將迫使某個原基變量為零 當(dāng)XK取值超過任意b i a ik時 將破壞非負(fù)性條件 于是令 min b i a ika ik 0 b L a Lk 這時原基變量XL 0 由基變量變成非基變量 a Lk處在變量轉(zhuǎn)換的交叉點(diǎn)上 稱之為樞軸元素 j 0 OR1 41 單純形法解題舉例 單純形表的格式 OR1 42 OR1 43 2 2 3單純形法的計算步驟 找到初始可行基 建立單純形表計算檢驗(yàn)數(shù) 若所有 j 0則得最優(yōu)解 結(jié)束 否則轉(zhuǎn)下步若某 K 0而P K 0 則最優(yōu)解無界 結(jié)束 否則轉(zhuǎn)下步根據(jù)max j K原則確定XK進(jìn)基變量 根據(jù) 規(guī)則 min b i a ika ik 0 b L a Lk確定XL為出基變量以a Lk為樞軸元素進(jìn)行迭代 回到第二步 OR1 44 2 3單純形法的進(jìn)一步探討 2 3 1極小化問題直接求解 檢驗(yàn)數(shù)的判別由所有 j 0即為最優(yōu) 變?yōu)樗?j 0則為最優(yōu) 人工變量法之一 大M法人工變量價值系數(shù)M例人工變量法之二 構(gòu)造目標(biāo)函數(shù) 分階段求解例2 3 2無窮多最優(yōu)解情形 非基變量檢驗(yàn)數(shù) j 02 3 3退化解的情形 有兩個以上 值相等 OR1 45 2 3 4單純形法的計算機(jī)求解 程序說明應(yīng)用舉例例題1例題2 OR1 46 2 5LP應(yīng)用舉例之一 例13合理下料問題料長7 4米 截成2 9 2 1 1 5米各200根 如何截取余料最少 關(guān)鍵 設(shè)變量 OR1 47 應(yīng)用舉例之二 例14混合配方問題A B C D四種原料配制三種產(chǎn)品 三類約束 技術(shù)要求 原料限量 市場容量 已知產(chǎn)品價格和原料價格 求利潤最大的配方 關(guān)鍵 設(shè)變量 OR1 48 應(yīng)用舉例之三 例15 滾動投資問題茲有100萬元閑錢 投資方向有四 第四年 第一年 第二年 第三年 A項(xiàng)目110 B項(xiàng)目135 C項(xiàng)目125 D項(xiàng)目104 第五年 各年投資什么項(xiàng)目 使第五年末資本總額為最大 OR1 49 應(yīng)用舉例之四 例16動態(tài)生產(chǎn)計劃問題工廠做n個月的生產(chǎn)計劃 第j月需求量dj 正常生產(chǎn)能力aj 加班生產(chǎn)能力bj 正常生產(chǎn)成本cj 加班生產(chǎn)成本ej 庫存能力為I 庫存費(fèi)用hj 設(shè)期初 期末庫存為零 求費(fèi)用最小的生產(chǎn)計劃 設(shè)第月正常生產(chǎn)xj件 加班生產(chǎn)件yj 存儲zj件 則 本期生產(chǎn) 上期庫存 本期庫存 本期需求 OR1 50 第三章對偶問題與靈敏度分析 要求 了解LP對偶問題的實(shí)際背景了解對偶問題的建立規(guī)則與基本性質(zhì)掌握對偶最優(yōu)解的計算及其經(jīng)濟(jì)解釋掌握LP的靈敏度分析理解計算機(jī)輸出的影子價格與靈敏度分析的內(nèi)容 OR1 51 3 1對偶問題 3 1 1對偶問題的提出回顧例題1 現(xiàn)在A B兩產(chǎn)品銷路不暢 可以將所有資源出租或外賣 現(xiàn)在要談判 我們的價格底線是什么 OR1 52 對偶模型 設(shè)每個工時收費(fèi)Y1元 設(shè)備臺時費(fèi)用Y2元 原材料附加費(fèi)Y3元 出租收入不低于生產(chǎn)收入 9y1 4y2 3y3 704y1 5y2 10y3 120目標(biāo) 360y1 200y2 300y3出租收入越多越好 至少不低于某數(shù) OR1 53 原問題與對偶問題之比較 原問題 對偶問題 maxZ 70X1 120X2min 360y1 200y2 300y39X1 4X2 3609y1 4y2 3y3 704X1 5X2 200 3 1 4y1 5y2 10y3 120 3 2 3X1 10X2 300y1 0 y2 0 y3 0X1 0X2 0 OR1 54 3 1 2對偶規(guī)則 原問題一般模型 對偶問題一般模型 maxZ CXmin YbAX bYA CX 0Y 0 OR1 55 對偶規(guī)則 原問題有m個約束條件 對偶問題有m個變量原問題有n個變量 對偶問題有n個約束條件原問題的價值系數(shù)對應(yīng)對偶問題的右端項(xiàng)原問題的右端項(xiàng)對應(yīng)對偶問題的價值系數(shù)原問題的技術(shù)系數(shù)矩陣轉(zhuǎn)置后為對偶問題系數(shù)矩陣原問題的約束條件與對偶問題方向相反原問題與對偶問題優(yōu)化方向相反 OR1 56 對偶規(guī)則 OR1 57 對偶規(guī)則簡捷記法 原問題標(biāo)準(zhǔn)則對偶問題標(biāo)準(zhǔn)原問題不標(biāo)準(zhǔn)則對偶問題不標(biāo)準(zhǔn)例題2max 7y1 4y2 2y3minZ 3x1 2x2 6x3 x52y1 y2 y3 32x1 x2 4x3 x4 3x5 7y1 3y3 2x1 2x3 x4 4 4y1 2y2 6 x1 3x2 x4 x5 2y1 y2 y3 0 x1 x2 x3 0 3y1 y3 1x4 0 x5無限制y1 0y2 0y3無約束 OR1 58 3 1 3對偶問題的基本性質(zhì) 對稱性 對偶問題的對偶問題是原問題弱對偶性 極大化原問題的任一可行解的目標(biāo)函數(shù)值 不大于其對偶問題任意可行解的目標(biāo)函數(shù)值 鞍型圖 無界性 原問題無界 對偶問題無可行解對偶定理 若一個問題有最優(yōu)解 則另一問題也有最優(yōu)解 且目標(biāo)函數(shù)值相等 若原問題最優(yōu)基為B 則其對偶問題最優(yōu)解Y CBB 1 OR1 59 3 1 4對偶最優(yōu)解的經(jīng)濟(jì)解釋 影子價格 Z CX Yb Z b Yb YZ Yb yibi的意義 Y是檢驗(yàn)數(shù)的反數(shù) 在Y確定的前提下 每增加一個單位的i種資源 對目標(biāo)函數(shù)的貢獻(xiàn) 結(jié)合例題1講解影子價格 y1 0 第一種資源過剩y2 13 6 設(shè)備臺時最緊張 每增加一個臺時 利潤增加13 6元 y3 5 2 影子價格所含有的信息 1 資源緊缺狀況2 確定資源轉(zhuǎn)讓基價參見 P403 取得緊缺資源的代價 OR1 60 3 2靈敏度分析 為什么進(jìn)行靈敏度分析 靈敏度分析的兩把尺子 j Cj CBB 1pj 0 xB B 1b 03 2 1價值系數(shù)的靈敏度分析Cj變化到什么程度可以保持最優(yōu)基不變 用 參看P96 例題4 87 5 C2 233 33 36 C1 96 OR1 61 靈敏度分析 右端項(xiàng)的靈敏度分析 bi變化到什么程度可以保持最優(yōu)基不變 用尺度 xB B 1b 0例題5 1 3 121 16360B 1b 00 4 0 2200 00 0 120 16b3b3的變化范圍 227 586 b3 400 OR1 62 其它形式的靈敏度分析 新產(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) 先算檢驗(yàn)數(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)解 OR