數(shù)據(jù)模型決策02規(guī)劃擴(kuò)展1（PPT45頁).ppt

1、第章 規(guī)劃擴(kuò)展,人們探討某些線性規(guī)劃問題，有時(shí)必須把全部或部分決策變量限制為整數(shù)。這樣的線性規(guī)劃問題，通常稱為整數(shù)規(guī)劃。作為線性規(guī)劃的特殊情況，整數(shù)規(guī)劃也有最小化和最大化之別。此外，整數(shù)規(guī)劃還可以分成純整數(shù)規(guī)劃和混整數(shù)規(guī)劃。二者的區(qū)別在于：前者的決策變量必定全部取整數(shù)。而后者的決策變量只是部分取整數(shù)。如果全部的決策變量?jī)H取0或1，稱之為0-1規(guī)劃。,2.1 整 數(shù) 規(guī) 劃,例1 (選址決策問題)某公司決定建1到2個(gè)新工廠： 甲地,乙地; 同時(shí)考慮是否建一倉庫。要求: (1)最多建一個(gè)倉庫,如建倉庫,要與工廠在同一地點(diǎn); (2)公司對(duì)此次擴(kuò)張的資金預(yù)算是1000萬; 問:公司如何決策使得投資凈現(xiàn)

2、值最大?,解：,Max z=9x1+5x2+6x3+4x4,St 6x1+3x2+5x3+2x410,x3+x41,-x1+x30,-x2+x40,x1,x2,x3,x4為0-1變量,(1)公司對(duì)此次擴(kuò)張的資金預(yù)算是1000萬 (2)最多建一個(gè)倉庫 (3)如建倉庫,要與工廠在同一地點(diǎn);,想一想:,1,0,做第i件事,不做第i件事,n件事中必須做k件并只做k件事,n件事中最多做k件事,做第4件事的充要條件是做第6件事,做第4件事的充要條件是不做第6件事,只在做了第4件事前提下才考慮是否做第6件事,如果做第4件事，則不能做第6件事,例2（布點(diǎn)問題）某城市共有6個(gè)區(qū)，每個(gè)區(qū)都可以建消防站。市政府希望

3、設(shè)置的消防站最少，但必須滿足在城市任何地區(qū)發(fā)生火警時(shí)，消防車要在15分鐘內(nèi)趕到現(xiàn)場(chǎng)。據(jù)實(shí)地測(cè)定，各區(qū)之間消防車行駛的時(shí)間見右表。,請(qǐng)為該市制定一最節(jié)省消防站數(shù)目的計(jì)劃。,在第i個(gè)地區(qū)建站,Z表示全區(qū)消防站總數(shù),不在第i個(gè)地區(qū)建站,i=1,2, ,6,布點(diǎn)問題模型：,最優(yōu)解 x2=1, x4=1,最優(yōu)值 Z=2,例3（背包問題）一個(gè)旅行者，為了準(zhǔn)備旅行的必備物品，要在背包里裝一些有用的東西，但他最多只能攜帶b公斤的東西，而每件物品都只能整件攜帶，于是他給每件物品規(guī)定了一個(gè)“價(jià)值”，以表示其有用程度。如果共有m件物品，第i件物品的重量為bi，價(jià)值為ci，問題就變成：在攜帶的物品總重量不超過b公斤的

4、條件下，攜帶哪些物品可使總價(jià)值最大,解：,Z表示所帶物品的總價(jià)值,攜帶物品的總重量,數(shù)學(xué)模型：,輔助0-1變量的使用,假設(shè)有兩個(gè)約束條件: x1+5x213 3x1+2x2 18， 要求只 有一個(gè)起作用。,x1+5x213+(1-y)M 3x1+2x2 18+My 其中M為足夠大的正數(shù),01決策變量是表示是非決策的01變量； 輔助01變量是引入模型的附加01變量，不代表一個(gè)是非決策，僅僅是為了方便建立模型，輔助01變量通常用y表示。,部分約束,選擇取值,固定費(fèi)用,邏輯關(guān)系,例4： 一服裝廠可生產(chǎn)三種服裝，生產(chǎn)不同種類的服裝要租用不同的設(shè)備，設(shè)備租金和其它經(jīng)濟(jì)參數(shù)見下表。假定市場(chǎng)需求不成問題，服

