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

1、 人們?nèi)藗兲接懩承┚€性規(guī)劃問題，有時(shí)必須把探討某些線性規(guī)劃問題，有時(shí)必須把全部或部分決策變量限制為整數(shù)。這樣的線性全部或部分決策變量限制為整數(shù)。這樣的線性規(guī)劃問題，通常稱為規(guī)劃問題，通常稱為整數(shù)規(guī)劃整數(shù)規(guī)劃。作為線性規(guī)劃。作為線性規(guī)劃的特殊情況，整數(shù)規(guī)劃也有最小化和最大化之的特殊情況，整數(shù)規(guī)劃也有最小化和最大化之別。此外，整數(shù)規(guī)劃還可以分成別。此外，整數(shù)規(guī)劃還可以分成純整數(shù)規(guī)劃純整數(shù)規(guī)劃和和混整數(shù)規(guī)劃混整數(shù)規(guī)劃。二者的區(qū)別在于：前者的決策變。二者的區(qū)別在于：前者的決策變量必定量必定。而后者的決策變量。而后者的決策變量。如果全部的決策變量僅取。如果全部的決策變量僅取0 0或或1 1，稱，稱之為之

2、為0-10-1規(guī)劃規(guī)劃。例1 (選址決策問題)某公司決定建1到2個(gè)新工廠：甲地,乙地; 同時(shí)考慮是否建一倉庫。要求:(1)最多建一個(gè)倉庫,如建倉庫,要與工廠在同一地點(diǎn);(2)公司對此次擴(kuò)張的資金預(yù)算是1000萬;問:公司如何決策使得投資凈現(xiàn)值最大?投資決策投資凈現(xiàn)值(百萬) 資本開支(百萬)工廠建在甲地96工廠建在乙地53倉庫建在甲地65倉庫建在乙地42解：不在乙地建廠在乙地建廠設(shè)不在甲地建廠在甲地建廠設(shè), 0, 1, 0, 121xx則數(shù)學(xué)模型為不在乙地建倉庫在乙地建倉庫設(shè)不在甲地建倉庫在甲地建倉庫設(shè), 0, 1, 0, 143xxMax z=9x1+5x2+6x3+4x4St 6x1+3x

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

4、的消防站最少，但必須滿足在城市任何地區(qū)發(fā)生火警時(shí)，消防車要在15分鐘內(nèi)趕到現(xiàn)場。據(jù)實(shí)地測定，各區(qū)之間消防車行駛的時(shí)間見右表。地區(qū)123456101016282720210024321710316240122721428321201525527172715014620102125140 請為該市制定一最節(jié)省消防站數(shù)目的計(jì)劃。解：01ix在第i個(gè)地區(qū)建站Z表示全區(qū)消防站總數(shù)不在第i個(gè)地區(qū)建站i=1,2, ,6布點(diǎn)問題模型：654321minxxxxxxZ6 , 2 , 11 , 0ixits.121 xx1621xxx143 xx1543xxx1652xxx最優(yōu)解x2=1, x4=1最優(yōu)值Z=2例

5、3（背包問題）一個(gè)旅行者，為了準(zhǔn)備旅行的必備物品，要在背包里裝一些有用的東西，但他最多只能攜帶b公斤的東西，而每件物品都只能整件攜帶，于是他給每件物品規(guī)定了一個(gè)“價(jià)值”，以表示其有用程度。如果共有m件物品，第i件物品的重量為bi，價(jià)值為ci，問題就變成：在攜帶的物品總重量不超過b公斤的條件下，攜帶哪些物品可使總價(jià)值最大解：件物品不帶第件物品帶第設(shè)iixi01Z表示所帶物品的總價(jià)值件帶第 iicZmiiixc1攜帶物品的總重量miiixb1數(shù)學(xué)模型：m1iiixcZmaxm, 2 , 1i1 , 0 xbxbt . sim1iii，輔助0-1變量的使用假設(shè)有兩個(gè)約束條件: x1+5x213 3x

