課件多目標規(guī)劃與數(shù)學(xué)模型

1、多目標規(guī)劃,引例1： 投資問題,某公司在一段時間內(nèi)有a(億元)的資金可用于建廠投資。若可供選擇的項目記為1，2，.，m。而且一旦對第i個項目投資，就用去ai億元；而這段時間內(nèi)可得收益ci億元。問如何如確定最佳的投資方案？,約束條件為：,最佳的投資方案投資最少、收益最大,投資最少：,收益最大,雙目標規(guī)劃,引例2： 生產(chǎn)問題,某工廠生產(chǎn)兩種產(chǎn)品，產(chǎn)品A每單位利潤為10元，而產(chǎn)品B每單位利潤為8元，產(chǎn)品A每單位需3小時裝配時間而B為2小時，每周總裝配有效時間為120小時。工廠允許加班，但加班生產(chǎn)出來的產(chǎn)品利潤減去1元，根據(jù)最近的合同，廠商每周最少得向用戶提供兩種產(chǎn)品各30單位。要求:1) 必須遵守合

2、同；2)盡可能少加班；3)利潤最大. 問怎樣安排生產(chǎn)？,約束條件為：,加班最少,利潤最大,多目標規(guī)劃的模型,一般形式:,求目標函數(shù)的最大值或約束條件為大于等于零的情況，都可通過取其相反數(shù)化為上述一般形式,定義1 把滿足問題中約束條件的解XRn稱為可行解(或可行點)，所有可行點的集合稱為可行集(或可行域)記為D即:,原問題可簡記為,定義2 x*是絕對最優(yōu)解fj(X)fj(x*), 任意XD, j=1 p x*是有效解不存在XD , 使得fj(X)fj(x*), j=1 p x*是弱有效解 不存在XD , 使得fj(X)fj(x*), j=1 p,定義3 像集F(R)=F(x)|xD約束集R在映像

3、F之下的值域 F*是有效點 不存在FF(D), 使得FF*； F *是弱有效點 不存在FF(R), 使得F0, 即此目標值再差也是可接受的!,多目標規(guī)劃的基本解法,3. 功效系數(shù)法對不同類型的目標函數(shù)統(tǒng)一量綱，分別得到一個功效系數(shù)函數(shù)，然后求所有功效系數(shù)乘積的最優(yōu)解。,線性型功效系數(shù)法，還有其它類型的方法，如指數(shù)型方法,多目標規(guī)劃的基本解法,4. 評價函數(shù)法這是一種最常見的方法，就是用一個評價函數(shù)來集中反映各不同目標的重要性等因素，并極小化此評價函數(shù)，得到問題的最優(yōu)解。常見的以下幾種方法：,原理：距理想點最近的點作為最優(yōu)解!,4.1 理想點法：,定義評價函數(shù)：,求解非線性規(guī)劃問題：,4.2 平

4、方和加權(quán)法：,定義評價函數(shù)：,求解非線性規(guī)劃問題：,先設(shè)定單目標規(guī)劃的下界(想象中的最好值),即,其中j為事先給定的一組權(quán)系數(shù)，滿足：,原理：平方和加權(quán)法體現(xiàn)了通常的“自報公議”原則那些強調(diào)各自目標重要者預(yù)先給出一個盡可能好的估計，然后“公議”給出一組表明各目標性的權(quán)系數(shù)，最后求解非線性規(guī)劃給出解答。,虛擬目標法,多目標規(guī)劃的基本解法,4.3 線性加權(quán)法：,再定義評價函數(shù)：,求解非線性規(guī)劃問題：,事先按目標函數(shù)f1(X)、.、fp(X)的重要程度給出一組權(quán)系數(shù)j，滿足：,多目標規(guī)劃的基本解法,4.4 “min-max”法(極小極大法),定義評價函數(shù)：,求解非線性規(guī)劃問題：,原理：在最不利的情況

