1、1高等運籌學主講 劉春山2高等與初等運籌的差別線性與非線性單目標與多目標決策與對策方法的運用與方法的創新3復習一下運籌學是作什么的4現實世界現實世界抽象模型輸出模型用戶輸入結論與建議實施5案例一汽車保險延展計劃由保險公司為顧客提供了三種 付款方案：方案一：月初一次性福清全年保險費1500美元方案二：分三期等額付款，第一月月初首付，以后每隔兩月付一次，每次付款加收服務費3.5美元方案三：月付。第一月月初首付兩個月保險費，以后每月月初提前交付，一年付完，最后十次由銀行劃付（無其他成本），每次付款加收服務費，服務費為每次付款額的3%假定銀行月息0.5%，（年存款利息率約為6%） 6 如何建立該問題有

2、效的模型（仿真模型），模型參數化，利率在決策中的敏感性，求解參數：利率，保險費（在電子表格中的體現）7案例二開采銅礦的決策開采銅礦的決策 某省根據初步勘探，發現一個銅礦，該某省根據初步勘探，發現一個銅礦，該礦含銅量，按估計可能高含量的概率為礦含銅量，按估計可能高含量的概率為0.20.2，中含量的概率為中含量的概率為0.30.3，低含量的概率為，低含量的概率為0.50.5。如果決定開采，在高含量的情況下可盈利如果決定開采，在高含量的情況下可盈利400400萬元萬元, ,中等含量下可盈利中等含量下可盈利100100萬元萬元, ,低含低含量下將虧損量下將虧損160160萬元萬元. .如果不開采如果不

3、開采, ,把準備開把準備開采的資金用于辦工廠將盈利采的資金用于辦工廠將盈利3535萬元，現在萬元，現在問是否應該開采？問是否應該開采？8 分析：本問題模型可以用決策樹解決。計算各決策的數學期望值。912400100-16035開采開采不開采不開采30S1:p1= 0.2S2:p2= 0.3S3:p3= 0.5決策點，狀態點的表示決策點，狀態點的表示10 開采的數學期望值為開采的數學期望值為30,所以選擇不開采所以選擇不開采，考慮到考慮到“開采開采”的期望值的期望值3030與與“不開采不開采”的的3535相比相差不太大。因而省政府計劃部門認為可相比相差不太大。因而省政府計劃部門認為可以對該礦作進

4、一步的勘探。進一步的勘探要耗以對該礦作進一步的勘探。進一步的勘探要耗費費4040萬元的勘探費用，其結果可能區分礦區地萬元的勘探費用，其結果可能區分礦區地質結構是否礦物化的情況，在礦物化的情況下，質結構是否礦物化的情況，在礦物化的情況下，銅礦含銅高含量的概率提高到銅礦含銅高含量的概率提高到0.50.5，中含量和，中含量和低含量的概率為低含量的概率為0.30.3和和0.20.2，如果地質結構非礦，如果地質結構非礦物化則含銅量高、中、低的概率分別為物化則含銅量高、中、低的概率分別為0.050.05、0.10.1和和0.850.85。據專家估計該礦區地質結構礦物。據專家估計該礦區地質結構礦物化和非礦物

5、化的概率分別為化和非礦物化的概率分別為0.60.6和和0.40.4。1113624578-40A1不勘探不勘探35A2 進一步勘探進一步勘探礦物化礦物化0.6非礦物化非礦物化0.4132.819835開采開采不開采不開采400100-160S2:(0.3)S3:(0.5)35開采開采不開采不開采198S1:(0.5)S2:(0.3)S3:(0.2)400100-16035開采開采不開采不開采-106S1:(0.05)S2:(0.1)S3:(0.85)400100-1604003512 用逆推的方法確定最優策略為：進一步進行勘探，用逆推的方法確定最優策略為：進一步進行勘探，如果勘探結果是礦物化則

6、決定開采，如非礦物如果勘探結果是礦物化則決定開采，如非礦物化則不開采。這里，化則不開采。這里，“進一步進行勘探進一步進行勘探”只是只是為了獲得為了獲得“是否礦物化是否礦物化”這個信息。這個信息這個信息。這個信息對我們的決策有多大的價值呢？當我們沒有獲對我們的決策有多大的價值呢？當我們沒有獲得這個信息時，我們采用了得這個信息時，我們采用了“不開采不開采”這個決這個決策，此時收益的期望值是策，此時收益的期望值是3535萬元（見圖萬元（見圖6.46.4）。）。當我們獲得這個信息后，便可以利用這個信息當我們獲得這個信息后，便可以利用這個信息決策是否開采，此時收益的期望值提高到決策是否開采，此時收益的期

