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

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

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

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

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 用逆推的方法確定最優(yōu)策略為：進一步進行勘探，用逆推的方法確定最優(yōu)策略為：進一步進行勘探，如果勘探結(jié)果是礦物化則

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

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

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

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

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

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

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

13、，或者增加庫存容量約束時，成為單一等式約束優(yōu)化，用lagrange乘數(shù)法求最優(yōu)解兼有庫存與資金約束的多產(chǎn)品EQQ模型具有兩個不等式約束的非線性規(guī)劃25 微觀經(jīng)濟中的非線性規(guī)劃 消費者選擇 成本最小化那么如何求非線性規(guī)劃問題的最優(yōu)解呢？那么如何求非線性規(guī)劃問題的最優(yōu)解呢？回顧一下線性規(guī)劃的圖解法回顧一下線性規(guī)劃的圖解法26 非線性規(guī)劃問題的數(shù)學(xué)模型非線性規(guī)劃問題的數(shù)學(xué)模型 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 非線性規(guī)劃的圖解非線性規(guī)劃的圖解x1x20662233最優(yōu)解最優(yōu)解 X*

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

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

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

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

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

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

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

21、目標(biāo)規(guī)劃70第一節(jié) 基本概念例：由n種成分組成的香蕉配方，可用x=(x1,x2,.xn)表示，對于每個配方要同時考察幾個指標(biāo)，如強度f1(x),硬度f2(x) ，伸長率，變形率等，如何得到好的配方。再如薪酬設(shè)計，業(yè)績考評等都需要考慮多方面的指標(biāo)。 絕對最優(yōu)解 有效解 弱有效解（非劣解） 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 練習(xí) 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第二節(jié) 化多為少法1、主要目標(biāo)法2、線性加權(quán)和法找合理權(quán)系數(shù)的方法：法以兩目標(biāo)規(guī)劃為例 75f1*f10f2*f20M2M1Cf1 f2 f1越小越好,f2越大越好M1與M2連線左上區(qū)域邊界是非劣解，可知C點是非劣解。f10=minf1=f1(x1)f20=maxf2 = f2(x2) f1*= f1(x2)f2*= f2(x