5、裝廠每月可用人工工時(shí)為1500小時(shí)，問該廠如何安排生產(chǎn)，可以使每月利潤(rùn)最大。,生產(chǎn)西裝的總利潤(rùn)=銷售價(jià)格*數(shù)量-生產(chǎn)成本*數(shù)量-設(shè)備租金 注意:只有生產(chǎn)西裝,才會(huì)產(chǎn)生生產(chǎn)西裝的設(shè)備租金.,這個(gè)問題的整數(shù)規(guī)劃模型為,上述整數(shù)規(guī)劃正確嗎?,這個(gè)問題的整數(shù)規(guī)劃模型為,如果這三種產(chǎn)品的產(chǎn)量之間還要滿足一定的邏輯關(guān)系，例如分別考慮以下關(guān)系：,每一種產(chǎn)品如果生產(chǎn)，最小批量為150件； 如果產(chǎn)品1安排生產(chǎn)，產(chǎn)品2就不能生產(chǎn)； 如果產(chǎn)品3生產(chǎn)，產(chǎn)品2必須生產(chǎn)，而且至少生產(chǎn)500件；,每一種產(chǎn)品如果生產(chǎn)，最小批量為150件；相應(yīng)的約束條件：,x1150y1，x2150y2，x3150y3,如果產(chǎn)品1安排生產(chǎn)，產(chǎn)

6、品2就不能生產(chǎn)；相應(yīng)的約束條件為：,y1+y21,如果產(chǎn)品3安排生產(chǎn)，產(chǎn)品2必須生產(chǎn)，而且至少生 產(chǎn)500件 .相應(yīng)的約束條件為：,y2y3 x2500y2,非線形規(guī)劃,在數(shù)學(xué)規(guī)劃問題中，當(dāng)目標(biāo)函數(shù)或約束函數(shù)中至少有一個(gè)是非線性函數(shù)時(shí)稱這類問題為非線性規(guī)劃。,基本投資組合模型: 例5: 股票投資問題,期望年收益率至少達(dá)到15%，應(yīng)當(dāng)如何投資？ 表中數(shù)據(jù)為年收益率數(shù)據(jù)。,問題分析,收益不確定,收益的期望值,風(fēng)險(xiǎn) 收益的方差,一種股票收益的均值衡量這種股票的平均收益狀況,一種股票收益的方差衡量這種股票收益的波動(dòng)幅度,兩種股票收益的協(xié)方差表示他們之間的相關(guān)程度,方差越大，風(fēng)險(xiǎn)越大；方差越小，風(fēng)險(xiǎn)越小

7、。,數(shù)學(xué)期望： ER1=0.0890833, ER2=0.213667, ER3=0.234583 協(xié)方差矩陣： COV =,假設(shè)股票A、B、C每年的收益率分別為R1，R2和R3,模型建立,年收益率（的數(shù)學(xué)期望）不低于15%,資金 全部用于投資這三種股票,決策變量,x1投資股票A,x2投資股票B,x3投資股票C,約束條件,x1, x2 , x3 0，x1+x2 +x3 = 1,x1ER1+x2ER2+x3ER3 0.15,目標(biāo)函數(shù),年投資收益率的方差極小,二次規(guī)劃模型(QP),數(shù)學(xué)模型的lingo程序,A占53%，B占36%，C占11%,min=0.009907*x12+0.053526*x2

8、2+0.086375*x32+2*0.011373*x1*x2+2*0.011986*x1*x3+2*0.050808*x3*x2; 0.089083*x1+0.213637*x2+0.234583*x3=0.15; x1+x2+x3=1; end,現(xiàn)有一種無風(fēng)險(xiǎn)的投資方式(如購買國庫券)。假設(shè)國庫券的年收益率為5%，如何考慮例5中的問題？,存在無風(fēng)險(xiǎn)資產(chǎn)時(shí)的投資組合模型- 例6:,問題分析,無風(fēng)險(xiǎn)的投資方式的收益固定,方差為0,特例,假設(shè)國庫券的投資方式記為D,投資A占8%，B占42%，C占14%，D占34%,要求的期望收益:15% 10%,投資A大約占4%，B占21%，C占7%，D（國庫券

