管理運籌學-管理科學方法.ppt

管理運籌學 -管理科學方法,謝家平 博士 教授 博士生導師 研究領域：管理科學、運營管理、供應鏈管理 講授課程：管理運籌學-管理科學方法、管理系統(tǒng)工程、 運營管理、 供應鏈管理、ERP、國際物流、 企業(yè)物流管理、管理決策模型與方法 單 位：上海財經大學工商學院 物流管理系 E-mail：,2,教材與參考書籍,教材： 謝家平編著.管理運籌學：管理科學方法， 中國人民大學出版社，2010 參考書： David et al. 數據、模型與決策，機械工業(yè)出版社，2004 費雷德里克. 數據、模型與決策，中國財政經濟出版社，2004 James et al. 數據、模型與決策，中國人民大學出版社，2006,3,32課時講授提綱,緒 論 第一章 線性規(guī)劃 第二章 線性規(guī)劃討論 第三章 對偶規(guī)劃 靜態(tài)規(guī)劃 第四章 整數規(guī)劃 第五章 目標規(guī)劃 第六章 動態(tài)規(guī)劃 動態(tài)優(yōu)化 第七章 網絡分析 第八章 網絡計劃 第九章 決策分析 第十章 方案排序 第十一章 庫存控制 第十二章 排隊理論,離散優(yōu)化,隨機優(yōu)化,淡化數學算法 LINDO求解,4,考核方式,結課考試： 筆試（開卷 or 閉卷？） 每章一題 80% 案例研究： 選擇合適方法結合企業(yè)實際進行應用 20%,5,管理運籌學的稱謂,管理運籌學是一門研究如何最優(yōu)安排的學科。 Operations Research 日本譯作“運用學” 香港、臺灣譯為“作業(yè)研究” 我國譯作“運籌學” 源于古語“運籌帷幄之中，決勝千里之外” 取“運籌”二字，體現運心籌謀、策略取勝 Management Science 管理科學 運用數學、統(tǒng)計學和運籌學中的量化分析原理和方法，建立數學模型/計算機仿真，給管理決策提供科學依據。,6,緒 論,一、發(fā)展歷史 二、學科作用 三、學科性質 四、工作程序 五、學科體系 六、學習要求,7,一、發(fā)展歷史,1. 早期的運籌思想 齊王賽馬 渭修皇宮 沈括運軍糧 科學管理 2. 軍事運籌學階段 20世紀40年代誕生于英美 1940年，英國為對付德國空軍的空襲，使用了雷達，但沒有科學布局，效果不好。為解決這個問題，成立運籌學小組，稱Operational Research，意為作戰(zhàn)研究。 美國和加拿大也在軍隊設立運籌學小組，稱Operations Research，協(xié)助指揮官研究戰(zhàn)略及戰(zhàn)術問題。 3. 管理運籌學階段 戰(zhàn)后許多從事運籌學研究的科學家轉向了民用問題的研究，使運籌學在企業(yè)管理方面的應用得到了長足進展。,8,企業(yè)的成功要素中： 觀念意識更新 47 人文文化 35 技術優(yōu)勢 18 決策意識的科學性 成功決策 正確決策,二、學科作用,理念的重要性,？,9,二、學科作用,1. 量化管理的重要性 管理科學是對與定量因素有關的管理問題通過應用科學的方法進行輔助管理決策的一門學科。 目的：用科學方法分析管理問題，為管理者決策提供依據 目標：在企業(yè)經營內外環(huán)境的限制下，實現資源效用最大,量化管理是第一步,它導致控制,并最終實現改進 如果不能量化某些事情，那么就不能理解它 如果不能理解它，那么就不能控制它 如果不能控制它，那么就不能改進它 H. James Harrington,定性到定量分析，數量界限的重要性：量變引起質變,10,聽一場音樂會：網絡訂票的票價500元，不去可退票 情況1：在你馬上要出發(fā)的時候，發(fā)現你把最近的價值500元的電話卡弄丟了。你是否還會去聽這場音樂會？ 情況2：假設昨天花500元錢買一張今晚的音樂會取票單。在你出發(fā)時，發(fā)現把票單丟了。如果去聽音樂會，就必須再花500元錢買張票，去還會不去？,二、學科作用,2. 量化思考使人理性 冰淇淋實驗： 一杯A有70克，裝在50克的杯子里，看上去要溢出了 一杯B是80克，裝在100克的杯子里，看上去還沒裝滿,單獨憑經驗判斷時，在相同的價格上，人們普遍選擇A,實驗表明，大部分的回答者仍舊會去聽,結果卻是，大部分人回答說不去了,11,二、學科作用,3. 量化分析輔助決策 盈虧平衡分析,利潤：I = ( P Cm Ch ) Q - F 策略1 差異化，領先者戰(zhàn)略 策略2 規(guī)?；?，大規(guī)模市場 策略3 機械化，第一利潤源 策略4 技能化，第二利潤源 策略5 信息化，第三利潤源,12,二、學科作用,量化輔助決策案例：盈虧平衡分析 例：某企業(yè) 總銷售額 1100萬元 物料成本 700萬元 員工工資 200萬元 管理費用 100萬元 現在利潤=100萬元，目標利潤150萬元,利潤實現的方法有： 將銷售收入增加100% 將員工工資減少 25% 將管理費用減少 50% 將物料成本減少 7.1%,13,二、學科作用,4. 決策意識的重要性 生產計劃決策,一星期工作5天, 每天正常工作8小時 一周作業(yè)費用：11000 (直接人工成本與間接費用) 直接人工成本：10/1h (一臺機器需一位作業(yè)人員) 間接費用：人工成本2.5倍,14,二、學科作用,甲產品產量40, 乙產品 80, 丙產品 40 利潤=4066+8089+4070=12560 人員有限如何實現?采取什么薪酬制度? 計件工資制，讓員工自愿加班,決策的科學性？方案 一,15,二、學科作用,甲產品產量 40, 乙產品 80, 丙產品 40 總收入=40173+80233+40170=32360 原料成本=4065+8095+4065=12800 營運費用=11000 總利潤=32360-12800-11000=8560 人員有限如何實現?采取什么薪酬制度? 崗位工資制（定崗定員），讓員工自覺加班,決策的科學性？方案 二,16,二、學科作用,決策的科學性？產能符合計算,乙與丙哪一個產品比較賺錢?,E是瓶頸,17,二、學科作用,方案 三：計時工資，且以單位利潤率高低為決策意識。 乙比較賺錢, 假如80個全部生產 需用E產能2400分鐘，但是E只有2400分鐘可用 因此只能生產80個乙 (2400/30)，而丙無法生產,方案：甲產品 40個，乙產品80個，丙產品0個 總收入=40173+80233+0170=25560 原料=4065+8095+065=10200 ，營運費用=11000 利潤=25560-10200-11000=4360,方案 四：計時工資，但以占用瓶頸資源大小為決策意識。 丙比較賺錢, 優(yōu)先生產40個 需用E產能600(4015)分鐘 剩下1800分鐘, 可生產60個乙 (1800/30),方案：甲產品 40個，乙產品 60個，丙產品 40個 總收入=40173+60233+40170=27700 原材料=4065+6095+406540=10900 ，營運費用=11000 利潤=27700-10900-11000=5800,18,三、學科性質,1. 研究對象 經濟和管理活動中能用“數量關系”描述的 如運營、規(guī)劃與組織管理問題 解決的理論模型和優(yōu)化方法實踐 2. 學科特點 強調科學性和定量分析 強調應用性和實踐性 強調從整體上進行把握,19,四、工作程序,20,五、學科體系,1. 管理問題,21,五、學科體系,2. 學科內容,22,五、學科體系,3. 學科應用 管理既是科學又是藝術 低層管理的科學成分較多，高層管理的藝術成分較多 運營管理需較多管理科學，人力資源管理需較多管理藝術 例行管理需要較多管理科學，例外管理需要較多管理藝術,M: 管理決策問題,MC: 定量解決方法,方案選擇依據,問題導向,技術支持,戰(zhàn)略決策 營銷決策 生產安排 財務分析 人力資源 方案優(yōu)選 ,應用統(tǒng)計 線性規(guī)劃 整數規(guī)劃 目標規(guī)劃 網絡計劃 網絡分析 決策分析 動態(tài)規(guī)劃 ,管理科學：運用合理的分析來改善決策的制定,管理者: 制定決策,23,六、學習要求,1. 學科地位,24,六、學習要求,經濟學,企業(yè)戰(zhàn)略、公司治理,會計學 財務管理,人力資源管理組織行為學,管理 科學 方法 支持,25,六、學習要求,2. 如何學習,重點在結合實際的應用 發(fā)揮自己管理實踐經驗豐富和理論聯系實際的能力 強化結合實際問題建立管理優(yōu)化模型的能力 強化解決問題的方案或模型的解的分析與應用能力 充分借用管理運籌學教學軟件,26,第1 章 線性規(guī)劃,Sub title,內容提要,第一節(jié) 線性規(guī)劃的一般模型 一、線性規(guī)劃的三個要素 二、線性規(guī)劃模型的特征 三、線性規(guī)劃的圖解方法 四、線性規(guī)劃解的可能性 第二節(jié) 線性規(guī)劃的單純形法 一、線性規(guī)劃的標準型式 二、線性規(guī)劃之解的概念 三、單純形法的基本原理,27,一、線性規(guī)劃的三個要素,第一節(jié) 線性規(guī)劃的一般模型,決策變量 決策問題待定的量值 取值要求非負 約束條件 任何管理決策問題都是限定在一定的條件下求解 把各種限制條件表示為一組等式或不等式稱約束條件 約束條件是決策方案可行的保障 約束條件是決策變量的線性函數 目標函數 衡量決策優(yōu)劣的準則，如時間最省、利潤最大、成本最低 目標函數是決策變量的線性函數 有的目標要實現極大，有的則要求極小,28,二、線性規(guī)劃模型的舉例,第一節(jié) 線性規(guī)劃的一般模型,1、生產計劃問題,例. 某廠生產甲乙兩種產品，生產工藝路線為：各自的零部件分別在設備A、B加工，最后都需在設備C上裝配。經測算得到相關數據如表所示。應如何制定生產計劃，使總利潤為最大。 據市場分析，單位甲乙產品的銷售價格分別為73和75元，試確定獲利最大的產品生產計劃。,29,第一節(jié) 線性規(guī)劃的一般模型,(1)決策變量：設x1為甲產品的產量，x2為乙產品的產量。 (2)約束條件：生產受設備能力制約，能力需求不能突破有效供給量。 設備A的約束條件表達為 2 x1 16 同理，設備B的加工能力約束條件表達為 2x2 10 設備C的裝配能力也有限，其約束條件為 3x1+ 4x2 32 (3)目標函數：目標是企業(yè)利潤最大化 max Z= 3x1 +5x2 (4)非負約束：甲乙產品的產量為非負 x1 0， x2 0,綜上的LP模型：,30,二、線性規(guī)劃模型的舉例,第一節(jié) 線性規(guī)劃的一般模型,2、物資運輸問題,例：某產品商有三個供貨源A1、A2、A3，其經銷商有4個（需求市場）B1、B2、B3、B4。已知各廠的產量、各經銷商的銷售量及從Ai 到Bj 的單位運費為Cij。為發(fā)揮集團優(yōu)勢，公司要統(tǒng)一籌劃運銷問題，求運費最小的調運方案。,31,第一節(jié) 線性規(guī)劃的一般模型,(1)決策變量：設從Ai到Bj的運輸量為xij， (2)目標函數：運費最小的目標函數為 minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34 (3)約束條件：產量之和等于銷量之和,故要滿足： 供應平衡條件,x11+x12+x13+x14=50 x21+x22+x23+x24=20 x31+x32+x33+x34 =30,銷售平衡條件,x11+x21+x31=20 x12+x22+x32=30 x13+x23+x33=10 x14+x24+x34=40,非負性約束 xij0 (i=1,2,3；j=1,2,3,4),32,二、線性規(guī)劃模型的舉例,第一節(jié) 線性規(guī)劃的一般模型,3、產品配比問題,例：用濃度45%和92%的硫酸配置100噸濃度80%的硫酸。,決策變量：取45%和92%的硫酸分別為 x1 和 x2 噸 約束條件：,求解二元一次方程組得解,非負約束： x1 0， x2 0,33,第一節(jié) 線性規(guī)劃的一般模型,若有5種不同濃度的硫酸可選(30%,45%,73%,85%,92%)會如何呢？,取這5種硫酸分別為 x1、x2、x3、x4、x5 ，有,有多少種配比方案？ 何為最好？,若5種硫酸價格分別為400, 700, 1400, 1900, 2500元/t，則：,34,三、線性規(guī)劃模型的特征,第一節(jié) 線性規(guī)劃的一般模型,1、模型隱含假定,（1）線性化假定 函數關系式f(x)= c1x1+c2x2+ +cnxn，稱線性函數。 建模技巧：將非線性的函數進行分段線性化。 （2）同比例假定 決策變量變化引起目標函數和約束方程的改變量比例。 （3）可加性假定 決策變量對目標函數和約束方程的影響是獨立于其他變量的。 目標函數值是決策變量對目標函數貢獻的總和。 （4）連續(xù)性假定 決策變量取值連續(xù)。 （5）確定性假定 所有參數都是確定的，不包含隨機因素。,35,三、線性規(guī)劃模型的特征,第一節(jié) 線性規(guī)劃的一般模型,2、一般數學模型,用一組非負決策變量表示的一個決策問題； 存在一組等式或不等式的線性約束條件； 有一個希望達到的目標，可表示成決策變量的極值線性函數。,36,四、線性規(guī)劃的圖解方法,第一節(jié) 線性規(guī)劃的一般模型,1、線性規(guī)劃的可行域,可行域：滿足所有約束條件的解的集合， 即所有約束條件共同圍城的區(qū)域。,maxZ= 3x1 +5 x2 2 x1 16 2x2 10 3x1 +4 x2 32 x1 0, x2 0,S.t.,37,四、線性規(guī)劃的圖解方法,第一節(jié) 線性規(guī)劃的一般模型,2、線性規(guī)劃的最優(yōu)解,目標函數 Z= 3x1 +5 x2 代表以 Z 為參數的一族平行線。,38,四、線性規(guī)劃的圖解方法,第一節(jié) 線性規(guī)劃的一般模型,3、線性規(guī)劃解的特性,由線性不等式組成的可行域是凸多邊形(凸多邊形是凸集) 凸集定義：集合內部任意兩點連線上的點都屬于這個集合,可行域有有限個頂點。 目標函數最優(yōu)值一定在可行域的邊界達到，而不可能在其區(qū)域的內部。,39,五、線性規(guī)劃解的可能性,第一節(jié) 線性規(guī)劃的一般模型,1、唯一最優(yōu)解：只有一個最優(yōu)點,2、多重最優(yōu)解：無窮多個最優(yōu)解,當市場價格下降到74元，其數學模型變?yōu)?40,五、線性規(guī)劃解的可能性,第一節(jié) 線性規(guī)劃的一般模型,3、無界解：可行域無界，目標值無限增大 (缺乏必要約束),41,五、線性規(guī)劃解的可能性,第一節(jié) 線性規(guī)劃的一般模型,4、沒有可行解：線性規(guī)劃問題的可行域是空集 (約束條件相互矛盾),42,一、線性規(guī)劃的標準型式,第二節(jié) 線性規(guī)劃的一般模型,1、標準型表達方式,(1)代數式,(2)向量式,(3)矩陣式,A：技術系數矩陣，簡稱系數矩陣； B：可用的資源量，稱資源向量； C：決策變量對目標的貢獻，稱價值向量； X：決策向量。,43,一、線性規(guī)劃的標準型式,第二節(jié) 線性規(guī)劃的一般模型,2、標準型轉換方法,(1)如果極小化原問題minZ=CX，則令 Z=-Z，轉為求 maxZ=-CX (2)若某個bi0，則以1乘該約束兩端，使之滿足非負性的要求。 (3)對于型約束，則在左端加上一個非負松弛變量，使其為等式。 (4)對于型約束，則在左端減去一個非負剩余變量，使其為等式。 (5)若某決策變量xk無非負約束，令xk=xk-x“k ，(xk0,x“k 0) 。,44,二、線性規(guī)劃之解的概念,第二節(jié) 線性規(guī)劃的一般模型,基矩陣：一個非奇異的子矩陣（線性無關）。 矩陣A中任意m列的線性無關子矩陣B ，稱為一個基。 組成基B的列為基向量，用Pj表示(j=1,2,n) 。 基變量： 與基向量Pj 相對應的m個變量xj稱為基變量 其余的n - m個變量為非基變量,1、線性規(guī)劃解之關系,基解：令所有非基變量等于零，得出基變量的唯一解 。,基變量是x3, x4, x5 非基變量是x1, x2 令非基變量x1=x2=0，得到一個基解 x3=16，x4=10， x5=32,45,二、線性規(guī)劃之解的概念,第二節(jié) 線性規(guī)劃的一般模型,1、線性規(guī)劃解之關系,可行解：滿足約束條件AX=b, X0的解。 可行基：可行解對應的基矩陣。 基可行解：滿足非負性約束的基解稱為基可行解。 最優(yōu)解：使目標函數最優(yōu)的可行解，稱為最優(yōu)解。 最優(yōu)基：最優(yōu)解對應的基矩陣，稱為最優(yōu)基。,46,二、線性規(guī)劃之解的概念,第二節(jié) 線性規(guī)劃的一般模型,2、線性規(guī)劃基本原理,定理1. 若線性規(guī)劃問題存在可行域，則其可行域一定是凸集。 定理2. 線性規(guī)劃問題的基可行解對應可行域的頂點。 定理3. 若可行域有界，線性規(guī)劃的目標函數一定可以在可行域的頂點上達到最優(yōu)。 定理4. 線性規(guī)劃如果有可行解，則一定有基可行解；如果有最優(yōu)解，則一定有基可行解是最優(yōu)解。,47,二、線性規(guī)劃之解的概念,第二節(jié) 線性規(guī)劃的一般模型,3、線性規(guī)劃解題思路,先找到一個初始基可行解，也就是找到一個初始可行基，想辦法判斷這個基可行解是不是最優(yōu)解。 如果是最優(yōu)解，就得到這個線性規(guī)劃問題的最優(yōu)解； 如果判斷出不是最優(yōu)解，就想法由這個可行基按一定規(guī)則變化到下一個可行基，然后再判斷新得到的基可行解是不是最優(yōu)解； 如果還不是，再接著進行下一個可行基變化，直到得到最優(yōu)解。,48,三、單純形法的基本原理,第二節(jié) 線性規(guī)劃的一般模型,maxZ=3x1 +5 x2 +0x3 +0x4+0x5 =0 2x1 + x3 =16 2x2 + x4 =10 3x1 +4 x2 + x5 =32,49,三、單純形法的基本原理,第二節(jié) 線性規(guī)劃的一般模型,最優(yōu)解 :X*=(4,5,8,0,0)T，Z*=37,50,三、單純形法的基本原理,第二節(jié) 線性規(guī)劃的一般模型,單純形的管理啟示,2x1=16,X0=(0,0,10,10,32)T,X1=(0,5,10,0,12)T,X1=(4,5,8,0,0)T,企業(yè)管理過程也是如此，把現有方案作為初始方案，找到最急需要改進的某個問題和改進方向，一次做好某個主要問題的解決與改進；一次只解決和改進一個問題的難度最?。唤鉀Q之后，再尋求可以改進的其它地方，再次改進，不斷地追求完美。,51,第2 章 線性規(guī)劃討論,Sub title,內容提要,第一節(jié) 目標函數的描述技巧 計件工資 崗位工資 計時工資 第二節(jié) 線性規(guī)劃的適用層次 第三節(jié) 線性規(guī)劃的典型案例 第四節(jié) 線性規(guī)劃靈敏度分析 價值系數的變動分析 資源數量的變動分析,52,計件工資體系，目標是企業(yè)利潤最大化：,第一節(jié) 目標函數的描述技巧,一、計件工資,計件工資制薪酬體系下，工作時間不會完全受每天8小時工作時間約束，但有產品市場需求約束，如下：,經Lindo軟件求解，得到最優(yōu)解為Z=12560，產品甲x1=40，產品乙x2=80，產品丙x3=40。,53,第一節(jié) 目標函數的描述技巧,二、崗位工資,崗位工資制薪酬體系，以計時工資制為基礎，實行定崗定員。 總收入=173x1+233x2+170x3， 原料成本=65x1+95x2+65x3，營運費用=11000， 則目標函數為maxZ= 108x1+138x2+105x3-11000 崗位工資制薪酬體系下，工作時間也不會完全受每天8小時工作時間約束，但有產品市場需求約束，如下：,經Lindo軟件求解，得到最優(yōu)解為Z=8560,x1=40,x2=80,x3=40。,54,第一節(jié) 目標函數的描述技巧,三、計時工資,目標函數為,經Lindo軟件求解，得到最優(yōu)解為Z=5800,x1=40,x2=60,x3=40。,市場需求約束,設備能力約束,55,第二節(jié) 線性規(guī)劃的適用層次,計劃鏈的層次,產值計劃 或 利潤計劃 絕對數量 或 增長幅度 期限:年度 單位:萬元,大類產品銷售收入或臺套 產品品種和數量如何確定 期限:年度 單位:萬臺,具體產品在具體 時段的出產計劃 合同訂單和預測 轉換為生產任務,將產品出產計劃轉換成物料需求表,大類產品年度生產計劃 確定產品的品種和數量 期限:年度 單位:萬臺,56,第三節(jié) 線性規(guī)劃的典型案例,配送中心選擇,例：某企業(yè)存在兩個供貨源（產地），已知原有供貨源每月的供貨能力是5萬臺產品，新增供貨源的生產能力可以滿足產品的需求，且兩個貨源的價格相同。 有三個區(qū)域目標市場（銷地或銷售商），各銷地每月的市場需求量為5萬臺、10萬臺、5萬臺。 在分銷渠道中，擬定在2個地點中選址設立分銷中心，執(zhí)行產品的轉運任務。各地之間的單位運輸物流成本（由距離和運輸方式決定）,57,第三節(jié) 線性規(guī)劃的典型案例,決策變量：設從供貨源到分銷中心的運輸量為 ，從分銷中心到需求市場的運輸量為 。選址規(guī)劃在于二者的實際取值。 如果 ，則不設置分銷中心； 反之，則設置,其規(guī)模為 如果 ，則不設置分銷中心； 反之，則設置，其規(guī)模為 目標函數：各條路段上的實際運輸量乘以物流運輸的單位費用之總和最小，即 存在供應能力約束、市場需求約束、配送中轉約束，如下：,58,第三節(jié) 線性規(guī)劃的典型案例,供應能力平衡約束： 市場需求平衡約束 配送中心不存留產品 所有變量大于等于零,59,第四節(jié) 線性規(guī)劃靈敏度分析,一、靈敏度分析的必要性,線性規(guī)劃研究的是一定條件下的最優(yōu)化問題 資源環(huán)境和技術條件是可變的 基礎數據往往是測算估計的數值 靈敏度分析的概念 靈敏度分析又稱敏感性分析或優(yōu)化后分析 研究基礎數據發(fā)生波動后對最優(yōu)解的影響 最優(yōu)解對數據變化的敏感程度 在多大的范圍內波動才不影響最優(yōu)基 靈敏度分析解決的問題： 參數在什么范圍變化而最優(yōu)基不變 已知參數的變化范圍，考察最優(yōu)解(最優(yōu)基)是否改變,60,第四節(jié) 線性規(guī)劃靈敏度分析,一、價值系數的變動分析,非基變量Cj的變化范圍 非基變量Cj變化，只影響它自己的檢驗數,參數Cj的變化范圍：價值系數Cj變化影響檢驗數,61,第四節(jié) 線性規(guī)劃靈敏度分析,一、價值系數的變動分析,基變量CBl的變化范圍,62,第四節(jié) 線性規(guī)劃靈敏度分析,二、右端常量的變動分析,參數bi的變化范圍 第r個約束的右端項為br，增量br，其它數據不變。新的基解為,只要XB0 ，則可保持最優(yōu)基不變。,63,第3 章 對偶規(guī)劃,Sub title,內容提要,第一節(jié) 對偶規(guī)劃的數學模型 對偶問題的提出 對偶規(guī)劃的性質 第二節(jié) 對偶規(guī)劃的經濟解釋 影子價值的內涵 影子價值的應用 第三節(jié) 資源定價的決策案例,64,第一節(jié) 對偶規(guī)劃的數學模型,一、對偶問題的提出,若例1中該廠的產品平銷，現有另一企業(yè)想租賃其設備。廠方為了在談判時心中有數，需掌握設備臺時費用的最低價碼，以便衡量對方出價，對出租與否做出抉擇。 在這個問題上廠長面臨著兩種選擇：自行生產或出租設備。首先要弄清兩個問題： 合理安排生產能取得多大利潤? 為保持利潤水平不降低，資源轉讓的最低價格是多少？ 問題 的最優(yōu)解：x1=4，x2=5，Z*=37。,65,第一節(jié) 對偶規(guī)劃的數學模型,一、對偶問題的提出,出讓定價,假設出讓A、B、C設備所得利潤分別為y1、y2、y3 原本用于生產甲產品的設備臺時，如若出讓，不應低于自行生產帶來的利潤，否則寧愿自己生產。于是有 2y1+0y2+3y3 3 同理，對乙產品而言，則有 0y1+2y2+4y3 5 設備臺時出讓的收益（希望出讓的收益最少值） min 16y1+10y2+32y3 顯然還有 y1，y2，y30,66,第一節(jié) 對偶規(guī)劃的數學模型,一、對偶問題的提出,例1的對偶問題的數學模型,對偶問題的最優(yōu)解： y1=0，y2=1/2，y3=1，W* =37 兩個問題的目標函數值相等并非偶然 前者稱為線性規(guī)劃原問題，則后者為對偶問題，反之亦然。 對偶問題的最優(yōu)解對應于原問題最優(yōu)單純型法表中，初始基變量的檢驗數的負值。,67,第一節(jié) 對偶規(guī)劃的數學模型,二、對偶規(guī)劃的性質,1、對稱性定理 對偶問題的對偶問題是原問題。 根據對偶規(guī)劃，很容易寫出對偶問題的對偶問題模型。 2、 最優(yōu)性定理 設 ， 分別為原問題和對偶問題的可行解，且 則 ， 分別為各自的最優(yōu)解。 3. 對偶性定理 若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解，而且 兩者的目標函數值相等。 4. 互補松弛性 最優(yōu)解的充分必要條件是 ，,68,第二節(jié) 對偶規(guī)劃的經濟解釋,一、影子價值的內涵,左邊是資源bi每增加一個單位對目標函數Z的貢獻； 對偶變量 yi在經濟上表示原問題第i種資源的邊際價值。 對偶變量的值 yi*表示第i種資源的邊際價值，稱為影子價值。 若原問題價值系數Cj表示單位產值，則yi 稱為影子價格。 若原問題價值系數Cj表示單位利潤，則yi 稱為影子利潤。 影子價格=資源成本+影子利潤,69,第二節(jié) 對偶規(guī)劃的經濟解釋,一、影子價值的內涵,影子價格不是資源的實際價格，反映了資源配置結構， 其它數據固定，某資源增加一單位導致目標函數的增量。 對資源i總存量的評估：購進 or 出讓 對資源i當前分配量的評估：增加 or 減少 第一，影子利潤說明增加哪種資源對經濟效益最有利 第二，影子價格告知以怎樣的代價去取得緊缺資源 第三，影子價格是機會成本，提示資源出租/轉讓的基價 第四，利用影子價格分析新品的資源效果：定價決策 第五，利用影子價格分析現有產品價格變動的資源緊性 第六，可以幫助分析工藝改變后對資源節(jié)約的收益 第七，可以預知哪些資源是稀缺資源而哪些資源不稀缺,70,第三節(jié) 資源定價的決策方案,例：某廠生產甲乙產品，（1）如何安排每周的利潤為最大? （2）如果企業(yè)可以不生產，那資源出讓如何定價？,一、最優(yōu)生產決策,71,第三節(jié) 資源定價的決策方案,二、資源獲利決策,如果決策者考慮自己不生產甲乙兩種產品，而把原擬用于生產這兩種產品的原材料、設備工時、電量資源全部出售給外單位，或者做代加工，則應如何確定這三種資源的價格。,設原材料的單位出讓獲利為y1，設備工時的單位出讓獲利為y3，電量的單位出讓獲利為y2 。 出讓決策的線性規(guī)劃模型：,72,第4 章 整數規(guī)劃,Sub title,內容提要,第一節(jié) 整數規(guī)劃問題 純整數規(guī)劃 0-1規(guī)劃 混合整數規(guī)劃 第二節(jié) 整數規(guī)劃求解 分枝定界法 第三節(jié) 整數規(guī)劃應用,73,第一節(jié) 整數規(guī)劃問題,線性規(guī)劃的決策變量取值可以是任意非負實數，但許多實際問題中，只有當決策變量的取值為整數時才有意義 例如，產品的件數、機器的臺數、裝貨的車數、完成工作的人數等，分數或小數解顯然是不合理的。 要求全部或部分決策變量的取值為整數的線性規(guī)劃問題，稱為整數規(guī)劃(Integer Programming)。 全部決策變量的取值都為整數，則稱為全整數規(guī)劃(All IP) 僅要求部分決策變量的取值為整數，則稱為混合整數規(guī)劃(Mixed IP) 要求決策變量只取0或1值，則稱0-1規(guī)劃(0-1 Programming),74,第一節(jié) 整數規(guī)劃問題,一、純整數規(guī)劃,例：某企業(yè)利用材料和設備生產甲乙產品，其工藝消耗系數和單臺產品的獲利能力如下表所示：,問如何安排甲、乙兩產品的產量，使利潤為最大。,解：設x1為甲產品的臺數，x2為乙產品的臺數。 maxZ= 6x1 +5 x2 2x1 + x2 9 5x1 +7 x2 35 x1, x2 0 x1, x2 取整數,75,第一節(jié) 整數規(guī)劃問題,二、0-1規(guī)劃,登山隊員可攜帶最大重量為25公斤。問都帶哪些物品的重要性最大。,解：對于每一種物品無非有兩種狀態(tài)，帶或者不帶，不妨設,0-1規(guī)劃的模型：,76,第一節(jié) 整數規(guī)劃問題,三、混合整數規(guī)劃,例：某產品有n個區(qū)域市場，各區(qū)域市場的需求量為 bj噸/月；現擬在m個地點中選址建生產廠，一個地方最多只能建一家工廠；若選 i地建廠，生產能力為 ai噸/月，其運營固定費用為F元/月；已知址i至j區(qū)域市場的運價為cij元/噸。如何選址和安排調運，可使總費用最??？,解：選址建廠與否是個0-1型決策變量， 假設 yi =1，選擇第 i 址建廠， yi=0，不選擇第 i 址建廠； 計劃從 i 址至區(qū)域市場 j 的運輸 運量xij為實數型決策變量。,77,第二節(jié) 整數規(guī)劃求解,一、舍入化整法,為了滿足整數解的要求，自然想到“舍入”或“截尾”處理，以得到與最優(yōu)解相近的整數解。 這樣做除少數情況外，一般不可行，因為化整后的解有可能超出了可行域，成為非可行解；或者雖是可行解，卻不是最優(yōu)解。,不考慮整數約束則是一個LP問題,稱為原整數規(guī)劃的松弛問題 對于例1的數學模型，不考慮整數約束的最優(yōu)解： x1 *=28/9， x2 * =25/9，Z * =293/9,舍入化整 x1 =3， x2 =3，Z =33，不滿足約束條件5x1 +7 x2 35，非可行解； x1 =3， x2 =2，Z =28，滿足約束條件，是可行解，但不是最優(yōu)解； x1 =4， x2 =1，Z =29，滿足約束條件，才是最優(yōu)解。,78,第二節(jié) 整數規(guī)劃求解,二、窮舉整數法,對于決策變量少，可行的整數解又較少時，這種窮舉法有時是可行的，并且也是有效的。 但對于大型的整數規(guī)劃問題，可行的整數解數量很多，用窮舉法求解是不可能的。例如，指派問題 。, (3,3),79,第二節(jié) 整數規(guī)劃求解,三、分支定界法,不考慮整數限制，先求出相應線性規(guī)劃 的最優(yōu)解， 若求得的最優(yōu)解符合整數要求，則是原IP的最優(yōu)解； 若不滿足整數條件，則任選一個不滿足整數條件的變量來構造新的約束，在原可行域中剔除部分非整數解。 依次在縮小的可行域中求解新構造的線性規(guī)劃的最優(yōu)解，直到獲得原整數規(guī)劃的最優(yōu)解。 定界的含義： IP是在相應的LP基礎上增加整數約束 IP的最優(yōu)解不會優(yōu)于相應LP的最優(yōu)解 對MaxZ，相應LP的Z*是原IP的上界,80,第二節(jié) 整數規(guī)劃求解,三、分支定界法,x13,x1 4,x22,x2 3,x12,x1 3,x23,x2 4,81,第三節(jié) 整數規(guī)劃應用,一、生產基地規(guī)劃,例：某公司擬建設A、B兩種類型的生產基地若干個，兩種類型的生產基地每個占地面積，所需經費，建成后生產能力及現有資源情況如下表所示。問A、B類型基地各建設多少個，可使總生產能力最大？,解：設A、B兩類基地各建設 x1,x2 個，則其模型為：,82,第三節(jié) 整數規(guī)劃應用,二、人員安排規(guī)劃,某服務部門各時段(每2小時為一時段)需要的服務人數如表：,解：設第j 時段開始時上班的服務員人數為xj 第 j 時段來上班的服務員將在第j+3 時段結束時下班，故決策變量有x1,x2,x3,x4,x5 。,按規(guī)定，服務員連續(xù)工作8小時(4個時段)為一班。請安排服務員的工作時間，使服務員總數最少.,83,第三節(jié) 整數規(guī)劃應用,三、項目投資選擇,有600萬元投資5個項目，收益如表，求利潤最大的方案？,84,第三節(jié) 整數規(guī)劃應用,四、互斥約束問題,例如關于煤資源的限制，其約束條件為： 企業(yè)也可以考慮采用天然氣進行加熱處理： 這兩個條件是互相排斥的。引入01變量y，令 互斥問題可由下述的條件來代替，其中M是充分大的數。,85,第三節(jié) 整數規(guī)劃應用,五、租賃生產問題,服裝公司租用生產線擬生產T恤、襯衫和褲子。 每年可用勞動力8200h，布料8800m2。,假設：yj=1，要租用生產線j yi=0，不租用生產線j 第j 種服裝生產量xj,86,第三節(jié) 整數規(guī)劃應用,六、任務指派問題,甲乙丙丁四個人，ABCD四項任務，如何指派總時間最短？,解： 引入0-1變量xij ， xij =1：任務j指派人員i去完成 xij =0：任務j不派人員i去完成,一項任務只由一個人完成 一人只能完成一項任務,87,第三節(jié) 整數規(guī)劃應用,七、設施選址問題,擬定在2個地點中選址設立分銷中心，執(zhí)行產品的倉儲和轉運，一個分銷中心擬定設立一個倉庫W1、W2。 若設立倉庫W1，建設成本為10萬元，最大庫容為20萬臺，單位產品的月庫存成本為2元； 若設立倉庫W2建造成本為20萬元，最大庫容為25萬臺，單位產品的月庫存成本為3元。 如何選址和安排調運，建造費用+運輸費用+倉儲費用為最??？,解：設從供貨源Si到分銷中心Wj的運輸量為xij，從分銷中心 到需求市場Rk的運輸量為yjk。倉庫選址決策引入0-1變量wj ：,88,第三節(jié) 整數規(guī)劃應用,七、設施選址問題,供應能力平衡約束： 市場需求平衡約束： 倉儲能力限制約束： 分銷中心不存留產品： 所有變量大于等于零：,89,第5 章 目標規(guī)劃,Sub title,內容提要,第一節(jié) 多目標規(guī)劃問題 第二節(jié) 目標規(guī)劃數學模型 目標的期望值 正負偏差變量 目標達成函數 目標優(yōu)先級別 第三節(jié) 目標規(guī)劃的圖解法 第四節(jié) 目標規(guī)劃單純形法 第五節(jié) 目標規(guī)劃應用案例,90,第一節(jié) 多目標規(guī)劃問題,一、線性規(guī)劃的局限性,線性規(guī)劃的局限性 只能解決一組線性約束條件下，某一目標而且只能是一個目標的最大或最小值的問題 實際決策中，衡量方案優(yōu)劣考慮多個目標 生產計劃決策，通?？紤]產值、利潤、滿足市場需求等 生產布局決策，考慮運費、投資、供應、市場、污染等 這些目標中，有主要的，也有次要的；有最大的，有最小的；有定量的，有定性的；有互相補充的，有互相對立的，LP則無能為力 目標規(guī)劃（Goal Programming） 多目標線性規(guī)劃 含有多個優(yōu)化目標的線性規(guī)劃,91,第一節(jié) 多目標規(guī)劃問題,二、多目標規(guī)劃的提出,例：甲乙產品的最優(yōu)生產計劃。,解：線規(guī)劃模型： maxZ=3x1+5x2 2x1 16 2x2 10 3x1+4x2 32 x1，x2 0,根據市場需求/合同規(guī)定： 希望盡量擴大甲產品 減少乙產品產量。 又增加二個目標：,maxZ1=3x1+5x2 maxZ2=x1 minZ3=x2 2x1 16 2x2 10 3x1+4x2 32 x1，x2 0,這些目標之間相互矛盾，一般的線性規(guī)劃方法不能求解,92,第一節(jié) 多目標規(guī)劃問題,三、多目標規(guī)劃的解法,加權系數法： 為每一目標賦一權數，把多目標轉化成單目標。 但權系數難以科學確定。 優(yōu)先等級法： 各目標按重要性歸不同優(yōu)先級而化為單目標。 有效解法： 尋求能照顧到各目標而使決策者感到滿意的解。 但可行域大時難以列出所有有效解的組合。 目標規(guī)劃法： 對每一個目標函數引入正的或負的偏差變量； 引入目標的優(yōu)先等級和加權系數。,93,第二節(jié) 目標規(guī)劃的數學模型,一、目標期望值,每一個目標希望達到的期望值(或目標值、理想值)。 根據歷史資料、市場需求或上級部門的布置等來確定。,二、偏差變量,目標約束,目標的實際值和期望值之間可能存在正的或負的偏差。 正偏差變量dk+ 表示第k個目標超過期望值的數值； 負偏差變量dk- 表示第k個目標未達到期望值的數值。 同一目標的dk+ 和dk- 中至少有一個必須為零。,引入正負偏差變量，對各個目標建立目標約束(軟約束),94,第二節(jié) 目標規(guī)劃的數學模型,上例中要求： 目標一是利潤最大，擬定利潤目標是30； 目標二是減少乙產品產量但希望不低于4件； 目標三是甲產品產量希望不少于6件 ； 對各目標引入正、負偏差變量： 3x1+5x2 +d1- d1+ = 30 x2 +d2- - d2+ =4 x1 +d3 -d3+ = 6,95,第二節(jié) 目標規(guī)劃的數學模型,三、目標達成函數,目標達成函數：偏差變量之和為最小值。 若要求盡可能達到規(guī)定的目標值 正負偏差變量dk+ , dk- 都盡可能小，即minSk=dk+dk- 若希望盡可能不低于期望值(允許超過) 負偏差變量dk- 盡可能小,不關心超出量dk+ ：minSk= dk- 若允許某個目標低于期望值，但希望不超過 正偏差變量dk+盡可能小,不關心低于量dk- ：minSk= dk+,四、優(yōu)先等級權數,目標重要度不同，用優(yōu)先等級因子Pk 表示第k等級目標。 優(yōu)先等級因子Pk 是正的常數， Pk Pk+1 。 同一優(yōu)先等級下目標的相對重要性賦以不同權數w。,96,第二節(jié) 目標規(guī)劃的數學模型,例如 P1 級目標實現利潤至少30元； P2級目標是甲乙產品的產量 假設：乙產品產量不少于4件比甲產品產量不少于6件更重要，取其權重為2 minG= P1 d1- + P2(2d2- + d3+ ) 3x1+5x2 +d1- d1+ = 30 x2 +d2- - d2+ = 4 x1 + d3- - d3+ = 6 x1 , x2 ,dk- , dk+ 0(k=1,2,3),97,第三節(jié) 目標規(guī)劃的圖解法,目標規(guī)劃的圖解法 首先，按照絕對約束畫出可行域， 其次，不考慮正負偏差變量，畫出目標約束的邊界線， 最后。按優(yōu)先級別和權重依次分析各級目標。,F,G,H,x1=5, x2=4,98,第四節(jié) 目標規(guī)劃的應用案例,一、無窮多滿意解,解：設x1,x2表示A、B產品的產量。兩個等級的目標： P1：充分利用電量限額，正負偏差之和為最小 目標達成函數 目標約束條件 P2 ：利潤額希望不能低于100元，負偏差最小 目標達成函數 目標約束條件,計劃生產兩種產品，首先要充分利用設備工時而不加班；然后考慮利潤不低于100元。問應如何制定產品A、B的產量。,99,第四節(jié) 目標規(guī)劃的應用案例,一、無窮多滿意解,由于材料供應限量為8單位，所以有系統(tǒng)約束條件，如下,該問題的目標規(guī)劃模型如下，圖解法求解如圖,C,G,100,第四節(jié) 目標規(guī)劃的應用案例,二、加班時間問題,例：某音像店有5名全職售貨員和4名兼職售貨員，全職售貨員每月工作160小時，兼職售貨員每月工作80小時。根據記錄，全職每小時銷售CD25張，平均每小時工資15元，加班工資每小時22.5元。兼職售貨員每小時銷售CD10張，平均工資每小時10元，加班工資每小時10元?，F在預測下月CD銷售量為27500張，商店每周開門營業(yè)6天，所以可能要加班。每出售一張CD盈利1.5元。 商店經理認為，保持穩(wěn)定的就業(yè)水平加上必要的加班，比不加班就業(yè)水平要好，但全職銷售員如果加班過多，就會因為疲勞過度而造成效率下降，因此不允許每月加班超過100小時，建立相應的目標規(guī)劃模型。,101,第四節(jié) 目標規(guī)劃的應用案例,二、加班時間問題,首先，確定目標約束的優(yōu)先級。如下： P1：下月的CD銷售量達到27500張； P2：全職售貨員加班時間不超過100小時； P3：保持全體售貨員充分就業(yè)，對全職的要比兼職的加倍優(yōu)先考慮； P4：盡量減少加班時間，對兩種售貨員區(qū)別對待，權重由他們對利潤的貢獻而定。 其次，建立目標約束函數 （1）銷售目標約束，設全體全職售貨員下月的工作時間x1，全體兼職售貨員下月的工作時間 x2；達不到銷售目標的偏差d1-，超過銷售目標的偏差 d1+。,102,第四節(jié) 目標規(guī)劃的應用案例,二、加班時間問題,（2）正常工作時間約束。設全體全職售貨員下月的停工時間d2-，加班時間d2+ ；全體兼職售貨員下月的停工時間d3-，加班時間d3+。 （3）加班時間的限制。設全體全職售貨員下月的加班不足100小時的偏差d4-，加班超過100小時的偏差 d4+ 。 兩類售貨員區(qū)別對待，權重比d2+:d3+ =1:3，另一加班目標約束為,103,第四節(jié) 目標規(guī)劃的應用案例,二、加班時間問題,第三，按目標的優(yōu)先級，寫出相應的目標規(guī)劃模型：,運用LINGO軟件求解得 x1=900,x2=500，下月共銷售CD盤27500張，獲利275001.5-80015-10022.5-50010=22000。,104,第四節(jié) 目標規(guī)劃的應用案例,三、目標管理方案,例：某公司準備生產甲、乙產品，據市場調查：甲產品的最大市場需求3臺，乙產品的最大市場需求2臺。,在滿足現有電力資源嚴格供給約束的前提下，該廠長考慮兩個目標：一是總利潤不低于3600元；二是充分利用設備臺時，但盡量少加班。問應如何制定產品甲、乙的產量，試建立其目標規(guī)劃的數學模型。,105,第四節(jié) 目標規(guī)劃的應用案例,三、目標管理方案,1. 利潤期望優(yōu)先 目標規(guī)劃數學模型：,運用圖解法進行求解,F,E,G,x1 =8, x2 = 3,106,第四節(jié) 目標規(guī)劃的應用案例,1. 利潤期望優(yōu)先,滿意解：x1 =8, x2 = 3 設備能力：需求：308+60 3=420，實際：360 實現目標P1和P2，降低甲乙產品的設備消耗:降低率(420-360)/360=17%， 甲產品的設備消耗降為30 (1-17%)=25, 乙產品的設備消耗降為60 (1-17%)=50。,107,第四節(jié) 目標規(guī)劃的應用案例,三、目標管理方案,2. 設備工時優(yōu)先 目標規(guī)劃數學模型：,運用圖解法進行求解,F,E,G,x1 =8, x2 = 2,108,第四節(jié) 目標規(guī)劃的應用案例,2. 設備工時優(yōu)先,滿意解：x1 =8, x2 = 2 利潤總額3008+4002=3200，目標：3600 不能提價，就必須降低成本以增加利潤，利潤增長率為12.5% 甲產品的成本需要降為1200-300(1+12.5%)=862.5元/臺，降低幅度4.2% 乙產品的成本需要降為1800-400(1+12.5%)=1350元/臺，降低幅度3.6%,109,第7 章 網絡分析,Sub title,內容提要,第一節(jié) 圖論的概念 第二節(jié) 最小樹問題 第三節(jié) 最短路問題 第四節(jié) 網絡最大流 第五節(jié) 最小費用流,110,18世紀，哥尼斯堡城中有一條普雷格爾河，河上有七座橋將河中的兩個小島與河岸連接起來。人們提出了這樣的問題：一個散步者能否從某地出發(fā)，走遍七橋且每座橋恰好經過一次，最后回到原地？,第7 章 網絡分析,陸地A,陸地B,島D,島C,A ,D , B, C,1736年瑞士數學家歐拉將兩岸和小島抽象為四個點，將橋抽象為七條邊，此問題歸結為一筆畫問題。,111,第一節(jié) 圖論的概念,一、圖的內涵,1、圖的定義, v1, v4,v2, v3,e1,e2,e3,e4,e5,e6, v1, v4,v2,v3 ,e1,e2,e3,e4,e5,e6, v1, v2, v3, v4,e1,e2,e3,e4,e5,e6,圖論的圖與一般幾何圖形或代數函數圖形是完全不同的 圖論中的圖:由一些點和連接點的線所組成的“圖形” 點和線的位置是任意的 線的曲直、長短與實際無關，代表的只是點與點之間的相互關系 例：表示蘇州v1 、杭州v2 、上海v3 、南京v4倉儲網點之間的物流運輸線路關系,112,第一節(jié) 圖論的概念,一、圖