6、1+2x2 18， 要求只有一個(gè)起作用。，第一個(gè)約束不起作用，第一個(gè)約束起作用設(shè)01yx1+5x213+(1-y)M 3x1+2x2 18+My其中M為足夠大的正數(shù)01決策變量是表示是非決策的01變量；輔助01變量是引入模型的附加01變量，不代表一個(gè)是非決策，僅僅是為了方便建立模型，輔助01變量通常用y表示。部分約束),.,2 , 1(.2211mibxaxaxamininii個(gè)約束條件：有個(gè)起作用要求只有k),.,2 , 1, 0, 1miiiyi（個(gè)約束條件起作用第個(gè)約束條件不起作用第定義：kmyyymiMybxaxaxamiininii.),.,2 , 1(.212211則有：選擇取值N

7、nNbbbxxxfbbbN.,),.,(),.,212121，或即：中的某一個(gè)個(gè)值（是約束條件的右端項(xiàng)可能),.,2 , 1, 0, 1Nibyii（否則約束條件右端項(xiàng)為定義：1.),.,(21121NNiiinyyyybxxxf則有：固定費(fèi)用0 x, 00 x,cxk)x(Ckx生產(chǎn)費(fèi)用函數(shù)通常為備費(fèi)用。是同產(chǎn)量無關(guān)的生產(chǎn)準(zhǔn)代表產(chǎn)品的生產(chǎn)數(shù)量，用:, s, p,此時(shí)模型為市場需求為并且產(chǎn)品市場價(jià)格是潤最大當(dāng)問題是生產(chǎn)產(chǎn)品的利)cxky(pxzmax10y, 0 xsx. t . s或0Myx0 x, 00 x, 1y定義10y, 0 xsyx. t . s)cxky(pxzmax或邏輯關(guān)系無

8、限制則不成立如果必須成立；則如果)x(k,0)x(f0)x(k, 0)x(f10yMy)x(k)y1 (M)x(f或則有：例4： 一服裝廠可生產(chǎn)三種服裝，生產(chǎn)不同種類的服裝要租用不同的設(shè)備，設(shè)備租金和其它經(jīng)濟(jì)參數(shù)見下表。假定市場需求不成問題，服裝廠每月可用人工工時(shí)為1500小時(shí)，問該廠如何安排生產(chǎn)，可以使每月利潤最大。 設(shè)備租金(元)生產(chǎn)成本(元/件)銷售價(jià)格(元/件)人工工時(shí)(小時(shí)/件)設(shè)備工時(shí)(小時(shí)/件)設(shè)備可用工時(shí)(小時(shí))西裝500028040053300襯衫2000304010.5300羽絨服300020030042300生產(chǎn)西裝的總利潤=銷售價(jià)格*數(shù)量-生產(chǎn)成本*數(shù)量-設(shè)備租金注意注

9、意:只有生產(chǎn)西裝只有生產(chǎn)西裝,才會產(chǎn)生生產(chǎn)西裝的設(shè)備租金才會產(chǎn)生生產(chǎn)西裝的設(shè)備租金.這個(gè)問題的整數(shù)規(guī)劃模型為max z=120 x1+10 x2+100 x3-5000y1-2000y2-3000y3st5x1+x2+4x31500 3x1-30000.5x2-30002x3-3000 x1，x2，x30，為整數(shù), y1，y2，y3=0或1上述整數(shù)規(guī)劃正確嗎上述整數(shù)規(guī)劃正確嗎?1111,x0y0,x0這個(gè)問題的整數(shù)規(guī)劃模型為max z=120 x1+10 x2+100 x3-5000y1-2000y2-3000y3st5x1+x2+4x31500 3x1-300y100.5x2-300y202

10、x3-300y30 x1，x2，x30，為整數(shù), y1，y2，y3=0或1如果這三種產(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，x3150y3max z=120 x1+10 x2+100 x3-5000y1-2000y2-3000y3st5x1+x2+4x31500 3x1-300y100.5x2-300y202x3-300y30 x1-150y10 x2-15

11、0y20 x3-150y30 x1，x2，x30，為整數(shù), y1，y2，y3=0或1如果產(chǎn)品1安排生產(chǎn)，產(chǎn)品2就不能生產(chǎn)；相應(yīng)的約束條件為：y1+y21 max z=120 x1+10 x2+100 x3-5000y1-2000y2-3000y3st5x1+x2+4x32000 3x1-300y100.5x2-300y202x3-300y30y1+y21x1，x2，x30，為整數(shù), y1，y2，y3=0或1如果產(chǎn)品3安排生產(chǎn)，產(chǎn)品2必須生產(chǎn)，而且至少生產(chǎn)500件 .相應(yīng)的約束條件為：y2y3 x2500y2max z=120 x1+10 x2+100 x3-5000y1-2000y2-3000

12、y3st5x1+x2+4x32000 3x1-300y100.5x2-300y202x3-300y30y2-y30 x2-500y20 x1，x2，x30，為整數(shù), y1，y2，y3=0或1非線形規(guī)劃在數(shù)學(xué)規(guī)劃問題中，當(dāng)目標(biāo)函數(shù)或約束函數(shù)中至少有一個(gè)是非線性函數(shù)時(shí)稱這類問題為非線性規(guī)劃。年份年份股票股票A股票股票B股票股票C股票指數(shù)股票指數(shù)19930.30.2250.1490.25899719940.1030.290.260.19752619950.2160.2160.4190.3643611996-0.046-0.272-0.078-0.080711997-0.0710.1440.1690.

13、0570819980.0560.107-0.0350.05501219990.0380.3210.13300890.3050.7320.3171320010.090.1950.0210.24016420020.0830.390.1310035-0.0720.006-0.0098920040.1760.7150.9080.526236基本投資組合模型:例5: 股票投資問題期望年收益率至少達(dá)到15%，應(yīng)當(dāng)如何投資？表中數(shù)據(jù)為年收益率數(shù)據(jù)。問題分析收益不確定 收益的期望值 風(fēng)險(xiǎn) 收益的方差一種股票收益的均值衡量這種股票的平均收益狀況一種股票收益的方

14、差衡量這種股票收益的波動幅度兩種股票收益的協(xié)方差表示他們之間的相關(guān)程度方差越大，風(fēng)險(xiǎn)越大；方差越小，風(fēng)險(xiǎn)越小。數(shù)學(xué)期望：ER1=0.0890833, ER2=0.213667, ER3=0.234583協(xié)方差矩陣：COV = 假設(shè)股票A、B、C每年的收益率分別為R1，R2和R3 0.0099070.0113730.0119860.0113730.0535260.0508080.0119860.0508080.086375模型建立年收益率（的數(shù)學(xué)期望）不低于15% 資金 全部用于投資這三種股票 決策變量 x1投資股票Ax2投資股票Bx3投資股票C約束條件x1, x2 , x3 0，x1+x2 +

15、x3 = 1 x1ER1+x2ER2+x3ER3 0.15 313332233112211332211332211),cov(),cov(2),cov(2),cov(2)()()()(jijijiRRxxRxRxRxRxRxRxRxDRxDRxDRxRxRxDV目標(biāo)函數(shù) 年投資收益率的方差極小 二次規(guī)劃模型(QP)數(shù)學(xué)模型的lingo程序A占53%，B占36%，C占11% min=0.009907*x12+0.053526*x22+0.086375*x32+2*0.011373*x1*x2+2*0.011986*x1*x3+2*0.050808*x3*x2;0.089083*x1+0.2136

16、37*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（國庫券）占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

17、,諾貝爾經(jīng)濟(jì)學(xué)獎 繼續(xù)考慮例5（要求的期望收益率仍定為15%）。假設(shè)握有的股票比例為：股票A占50%，B占35%，C占15%。如按交易額的1% 收取交易費(fèi)，考慮交易成本的的投資組合模型- 例7:問題:是否需要對手上的股票進(jìn)行買賣（換手）？模型建立決策變量 x1投資股票Ax2投資股票Bx3投資股票C假設(shè)購買股票A、B、C的比例為y1 、y2和 y3 假設(shè)賣出股票A、B、C的比例為z1 、z2和 z3 投資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

18、 +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*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-z

19、2;x3=0.15+y3-z3;end能否通過一定方式避免協(xié)方差的計(jì)算，對模型進(jìn)行簡化呢？利用股票指數(shù)簡化投資組合模型- 例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) 假設(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） 1212

20、)()(1212)(|)(minkkikiikkiRMbue優(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 C :u3 = -0.5809590， b3 = 1.523798， s32= 0.03025165， s3= 0.1739300 年收益率(數(shù)學(xué)期望)不低于15% 決

21、策變量 x1投資股票Ax2投資股票Bx3投資股票C約束條件x1, x2 , x3 0，x1+x2 +x3 = 1 目標(biāo)函數(shù) 年投資收益率的方差極小 優(yōu)化模型對應(yīng)的收益:)(3131iiiiiiiieMbuxRxR31031)()(iiiiiiiiimbuxeMbuExER15. 0)(310iiiimbux3122202312)()(iiiiiiiiiisxsbxeMbuDxDR二次規(guī)劃模型(QP)與前結(jié)果A占53%，B占36%，C占11%比較,略有差異 32222201123301123min() 1 . . ()0.15 , , 0 iiiiiiiiix b sx sxxxstx ubmx

22、xxA占53%，B占38%，C占9% 結(jié)果其他目標(biāo)下的投資組合模型- 例9:保守股票投資 市場上只有兩只股票A、B可供某個(gè)投資者購買 ,市場只能出現(xiàn)兩種可能的情況（1和2） 情形情形發(fā)生概率發(fā)生概率股票股票A股票股票B10.81.01.220.21.50.7現(xiàn)要使兩種情況下最小的收益最大化（即不管未來發(fā)生哪種情況，都能至少獲得這個(gè)收益），如何建立模型和求解？優(yōu)化模型與求解決策變量 約束條件目標(biāo)函數(shù) X1年初投資股票AX2年初投資股票Bx1, x2 0，x1+x2 = 1 最小收益最大的“保守”目標(biāo)實(shí)際上就是希望：Max min(1.0 x1+1.2x2 , 1.5x1+0.7x2) 引入一個(gè)輔

23、助變量y，這個(gè)模型就可以線性化。相應(yīng)的LINDO模型為： MAX ySubject tox1 + x2 = 1x1 + 1.2 x2 - y 01.5 x1 + 0.7 x2 - y 0求解得到 ：應(yīng)該投資A、B股票各50%，至少可以增值10% 求解得到 ：應(yīng)該投資A股票54.5455%， B 股票45.4545%，至少可以增值13.6364% .現(xiàn)在，假設(shè)有一條重要信息：如果情形1發(fā)生，股票B的增值將達(dá)到30%而不是表中給出的20%。那么，一般人的想法應(yīng)該是增加對股票B的持有份額。果真如此嗎？這個(gè)投資人如果將上面模型中的1.2改為1.3計(jì)算也就是說，應(yīng)該減少對股票B的持有份額，增加對股票A的

24、持有份額！這真是叫人大吃一驚！這相當(dāng)于說：有人告訴你有某只股票漲幅要增加了，你趕緊說：那我馬上把這只股票再賣點(diǎn)吧。之所以出現(xiàn)如此奇怪的現(xiàn)象，就是由于這個(gè)例子中的目標(biāo)的特殊性引起的 某裝飾材料公司欲以每桶2元的價(jià)錢購進(jìn)一批彩漆。一般來說隨著彩漆售價(jià)的提高，預(yù)期銷售量將減少，并對此進(jìn)行了估算，見表1。為了盡快收回資金并獲得較多的贏利，裝飾材料公司打算做廣告，投入一定的廣告費(fèi)后，銷售量將有一個(gè)增長，可由銷售增長因子來表示。根據(jù)經(jīng)驗(yàn)，廣告費(fèi)與銷售增長因子關(guān)系見表2。現(xiàn)在的問題是裝飾材料公司采取怎樣怎樣的營銷戰(zhàn)略的營銷戰(zhàn)略會使預(yù)期的利潤最大？表1 表2 售價(jià)（元） 預(yù)期銷售量（桶） 2.00 41000 2.50 38000 3.00 34000 3.50 32000 4.00 29000 4.50 28000 5.00 25000 5.50 2200