5、下找出一個最有利的策略!悲觀主義決策,多目標規(guī)劃的基本解法,4.4 “min-max”法(極小極大法)(轉(zhuǎn)化),此非線性規(guī)劃問題目標函數(shù)不可微，不能直接用基于梯度的算法：,但可方便轉(zhuǎn)化為一個簡單非線性規(guī)劃問題！,則該規(guī)劃問題可等價為：,該技巧非常有用，將一個不可微的規(guī)劃問題轉(zhuǎn)化為可微的約束規(guī)劃！,多目標規(guī)劃的基本解法,4.5 乘除法,考慮兩個目標的規(guī)劃問題：,求解非線性規(guī)劃問題:,則定義評價函數(shù)：,如f1(x)為投資總金額，而f2(x)為投資后的總收益，則最優(yōu)結(jié)果應(yīng)是單位投資的總收入最大！,多目標規(guī)劃的基本解法,理論性結(jié)果,以上所有方法所得到的最優(yōu)解都是有效解(線性加權(quán)法當(dāng)有權(quán)系數(shù)為零時得到的

6、是弱有效解)!,1998A 投資的收益和風(fēng)險,市場上有n種資產(chǎn)Si(i=1,2n)可以選擇, 現(xiàn)用數(shù)額為M的相當(dāng)大的資金作一個時期的投資. 這n種資產(chǎn)在這一時期內(nèi)購買Si的平均收益率為ri, 風(fēng)險損失率為qi, 投資越分散, 總的風(fēng)險越小, 總體風(fēng)險可用投資的Si中最大的一個風(fēng)險來度量. 購買Si時要付交易費 (費率pi), 當(dāng)購買額不超過給定值ui時, 交易費按購買ui計算. 另外, 假定同期銀行存款利率是r0, 既無交易費又無風(fēng)險(r0=5%). 已知n=4時相關(guān)數(shù)據(jù)如下：,投資的收益和風(fēng)險(1998A),1)試給設(shè)計一種投資組合方案, 即用給定的資金M, 有選擇地購買若干種資產(chǎn)或存銀行生

7、息, 使凈收益盡可能大, 使總體風(fēng)險盡可能小.,2)使就一般情況對以上問題進行討論，并利用下表數(shù)據(jù)進行計算:,基本假設(shè)： 1. 投資數(shù)額M相當(dāng)大, 為了便于計算，假設(shè)M=1； 2. 投資越分散，總的風(fēng)險越小； 3. 總體風(fēng)險用投資項目Si中最大的一個風(fēng)險來度量； 4. n種資產(chǎn)Si之間是相互獨立的； 5. 在投資的這一時期內(nèi), ri, pi, qi, r0為定值, 不受意外因素影響; 6. 凈收益和總體風(fēng)險只受 ri, pi, qi影響，不受其他因素干擾。,二、基本假設(shè)和符號規(guī)定,符號規(guī)定： Si -第i種投資項目，如股票，債券; ri, pi, qi -分別為Si的平均收益率, 風(fēng)險損失 率

8、, 交易費率; ui -Si的交易定額; r0 -同期銀行利率; xi -投資項目Si的資金; Q(x) -總體收益函數(shù); P(x)-總體風(fēng)險函數(shù)；,三、模型的建立與分析,總體風(fēng)險用所投資的Si中最大的一個風(fēng)險來衡量,即 max qixi|i=1，2,n,2購買Si所付交易費是一個分段函數(shù), 即交易費= pi*sgn(xi)*maxui, xi;,3要使凈收益盡可能大,總體風(fēng)險盡可能小, 這是一個多目標規(guī)劃模型:,目標,約束條件,4. 模型簡化：,1) 簡化總收益函數(shù)Q(x) 購買Si所付交易費是一個分段函數(shù), 即交易費= pisgn(xi)maxui, xi; 而題目所給定的定值ui(單位:

9、元)相對總投資M很小, piui更小,可以忽略不計, 這樣購買Si的凈收益為(ri-pi)xi,2) 簡化總體風(fēng)險函數(shù)P(x):,簡化后的模型雙目標線性規(guī)劃模型,四、模型求解,模型1固定風(fēng)險水平，極大化凈收益,模型2固定凈收益水平,極小化風(fēng)險損失,模型3權(quán)衡資產(chǎn)風(fēng)險和預(yù)期凈收益兩方面, 對風(fēng)險、收益賦予權(quán)重s和1s(s稱為投資偏好系數(shù)),模型1 確定風(fēng)險水平a0,使每一項投資的風(fēng)險損失不超過a0M,并極大化凈收益，來得到最優(yōu)投資組合把多目標問題轉(zhuǎn)化為單目標問題,通常在分析問題時,需要取多組不同的風(fēng)險水平a0,觀察凈收益的變化情況,以便給出合理的風(fēng)險水平a0.,對于1)(n=4),具體的模型為