7、望值提高到132.8132.8萬元（見圖萬元（見圖 的狀態點的狀態點2 2），但為獲得這），但為獲得這個信息要耗費個信息要耗費4040萬元的成本。因此，這個信息萬元的成本。因此，這個信息的純價值為：的純價值為：132.8-35-40 = 57.8132.8-35-40 = 57.8（萬元）（萬元） 13兩大問題：建模與算法在本課程中將都有所涉及14課程安排第一章 非線性規劃第二章 多目標規劃第三章 對策論第四章 決策論其他方法15第一章第一章非線性規劃非線性規劃 16第一節 非線性規劃問題一 、一般非線性規劃17非線性規劃非線性規劃 在科學管理和其他領域中，大量應用問題可以在科學管理和其他領域

8、中，大量應用問題可以歸結為線性規劃問題，但是，也有另外一些問題，其歸結為線性規劃問題，但是，也有另外一些問題，其目標函數和（或）約束條件很難用線性函數表達。如目標函數和（或）約束條件很難用線性函數表達。如果目標函數和（或）約束條件中包含有自變量的非線果目標函數和（或）約束條件中包含有自變量的非線性函數，則這樣的規劃問題就屬于非線性規劃。性函數，則這樣的規劃問題就屬于非線性規劃。 一般來說，求解非線性規劃問題比線性規劃問題一般來說，求解非線性規劃問題比線性規劃問題困難得多。而且，也不象線性規劃那樣有單純形法這困難得多。而且，也不象線性規劃那樣有單純形法這一通用的方法，非線性規劃目前還沒有適合于各

9、種問一通用的方法，非線性規劃目前還沒有適合于各種問題的一般算法，這是需要深入研究的一個領域題的一般算法，這是需要深入研究的一個領域。 18 問題的提出問題的提出例例1 某公司經營兩種設備，第一種設備每件售價某公司經營兩種設備，第一種設備每件售價 30 元，第二種設備每件售價元，第二種設備每件售價 450 元。據統計，每銷元。據統計，每銷售一件第一種設備所需時間平均售一件第一種設備所需時間平均 0.5 小時，第二種設小時，第二種設備是（備是（2 + 0.25X2）小時，其中）小時，其中 X2 是第二種設備的是第二種設備的售數量。已知該公司在這段時間內的總營業時間為售數量。已知該公司在這段時間內的

10、總營業時間為 800 小時，試確定使其營業額最大的營業計劃。小時，試確定使其營業額最大的營業計劃。 19 例例2 某工廠向用戶提供發動機，按合同規定，其交某工廠向用戶提供發動機，按合同規定，其交貨數量和日期是：第一季度末交貨數量和日期是：第一季度末交 40 臺，第二季度末臺，第二季度末交交 60 臺，第三季度末交臺，第三季度末交 100 臺。工廠的最大生產能臺。工廠的最大生產能力為每季度力為每季度 100 臺，每季的生產費用是臺，每季的生產費用是 f（X）= 50X + 0.2X2 （元），（元），X 為該季度生產的發為該季度生產的發動機數量。若某季度生產的多，多余的發動機可移到動機數量。若某

11、季度生產的多，多余的發動機可移到下季度向用戶交貨，這樣，工廠就需要支付存儲費，下季度向用戶交貨，這樣，工廠就需要支付存儲費，每臺發動機每季的存儲費為每臺發動機每季的存儲費為 4 元。問該廠每季應生產元。問該廠每季應生產多少發動機，才能既滿足交貨合同，又使工廠所花費多少發動機，才能既滿足交貨合同，又使工廠所花費的費用最少（假定第一季開始時發動機無存貨）。的費用最少（假定第一季開始時發動機無存貨）。 20 最優動態定價法模型基本特征：1、在各個價格期間給定數量的產品，公司會不段優化價格去獲取最大收入2、公司在每個價格期間結束時都會制定新的最優價格，這個新價格考慮了實際銷量和真實的庫存水平3、從一個