9、）占67%,結(jié)果分析,風(fēng)險(xiǎn)資產(chǎn)之間的投資比例與期望收益和風(fēng)險(xiǎn)偏好無關(guān),風(fēng)險(xiǎn)資產(chǎn)本身相互之間的比例不變,變化的只是投資于風(fēng)險(xiǎn)資產(chǎn)與無風(fēng)險(xiǎn)資產(chǎn)之間的比例,分離定理,Tobin教授,1981, 諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng),繼續(xù)考慮例5（要求的期望收益率仍定為15%）。假設(shè)握有的股票比例為：股票A占50%，B占35%，C占15%。如按交易額的1% 收取交易費(fèi)，,考慮交易成本的的投資組合模型- 例7:,問題:是否需要對(duì)手上的股票進(jìn)行買賣（換手）？,模型建立,決策變量,x1投資股票A,x2投資股票B,x3投資股票C,假設(shè)購買股票A、B、C的比例為y1 、y2和 y3,假設(shè)賣出股票A、B、C的比例為z1 、z2和 z3

10、,投資A大約占52.91%，B占35%，C占11.56%，,約束條件,x1, x2 , x3 0，y1, y2 , y3 0 , z1, z2 , z3 0。,x1+x2 +x3 +0.01( y1+y2 +y3 + z1+z2 +z3 )= 1,注:持有的總資金守恒,ci為當(dāng)前握有的各支股票的份額,xi = ci + yi - zi（i=1，2，3）,三者之和略小于100% ,為什么?,數(shù)學(xué)模型的lingo程序,min=0.009907*x12+0.053526*x22+0.086375*x32+2*0.011373*x1*x2+2*0.011986*x1*x3+2*0.050808*x3*

11、x2; 0.089083*x1+0.213637*x2+0.234583*x3=0.15; x1+x2+x3+0.01*(y1+y2+y3+z1+z2+z3)=1; x1=0.5+y1-z1; x2=0.35+y2-z2; x3=0.15+y3-z3; end,能否通過一定方式避免協(xié)方差的計(jì)算，對(duì)模型進(jìn)行簡(jiǎn)化呢？,利用股票指數(shù)簡(jiǎn)化投資組合模型- 例8:,線性回歸,利用股票指數(shù),假設(shè)每只股票的收益與股票指數(shù)成線性關(guān)系,M表示股票指數(shù),均值為m0=E(M)，方差為s02=D(M),股票i，其價(jià)值Ri = ui + biM+ ei ,ei是一個(gè)隨機(jī)誤差項(xiàng),均值為E(ei)=0，方差為si2=D(ei

12、),假設(shè)隨機(jī)誤差項(xiàng)ei是與其他股票j（ji）和股票指數(shù)M都是獨(dú)立的,E(eiej) = E(eiM) =0,如何根據(jù)所給數(shù)據(jù)經(jīng)過回歸計(jì)算得到ui 和 bi?,記12年的數(shù)據(jù)為 M (k)，Ri (k)，（k=1，2，,12）,優(yōu)化問題,結(jié)果,M的均值m0=1.191458，方差為s02=0.02873661,標(biāo)準(zhǔn)差為s0=0.1695188,A:u1 =0.5639761， b1 =0.4407264， s12=0.005748320， s1=0.07581767,B:u2 = -0.2635059， b2 = 1.239802， s22= 0.01564263， s2= 0.1250705,

13、C :u3 = -0.5809590， b3 = 1.523798， s32= 0.03025165， s3= 0.1739300,年收益率(數(shù)學(xué)期望)不低于15%,決策變量,x1投資股票A,x2投資股票B,x3投資股票C,約束條件,x1, x2 , x3 0，x1+x2 +x3 = 1,目標(biāo)函數(shù),年投資收益率的方差極小,優(yōu)化模型,對(duì)應(yīng)的收益:,二次規(guī)劃模型(QP),與前結(jié)果A占53%，B占36%，C占11%比較,略有差異,A占53%，B占38%，C占9%,結(jié)果,其他目標(biāo)下的投資組合模型- 例9:保守股票投資,市場(chǎng)上只有兩只股票A、B可供某個(gè)投資者購買 ,市場(chǎng)只能出現(xiàn)兩種可能的情況（1和2）,

