高等運(yùn)籌課件1

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

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

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

4、一步的勘探。進(jìn)一步的勘探要耗以對(duì)該礦作進(jìn)一步的勘探。進(jìn)一步的勘探要耗費(fèi)費(fèi)4040萬(wàn)元的勘探費(fèi)用，其結(jié)果可能區(qū)分礦區(qū)地萬(wàn)元的勘探費(fèi)用，其結(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ù)專家估計(jì)該礦區(qū)地質(zhì)結(jié)構(gòu)礦物。據(jù)專家估計(jì)該礦區(qū)地質(zhì)結(jié)構(gòu)礦物化和非礦物

5、化的概率分別為化和非礦物化的概率分別為0.60.6和和0.40.4。1113624578-40A1不勘探不勘探35A2 進(jìn)一步勘探進(jìn)一步勘探礦物化礦物化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)策略為：進(jìn)一步進(jìn)行勘探，用逆推的方法確定最優(yōu)策略為：進(jìn)一步進(jìn)行勘探，如果勘探結(jié)果是礦物化則

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

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

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

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

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

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

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

13、，或者增加庫(kù)存容量約束時(shí)，成為單一等式約束優(yōu)化，用lagrange乘數(shù)法求最優(yōu)解兼有庫(kù)存與資金約束的多產(chǎn)品EQQ模型具有兩個(gè)不等式約束的非線性規(guī)劃25 微觀經(jīng)濟(jì)中的非線性規(guī)劃 消費(fèi)者選擇 成本最小化那么如何求非線性規(guī)劃問(wèn)題的最優(yōu)解呢？那么如何求非線性規(guī)劃問(wèn)題的最優(yōu)解呢？回顧一下線性規(guī)劃的圖解法回顧一下線性規(guī)劃的圖解法26 非線性規(guī)劃問(wèn)題的數(shù)學(xué)模型非線性規(guī)劃問(wèn)題的數(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ù)極值問(wèn)題應(yīng)該怎么求30 二、多元函數(shù)極值的有關(guān)概念和性質(zhì) 梯度梯度 f(X)（n維列向量） 海森矩陣海森矩陣 H(X)（nn對(duì)稱方陣）定理 1 f(X)的臺(tái)勞展開式臺(tái)勞展

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

16、，生產(chǎn)要素最佳組合的相似性-無(wú)差異曲線，等產(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ù)極值問(wèn)題一維搜索的來(lái)歷求非線性規(guī)劃 的基本思路：1、選定初始點(diǎn)X0 k=02、檢查Xk是否極小，是停，否繼續(xù)3、確定搜索方向Pk4、從Xk出發(fā)，沿Pk求步長(zhǎng)k ,產(chǎn)生Xk1令k=k+1轉(zhuǎn)2 37 確定Pk為關(guān)鍵，這決定于不同算法，確定步長(zhǎng)有幾種方法：1、令其為一常數(shù)（最簡(jiǎn)單）2、任選步長(zhǎng)，只要能使f下降3、沿搜索方向使f下降最多即求 k ：minf(Xk+ k Pk)稱這一過(guò)程為一維搜一維搜索索，這樣確定的步長(zhǎng)為最佳步長(zhǎng)4、確定能使f更快接近最優(yōu)的步長(zhǎng)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 一、牛頓法與對(duì)分法利用局部極小點(diǎn)的一階 必要條件，對(duì)于一元函數(shù)有f(x)=0，該方程解析解有時(shí)候不易求得，用迭代法求解。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對(duì)分法對(duì)分法判別規(guī)則判別規(guī)則最后的區(qū)間很小最后的區(qū)間很小迭代方法，三點(diǎn)中去掉迭代方法，三點(diǎn)中去掉一個(gè)邊界點(diǎn)，保留正負(fù)一個(gè)邊界點(diǎn)，保留正負(fù)兩點(diǎn)兩點(diǎn)，44 二、拋物線法 （二次插值法），0.618法基本思想 利用f(x)在三個(gè)不同點(diǎn)的函數(shù)值，形成高、低、高，縮小區(qū)間迭代45拋物線法拋物線法x3x1x2x4判別規(guī)則：判別規(guī)則：|x2- x4|0,對(duì)于所有X,P(X)0,當(dāng)且僅當(dāng)XD時(shí)，P(X)=0 P(X)是罰函數(shù)罰函數(shù)， 為罰因子，64 不斷增加，使F極小點(diǎn)X不斷靠近可行域P(X)的取法：當(dāng)st hj

20、(X)=0 j=1,2,l時(shí)，取P(X)=hj(X)2當(dāng)st gi(X)0 i=1,2m 時(shí)，取 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)點(diǎn)法 基本思想：從原問(wèn)題可行點(diǎn)出發(fā)，在可行域邊界建立一個(gè)障礙函數(shù)q(X)，阻擋可行點(diǎn)離開可行域，從而使迭代在可行域內(nèi)部逐漸逼近約束最優(yōu)解。逐漸縮小r當(dāng)約束為gi(X)0 時(shí)，q(X)=r1/ gi(X)68 例：用內(nèi)點(diǎn)法求解 minf(x)=x3/3 x-a069 第二章第二章 多目標(biāo)規(guī)劃多

21、目標(biāo)規(guī)劃70第一節(jié) 基本概念例：由n種成分組成的香蕉配方，可用x=(x1,x2,.xn)表示，對(duì)于每個(gè)配方要同時(shí)考察幾個(gè)指標(biāo)，如強(qiáng)度f(wàn)1(x),硬度f(wàn)2(x) ，伸長(zhǎng)率，變形率等，如何得到好的配方。再如薪酬設(shè)計(jì)，業(yè)績(jī)考評(píng)等都需要考慮多方面的指標(biāo)。 絕對(duì)最優(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點(diǎn)是非劣解。f10=minf1=f1(x1)f20=maxf2 = f2(x2) f1*= f1(x2)f2*= f2(x