12、價格期間到另一個價格期間，價格都會發生變化，需求較高的時期，價格往往高于需要低時期的價格21 4、通常價格會由于實際銷量水平而與計劃價格有所偏離。如果實際銷量低于計劃銷量，價格一般會下跌，若實際銷量高于計劃銷量，價格往往會上升。22最佳批量模型我們討論的最佳批量模型中，包括了一個模型系列，其基本特征是非線性優化，由無約束優化到單一等式約束優化，最終到含有多個不等式約束的非線性優化23 經濟訂貨量公式EQQ在確定性、周期性的補充存貯消耗過程中，假設單一產品1均勻消耗，消耗率R即時補充，3不允許缺貨4 每次訂貨量Q ，固定費K，單位存貯費h均不變，貨物單價C24 考慮多產品存貯模型，增加資金約束時

13、，或者增加庫存容量約束時，成為單一等式約束優化，用lagrange乘數法求最優解兼有庫存與資金約束的多產品EQQ模型具有兩個不等式約束的非線性規劃25 微觀經濟中的非線性規劃 消費者選擇 成本最小化那么如何求非線性規劃問題的最優解呢？那么如何求非線性規劃問題的最優解呢？回顧一下線性規劃的圖解法回顧一下線性規劃的圖解法26 非線性規劃問題的數學模型非線性規劃問題的數學模型 min f（X） hi（X）= 0 i = 1，2，m gj（X） 0 j = 1，2，l min f（X） gj（X） 0 j = 1，2，l 27 非線性規劃的圖解非線性規劃的圖解x1x20662233最優解最優解 X*

14、= ( 3，3 )T可行解可行解 可行域可行域D min f（X）=（x1 - 2）2 +（x2 - 2）2 h（X）= x1 + x2 - 6 = 0等值線或者等值面 28 非線性規劃的圖解非線性規劃的圖解 min f（X）=（x1 - 2）2 +（x2 - 2）2 h（X）= x1 + x2 - 6 0 x1x206622最優解最優解 X* = ( 2，2 )T D可行域可行域 29 回顧一下一元函數極值的求法那么多元函數極值問題應該怎么求30 二、多元函數極值的有關概念和性質 梯度梯度 f(X)（n維列向量） 海森矩陣海森矩陣 H(X)（nn對稱方陣）定理 1 f(X)的臺勞展開式臺勞展

15、開式 定義 鄰域鄰域 （嚴格）局部極小點（嚴格）局部極小點 （嚴（嚴格）全局極小點格）全局極小點 駐點（平穩點）正定駐點（平穩點）正定 半正定半正定 負定（主子式負正間隔）負定（主子式負正間隔） 半負半負定定 不定不定定理2、3、4、5 局部極小點的一階必要條件，二階必要條件，二階充分條件（嚴格局部極小點，局部極小點）31 例 求f(X)=1/3x12+ 1/ 2x22 的梯度向量例 求f(X)= x12+ 2x22 -4x1-2x1x2海森矩陣32 例例 生產函數Q=3K1/3L1/2 若商品價格為4,要素的價格為Pk=4,PL=3 試求該企業得到最大利潤時的要素投入水平（消費者最優商品組合

16、，生產要素最佳組合的相似性-無差異曲線，等產量曲線；效用函數，生產函數）33 三、正定矩陣與二次型 四 凸函數的極值 凸函數凸函數 嚴格凸函數嚴格凸函數 （嚴格）凹函數（嚴格）凹函數非凸非凹函數非凸非凹函數 凸函數的性質 1、2、3 凸函數的判別 定理6、7 可引申出凹函數的性質與判別 34凸函數凹函數非凸非凹函數35 凸函數極值的性質 定理8 、9凸規劃 定義 判別定理：定理10、凸規劃性質：定理11例例 證明 f(X)=x12 x22為嚴格凹函數兩種方法證明 利用凹函數的判別定理例例 凸規劃的判別minf(X)= x12+ x224x1+4 g1(x)= x1 x2 +20 g2(x)=