10、max 0.05x0+0.27x1+0.19x2+0.185x3+0.185x4 s.t. 0.025x1a0 0.015x2a0 0.055x3a0 0.026x4a0 x0+1.01x1+1.02x2+1.045x3+1.065x4=1 xi0,(i=0,1,2,3,4),Mathematica軟件求解,將a0的值從0取到0.1,步長為0.002,用Mathematica軟件編程求解: (將問題轉(zhuǎn)化為 min cTx s.t. Axb,x0) Fora0 = 0, a0=0.1,a0=a0 + 0.002, c = -0.05, -0.27, -0.19, -0.185, -0.185;

11、A = -0,0.025,0,0,0,0,0,0.015,0,0,0,0,0,0.055,0, 0, 0, 0,0,0.026,1,1.01,1.02,1.045,1.065,-1,-1.01,-1.02, -1.045,-1.065; b=-a0,-a0,-a0,-a0,-1,1;u=LinearProgrammingc, A, b; Printa0, u, -c.u,求解結(jié)果,當(dāng)a0從0.026開始,最優(yōu)值不再變化.,x0 x1 x2 x3 x4 a0 Q(x) 1.00 0 0 0 0 0 0.050 0.66 0.08 0.13 0.04 0.08 0.002 0.101 0.33 0

12、.16 0.27 0.07 0.15 0.004 0.152 0 0.24 0.40 0.11 0.22 0.006 0.202 0 0.32 0.53 0.13 0 0.008 0.211 0 0.40 0.58 0 0 0.01 0.220 0 0.48 0.51 0 0 0.012 0.226 0 0.56 0.43 0 0 0.014 0.232 0 0.64 0.35 0 0 0.016 0.239 0 0.72 0.27 0 0 0.018 0.245 0 0.80 0.19 0 0 0.020 0.252 0 0.88 0.11 0 0 0.022 0.258 0 0.96 0.

13、03 0 0 0.024 0.265 0 0.99 0 0 0 0.026 0.267 0 0.99 0 0 0 0.028 0.267,右圖是目標函數(shù)的最優(yōu)值隨a0變化的圖形.,在a0取值0.006的左邊,目標值增加較快, 在其右邊,目標值增加較慢,所以取a0=0.006是一個合理的選擇.,Matlab軟件求解,Matlab中的命令x,fval=linprog(c,A,b,Aeq,beq,lb,ub) 用來求解規(guī)劃min cTx s.t. A xb Aeq x=beq lbxub 其中A,Aeq為矩陣,c,b,beq,lb,ub為向量. 在某些約束空缺時,可用表示.,for a0=0:0.0

