【正文】 Erlang 1917 排隊論 Harris 1920 存儲論 緒論 ? 軍事運籌學階段 德軍空襲 防空系統(tǒng) Blackett 運輸船編隊 空襲逃避 深水炸彈 轟炸機編隊 緒論 ? 管理運籌學階段 戰(zhàn)后人員三分 :軍隊、大學、企業(yè) 大學：課程、專業(yè)、碩士、博士 企業(yè)：美國鋼鐵聯(lián)合公司 英國國家煤炭局 運籌學在中國： 50年代中期引入 華羅庚推廣 優(yōu)選法、統(tǒng)籌法 中國郵遞員問題、運輸問題 ? 兩者都是常用的決策方法 ? 定性是基礎(chǔ)，定量是工具，定量為定性服務。 ? 定性有主觀性，定量有科學性，管理科學的發(fā)展，定量越來越多。 ? 模型：真實事物的模仿，主要因素、相互關(guān)系、系統(tǒng)結(jié)構(gòu)。學生模擬企業(yè)管理系統(tǒng)運行。 V=F（ xi,yj,uk) G(xi,yj,uk)≥0 ? 規(guī)劃論：線性規(guī)劃、非線性規(guī)劃 |、整數(shù)規(guī)劃、目標規(guī)劃、動態(tài)規(guī)劃 ? 圖論與網(wǎng)絡 ? 存儲論 ? 排隊論 ? 決策論 ? 對策論 QM for Windows 的常用工具 人事 (工作分配問題 ) 整數(shù)規(guī)劃 （當線形規(guī)劃結(jié)果不為整數(shù)時 ,而需要是整數(shù)時用 當約束條件中 ,有選擇和不選擇的問題是用 一般的線性問題 運輸問題 ? 確定問題 ? 搜集數(shù)據(jù)建立模型 ? 檢驗模型 ? 求解模型 ? 結(jié)果分析 ? 結(jié)果實施 ? 計算機為運籌學提供解題工具。 第二章 線性規(guī)劃與單純形法 ? 引例 :一元優(yōu)化問題 ? 例題 1—— 生產(chǎn)計劃問題 產(chǎn)品 A 產(chǎn)品 B 資源限量 勞動力 設(shè) 備 原材料 9 4 3 4 5 10 360 200 300 利潤元 /KG 70 120 例題 1建模 ? 問題：如何安排生產(chǎn)計劃，使得獲利最多？ ? 步驟： 確定決策變量：設(shè)生產(chǎn) A產(chǎn)品 x1kg,B產(chǎn)品 x2kg 確定目標函數(shù)： maxZ=70X1+120X2 確定約束條件：人力約束 9X1+4X2≤360 設(shè)備約束 4X1+5X2 ≤200 原材料約束 3X1+10X2 ≤300 非負性約束 X1≥0 X2≥0 選擇變量個數(shù) QM\liner programming 數(shù)據(jù)輸入 分析結(jié)果 影子價格 例 (排產(chǎn)問題 ) :某公司生產(chǎn)兩種產(chǎn)品，具體的情況見表所示?，F(xiàn)有五種飼料，搭配使用，飼料成分如下表： 飼料 Va Vb Vc 價格元 /KG I II III IV V 3 2 1 6 18 1 2 1 2 2 7 4 9 5 營養(yǎng)要求 700 30 200 例題 2建模 ? 設(shè)抓取飼料 I x1kg。飼料 III x3kg…… ? 目標函數(shù)：最省錢 minZ=2x1+7x2+4x3+9x4+5x5 ? 約束條件： 3x2+2x2+x3+6x4+18x5 ≥700 營養(yǎng)要求： x1+++2x4+ ≥30 +x2++2x4+ =200 用量要求： x1 ≤50,x2 ≤60,x3 ≤50,x4 ≤70,x5 ≤4 非負性要求： x1 ≥0,x2 ≥0,x3 ≥0,x4 ≥0,x5 ≥0 例 2(排班問題 )：某公司日常工作統(tǒng)計，每晝夜至少需要的人數(shù)見表所示。不同時段需要的護士人數(shù)不等。不同時段需要的護士人數(shù)不等。一個全日制工人每天從 11點開始上班，工作 4小時，休息 1小時，然后再干 4小時。現(xiàn)在分析，要多少兼職工人。 9x1+4x2 ≤360 → x1 ≤360/94/9x2 是直線 x1=360/94/9x2 下方的半平面 線形的圖解化 區(qū)域是要封閉的 , 解在交點上 3x1+10x2=300 4x1+5x2=200 9x1+4x2=360 概念 ? 概念： 可行解：滿足所有約束條件的解。 基解：約束條件的交點稱為基解（直觀） 基可行解：基解當中的可行解。如：實心球、三角形 結(jié)論 ? 可行域是個凸集 ? 可行域有有限個頂點 ? 最優(yōu)值在可行域的頂點上達到 ? 無窮多解的情形 ? 無界解情形 ? 無解情形 ? 代數(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 線性規(guī)劃的標準型 ? 和式： maxZ=∑cjxj ∑aijxj=bi i=1,2,…,m xj ≥0 j=1,2,…,n 線性規(guī)劃的標準型 ? 向量式： maxZ=CX ∑pjxj=bi i=1,2,…,m xj ≥0 j=1,2,…,n C=(c1,c2,c3,…,c n) X=(X1,X2,X3,…,X n) T 線性規(guī)劃的標準型 ? 矩陣式： maxZ=CX AX=b X ≥0 b=(b1,b2,…,b m)T a11 a12 …. a1n A= a21 a22 … a2n … … … am1 am2 … amn 非標準型轉(zhuǎn)化舉例 之二 minZ=x1+2x23x3 maxZ’=x’12x2+3(x’3 x”3) x1+x2+x3 ≤9 x’1+x2+x’3 x”3 + x4=9 x12x2+x3 ≥2 x’12x2+x’3 x”3 x5= 2 3x1+x23x3=5 3x’1+x23(x’3 x”3 )=5 x1 ≤0 x2 ≥0 x3無約束 x’1 ≥ 0 x2 ≥0 x’3 ≥0 x”3 ≥0 x4≥0 x5≥0 非標準型轉(zhuǎn)化舉例 之二 minZ=x1+2x23x3 maxZ’=x’12x2+3(x’3 x”3) x1+x2+x3 ≤9 x’1+x2+x’3 x”3 + x4=9 x12x2+x3 ≥2 x’12x2+x’3 x”3 x5= 2 3x1+x23x3=5 3x’1+x23(x’3 x”3 )=5 x1 ≤0 x2 ≥0 x3無約束 x’1 ≥ 0 x2 ≥0 x’3 ≥0 x”3 ≥0 x4≥0 x5≥0 例 5(混合配方問題 )：一家化工廠將四種原料 A、 B、 C、 D混合調(diào)配出三種產(chǎn)品，三種產(chǎn)品的銷售價格分別為每公斤 9元、 元和 8元，各種原料 A、 B、 C、 D的供應量分別是 1000、 1000，750和 800公斤；單價分別是每公斤 5元、 6元、 4元和 。產(chǎn)品 Ⅰ 可在 A、 B任何設(shè)備上加工； Ⅱ 產(chǎn)品可在任何 A上完成，但是只能在 B1上完成 B工序； Ⅲ 產(chǎn)品只能在 A2上完成 A工序、 B2上完成 B工序，各種生產(chǎn)參數(shù)見表所示。 設(shè)備 產(chǎn)品 設(shè)備有效臺時 滿負荷時設(shè)備費用 (元 ) Ⅰ Ⅱ Ⅲ A1 A2 B1 B2 B3 5 10 7 9 12 6 8 4 11 7 6000 10000 4000 7000 4000 600 642 500 1566 400 原料費 (元 /件 ) 單價 (元 /件 ) 例 4(一維下料問題 )：某廠有一批長度為 (數(shù)量充分多 )，今為制造零件要將它們截成長度為 ， ，需要量都是 200根，問應如何下料，使用的原材料最少？ 方案 1 2 3 4 5 6 7 8 1 2 0 1 0 1 0 0 0 0 2 2 1 1 3 0 3 1 2 0 3 1 0 4 合計 6 料頭 0 解：設(shè)每種方案下料根數(shù)為 X1， X2， X3， X4， X5， X6， X7， X8 Obj： MinZ=X1+X2+X3+X4+X5+X6+X7+X8 S． T． X1+2x2+x4+x6=200 2x3+2x4+x5+x6+3x7=200 3x1+x2+2x3+3x5+x6+4x8=200 x1=60。x4=100 二維下料問題：平面下料問題 三維下料問題：運輸裝配問題 第三章對偶問題與靈敏度分析 ? 要求： 了解 LP對偶問題的實際背景 了解對偶問題的建立規(guī)則與基本性質(zhì) 掌握對偶最優(yōu)解的計算及其經(jīng)濟解釋 掌握 LP的靈敏度分析 理解計算機輸出的影子價格與靈敏度分 析的內(nèi)容 對偶問題 ? 對偶問題的提出 回顧例題 1： 現(xiàn)在 A、 B兩產(chǎn)品銷路不暢，可以將所有資源出租或外賣，現(xiàn)在要談判