17、x1 2 x2 10 36第二節 一維搜索一元函數極值問題一維搜索的來歷求非線性規劃 的基本思路：1、選定初始點X0 k=02、檢查Xk是否極小，是停，否繼續3、確定搜索方向Pk4、從Xk出發，沿Pk求步長k ,產生Xk1令k=k+1轉2 37 確定Pk為關鍵，這決定于不同算法，確定步長有幾種方法：1、令其為一常數（最簡單）2、任選步長，只要能使f下降3、沿搜索方向使f下降最多即求 k ：minf(Xk+ k Pk)稱這一過程為一維搜一維搜索索，這樣確定的步長為最佳步長4、確定能使f更快接近最優的步長38 可見一維搜索是求目標函數可見一維搜索是求目標函數minf(Xk+ Pk)的的 ，即求以，

18、即求以 為自變量的為自變量的一元函數的最優解與最優值，可以直接一元函數的最優解與最優值，可以直接用求極值的方法用求極值的方法 39 如果解析解不易求得，一般采用迭代方法求解，本節介紹的基本為迭代方法，基本步驟為：1、初值x0 k=02、判斷xk，滿足條件終止，否則繼續3、迭代xk xk+1 k=k+1轉2關鍵在于確定 判別規則，及迭代公式40 一、牛頓法與對分法利用局部極小點的一階 必要條件，對于一元函數有f(x)=0，該方程解析解有時候不易求得，用迭代法求解。41 x0 x1x2x*f (x)0判別規則：判別規則：|f (xk)|迭代公式：迭代公式：xk+1=xk-f (xk)/f ”（xk

19、）牛頓法牛頓法42 牛頓法發散的情況牛頓法發散的情況f(x)x0 x1x2x*43f(x)ab c對分法對分法判別規則判別規則最后的區間很小最后的區間很小迭代方法，三點中去掉迭代方法，三點中去掉一個邊界點，保留正負一個邊界點，保留正負兩點兩點，44 二、拋物線法 （二次插值法），0.618法基本思想 利用f(x)在三個不同點的函數值，形成高、低、高，縮小區間迭代45拋物線法拋物線法x3x1x2x4判別規則：判別規則：|x2- x4|0,對于所有X,P(X)0,當且僅當XD時，P(X)=0 P(X)是罰函數罰函數， 為罰因子，64 不斷增加，使F極小點X不斷靠近可行域P(X)的取法：當st hj

20、(X)=0 j=1,2,l時，取P(X)=hj(X)2當st gi(X)0 i=1,2m 時，取 P(X)=min 0,gi(X) 265xMP(x)g(x)=x-a0aM=1M=10M=10066 例：求解非線性規劃 minf(X)=x1+x2 g1(X)=-x12+x20 g2(x)=x1067 2、內點法 基本思想：從原問題可行點出發，在可行域邊界建立一個障礙函數q(X)，阻擋可行點離開可行域，從而使迭代在可行域內部逐漸逼近約束最優解。逐漸縮小r當約束為gi(X)0 時，q(X)=r1/ gi(X)68 例：用內點法求解 minf(x)=x3/3 x-a069 第二章第二章 多目標規劃多

21、目標規劃70第一節 基本概念例：由n種成分組成的香蕉配方，可用x=(x1,x2,.xn)表示，對于每個配方要同時考察幾個指標，如強度f1(x),硬度f2(x) ，伸長率，變形率等，如何得到好的配方。再如薪酬設計，業績考評等都需要考慮多方面的指標。 絕對最優解 有效解 弱有效解（非劣解） 71fi(x)xf1(x)f2(x)f2(x)fi(x)xf1(x)f2(x)f1(x)f1(x)f2(x)例 minf(x)=(f1(x),f2(x)72 練習 1、f1(x)=2x-x2 f2(x)= R=0,2 max2、f1(x)=2x-x2 f2(x)=x R=0,2 max3、 f1(x)=2x-x

22、2 f2(x)=1/8(-12x2+36x-15) R=0,2 max x 0 x1 2x+3 1x273 4、f1(x)=-3x1+2x2 f2=x1+2x2 求max5、上例中f2= 4x1+3x2其他不變 求max-2x1-3x2+180-2x1- x2+100 x1 0 x2 0R:74第二節 化多為少法1、主要目標法2、線性加權和法找合理權系數的方法：法以兩目標規劃為例 75f1*f10f2*f20M2M1Cf1 f2 f1越小越好,f2越大越好M1與M2連線左上區域邊界是非劣解，可知C點是非劣解。f10=minf1=f1(x1)f20=maxf2 = f2(x2) f1*= f1(x2)f2*= f2(x