14、02:0.1; c=-0.05;-0.27;-0.19;-0.185;-0.185; A = 0,0.025,0,0,0; 0,0,0.015,0,0; 0,0,0,0.055,0; 0,0,0,0,0.026; b=a0;a0;a0;a0; Aeq=1,1.01,1.02,1.045,1.065; beq=1; lb=zeros(5,1);x,fval=linprog(c,A,b,Aeq,beq,lb) end;,理論求解,此處的線性規(guī)劃約束條件比較特殊,可以得到理論的結(jié)果.,令(1+pi)xi=yi (xi=yi/(1+pi), 可以將模型轉(zhuǎn)化為,理論求解,該模型可以理解為將數(shù)1分解為n+

15、1個數(shù)的和,其中每個數(shù)有一個上界,最終的目標是使得這n+1個數(shù)的線性組合最大.,顯然,要求解該模型,只要將目標函數(shù)中的價格系數(shù)(ri-pi)/(1+pi)進行排序,價格系數(shù)大的,其變量盡量的大.,理論求解,不失一般性,假設(shè) d1d2dnd0 (di=(ri-pi)/(1+pi) 則可以得到該模型的解為,(hi=a0(1+pi)/qi) y1=min(1,h1),y2=min(1-y1,h2), yk=min(1-y1-yk-1,hk),y0=1-y1-yn,n=4的理論結(jié)果,max 0.05y0+0.2673y1+0.1863y2+0.1770y3+0.1737y4 s.t. y140.4a0

16、,y268a0,y319a0,y440.96a0 y0+y1+y2+y3+y4=1, y0,y1,y2,y3,y40.,若40.4a01,則最優(yōu)解為y1=1,y2=y3=y4=y0=0 若40.4a01,40.4a0+68a01,則最優(yōu)解為y1=40.4a0, y2=1-y1=1-40.4a0,y3=y4=y0=0 若40.4a0+68a00.2673時,上述模型無可行解.,在b00.2673時,顯然有min a=1/40.4=0.02475,在0.2165b00.2673時,min a=(b0-0.1863)/3.275,以下討論略去.,模型3 權(quán)衡投資風(fēng)險和預(yù)期凈收益兩方面, 對風(fēng)險、收益

17、賦予權(quán)重s和1s(s稱為投資偏好系數(shù)),取多組不同的偏好系數(shù)s，觀察風(fēng)險和收益的變化情況，以便給出合理的偏好系數(shù)s。,注意這里決策變量為x和a！,模型3的理論求解,模型3可以通過計算機軟件求解. 借助于模型1的結(jié)果,我們可以對模型3進行理論求解. 在模型1中我們求得了收益函數(shù)Q(a)(自變量為風(fēng)險a0),模型3的理論求解,因此,求解模型3,只要求解min s a0+(1-s)Q(a0),在a0的每個區(qū)間上,sa0+(1-s)Q(a0)都是a0的線性函數(shù),因此只可能在區(qū)間的兩端取最小值.,模型3的理論求解,因此,求解模型3,只要求解min s a0+(1-s)Q(a0),若a01/168.36,

18、則 sa0+(1-s)Q(a0)=sa0+(1-s)(0.05+25.53a0) =-0.05(1-s)+(26.53s-25.53)a0,a01/168.36,顯然,類似地我們可以討論a0在其它取值下,目標函數(shù)的最小值.,其結(jié)果可以寫為右邊兩個函數(shù)的最小值,即 min(-0.05+0.05s,-0.2016+0.2076s),1/168.36a01/127.4,1/127.4a01/108.4,1/108.4a01/40.4,1/40.4a0,針對a0的不同范圍,可以畫出上述5個s的函數(shù).對這5個函數(shù)求最小值,即可得到目標函數(shù)的最小值.,事實上,目標函數(shù)的最小值是5個線性函數(shù)的最小值(9個函

19、數(shù)中,有4對是對應(yīng)相等的): -0.05+0.05s, -0.2016+0.2076 s, -0.2106+0.2184 s,-0.2165+0.2257 s, -0.2673+0.2921 s,顯然很容易求得這5個函數(shù)的最小值. 其詳細數(shù)據(jù)結(jié)果在此略去.,與前面兩個模型所不同的是,模型3的最優(yōu)解必然在a0的臨界點處取得.,誤差討論,在前面的簡化過程中,將 maxui, xi取為xi,理由是ui一般比xi小. 根據(jù)上面幾種模型的理論求解,在有些條件下，會出現(xiàn)xi比ui小的情況.,比如在模型1中,中間的三條線段的最右端必然對應(yīng)著某個投資項目的費用很少的情況. 所以實際的圖形在三個小段要比左圖低一些.,誤差討論,比如在模型1中,中間的三條線段的最右端以及原點的右端必然對應(yīng)著某個投資項目的費用很少的情況. 所以實際的圖形在四個小段要比左圖低一些,誤差討論,由于M的值很大,上面四個小段的長度很短. 而且,如果出現(xiàn)上述的情況,我們簡單地將小額資金改為投入到銀行,產(chǎn)生的誤差應(yīng)該小于千分之一(具體誤差與資金有關(guān)).,設(shè)