【正文】 PERATIONS RESEARCH 運(yùn)籌學(xué) Ⅰ ? ——怎樣把事情做到最好 ? 郝英奇 OR1 1 第一章 緒論 ? Operations 漢語(yǔ)翻譯 工作、操作、行動(dòng)、手術(shù)、運(yùn)算 Operations Research 日本 ——運(yùn)用學(xué) 港臺(tái) ——作業(yè)研究 中國(guó)大陸 ——運(yùn)籌學(xué) Operational Research原來(lái)名稱，意為軍事行動(dòng)研究——?dú)v史淵源 OR1 2 緒論 ? 運(yùn)籌學(xué)的歷史 早期運(yùn)籌思想：田忌賽馬 丁渭修宮 沈括運(yùn)糧 Erlang 1917 排隊(duì)論 Harris 1920 存儲(chǔ)論 Levinson 1930 零售貿(mào)易 康脫洛維奇 1939 LP OR1 3 緒論 ? 軍事運(yùn)籌學(xué)階段 德軍空襲 防空系統(tǒng) Blackett 運(yùn)輸船編隊(duì) 空襲逃避 深水炸彈 轟炸機(jī)編隊(duì) OR1 4 緒論 ? 管理運(yùn)籌學(xué)階段 戰(zhàn)后人員三分 :軍隊(duì)、大學(xué)、企業(yè) 大學(xué)：課程、專業(yè)、碩士、博士 企業(yè)：美國(guó)鋼鐵聯(lián)合公司 英國(guó)國(guó)家煤炭局 運(yùn)籌學(xué)在中國(guó)： 50年代中期引入 華羅庚推廣 優(yōu)選法、統(tǒng)籌法 中國(guó)郵遞員問(wèn)題、運(yùn)輸問(wèn)題 OR1 5 ?應(yīng)用學(xué)科 ?MorseKimball定義：運(yùn)籌學(xué)是為決策機(jī)構(gòu)在對(duì)其控制的業(yè)務(wù)活動(dòng)進(jìn)行決策時(shí)提供的數(shù)量化為基礎(chǔ)的科學(xué)方法。 ?Churchman定義：運(yùn)籌學(xué)是應(yīng)用科學(xué)的方法、技術(shù)和工具，來(lái)處理一個(gè)系統(tǒng)運(yùn)行中的問(wèn)題，使系統(tǒng)控制得到最優(yōu)的解決方法。 OR1 6 ? 例：店主進(jìn)貨 ? 兩者都是常用的決策方法 ? 定性是基礎(chǔ)，定量是工具，定量為定性服務(wù)。管理科學(xué)的發(fā)展，定量越來(lái)越多。 OR1 7 ? 模型：真實(shí)事物的模仿，主要因素、相互關(guān)系、系統(tǒng)結(jié)構(gòu)。學(xué)生模擬企業(yè)管理系統(tǒng)運(yùn)行。 V=F（ xi,yj,uk) G(xi,yj,uk)≥0 OR1 8 ? 規(guī)劃論：線性規(guī)劃、非線性規(guī)劃 |、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動(dòng)態(tài)規(guī)劃 ? 圖論與網(wǎng)絡(luò) ? 存儲(chǔ)論 ? 排隊(duì)論 ? 決策論 ? 對(duì)策論 ? 計(jì)算機(jī)仿真 OR1 9 ? 確定問(wèn)題 ? 搜集數(shù)據(jù)建立模型 ? 檢驗(yàn)?zāi)Ｐ? ? 求解模型 ? 結(jié)果分析 ? 結(jié)果實(shí)施 OR1 10 ? 計(jì)算機(jī)為運(yùn)籌學(xué)提供解題工具。 OR1 11 第二章 線性規(guī)劃與單純形法 ? LP(linear programming)的基本概念 LP是在有限資源的條件下，合理分配和利用資源，以期取得最佳的經(jīng)濟(jì)效益的優(yōu)化方法。 OR1 12 LP的數(shù)學(xué)模型 例題 1—生產(chǎn)計(jì)劃問(wèn)題 ? 某廠生產(chǎn)兩種產(chǎn)品，需要三種資源，已知各產(chǎn)品的利潤(rùn)、各資源的限量和各產(chǎn)品的資源消耗系數(shù)如下表： 產(chǎn)品 A 產(chǎn)品 B 資源限量 勞動(dòng)力 設(shè) 備 原材料 9 4 3 4 5 10 360 200 300 利潤(rùn)元 /kg 70 120 OR1 13 例題 1建模 ? 問(wèn)題：如何安排生產(chǎn)計(jì)劃，使得獲利最多？ ? 步驟： 確定決策變量：設(shè)生產(chǎn) A產(chǎn)品 x1kg,B產(chǎn)品 x2kg 確定目標(biāo)函數(shù)： maxZ=70X1+120X2 確定約束條件：人力約束 9X1+4X2≤360 設(shè)備約束 4X1+5X2 ≤200 原材料約束 3X1+10X2 ≤300 非負(fù)性約束 X1≥0 X2≥0 OR1 14 例題 2——配方問(wèn)題 ? 養(yǎng)海貍鼠 飼料中營(yíng)養(yǎng)要求： VA每天至少 700克， VB每天至少 30克， VC每天剛好 200克。飼料 II x2kg。不同時(shí)段需要的護(hù)士人數(shù)不等。 9x1+4x2 ≤360 → x 1 ≤360/94/9x2 是直線 x1=360/94/9x2 下方的半平面。 OR1 20 例 1圖示 . 90 80 60 40 20 0 20 40 60 80 100 x1 x2 9x1+4x2 ≤ 360 4x1+5x2 ≤200 3x1+10x2 ≤300 A B C D E F G H I Z=70x1+120x2 OR1 21 概念 ? 概念： 可行解：滿足所有約束條件的解。所有約束條件的交集，也就是各半平面的公共部分。 基解：約束條件的交點(diǎn)稱為基解（直觀） 基可行解：基解當(dāng)中的可行解。如：實(shí)心球、三角形 OR1 22 結(jié)論 ? 可行域是個(gè)凸集 ? 可行域有有限個(gè)頂點(diǎn) ? 最優(yōu)值在可行域的頂點(diǎn)上達(dá)到 ? 無(wú)窮多解的情形 ? 無(wú)界解情形 ? 無(wú)解情形 OR1 23 ? 代數(shù)式 maxZ=c1x1+c2x2+…+c nxn a11x1+a12x2+…+a 1nxn=b1 a21x1+a22x2+…+a 2nxn=b2 … … … am1x1+am2x2+…+a mnxn=bm xj ≥0 j=1,2,…,n OR1 24 線性規(guī)劃的標(biāo)準(zhǔn)型 ? 和式： maxZ=∑cjxj ∑aijxj=bi i=1,2