14、現(xiàn)要使兩種情況下最小的收益最大化（即不管未來發(fā)生哪種情況，都能至少獲得這個(gè)收益），如何建立模型和求解？,優(yōu)化模型與求解,決策變量,約束條件,目標(biāo)函數(shù),X1年初投資股票A,X2年初投資股票B,x1, x2 0，x1+x2 = 1,最小收益最大的“保守”目標(biāo)實(shí)際上就是希望： Max min(1.0 x1+1.2x2 , 1.5x1+0.7x2) ,引入一個(gè)輔助變量y，這個(gè)模型就可以線性化。相應(yīng)的LINDO模型為：,MAX y Subject to x1 + x2 = 1 x1 + 1.2 x2 - y 0 1.5 x1 + 0.7 x2 - y 0,求解得到 ：應(yīng)該投資A、B股票各50%，至少可以

15、增值10%,求解得到 ：應(yīng)該投資A股票54.5455%， B 股票45.4545%，至少可以增值13.6364% .,現(xiàn)在，假設(shè)有一條重要信息：如果情形1發(fā)生，股票B的增值將達(dá)到30%而不是表中給出的20%。那么，一般人的想法應(yīng)該是增加對(duì)股票B的持有份額。果真如此嗎？這個(gè)投資人如果將上面模型中的1.2改為1.3計(jì)算,也就是說，應(yīng)該減少對(duì)股票B的持有份額，增加對(duì)股票A的持有份額！這真是叫人大吃一驚！這相當(dāng)于說：有人告訴你有某只股票漲幅要增加了，你趕緊說：那我馬上把這只股票再賣點(diǎn)吧。之所以出現(xiàn)如此奇怪的現(xiàn)象，就是由于這個(gè)例子中的目標(biāo)的特殊性引起的,某裝飾材料公司欲以每桶2元的價(jià)錢購進(jìn)一批彩漆。一般

16、來說隨著彩漆售價(jià)的提高，預(yù)期銷售量將減少，并對(duì)此進(jìn)行了估算，見表1。為了盡快收回資金并獲得較多的贏利，裝飾材料公司打算做廣告，投入一定的廣告費(fèi)后，銷售量將有一個(gè)增長(zhǎng)，可由銷售增長(zhǎng)因子來表示。根據(jù)經(jīng)驗(yàn)，廣告費(fèi)與銷售增長(zhǎng)因子關(guān)系見表2。現(xiàn)在的問題是裝飾材料公司采取怎樣的營銷戰(zhàn)略會(huì)使預(yù)期的利潤(rùn)最大？,廣告的費(fèi)用及其效應(yīng),表1 表2,符號(hào)說明及問題的分析,設(shè)x表示售價(jià)（單位：元），y表示預(yù)期銷售量（單位：桶），z表示廣告費(fèi)（單位：元），k表示銷售增長(zhǎng)因子。投入廣告費(fèi)后，實(shí)際銷售量記為s，獲得的利潤(rùn)記為P（單位：元）。由表1易見預(yù)期銷售量 y 隨著售價(jià)x 的增加而單調(diào)下降，而銷售增長(zhǎng)因子k在開始時(shí)隨著廣告費(fèi)z的增加而增加，在廣告費(fèi)z等于50000元時(shí)達(dá)到最大值，然后在廣告費(fèi)增加時(shí)反而有所回落，為此可用spss畫出散點(diǎn)圖.,運(yùn)行之后，可顯示圖1，圖2 圖-1 圖-2,從圖1和圖2易見，預(yù)期銷售量y與售價(jià)x近似于一條直線， 廣告費(fèi) z 與銷售增長(zhǎng)因子k近似于一條二次曲線。為此可令： y=a+bx k=c+dz+ez2